Eqcs-0.0.8

Peter Belkner <pbelkner@snafu.de>

04.03.2012:   Eqcs-0.0.8 fixes an error appearing on some systems with Eqcs-0.0.7:
eqcs_bitset.cc:73:61: warning: left shift count >= width of type [enabled by default]
In case you're faced with some g++ problems regarding template instantiation you may consider applying eqcs-0.0.8.patch:
$ patch -p0 -i eqcs-0.0.8.patch
(Thanks to Johan Brandhorst)
18.04.2010:   Created Eqcs-0.0.7:
  • Included <cstdlib> into "eqcs_state_rep.cc".
  • Extended "hello.cc" in order to demonstrate how to interate through a state's terms.
(Thanks to Sujeet Kumar Shukla)
29.10.2005:   Did some minor syntactical changes in order to compensate for evolving C++ standards. Eqcs-0.0.6 now compiles at least under Cygwin g++ 3.4.4.
27.10.2005:   Eqcs is referenced in "Computational Methods for Simulating Quantum Computers" by H. De Raedt, K. Michielsen (quant-ph/0406210) appearing in the "Handbook of Theoretical and Computational Nanotechnology" (American Scientific Publishers, http://www.aspbs.com/tcn.html).

Eqcs is a library allowing clients to simulate a quantum computer. The name of the library was chosen because

If you like to download the eqcs source code you may start with listing available versions or directly download the latest version. Note that compiling the source code requires g++ 2.81 or egcs.

The core of the eqcs library is made up by the following classes:

EqcsBitset
a classical bitset. The class EqcsBitset is declared in file "eqcs_bitset.h"
EqcsState
a quantum bitset, i.e. a complex superposition of EqcsBitsets. The class EqcsState is declared in file "eqcs_state.h"
EqcsGate
an (unitary) operator acting on a subset of an EqcsState's bits. EqcsGate itself is an abstract class from which EqcsLambda is the most useful concrete specialization. Note that EqcsLambda is due to quant-ph/9503016 (Barenco et.al.: Elementary gates for quantum computation). The classes EqcsGate and EqcsLambda are declared in files "eqcs_gate.h" and "eqcs_lambda.h", respectively.
EqcsGateArray
a sequence of EqcsGates. The class EqcsGateArray is declared in file "eqcs_gate_array.h"
EqcsQc
a quantum computer holding an EqcsState and beeing able to accept EqcsGateArrays as programs. It performs the program by successively applying the EqcsGates form the EqcsGateArray to it's EqcsState. The class EqcsQc is declared in file "eqcs_qc.h"

On the user level the eqcs library provides the following class:

EqcsVedral
provides methods for constructing EqcsGateArrays performing arithmetics as proposed in quant-ph/9511018 (Vedral et.al.: Quantum networks for elementary arithmetic operations). The class EqcsVedral is declared in file "eqcs_vedral.h". You might want to look at the implementation file "eqcs_vedral.cc" to see how to construct EqcsGateArrays. It's implementation is discussed here.

There is also a test driver for the library called eqcs. The test driver is implemented in file "eqcs.cc". Following is an eqcs sample session.

$ eqcs
To test the plain adder type an expression like
eqcs >1 + 2
and hit the enter button. Be aware that the sum is less then 256.
To quit eqcs type 'q' like in
eqcs >q
and hit the enter button.
eqcs >
eqcs >
eqcs >77 + 95
preparing the quantum computer in state (1,0)|0>|77>|95>
expected result: (1,0)|0>|172>|95>
adding ... done: (1,0)|0>|172>|95>
eqcs >13 + 45
preparing the quantum computer in state (1,0)|0>|13>|45>
expected result: (1,0)|0>|58>|45>
adding ... done: (1,0)|0>|58>|45>
eqcs >q
$ _

The rest of the paper is a kind of user's guide for programming with the eqcs library. It is organized as follows:

1. Bitsets
1.1. The Class EqcsBitset
1.2. Comparing two EqcsBitsets
1.3. Set Operations
1.4. Printing an EqcsBitset

2. States
2.1. The Class EqcsState
2.2. Arithmetics with EqcsStates
2.3. Printing an EqcsState

3. Gate Arrays

4. The Quantum Computer
4.1. An Example Program

1. Bitsets

Because a bitset build from a 32 bit unsigned long is by far to small for holding all the bits nessecary to simulate a multi register quantum computer, a special class for holding a theoreticlly infinite number of bits is needed. The class should allow for all the bit operations known from the integral build-in types.

Looking at the standard template library (STL) the following classes are provided:

vector<bool>
bitset<n>

Both classes offer only part of the features needed. That's why the eqcs library has it's own class for bitsets:

EqcsBitset

1.1. The Class EqcsBitset

Following is an excerpt from class EqcsBitset's declaration. (See "eqcs_bitset.h" for details.)

class EqcsBitset: public EqcsHandle {
public:
    // ...

    EqcsBitset();
    explicit EqcsBitset(int nbits);

    int nbits() const;

    void set(int i) const;
    void reset(int i) const;
    bool test(int i) const;

    EqcsBitset operator~() const;
    EqcsBitset &operator&=(const EqcsBitset &bitset);
    EqcsBitset &operator|=(const EqcsBitset &bitset);
    EqcsBitset &operator<<=(int i);
    EqcsBitset &operator>>=(int i);

    // ...
};

Listing 1: The class EqcsBitset.

The class EqcsBitset has the following operations:

1.2. Comparing two EqcsBitsets

Listing 2 shows the global operators for comparing two EqcsStates.

bool operator==(const EqcsBitset &l, const EqcsBitset &r);
bool operator!=(const EqcsBitset &l, const EqcsBitset &r);
bool operator<(const EqcsBitset &l, const EqcsBitset &r);
bool operator<=(const EqcsBitset &l, const EqcsBitset &r);
bool operator>=(const EqcsBitset &l, const EqcsBitset &r);
bool operator>(const EqcsBitset &l, const EqcsBitset &r);

Listing 2: Comparing two EqcsBitsets.

The operators behave as expected. The program fragment

EqcsBitset bitset1(2);
bitset1.set(0);
bitset1.set(1);
cout << "bitset 1: " << bitset1 << endl;

EqcsBitset bitset2(4);
bitset2.set(3);
cout << "bitset 2: " << bitset2 << endl;

cout << endl;
cout << "bitset 1 == bitset 2: " << (bitset1 == bitset2) << endl;
cout << "bitset 1 != bitset 2: " << (bitset1 != bitset2) << endl;
cout << "bitset 1 < bitset 2:  " << (bitset1 < bitset2) << endl;
cout << "bitset 1 <= bitset 2: " << (bitset1 <= bitset2) << endl;
cout << "bitset 1 >= bitset 2: " << (bitset1 >= bitset2) << endl;
cout << "bitset 1 > bitset 2:  " << (bitset1 > bitset2) << endl;
should produce the output
bitset 1: 11
bitset 2: 0100

bitset 1 == bitset 2: 0
bitset 1 != bitset 2: 1
bitset 1 < bitset 2:  1
bitset 1 <= bitset 2: 1
bitset 1 >= bitset 2: 0
bitset 1 > bitset 2:  0

1.3. Set Operations

Listing 3 shows the global operators for doing set operations with two EqcsStates.

EqcsBitset operator&(const EqcsBitset &l, const EqcsBitset &r);
EqcsBitset operator|(const EqcsBitset &l, const EqcsBitset &r);
EqcsBitset operator>>(const EqcsBitset &l, int i);
EqcsBitset operator<<(const EqcsBitset &l, int i);

Listing 3: The set operations of EqcsBitset.

There are the following operators:

1.3. Printing an EqcsBitset

ostream &operator<<(ostream &os, const EqcsBitset &bitset);
EqcsBitset::omanip0_t ket(const EqcsBitset &bitset);
EqcsBitset::omanip1_t ket(const EqcsBitset &bitset, int nbits);
EqcsBitset::omanip2_t bits(const EqcsBitset &bitset, int nregs, int regwidth);
EqcsBitset::omanip2_t nums(const EqcsBitset &bitset, int nregs, int regwidth);

Listing 4: Printing an EqcsBitset.

The following methods to print an EqcsBitset are provided:

2. States

+---------------+        * +---------------+
|     State     |<>--------+    Bitset     |
+---------------+          +---------------+

2.1. The Class EqcsState

class EqcsState: public EqcsHandle {
public:
    // ...

    EqcsState(unsigned long bits);

    // Define a partial order.
    bool operator<(const EqcsState &state) const;

    // Negate the state.
    EqcsState operator-() const;

    // Add a state.
    EqcsState operator+=(const EqcsState &state) const;
    EqcsState operator-=(const EqcsState &state) const;
    // Multiply by a complex number.
    EqcsState operator*=(const complex_t &c) const;

    // Measure some bits.
    EqcsState collapse(unsigned long bits) const;

    // ...
};

Listing 5: The class EqcsState

2.2. Arithmetics with EqcsStates

// Add two states.
EqcsState operator+(const EqcsState &l, const EqcsState &r);
EqcsState operator-(const EqcsState &l, const EqcsState &r);
// Multiply a state by a complex number.
EqcsState operator*(const EqcsState::complex_t &l, const EqcsState &r);
EqcsState operator*(const EqcsState &l, const EqcsState::complex_t &r);

Listing 6: Arithmetics with EqcsStates

2.3. Printing an EqcsState

ostream &operator<<(ostream &os, const EqcsState &state);
EqcsState::omanip2_t bits(const EqcsState &state, int nregs, int regwidth);
EqcsState::omanip2_t nums(const EqcsState &state, int nregs, int regwidth);

Listing 7: Printing an EqcsState

3. Gate Arrays

+---------------+        * +---------------+
|   GateArray   |<>--------+     Gate      |
+---------------+          +---------------+
                                  ^
                                  |
                         +--------+--------+
                         |                 |
                 +-------+-------+ +-------+-------+
                 |    Lambda     | |    Matrix     |
                 +---------------+ +---------------+

4. The Quantum Computer

+---------------+        1 +---------------+
|      QC       |<>--------+     State     |
+---------------+          +---------------+

4.1. An Example Program

#include "eqcs_state_rep.h"
#include "eqcs_qc.h"
#include "eqcs_lambda.h"

int main()
{
    EqcsGateArray program;      // A gate array.

    // Create a controlled not gate (a special lamda(1) gate).
    EqcsLambda cnot(0.0, 1.0, 1.0, 0.0, 1);

    cnot.set(0, 1);             // The working bit is 1.
    cnot.set(1, 5);             // The controlling bit is 5.

    // Add the controlled not gate to the gate array.
    program.push_back(cnot);

    // Create the state |0010>|0010>.
    EqcsState state = (1ul << 5) | (1ul << 1);
    cout << "the input:  " << bits(state, 2, 4) << endl;

    // Create a quantum computer initially in state |0010>|0010>.
    EqcsQc qc(state);

    // Run the program.
    qc.perform(program);

    // Print the result.
    cout << "the result: " << bits(qc.state(), 2, 4) << endl;

    // Iterate through the result's terms.
    cout << "the result's terms:" << endl;

    for (EqcsStateRep::const_iterator i=qc.state()->terms().begin();
            i!=qc.state()->terms().end(); ++i) {

        EqcsBitset bitset = i->first;
        complex<double> coeff = i->second;

        cout << "    " << bits(bitset, 2, 4) << ": " << coeff << endl;
    }
}

Listing 8: The example program "hello.cc".


Peter Belkner <pbelkner@snafu.de>