Quantum Registers and Expressions

Registers and States

Machine State and Program State

The memory of a quantum computer is usually a combination of 2-state subsystems, referred to as quantum bits (qubits). As pointed out in section 1.2.2 the ``memory content'' is the combined state of all qubits. This state is referred to as the (quantum) machine state as opposed to the program state which is the current state of the controlling (classic) algorithm (e.g. contents of variable, execution stack, etc.) ^2.3

The machine state ${\vert\Psi \rangle}$ of an $n$ qubit quantum computer is a vector in the Hilbert space ${\cal H}={\bf C}^{2^n}$, however - due to the destructive nature of measurement (see section 1.2.5) - ${\vert\Psi \rangle}$ cannot be directly observed.

Quantum Registers

QCL uses the concept of quantum registers (see section 1.3.2) as an interface between the machine state and the controlling algorithm. A quantum register is a pointer to a sequence of (mutually different) qubits and all operations on the machine state (except for the reset command, see section 2.4.2.2) take quantum registers as arguments.

Since an $n$ qubit quantum computer allows for $\frac{n!}{(n-m)!}$ different $m$ qubit registers, any unitary or measurement operation on a $m$ qubit register, can result in $\frac{n!}{(n-m)!}$ different operations on the machine state:

Let $\mathbf{s}$ be an $m$ qubit register covering the qubits at the zero-based positions ${\langle s_0, s_1 \ldots s_{m-1} \rangle}$ (with $s_i\neq s_j$ for all $i,j<m$) of the $n$ qubit machine state ${\vert\Psi \rangle}$ and $\mathit{Op}$ be a $m$ qubit unitary or measurement operator, then the register operation $\mathit{Op}(\mathbf{s})$ corresponds to the following machine state operation (see section 1.3.2.2):

$$\mathit{Op}(\mathbf{s})\,\colon\, {\vert\Psi \rangle}\,\ri... ...agger _s\,(\mathit{Op}\times I(n-m))\,R_s\,{\vert\Psi \rangle}$$ (2.1)

The reordering operator $R_s$ and the $k$-qubit identity operator $I(k)$ are defined in eq-reord and eq-gate, respectively.

Memory Management

In QCL, the relation between registers and qubits is handled transparently by allocation and deallocation from qubits of the quantum heap, which allows the use of local quantum variables. All free (i.e. unallocated) quantum memory has to be empty.

Definition 6 (Empty Registers)   A quantum register $\mathbf{s}$ is considered empty if

$$P_0(\mathbf{s})\,{\vert\Psi \rangle}={\vert\Psi \rangle}\quad{\rm with}\quad P_0={\vert \rangle}{\langle 0\vert}$$ (2.2)

At startup or after the reset command, the whole machine state is empty, thus ${\vert\Psi \rangle}={\vert \rangle}$.

Pseudo-classic operators (qufunct) allow the use of local quantum variables as scratch space (see section 1.3.4). When temporary scratch registers (quscratch) are allocated, memory management has to keep track of all applied operators until the local register is deallocated again. Then the result registers are saved using $\mathit{FANOUT}$ and the computation is run in reverse.

The user can override default memory management by explicitly exclude local variables form uncomputing by declaring them as general registers qureg (see section 2.3.2.1). In this case, proper cleanup is in the responsibility of the programmer.

Simulation

While QCL - as a programming language - is designed to work with any qubit-based quantum computer architecture, the development of the necessary hardware will most probably take a few more decades. This is why QCL also supports the simulation of quantum computers and provides special commands for accessing the (simulated) machine state.

The interpreter qcl can simulate quantum computers with arbitrary numbers of qubits (option -bits). Only base-vectors with a nonzero amplitude are actually stored, so the use of scratch registers doesn't require additional memory.

All numerical simulations are handled by the QC library. Please refer to [17] for a more detailed description.

Quantum Variables

Quantum registers bound to a symbolic name are referred to as quantum variables.

General Registers

A general quantum Register with $n=\,\mbox{\it expr}\,$ qubits can be declared with

