Quantum Programming

Quantum Parallelism

Since all unitary transformations are linear operators, any operation performed on a quantum state is simultaneously applied to all its base-vectors, thus

$$U \sum_i c_i {\vert i \rangle} = \sum_i c_i U {\vert i \rangle}$$ (1.9)

This unique feature of quantum computers is called quantum parallelism. Since the number of base-vectors exponentially increases with the number of qubits, it is possible to solve certain problems (e.g. Deutsch-Jozsa's problem [4]) in polynomial time (i.e. the number of elementary operations is a polynomial in the length of the input) where a classical computer would need an exponential number of steps.

Quantum Registers

2-register states

Since the qubits of a quantum computer constitute a possible entangled overall state, there is - strictly speaking - no such thing as a sub-state for particular qubits, since an $n+m$ qubit state of the form

$${\vert\psi \rangle}=\sum_{i=0}^{2^n-1}\sum_{j=0}^{2^m-1}a_{ij}\,{\vert i,j \rangle}$$ (1.10)

usually cannot be written as a product state ${\vert\phi \rangle}{\vert\chi \rangle}$ of an $n$ and an $m$ qubit state, because generally

$${\vert\psi \rangle}\neq{\vert\phi \rangle}\times{\vert\chi ... ...m_{i=0}^{2^n-1}\sum_{j=0}^{2^m-1} b_ic_j\,{\vert i,j \rangle}$$ (1.11)

In analogy to the gate model (see section 1.1.3), we can, however, easily extent the notion of $n$ qubit unitary operators (see section 1.3.3.1) to work on $n+m$ qubit states, by using the extended operator $U_1$ (the index indicates that the first register is affected):

$$U_1=U\times I(m)=\sum_{i,j=0}^{2^n-1}\sum_{k=0}^{2^m-1} u_{ij}\,{\vert i,k \rangle}{\langle j,k\vert}$$ (1.12)

The first $n$ qubits of the $n+m$ qubit state ${\vert\psi \rangle}$ are referred to as an $n$ qubit quantum register relative to the operator $U$.

$$U_1\,{\vert\psi \rangle}=\sum_{i,j=0}^{2^n-1}\sum_{k=0}^{2^m-1}\,... ...0}^{2^m-1} u_{ij}a_{i'j'}\,{\vert i,k \rangle}{\langle j,k\vert i',j' \rangle}=$$

$$\sum_{i,j,i'=0}^{2^n-1}\sum_{k,j'=0}^{2^m-1} u_{ij}a_{i'j'}\delta... ...ngle}= \sum_{i,j=0}^{2^n-1}\sum_{k=0}^{2^m-1} u_{ij}a_{jk}\,{\vert i,k \rangle}$$ (1.13)

Register Reordering

The concept of quantum registers can be extended to arbitrary sequences of qubits.

Definition 1 (Quantum Register)   An $n$ qubit quantum Register $\mathbf{s}$ is a sequence of mutually different zero-based qubit positions ${\langle s_0, s_1 \ldots s_{n-1} \rangle}$ of some state ${\vert\psi \rangle}\in{\bf C}^{2^N}$ with $N\geq n$.

Let $\mathbf{s}$ be an $n$ qubit register of the $n+m$ qubit state ${\vert\psi \rangle}$. Using an arbitrary permutation $\pi$ over $n+m$ elements with $\pi_i=s_i$ for $i<n$, we can construct a reordering operator $\Pi_s$ by permutating the qubits.

$$\Pi_s\,{\vert b_0,b_1\ldots b_l \rangle}= {\vert b_{\pi_0},b_{\pi_1}\ldots b_{\pi_l} \rangle}\quad{\rm with}\quad l=n+m$$ (1.14)

Using any $\Pi_s$ and $U_1$ we can define the application of $U$ to the register $\mathbf{s}$ of ${\vert\psi \rangle}$ as

$$U(\mathbf{s})\,{\vert\psi \rangle}= \Pi^\dagger _s\,U_1\,\Pi_s\,{\vert\psi \rangle}$$ (1.15)

Note that despite the fact, that here are $m!$ possible implementations of $\Pi_s$, the definition of $U(\mathbf{s})$ is unique:

Definition 2 (Register Operators)   The register operator for an $n$ qubit quantum register $\mathbf{s}$ of the state ${\vert\psi \rangle}\in{\bf C}^{2^N}$ and a unitary operator $U:{\bf C}^{2^n}\to{\bf C}^{2^n}$ is the $N$ qubit unitary operator $U(\mathbf{s})=\Pi^\dagger _s\,(U \times I(m))\,\Pi_s$.

