Simulation of Quantum Computers

Representation of Basevectors

The Hilbert space ${\cal H}$ of a quantum computer with $n$ qubits has $2^n$ dimensions. The basevectors of ${\cal H}$ are bitstrings of the length $n$, which are represented by the class bitvec.

If the wordlength $N$ of the computer is smaller than $n$, then an array is dynamically allocated; if it $N \geq n$, the vector is stored as an unsigned int, which is considerably faster and should suffice for most applications.

Representation of Quantum States

A quantum state ${\vert\psi \rangle} \in {\cal H}$ of $n$ qubits can be described by $2^n$ complex numbers.

$${\vert\psi \rangle}=\sum_{i=0}^{2^n-1} c_i {\vert i \rangle} \quad{\rm with}\quad \sum_{i=0}^{2^n-1} c_i c_i^* = 1$$

Only terms with $c_i \neq 0$ must be stored, which can considerably reduce the required amount of memory since registers which are entangled by an arithmetic function (which is normally the case with all scratch registers) don't require additional entries.

The best datastructure for storing those terms is determined by the most common forms of access, which, in our case, are sequential read out and adding of terms, where it is crucial that the time to determine whether a basevector is already in the list (and the amplitudes have to be added) and the time fore adding a new entry (if the basevector in not in the list) are of the order $O(1)$ i.e. don't increase with the size of the list. Removing of single elements is normally not needed an may take longer.

A linear array in combination with a hashtable as index can meet all these requirements. A basevector is thereby mapped onto the hashtable by a hashfunction which provides a pseudo-random distribution. The entry of the hashtable contains a pointer to the corresponding entry in the array or indicates that such an entry doesn't exist. The overhead for the detection and handling of collisions is of order $O(1)$ if the hashtable is considerably longer than the list itself.

The internal class termlist provides this datastructure with all necessary access function and the ability to dynamically adapt the size of arrays and hashtables by powers of 2. The class quBaseState is the user class representing the common state of all qubits and contains two termlist objects which alternately serve as argument or result of operations.

Substates

Since all qubits are entangled, substates can't be represented as an isolated datastructure, but are merely references to certain qubits of an associated basestate. A reference to $m$ qubits of an $n$ qubit basestate represents a subspace ${\cal S}={\bf C}^{2^m}$ of ${\cal H}$.

The class quSubState and all its derived classes make this reference transparent to the user i.e. all manipulations on the substate are correctly mapped onto its basestate:

Let ${\vert\psi \rangle}={\vert\phi \rangle}{\vert\chi \rangle}$ be the $n$ qubit basestate of the substate ${\vert\phi \rangle}$ referring to the first $m$ qubits of ${\vert\psi \rangle}$ and $U: {\cal S} \to {\cal S}$ a unitary operator

$${\vert\psi \rangle}={\vert\phi \rangle}{\vert\chi \rangle}=\s... ...vert i \rangle} = \sum_{k=0}^{2^m-1} u_{i,k} {\vert k \rangle}$$

Applying $U$ to ${\vert\phi \rangle}$ would be equivalent to applying $U \times {\it ID}(n-m)$ to ${\vert\psi \rangle}$ where ${\it ID}(k)$ is the identity operator over ${\bf C}^{2^k}$.

$$U \times {\it ID}(n-m) {\vert\psi \rangle} = \sum_{i=0}^{2^m-... ...-m}-1} \sum_{k=0}^{2^m-1} u_{i,k} c_{i,j} {\vert k,j \rangle}$$

Operators

In principle, any unitary operator on $n$ qubits can be represented by a complex $2^n \times 2^n$ matrix. Applying this operator to a state with $k$ nonzero terms would require $O(2^n k)$ multiplications. Operators of this kind are represented by the class opMatrix, which stores the nonzero elements of each row in an array of linear lists.

Most operators, however, work on limited subspaces of only a few qubits or (as e.g. all arithmetic operators) merely substitute basevectors with or without an additional phase factor. QULIB provides classes for all these special cases:

The class opEmbedded represents operators of the kind ${\it OP}= {\it ID}(n) \times U \times {\it ID}(m)$, opPermutation are operators of the form $U {\vert i \rangle} = c_i {\vert j_i \rangle}$ and are stored as a one dimensional array of terms.

The class opFunction represents arithmetic functions of the form $U {\vert i,0 \rangle} \to {\vert i,f(i) \rangle}$, where $f(i)$ is defined as a virtual member function. The result of $U {\vert i,j \neq 0 \rangle}$ is undefined and would lead to an error.

A more general interface for user defined function is the class opGate for operators of the form $U {\vert i \rangle} \to c(i) {\vert f(i) \rangle}$. The functions $f(i)$ and $c(i)$ are provided by the user, who is responsible that the transformation is unitary.