Quantum Programming

Quantum Parallelism

Since all unitary transformations are linear operators, any operation performed on a quantum state is simultaneous applied to all its basevectors, thus

$$U \sum_i c_i {\vert i \rangle} = \sum_i c_i U {\vert i \rangle}$$

This unique feature of quantum computers is called quantum parallelism.

Since the number of basevectors exponentially increases with the number of qubits, it is possible to solve certain problems (e.g. prime factorisation of large numbers, see section 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.

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 ( ${\it 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 ${\it DIV2}' {\vert \rangle}={\it DIV2}' {\vert 1 \rangle}$.

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

Generally it can be said that for any function $f: {\bf B}^n \to {\bf B}^n$ (or equivalently $f: {\bf Z}_{2^n} \to {\bf Z}_{2^n}$) there exists a unitary operator $F: {\bf C}^{2^{2n}} \to {\bf C}^{2^{2n}}$ (thus working on two $n$ qubits registers) with $F {\vert x,0 \rangle} = {\vert x,f(x) \rangle}$.

Scratch Space Management

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 [3,4]. 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:

$${\vert x,0,0 \rangle} \to {\vert x,g(x),0 \rangle} \to {\vert... ...e} \to {\vert x,0,h(g(x)) \rangle} = {\vert x,0,f(x) \rangle}$$

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.

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} \to {\vert x,f(x),j(x),0 \rangle} \to {\vert x,f(x),j(x),f(x) \rangle} \to {\vert x,0,0,f(x) \rangle}$$

Again, the last step is the inversion of the first. The intermediate step is a FANOUT operation which copies the function result into an additional empty (i.e. in substate ${\vert \rangle}$) register.

Footnotes

... unitary¹

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