Programming Techniques

Design of Quantum Algorithms

As has been shown in 3.1.2, quantum computers and probabilistic classical computers are computationally equivalent, but for certain tasks, quantum algorithms can provide a more efficient solution than classical implementations.

In order to achieve any speedup over classical algorithms, it is necessary to take advantage of the unique features of quantum computing namely

• Superpositioning
• Quantum Parallelism
• Interference

Superpositioning

A key element in any universal programming language is conditional branching. Any classical program can be modeled as a decision tree where each node corresponds to a binary state $s_n$ and leads to one or more successor states $s_{n+1}^{(i)}$. On a deterministic Turing machine (TM), only one of those transitions $s_n \to s_{n+1}^{(k)}$ is possible, so the computational path ${\langle s_0,s_1,\ldots s_n \rangle}$ is predetermined.

On a probabilistic TM, the transitions are characterized by probabilities $p_i$ with $\sum_i p_i=1$ and one of the possible successor states $s_{n+1}^{(i)}$ is chosen accordingly at random.

Since the eigenvectors ${\vert i \rangle}$ directly correspond to classical binary states, we might interpret a unitary transformation

$$U: {\vert s \rangle}\to\sum_{s'} u_{ss'} {\vert s' \rangle}... ...,s'\in\mathbf{B}^n \quad\mathrm{and}\quad u_{ss'}\in\mathbf{C}$$ (3.37)

as a probabilistic transition form the classical state $s$ to the successor states $s'$ with the transition probabilities $p_{s'}=\vert u_{ss'}\vert^2$, but unless we perform a measurement, the resulting machine state remains in a superposition of all possible classical successor states

$${\vert\Psi \rangle}={\vert s_n \rangle}\stackrel{U}{\longri... ...gle}=\sum_i u_{s_ns_{n+1}^{(i)}} {\vert s_{n+1}^{(i)} \rangle}$$ (3.38)

So from a classical point of view, we can consider a unitary operator which transforms an eigenstate into a superposition of $n$ eigenstates with nonzero amplitudes as a 1-$n$ fork-operation, which enables a quantum computer to follow several classical computational paths at once.

Most non-classical algorithms take advantage of this feature by bringing a register into a even superposition of eigenstates to serve as search space. This can be achieved by applying the Hadamard transformation (see 3.4.4.3) to each qubit

[0/4] 1 |0000>
qcl> qureg q[2];         // allocate 2-qubit register
qcl> Mix(q[0]);          // rotate first qubit
[2/4] 0.707107 |0000> + 0.707107 |0001>
qcl> Mix(q[1]);          // rotate second qubit
[2/4] 0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0011>

Classically, this can be viewed as a binary decision tree with a 50% chance for each bit to flip. For an $n$-qubit register, this leads to $2^n$ classical computational paths all of which are followed simultaneously resulting in a superposition of $2^n$ eigenvectors.

Since the Hadamard transforms for each single qubit commute, we can a-posteriori emulate classic probabilistic behavior by performing a measurement on the single qubits; thereby, the temporal order of the measurements is unimportant so we can force a decision on the second qubit before we decide on the the first and reconstruct the classical computational path in reverse

qcl> measure q[1];       // second qubits gives 0 
[2/4] 0.707107 |0000> + 0.707107 |0001>
qcl> measure q[0];       // first qubit gives 1
[2/4] 1 |0001>

Quantum Parallelism

If we restrict unitary transformations to pseudo-classic operators (see 2.2.2.4) then the classical decision tree degenerates into a list and we end up with the functionality of a classical reversible computer i.e. for any bijective binary function $f$ there is a corresponding pseudo-classic operator

$$U_f:{\vert s \rangle}\to{\vert f(s) \rangle} \quad\mathrm{... ...athbf{B}^n\quad\mathrm{and}\quad f:\mathbf{B}^n\to\mathbf{B}^n$$ (3.39)

The restriction to bijective functions is not a severe as it seems, since for any general binary function $g$ a corresponding quantum function

$$U_g:{\vert s,0 \rangle}\to{\vert s,g(s) \rangle} \quad\mat... ...athbf{B}^n\quad\mathrm{and}\quad f:\mathbf{B}^n\to\mathbf{B}^n$$ (3.40)

can be constructed, which implements $g$ with a maximum overhead of $O(\sqrt{n})$ in space- and $O(2)$ time-complexity, so besides this minor performance penalty, a quantum computer with only pseudo-classic operators is functionally equivalent to a deterministic classical computer.

However, if we use a quantum function on an superposition of eigenstates, the same classical computation is performed on all bit-strings simultaneously.

$${\vert\Psi \rangle}=\sum_s {\vert s,0 \rangle} \stackrel{U_... ...htarrow} {\vert\Psi' \rangle}= \sum_s {\vert s,g(s) \rangle}$$ (3.41)

In classical terms, this can be described as a SIMD (single instruction, multiple date) vector operation, in quantum terms this feature is referred to as quantum parallelism.

As an example, lets consider a full binary adder

$$\mathit{ADD}(\mathbf{a},\mathbf{b},\mathbf{s}): {\vert a \... ...{\vert b \rangle}_{\mathbf{b}}{\vert a+b \rangle}_{\mathbf{s}}$$ (3.42)

Using the controlled-not operator $C_{[[\mathbf{e}]]}$ (see 3.4.7.4), this can be implemented as

$$\mathit{ADD}(\mathbf{a},\mathbf{b},\mathbf{s})= C_{[[\math... ...) \quad\mathrm{with}\quad \mathbf{s}=\mathbf{s_0}\mathbf{s_1}$$ (3.43)

If we put the argument qubits $\mathbf{a}$ and $\mathbf{b}$ into an even superposition of ${\vert \rangle}$ and ${\vert 1 \rangle}$, then we can perform the addition on all possible combinations of inputs simultaneously:

qcl> qureg a[1];         // argument a
qcl> qureg b[1];         // argument b
qcl> qureg s[2];         // target register s=a+b
qcl> Mix(a & b);         // bring arguments into superposition
[4/4] 0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0011>
qcl> CNot(s[0],a);       // calculate low bit of sum
[4/4] 0.5 |0000> + 0.5 |0010> + 0.5 |0101> + 0.5 |0111>
qcl> CNot(s[0],b);
[4/4] 0.5 |0000> + 0.5 |0110> + 0.5 |0101> + 0.5 |0011>
qcl> CNot(s[1],a & b);   // calculate high bit of sum
[4/4] 0.5 |0000> + 0.5 |0110> + 0.5 |0101> + 0.5 |1011>

Interference

While superpositioning and quantum parallelism allow us to perform an exponentially large number of classical computations in parallel, the only way to read out any results is by performing a measurement whereby all but one of the superpositioned eigenstates get discarded. Since it doesn't make any difference if the computational path is determined during the calculation (as with the probabilistic TM) or a-posteriori (by quantum measurement), the use of quantum computers wouldn't provide any advantage over probabilistic classical computers.

Quantum states, however, are not merely a probability distribution of binary values but are vectors i.e. each eigenstate in a superposition isn't characterized by a real probability, but a complex amplitude, so

$${\vert\psi_1 \rangle}=\frac{1}{\sqrt{2}}({\vert \rangle}+{\... ...\rangle}=\frac{1}{\sqrt{2}}({\vert \rangle}-{\vert 1 \rangle})$$ (3.44)

describe different states, even if they have the same probability spectrum.

So, while on a probabilistic TM, the probabilities of two different computational paths leading to the same final state $s$ simply add up, this is not necessarily the case on a quantum computer since generally

$$\vert\alpha+\beta\vert^2\neq \vert\alpha\vert^2+\vert\beta\vert^2 \quad\mathrm{for}\quad \alpha,\beta\in\mathbf{C}$$ (3.45)

To illustrate this concept, consider the three states

$${\vert\psi_1 \rangle}={\vert \rangle},\quad {\vert\psi_2 \... ...\rangle}=\frac{1}{\sqrt{2}}({\vert \rangle}+{\vert 1 \rangle})$$ (3.46)

If we apply the Hadamard-transform $H$ (see 3.4.4.3) to the eigenstates ${\vert\psi_1 \rangle}$ and ${\vert\psi_2 \rangle}$ we get

$${\vert\psi_1' \rangle}=H {\vert\psi_1 \rangle}=\frac{1}{\s... ...\rangle}=\frac{1}{\sqrt{2}}({\vert \rangle}-{\vert 1 \rangle})$$ (3.47)

Since ${\vert\psi_1' \rangle}$ and ${\vert\psi_2' \rangle}$ have the same probability distribution and ${\vert\psi_3 \rangle}$ is merely a superposition of ${\vert\psi_1 \rangle}$ and ${\vert\psi_2 \rangle}$, classically we would assume that ${\vert\psi_3' \rangle}$ also shows the same probability spectrum, however

$${\vert\psi_3' \rangle}=H {\vert\psi_3 \rangle}= \frac{1}{... ...{\vert\psi_1' \rangle}+{\vert\psi_2' \rangle})={\vert \rangle}$$ (3.48)

so in case of ${\vert \rangle}$ the probabilities added up while in case of ${\vert 1 \rangle}$, the complex amplitudes had opposing signs leading to a partial probability of 0. This phenomenon is referred to as positive or negative interference.

So while the computational paths on a probabilistic TM are independent, interference allows computations on superpositioned states to interact and it is this interaction which allows a quantum computer to solve certain problems more efficiently than classical computers. The foremost design principle for any quantum algorithm therefor is to use interference to increase the probability of ``interesting'' eigenstates while trying to reduce the probability of ``dull'' states, in order to raise the chance that a measurement will pick one of the former.

Since any unitary operator $U$ can also be regarded as a base-transformation (see 1.3.2.6), the above problem can also be reformulated as finding an appropriate observable for the measurement, thereby effectively replacing the register observable $\mathcal{S}$ (see 2.2.1.5) by an observable $\tilde{\mathcal{S}}$ with the Hermitian operator

$$\tilde{S}=U(\mathbf{s}) S {U}^\dagger (\mathbf{s})$$ (3.49)

If the whole machine state is measured at once, then the eigenvalues ${\vert\tilde{\imath} \rangle}$ of $\tilde{S}$ are the column vectors of $U$

$$\tilde{S} {\vert\tilde{\imath} \rangle}= U S {U}^\dagge... ...rangle}=U {\vert i \rangle}= \sum_j u_{ji} {\vert j \rangle}$$ (3.50)

Fourier transformations are esp. useful, if global properties of classic functions such as periodicy are of interest for the problem.

Dealing with Reversibility

In 2.2.2.5 we have shown that for any non-reversible boolean function $f: \mathbf{B}^n \to \mathbf{B}^m$ there exists a set of unitary quantum functions

$$F: {\vert x \rangle}_{\mathbf{x}}{\vert \rangle}_{\mathbf{... ...mathbf{x}\vert=n \quad\mathrm{and}\quad \vert\mathbf{y}\vert=m$$ (3.51)

which can be used to circumvent the inherent restriction of quantum computers to reversible operations.

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. Since longer calculations usually involve the composition of many quantum functions this would leave us with a steadily increasing amount of ``junk'' bits which are of no concern for the final result. A straightforward implementation of $f(x)=l(k(h(g(x))))$ already uses 3 additional registers (function values are in prefix notation, $O$ stands for a quantum function $O: {\vert x,0 \rangle}\to{\vert x,o(x) \rangle}$, indices indicate the registers operated on):

$${\vert x,0,0,0,0 \rangle}\stackrel{G_{12}}{\longrightarrow}... ...{\vert x,gx,hgx,0,0 \rangle}\stackrel{K_{34}}{\longrightarrow}$$ (3.52)

$${\vert x,gx,hgx,khgx,0 \rangle}\stackrel{L_{45}}{\longrightarrow} {\vert x,gx,hgx,khgx,lkhgx \rangle}$$

Generally, a composition of $n$ non-revertible functions would require $n-1$ registers to store intermediary results.

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:

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

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... ...gle} \stackrel{{J}^\dagger _{42}K_{23}J_{42}}{\longrightarrow}$$ (3.54)

$${\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}... ...}^\dagger _{123}}{\longrightarrow} {\vert x,0,0,f(x) \rangle}$$ (3.55)

Again, the last step is the inversion of the first. The intermediate step is a $\mathit{Fanout}$ operation (see 3.4.7.2) which copies the function result into an additional empty 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}$$ (3.56)

Overwriting Invertible Functions

As pointed out in 2.2.2.4, 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^3.6, 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}$$ (3.57)

Footnotes

... operators^3.6

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