Functions

Pseudo-classic Operators

The general form of a unitary operator $U$ over $n$ qubits is

$$U=\sum_{i=0}^{2^n-1} \sum_{j=0}^{2^n-1} {\vert i \rangle}... ...rm with}\quad \sum_{k=0}^{2^n-1} {u}^*_{ki} u_{kj}=\delta_{ij}$$ (1.16)

If the matrix elements $u_{ij}$ are of the form $u_{ij}=\delta_{i\pi_j}$ with some permutation $\pi$, then their effect on pure states (base-vectors) can be described in terms of classical reversible boolean logic.

Definition 3 (Pseudo-classic Operator)   A pseudo-classic operator is a unitary operator of the form $U:{\vert i \rangle}\to{\vert\pi_i \rangle}$.

Let $f: {\bf Z}_{2^n} \to {\bf Z}_{2^n}$ be a bijective function, then the corresponding pseudo-classic operator $F$ is given as

$$F=\sum_{i=0}^{2^n-1} {\vert f(i) \rangle}{\langle i\vert} ... ...agger =\sum_{i=0}^{2^n-1} {\vert i \rangle}{\langle f(i)\vert}$$ (1.17)

Handling of Non-Reversible Functions

One obvious problem of quantum computing is its restriction to reversible computations. Consider a simple arithmetical operation like integer division by 2 ( $\mathit{DIV2}' {\vert i \rangle} = {\vert i/2 \rangle}$ for even $i$ and ${\vert(i-1)/2 \rangle}$ for odd $i$). Clearly, this operation is non-reversible since $\mathit{DIV2}' {\vert \rangle}=\mathit{DIV2}' {\vert 1 \rangle}$, so no corresponding pseudo-classic operator exists.

However, if we use a second register with the initial value ${\vert \rangle}$, then we can define an operator $\mathit{DIV2}$ witch matches the condition $\mathit{DIV2}{\vert x,0 \rangle} = {\vert x,x/2 \rangle}$ or ${\vert x,(x-1)/2 \rangle}$ respectively. The behaviour of $\mathit{DIV2}{\vert x,y \neq 0 \rangle}$ is undefined and can be set arbitrarily under the condition that $\mathit{DIV2}$ is unitary^1.6.

Definition 4 (Quantum Functions)   For any function $f: {\bf B}^n \to {\bf B}^m$ (or equivalently $f: {\bf Z}_{2^n} \to {\bf Z}_{2^m}$) there exists a pseudo-classic operator $F: {\bf C}^{2^{n+m}} \to {\bf C}^{2^{n+m}}$ working on an $n$-qubits input and an $m$-qubits output register with $F {\vert x,0 \rangle} = {\vert x,f(x) \rangle}$. Operators of that kind shall be called quantum functions.

Scratch Space Management

Register Reuse

While keeping a copy of the argument will allow us to compute non reversible functions, this also forces us to provide extra storage for intermediate results. In longer calculations this would leave us with a steadily increasing amount of ``junk'' bits which are of no concern for the final result.

A simple and elegant solution of this problem was proposed by Bennet [8,9]: If a composition of two non-reversible functions $f(x)=h(g(x))$ is to be computed, the scratch space for the intermediate result can be ``recycled'' using the following procedure ($G$ and $H$ are the quantum functions for $g$ and $h$, the indices indicate the registers operated on):

$${\vert x,0,0 \rangle} \stackrel{G_{12}}{\longrightarrow} {... ...l{G^\dagger _{12}}{\longrightarrow} {\vert x,0,f(x) \rangle}$$ (1.18)

The last step is merely the inversion of the first step and uncomputes the intermediate result. The second register can then be reused for further computations.

Without scratch-management, the evaluation of a composition of depth $d$ needs $d$ operations and consumes $d-1$ junk registers. Bennet's method of uncomputing can then be used to trade space against time: Totally uncomputing of all intermediate results needs $2d-1$ operations and $d-1$ scratch registers, which is useful, if the scratch can be reused in the further computation.

By a combined use of $r$ registers as scratch and junk space, a composition of depth $d=(r+2)(r+1)/2$ can be evaluated with $2d-r-1=(r+1)^2$ operations. An calculation of $f(x)=l(k(j(i(h(g(x))))))$ on a 4-register machine (1 input, 1 output and 2 scratch/junk registers) would run as follows (function values are in prefix notation):

$${\vert x,0,0,0 \rangle} \stackrel{I_{34}H_{23}G_{12}}{\long... ...angle} \stackrel{J^\dagger _{42}K_{23}J_{42}}{\longrightarrow}$$ (1.19)

$${\vert x,0,kjihgx,ihgx \rangle} \stackrel{L_{32}}{\longrigh... ...kjihgx,kjihgx,ihgx \rangle} = {\vert x,fx,kjihgx,ihgx \rangle}$$

By using this method, we can reduce the needed space by $O(1/\sqrt{d})$ with a computation overhead of $O(2)$.

Junk Registers

If the computation of a function $f(x)$ fills a scratch register with the junk bits $j(x)$ (i.e. ${\vert x,0,0 \rangle} \to {\vert x,f(x),j(x) \rangle}$), a similar procedure can free the register again:

$${\vert x,0,0,0 \rangle} \stackrel{F_{123}}{\longrightarrow}... ...F^\dagger _{123}}{\longrightarrow} {\vert x,0,0,f(x) \rangle}$$ (1.20)

Again, the last step is the inversion of the first. The intermediate step is a $\mathit{FANOUT}$ operation which copies the function result into an additional empty (i.e. in sub-state ${\vert \rangle}$) register. Possible implementations are e.g.

$$\mathit{FANOUT}: {\vert x,y \rangle} \to {\vert x,x \oplus ... ...uad\mbox{\rm or}\quad {\vert x,(x+y) \,{\rm mod}\,2^n \rangle}$$ (1.21)

Overwriting Invertible Functions

As pointed out in section 1.3.3.1, every invertible function $f: {\bf Z}_{2^n} \to {\bf Z}_{2^n}$ has a corresponding pseudo classic operator $F:{\vert i \rangle}\to{\vert f(i) \rangle}$. While a direct implementation of $F$ is possible with any complete set of pseudo-classic operators^1.7, the implementation as a quantum function can be substantially more efficient.

If we have efficient implementations of the quantum functions $U_f:{\vert i,0 \rangle}\to{\vert i,f(i) \rangle}$ and $U_{f^{-1}}:{\vert i,0 \rangle}\to{\vert i,f^{-1}(i) \rangle}$, then an overwriting operator $F'$ can be constructed by using an $n$ qubit scratch register.

$$F': {\vert i,0 \rangle} \stackrel{U_f}{\longrightarrow} ... ...{U^\dagger _{f^{-1}}}{\longrightarrow} {\vert f(i),0 \rangle}$$ (1.22)

Conditional Operators

Classical programs allow the conditional execution of code in dependence on the content of a boolean variable (conditional branching).

A unitary operator, on the other hand, is static and has no internal flow-control.^1.8 Nevertheless, we can conditionally apply an $n$ qubit operator $U$ to a quantum register by using an enable qubit and define an $n+1$ qubit operator $U'$

$$U'={\left(\begin{array}{cc}I(n) & 0 \\ 0 & U\end{array}\right)}$$ (1.23)

So $U$ is only applied to base-vectors where the enable bit is set. This can be easily extended to enable-registers of arbitrary length.

Definition 5 (Conditional Operator)   A conditional operator $U_{[[\mathbf{e}]]}$ with the enable register $\mathbf{e}$ is a unitary operator of the form

$$U_{[[\mathbf{e}]]}:{\vert i,\epsilon \rangle}={\vert i \ran... ...angle}_\mathbf{e} & \;\mbox{otherwise} \\ \end{array}\right.$$ (1.24)

Conditional operators a frequently used in arithmetic quantum functions and other pseudo-classic operators.

If the architecture allows the efficient implementation of the controlled-not gate $C:{\vert x,y_1,y_2\ldots \rangle}\to {\vert(x\oplus\bigwedge_i y_i),y_1,y_2\ldots \rangle}$, then conditional pseudo-classic operators can be realised by simply adding the enable string to the control register of all controlled-not operations.

Footnotes

... unitary^1.6

In this special case, just one additional qubit to hold the lowest bit of the argument would suffice to extend $\mathit{DIV2}'$ to a unitary operator.

... operators^1.7

One example would be the Toffoli gate $T:{\vert x,y,z \rangle}\to{\vert x\oplus (y\wedge z),y,z \rangle}$ which can be used to implement any pseudo-classic operator for 3 or more qubits

... flow-control.^1.8

One might argue, that a QTM does in fact have internal flow control because head state and head position are quantum registers. Here, however, flow-control refers to the dynamic generation of a gate sequence, see section 1.1.3