$$\begin{eqnarray*}\,\mbox{\it var-def}\,\leftarrow \,\mbox{\tt qureg}\,\,\mbox{\i... ...\mbox{\tt [}\,\,\mbox{\it expr}\,\,\mbox{\tt ]}\,\,\mbox{\tt ;}\,\end{eqnarray*}$$

Empty quantum memory is allocated from the heap and bound to the symbol $\,\mbox{\it identifier}\,$.

A declaration in global scope defines a permanent quantum register which is not to prone to scratch space management. This means that - as with classic global variables - there is no way to reclaim allocated qubits within the same shell.

If a global register is defined in a subshell (see section 2.2.4.4) and the subshell is closed, the symbol is destroyed and the allocated qubits are again marked as free. It is up to the programmer to guarantee that the deallocated qubits are in fact empty.^2.4

qcl> qureg q[1];              // allocate a qubit
qcl> Rot(-pi/2,q);            // perform single bit rotation
[1/4] 0.707107 |0000> + 0.707107 |0001>
qcl> shell;                   // open subshell
: shell escape
qcl1> qureg p[1];             // allocate another qubit
qcl1> Rot(-pi/2,p);           // also rotate register p
[2/4] 0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0011>
qcl1> exit;                   // leave subshell
qcl> dump;                    // former register p is not empty
: STATE: 1 / 4 qubits allocated, 3 / 4 qubits free
0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0011>
qcl> list p;                  // however symbol p is undefined
: symbol p is undefined.

The reseting of the machine state with the reset command has no effect on register bindings.

[0/4] 1 |0000>
qcl> qureg q[1];              // allocate a qubit
qcl> reset;                   // reset: |Psi> -> |0>
[1/4] 1 |0000>
qcl> list q;                  // register q still exists
: global symbol q = |...0>:
qureg q[1];

The quantum types quvoid and quscratch are restricted to pseudo-classic operators (qufunct) and are equivalent to qureg, except that they are treated differently by memory management (see section 2.5.6.3 for details).

Quantum Constants

Registers can be declared constant, by using the register type quconst. A quantum constant has to be invariant to all applied operators.

Definition 7 (Invariance of Registers)   A quantum register $\mathbf{c}$ is considered invariant to a register operator $U(\mathbf{s},\mathbf{c})$ if $U$ meets the condition

$$U:\,{\vert i,j \rangle}={\vert i \rangle}_\mathbf{s}{\vert ... ...j\,{\vert i \rangle}_\mathbf{s})\,{\vert j \rangle}_\mathbf{c}$$ (2.3)

Quantum constants have a fixed probability spectrum: Let ${\vert\Psi \rangle}=\sum a_{ij}{\vert i,j \rangle}$ be the machine state and ${\vert\Psi' \rangle}=U(\mathbf{s},\mathbf{c})\,{\vert\Psi \rangle}$ and $p(J)$ and $p'(J)$ the probabilities to measure $J$ in register $\mathbf{c}$ before and after the operator is applied, then

$$p(J) = {\langle \Psi\vert}P_J{\vert\Psi \rangle}=\sum_i a^*_{iJ} a_{iJ} \quad{\rm with}\quad P_J=\sum_k{\vert k,J \rangle}{\langle k,J\vert}$$ (2.4)

$$p'(J) = {\langle \Psi'\vert}P_J{\vert\Psi' \rangle}= {\langle \Psi\vert}U^\dagger P_JU{\vert\Psi \rangle}=$$ (2.5)

$$= \sum_{i',j',i,j} a^*_{i'j'}a_{ij}\; ({\langle i'\vert}_\mathbf{s}... ...f{c})\;P_J\; (U_j\,{\vert i \rangle}_\mathbf{s}\,{\vert j \rangle}_\mathbf{c})=$$

$$= \sum_{i',i} a^*_{i'J}a_{iJ}\; {\langle i\vert}U^\dagger _J U_J{\vert i \rangle}=p(J)$$

While global registers can be declared as quantum constants, this isn't particularly useful, since there is no way to change the register spectrum and the register will consequently always be empty.

qcl> quconst c[1];
qcl> Mix(c);
! parameter mismatch: quconst used as non-const argument to Mix

If an argument to an operator is declared as quconst, the register has to be invariant to all subsequent operator calls within the operator definition.

qcl> operator foo(quconst c) { Rot(pi,c); }
! in operator foo: parameter mismatch: quconst used as non-const 
argument to Rot

When used as an argument type to a quantum function, constant registers aren't swapped out when local scratch registers are uncomputed (see section 2.5.5).

Empty Registers

If an argument $\mathbf{v}$ to an operator is declared quvoid, the quantum register is expected to be empty when the operator is called normally (see section 2.4.1.2), or to be uncomputed if the operator is called inverted. So, depending on the adjungation flag of the operator, the machine state ${\vert\Psi \rangle}$ has to conform to either

$$U(\mathbf{v},\ldots):{\vert\Psi \rangle}={\vert \rangle}_\m... ...i \rangle} \to {\vert \rangle}_\mathbf{v}{\vert\psi' \rangle}$$ (2.6)

This can be checked at runtime with the option -check.

qcl> qureg q[4];
qcl> qureg p[4];
qcl> set check 1;        // turn on consistency checking
qcl> Rot(pi/100,p[2]);   // slightly rotate one target qubit
[8/8] 0.999877 |00000000> + -0.0157073 |01000000>
qcl> Fanout(q,p);        // p is assumed void
! in qufunct Fanout: memory error: void or scratch register not empty

When used as an argument type to a quantum function, void registers are swapped out to a temporary register if local scratch registers are uncomputed.

Scratch Registers

As an argument $\mathbf{s}$ to an operator, registers of type quscratch are considered to be explicit scratch registers which have to be empty when the operator is called and have to get uncomputed before the operator terminates, so operator and machine state have to satisfy the condition

$$U(\mathbf{s},\ldots):{\vert\Psi \rangle}={\vert \rangle}_\m... ...t \rangle}_\mathbf{s}{\vert\psi' \rangle}={\vert\Psi' \rangle}$$ (2.7)

As with quvoid, this is verified at runtime if the option -check is set.

If a scratch register is defined within the body of a quantum function, Bennet-style uncomputing as introduced in section 1.3.4.2 is used to empty the register again (see section 2.5.5 for a detailed explanation).

Quantum functions using local scratch registers may not take general (qureg) registers as arguments.

qcl> qufunct nop(qureg q) { quscratch s[1]; }
! invalid type: local scratch registers can't be used with 
qureg arguments

Register References

To conveniently address subregisters or combined registers (see below), quantum expressions can be named by declaring a register reference.

$$\begin{eqnarray*}\,\mbox{\it def}\,\leftarrow \,\mbox{\it type}\,\,\mbox{\it ide... ...left[ \,\mbox{\tt =}\,\,\mbox{\it expr}\, \right]\,\mbox{\tt ;}\,\end{eqnarray*}$$

The quantum expression $\,\mbox{\it expr}\,$ is bound the register $\,\mbox{\it identifier}\,$ of the quantum type $\,\mbox{\it type}\,$ which can be qureg or quconst.

qcl> qureg q[8];
qcl> qureg oddbits=q[1]&q[3]&q[5]&q[7];
qcl> qureg lowbits=q[0:3];
qcl> list q,oddbits,lowbits;
: global symbol q = |........76543210>:
qureg q[8];
: global symbol oddbits = |........3.2.1.0.>:
qureg oddbits;
: global symbol lowbits = |............3210>:
qureg lowbits;

References can also can be used to override typechecking by redeclaring a quconst as qureg, which can be useful if a constant argument should be temporarily used as scratch space but is restored later. See the implementation of modular addition (addn) in section 3.2.2.1 (page ) for an example.

Quantum Expressions

A quantum expression is an anonymous register reference, which can be used as an operator argument or to declare named references (see above).

Table 2.9: quantum expressions

Expr.	Description	Register
a	reference	${\langle a_0,a_1\ldots a_n \rangle}$
a[i]	qubit	${\langle a_i \rangle}$
a[i:j]	substring	${\langle a_i,a_{i+1}\ldots a_j \rangle}$
a[i\l]	substring	${\langle a_i,a_{i+1}\ldots a_{i+l-1} \rangle}$
a&b	concatenation	${\langle a_0,a_1\ldots a_n,b_0,b_1\ldots b_m \rangle}$

Subregisters

Subregisters can be addressed with the subscript operator [$\ldots$]. Depending on the syntax (see table 2.9), Single qubits are specified by their zero-based offset and substrings are specified by the offset of the first qubit and either the offset of the last qubit (syntax [$\ldots$:$\ldots$]) or the total length of the subregister (syntax [$\ldots$\$\ldots$]).

qcl> qureg q[8];
qcl> print q[3],q[3:4],q[3\4];    
: |....0...> |...10...> |.3210...>

Indices can be arbitrary expressions of type int. Invalid subscripts trigger an error.

qcl> int i=255;        
qcl> print q[floor(log(i,2))];
: |0.......> 
qcl> print q[floor(log(i,2))\2];
! range error: invalid quantum subregister

Combined Registers

Registers can be combined with the concatenation operator &. If the registers overlap, an error is triggered.

qcl> print q[4:7]&q[0:3];
: |32107654> 
qcl> print q[2]&q[0:3];
! range error: quantum registers overlap

Footnotes

... etc.)^2.3

Note that QTM has no program state in this sense, since it isn't subject to any classic meta-algorithm

... empty.^2.4

Note that proper uncomputation is only possible if no non-reversible operations as measurements have been performed since the allocation.