Quantum States and Variables

Quantum Memory Management

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 2.2.1.3 the ``memory content'' is the combined state ${\vert\Psi \rangle}$ 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.) described by the QCL program.

The machine state ${\vert\Psi \rangle}$ of an $n$ qubit quantum computer is a vector in the Hilbert space $\mathcal{H}=\mathbf{C}^{2^n}$, however -- due to the destructive nature of measurement (see 1.3.2.3) -- ${\vert\Psi \rangle}$ cannot be directly observed and consequently isn't accessible from within QCL.

Due to the current lack of real-live quantum computers, the interpreter qcl contains the emulation library libqc which can simulate a quantum computer with an arbitrary number of qubits. It also provides an interface to access the simulated machine state via the load, save and dump commands (see 3.3.1.6). These commands, however don't interfere with the program state.

Quantum Registers

QCL uses the concept of quantum registers (see 2.2.1.5) as an interface between the machine state and the controlling classical computer. A quantum register is a pointer to a sequence of (mutually different) qubits and thus, while referring to a quantum subsystem, is still a classical variable.

All operations on the machine state (except for the reset command, see 3.4.1) take quantum registers as operands. Since an $n$ qubit quantum computer allows for $\frac{n!}{(n-m)!}$ different $m$ qubit registers $\mathbf{s}\in\mathbf{Z}_n^m$, any unitary or measurement operation on a $m$ qubit register, can result in $\frac{n!}{(n-m)!}$ different operations on the machine state: This requires that all elementary unitary operations of the quantum computer to be applicable to arbitrary qubits and requires the physical architecture to allow the measurement of single qubits.^3.2

The Quantum Heap

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

Definition 9 (Empty Registers)   A quantum register $\mathbf{s}$ is empty iff

$$P_0(\mathbf{s}) {\vert\Psi \rangle}={\vert\Psi \rangle}\quad\mathrm{with}\quad P_0={\vert \rangle}{\langle 0\vert}$$ (3.4)

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

The machine state of an $n$-qubit quantum computer with $m$ allocated qubits therefor is a product state of the form

$${\vert\Psi \rangle}={\vert\psi \rangle}_{\mathbf{s}}{\vert ... ... \quad\mathrm{and}\quad \mathbf{s}_{\bot}\in\mathbf{Z}_n^{n-m}$$ (3.5)

As has been pointed out in 1.3.3.2, two quantum systems whose common wave function is a product state are physically independent. This esp. means that neither measurements nor unitary transformations on the allocated bits $\mathbf{s}$ will affect $\mathbf{s}_{\bot}$ being in substate ${\vert \rangle}$.

The concept of the quantum heap allows two important abstractions:

• Since the allocation of registers is transparent, no qubit positions need to be specified.
• Since allocated and unallocated qubits are in a product state, the definition of quantum algorithms is independent from the total number of qubits.

Register allocation

Quantum registers are allocated, when a quantum variable is defined. The qubit positions for each register can be inspected using the print statement.

$ qcl -b10  # start qcl-interpreter with 10 qubits
qcl> qureg a[4];    // allocate a 4-qubit register 
qcl> qureg b[3];    // allocate another 3-qubit register
qcl> print a,b;     // show actual qubit mappings
: |......3210> |...210....>
qcl> qureg c[5];    // try to allocate another 5 qubits
! memory error: not enough quantum memory

In QCL, the quantum heap is organized as a stack: qubits are pushed on allocation and poped on deallocation. A quantum register is deallocated, when the scope of the variable is left.

qcl> qureg a[3];    // allocate 3 qubits 
qcl> procedure foo() { qureg b[2]; print a,b; }
qcl> foo();         // temp. register b gets allocated
: |.......210> |.....10...> 
qcl> qureg c[3];    // allocate another 3 qubits
qcl> print a,c;     // qubits from b have been reclaimed
: |.......210> |....210...>

Scratch Space Management

If temporary registers are used, then, in order to avoid the corruption of the quantum heap, it has to be assured that the register is empty befor it is deallocated. Quantum functions (see 2.2.2.5) allow the declaration of local quantum variables as scratch space (see 3.3.1.5), in which case the ``uncomputing'' of the temporary registers is transparently taken care of by using the following procedure suggested by Bennet: [8]

Let $F$ be a quantum function with the argument register $\mathbf{x}$ (type quconst, see 3.3.2.2), the target register $\mathbf{y}$ (type quvoid, see 3.3.2.3) and the scratch register $\mathbf{s}$ (type quscratch, see 3.3.2.4)

$$F(\mathbf{x},\mathbf{y},\mathbf{s}): {\vert i \rangle}_{\m... ...rt f(i) \rangle}_{\mathbf{y}}{\vert j(i) \rangle}_{\mathbf{s}}$$ (3.6)

During the application of $F$, the register $\mathbf{s}$ is filled with the temporary junk bits $j(i)$. To reclaim $\mathbf{s}$, QCL allocates an auxiliary register $\mathbf{t}$ and translates $F$ into an operator $F'$ which is defined as

$$F'(\mathbf{x},\mathbf{y},\mathbf{s},\mathbf{t})= {F}^\dagg... ...(\mathbf{t},\mathbf{y}) F(\mathbf{x},\mathbf{t},\mathbf{s})$$ (3.7)

The fanout operator is a quantum function defined as

$$\mathit{Fanout}: {\vert i \rangle}{\vert \rangle}\to{\vert i \rangle}{\vert i \rangle}$$ (3.8)

The application of $F'$ restores the scratch register $\mathbf{s}$ and the auxiliary register $\mathbf{a}$ to ${\vert \rangle}$ while preserving the function value in the target register $\mathbf{t}$:

$${\vert i,0,0,0 \rangle}\to{\vert i,0,j(i),f(i) \rangle}\to {\vert i,f(i),j(i),f(i) \rangle}\to{\vert i,f(i),0,0 \rangle}$$ (3.9)

Simulation

The interpreter qcl can simulate quantum computers with arbitrary numbers of qubits. According to the hybrid architecture as introduced in 3.1.3, the numerical simulations are handled by a library (libqc) to separate the classical program state from the quantum machine state. QCL provides special commands for inspecting the simulated machine state.

The dump command prints the current machine state in Braket notation. When a quantum expression is given, it prints the probability spectrum instead.

qcl> qureg q[2];
qcl> Mix(q);
qcl> dump;
: STATE: 2 / 4 qubits allocated, 2 / 4 qubits free
0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0011>
qcl> dump q[0];
: SPECTRUM q[0]: |...0>
0.5 |0> + 0.5 |1>

The current machine-state can be loaded and saved with the load and save command.

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 global declaration 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 scope.

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 3.3.1.5 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 10 (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}$$ (3.10)

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\mathrm{with}\quad P_J=\sum_k{\vert k,J \rangle}{\langle k,J\vert}$$ (3.11)

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

$$= \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)$$

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 3.3.1.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, or to be uncomputed if the operator is called inverted (see 3.4.3.2). 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}$$ (3.13)

This can be checked at runtime with simulator 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}$$ (3.14)

If a scratch register is defined within the body of a quantum function, Bennet's method of ``uncomputing'' temporary registers (see 3.3.1.5) is used to free the register again.

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 to 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 be used to override type-checking 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.

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 3.5: 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 3.5), 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 [$\cdot$:$\cdot$]) or the total length of the subregister (syntax [$\cdot$\$\cdot$]).

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

... qubits.^3.2

Since the operators $N_i$ for the value of the qubits commute (i.e $[N_i,n_j]=0$), the number of physically different measurement operations is merely ${n \choose m}$ as the additional bit-permutations are in fact classical operations.