Article Discussion View source History

Basic concepts in quantum computation

Author:	Artur Ekert, Patrick Hayden, Hitoshi Inamori
Title:	Basic concepts in quantum computation
Keywords	basic concepts, quantum computing
Journal:	lectures given at les Houches Summer School on "Coherent Matter Waves", July-August 1999
arXiv:	http://www.arxiv.org/abs/quant-ph/0011013
Commnets:	converted to wiki format by Burgarth 22:37, 8 Jun 2005 (BST)

1 Qubits, gates and networks
2 Quantum arithmetic and function evaluations
3 Algorithms and their complexity
4 From interferometers to computers
5 The first quantum algorithms
6 Quantum search
7 Optimal phase estimation
8 Periodicity and quantum factoring
9 Cryptography
10 Conditional quantum dynamics
11 Decoherence and recoherence
12 Concluding remarks
13 Acknowledgments
14 Bibliography

Qubits, gates and networks

Consider the two binary strings,

$011,$

$111.$

The first one can represent, for example, the number $3$ (in binary) and the second one the number $7.$ In general three physical bits can be prepared in $23 = 8$ different configurations that can represent, for example, the integers from $0$ to $7.$ However, a register composed of three classical bits can store only one number at a given moment of time. Enter qubits and quantum registers:

A qubit is a quantum system in which the Boolean states $0$ and $1$ are represented by a prescribed pair of normalised and mutually orthogonal quantum states labeled as $\{|0\rangle ,|1\rangle \}$ Sch95. The two states form a `computational basis' and any other (pure) state of the qubit can be written as a superposition $\alpha |0\rangle +\beta |1\rangle$ for some $α$ and $β$ such that $| α | 2 + | β | 2 = 1.$ A qubit is typically a microscopic system, such as an atom, a nuclear spin, or a polarised photon. A collection of $n$ qubits is called a quantum register of size $n$ .

We shall assume that information is stored in the registers in binary form. For example, the number $6$ is represented by a register in state $|1\rangle \otimes |1\rangle \otimes |0\rangle$ . In more compact notation: $|a\rangle$ stands for the tensor product $|a_{n-1}\rangle \otimes |a_{n-2}\rangle \ldots |a_{1}\rangle \otimes |a_{0}\rangle$ , where $a_i\in\{0,1\}$ , and it represents a quantum register prepared with the value $a=2^{0}a_{0}+2^{1}a_{1}+\ldots2^{n-1}a_{n-1}$ . There are $2 n$ states of this kind, representing all binary strings of length $n$ or numbers from $0$ to $2 n - 1$ , and they form a convenient computational basis. In the following $a\in \{0,1\}^n$ ( $a$ is a binary string of length $n$ ) implies that $\left| a \right\rangle$ belongs to the computational basis.

Thus a quantum register of size three can store individual numbers such as $3$ or $7$ ,

but, it can also store the two of them simultaneously. For if we take the first qubit and instead of setting it to $|0\rangle$ or $|1\rangle$ we prepare a superposition $1/\sqrt{2}\left( |0\rangle +|1\rangle \right)$ then we obtain

$\frac{1}{\sqrt{2}}\left( |0\rangle +|1\rangle \right) \otimes |1\rangle \otimes |1\rangle \equiv \frac{1}{\sqrt{2}}\left( |011\rangle +|111\rangle \right) ,$

$\equiv \frac{1}{\sqrt{2}}\left( |3\rangle +|7\rangle \right) .$

In fact we can prepare this register in a superposition of all eight numbers -- it is enough to put each qubit into the superposition $1/\sqrt{2} \left( |0\rangle +|1\rangle \right) .$ This gives

$\frac{1}{\sqrt{2}}\left( |0\rangle +|1\rangle \right) \otimes \frac{1}{\sqrt{ 2}}\left( |0\rangle +|1\rangle \right) \otimes \frac{1}{\sqrt{2}}\left( |0\rangle +|1\rangle \right) ,$

which can also be written in binary as (ignoring the normalisation constant $2 - 3 / 2$ ),

or in decimal notation as

or simply as

$\sum_{x=0}^7|x\rangle.$

These preparations, and any other manipulations on qubits, have to be performed by unitary operations. A quantum logic gate is a device which performs a fixed unitary operation on selected qubits in a fixed period of time and a quantum network is a device consisting of quantum logic gates whose computational steps are synchronised in time Deu89. The outputs of some of the gates are connected by wires to the inputs of others. The size of the network is the number of gates it contains.

The most common quantum gate is the Hadamard gate, a single qubit gate $H$ performing the unitary transformation known as the Hadamard transform. It is defined as

The matrix is written in the computational basis $\{|0\rangle, |1\rangle \}$ and the diagram on the right provides a schematic representation of the gate $H$ acting on a qubit in state $|x\rangle$ , with $x = 0,1$ .

And here is a network, of size three, which affects the Hadamard transform on three qubits. If they are initially in state $|000\rangle$ then the output is the superposition of all eight numbers from $0$ to $7.$

If the three qubits are initially in some other state from the computational basis then the result is a superposition of all numbers from $0$ to $7$ but exactly half of them will appear in the superposition with the minus sign, for example,

In general, if we start with a register of size $n$ in some state $y\in\{0,1\}^n$ then

$|y\rangle\mapsto 2^{-n/2} \sum_{x\in\{0, 1\}^n}(-1)^{y\cdot x}|x\rangle,$

where the product of $y =(y_{n-1},\ldots , y_0)$ and $x=(x_{n-1},\ldots, x_0)$ is taken bit by bit:

$y\cdot x = (y_{n-1}x_{n-1}+\ldots y_1x_1 +y_0x_0).$

We will need another single qubit gate -- the phase shift gate $\mathbf{\phi }$ defined as $\left| \,0\right\rangle \mapsto \left| \,0\right\rangle$ and $\left| \,1\right\rangle \mapsto e^{i\phi }\left| \,1\right\rangle$ , or, in matrix notation,

The Hadamard gate and the phase gate can be combined to construct the following network (of size four), which generates the most general pure state of a single qubit (up to a global phase),

Consequently, the Hadamard and phase gates are sufficient to construct any unitary operation on a single qubit.

Thus the Hadamard gates and the phase gates can be used to transform the input state $|0\rangle |0\rangle ...|0\rangle$ of the $n$ qubit register into any state of the type $|\Psi _{1}\rangle$ $|\Psi _{2}\rangle ...$ $|\Psi _{n}\rangle ,$ where $|\Psi _{i}\rangle$ is an arbitrary superposition of $|0\rangle$ and $|1\rangle .$ These are rather special $n$ -qubit states, called the product states or the separable states. In general, a quantum register of size $n > 1$ can be prepared in states which are not separable -- they are known as entangled states. For example, for two qubits ( $n = 2$ ), the state

$\alpha \ |00\rangle +\beta \ |11\rangle\neq |\Psi_1\rangle\otimes|\Psi_2\rangle$

is entangled ( $\alpha ,\beta \neq 0$ ), because it cannot be written as a tensor product.

In order to entangle two (or more qubits) we have to extend our repertoire of quantum gates to two-qubit gates. The most popular two-qubit gate is the controlled-NOT (C-NOT), also known as the XOR or the measurement gate. It flips the second (target) qubit if the first (control) qubit is $\left| \,1\right\rangle$ and does nothing if the control qubit is $\left| \,0\right\rangle$ . The gate is represented by the unitary matrix

where $x, y = 0 or 1$ and $\oplus$ denotes XOR or addition modulo 2. If we apply the C-NOT to Boolean data in which the target qubit is $|0\rangle$ and the control is either $|0\rangle$ or $|1\rangle$ then the effect is to leave the control unchanged while the target becomes a copy of the control, i.e.

$|x\rangle |0\rangle \mapsto |x\rangle |x\rangle \qquad x=0,1.$

One might suppose that this gate could also be used to copy superpositions such as $|\Psi \rangle =\alpha \ |0\rangle +\beta \ |1\rangle ,$ so that

$|\Psi \rangle |0\rangle \mapsto |\Psi \rangle |\Psi \rangle$

for any $|\Psi \rangle .$ This is not so! The unitarity of the C-NOT requires that the gate turns superpositions in the control qubit into entanglement of the control and the target. If the control qubit is in a superposition state $|\Psi \rangle =\alpha |0\rangle +\beta |1\rangle ,$ \noindent $(\alpha ,\beta \neq 0),$ and the target in $|0\rangle$ then the C-NOT generates the entangled state

Let us notice in passing that it is impossible to construct a universal quantum cloning machine effecting the transformation in Eq.(\ref{cloning}), or even the more general

$|\Psi \rangle |0\rangle |W\rangle \mapsto |\Psi \rangle |\Psi \rangle |W^{\prime }\rangle$

$|\Psi \rangle |0\rangle |W\rangle \mapsto |\Psi \rangle |\Psi \rangle |W^{\prime}\rangle$

$|\Phi \rangle |0\rangle |W\rangle \mapsto |\Phi \rangle |\Phi \rangle |W^{\prime \prime }\rangle$

As this must be a unitary transformation which preserves the inner product hence we must require

$\langle \Phi |\Psi \rangle =\langle \Phi |\Psi \rangle ^{2}\langle W^{\prime }|W^{\prime \prime }\rangle$

and this can only be satisfied when $|\langle \Phi |\Psi \rangle| =0$ or $1$ , which contradicts our assumptions. Thus states of qubits, unlike states of classical bits, cannot be faithfully cloned. This leads to interesting applications, quantum cryptography being one such.

Another common two-qubit gate is the controlled phase shift gate $B (φ)$ defined as

Again, the matrix is written in the computational basis $\{ |00\rangle, |01\rangle, |10\rangle, |11\rangle \}$ and the diagram on the right shows the structure of the gate.

More generally, these various 2-qubit controlled gates are all of the form controlled- $U$ , for some single-qubit unitary transformation $U$ . The controlled- $U$ gate applies the identity transformation to the auxiliary (lower) qubit when the control qubit is in state $|0\rangle$ and applies an arbitrary prescribed $U$ when the control qubit is in state $|1\rangle$ . The gate maps $|0\rang|y\rang$ to $|0\rangle|y\rangle$ and $|1\rangle|y\rangle$ to $|1\rangle(U |y\rangle)$ , and is graphically represented as

The Hadamard gate, all phase gates, and the C-NOT, form an infinite universal set of gates i.e. if the C-NOT gate as well as the Hadamard and all phase gates are available then any $n$ -qubit unitary operation can be simulated exactly with $O (4 n n)$ such gates BBC95. (Here and in the following we use the asymptotic notation -- $O (T (n))$ means bounded above by $c\,T(n)$ for some constant $c > 0$ for sufficiently large $n$ .) This is not the only universal set of gates. In fact, almost any gate which can entangle two qubits can be used as a universal gate BDEJ95,Llo95. Mathematically, an elegant choice is a pair of the Hadamard and the controlled- $V$ (C- $V$ ) where $V$ is described by the unitary matrix

$V|0\rang=\begin{pmatrix} 1& 0 \\ 0 &i\\ \end{pmatrix}\begin{pmatrix} 1 \\ 0 \\ \end{pmatrix}=\begin{pmatrix} 1 \\ 0 \\ \end{pmatrix}=|0\rang$

$V|1\rang=\begin{pmatrix} 1 &0 \\ 0 & i\\ \end{pmatrix}\begin{pmatrix} 0 \\ 1 \\ \end{pmatrix}=\begin{pmatrix} 0 \\ i \\ \end{pmatrix}=i|1\rang$

The two gates form a finite universal set of gates -- networks containing only a finite number of these gates can approximate any unitary transformation on two (and more) qubits. More precisely, if $U$ is any two-qubit gate and $\varepsilon >0$ then there exists a quantum network of size $O(\log ^{d}(1/\varepsilon ))$ (where $d$ is a constant) consisting of only $H$ and C- $V$ gates which computes a unitary operation $U^{\prime }$ that is within distance $\varepsilon$ from $U$ Sol99. The metric is induced by the Euclidean norm - we say that $U^{\prime }$ is within distance $\varepsilon$ from $U$ if there exists a unit complex number $λ$ (phase factor) such that $||U-\lambda U^{\prime }||\leq \varepsilon$ . Thus if $U^{\prime }$ is substituted for $U$ in a quantum network then the final state $\sum_{x}\alpha _{x}^{\prime }\left| x\right\rangle$ approximates the final state of the original network $\sum_{x}\alpha _{x}\left| x\right\rangle$ as follows: $\sqrt{ \sum_{x}|\lambda \alpha _{x}^{\prime }-\alpha _{x}|^{2}}\leq \varepsilon$ . The probability of any specified measurement outcome on the final state is affected by at most $\varepsilon$ .

A quantum computer will be viewed here as a quantum network (or a family of quantum networks)and quantum computation is defined as a unitary evolution of the network which takes its initial state "input" into some final state "output". We have chosen the network model of computation, rather than Turing machines, because it is relatively simple and easy to work with and because it is much more relevant when it comes to physical implementation of quantum computation.

Quantum arithmetic and function evaluations

Let us now describe how quantum computers actually compute, how they add and multiply numbers, and how they evaluate Boolean functions by means of unitary operations. Here and in the following we will often use the modular arithmetic HW79. Recall that

$a mod b$

denotes the remainder obtained by dividing integer $b$ into integer $a$ , which is always a number less than $b$ . Basically $a = b mod n$ if $a = b + k n$ for some integer $k$ . This is expressed by saying that $a$ is congruent to $b$ modulo $n$ or that $b$ is the residue of $a$ modulo $n$ . For example, $1mod 7 = 8mod 7 = 15mod 7 = 50mod 7 = 1$ . Modular arithmetic is commutative, associative, and distributive.

$(a\pm b)\bmod n =((a\bmod n)\pm (b\bmod n))\bmod n$

$(a\times b)\bmod n =((a\bmod n)\times (b\bmod n))\bmod n$

$(a\times (b+c))\bmod n =(((a b)\bmod n+((a c)\bmod n))\bmod n$

Thus, if you need to calculate, say, $38 mod 7$ do not use the naive approach and perform seven multiplications and one huge modular reduction. Instead, perform three smaller multiplications and three smaller reductions,

$((3 2 mod 7) 2 mod 7) 2 mod 7 = (2 2 mod 7) 2 mod 7 = 16mod 7 = 2.$

This kind of arithmetic is ideal for computers as it restricts the range of all intermediate results. For $l$ -bit modulus $n$ , the intermediate results of any addition, subtraction or multiplication will not be more than $2 l$ bits long. In quantum registers of size $n$ , addition modulo $2 n$ is one of the most common operations; for all $x \in \{0,1\}^n$ and for any $a\in \{0,1\}^n$ ,

$|x\rangle\mapsto|(x+a)\bmod 2^n\rangle$

is a well defined unitary transformation.

The tricky bit in the modular arithmetic is the inverse operation, and here we need some basic number theory. An integer $a\geq 2$ is said to be prime if it is divisible only by 1 and $a$ (we consider only positive divisors). Otherwise, $a$ is called composite. The greatest common divisor of two integers $a$ and $b$ is the greatest positive integer $d$ denoted $d = gcd(a, b)$ that divides both $a$ and $b$ . Two integers $a$ and $b$ are said to be coprime or relatively prime if $gcd(a, b) = 1$ . Given two integers $a$ and $n$ that are coprime, it can be shown that there exists an unique integer $d\in\{0,\ldots,n-1\}$ such that $a d = 1mod n$ HW79. The integer $d$ is called inverse modulo $n$ of $a$ , and denoted $a - 1$ . For example, modulo $7$ we find that $3 - 1 = 5mod n$ , since $3 \times 5 = 15 = 2\times 7 +1=1 \bmod 7$ . This bizarre arithmetic and the notation is due to Karl Friedrich Gauss (1777-1855). It was first introduced in his Disquistiones Arithmeticae in 1801.

In quantum computers addition, multiplication, and any other arithmetic operation have to be embedded in unitary evolution. We will stick to the Hadamard and the controlled- $V$ (C- $V$ ), and use them as building blocks for all other gates and eventually for quantum adders and multipliers.

If we apply C- $V$ four times we get identity, so any three subsequent applications of C- $V$ give the inverse of C- $V$ , which will be called C- $V^{\dagger }$ . Now, if we have a couple of the C- $V$ gates and a couple of the Hadamard gates we can build the C-NOT as follows

$|0\rang|0\rang\to|0\rang{1\over\sqrt{2}}(|0\rang+|1\rang)\to|0\rang{1\over\sqrt{2}}(|0\rang+|1\rang)\to|0\rang|0\rang,$

$|0\rang|1\rang\to|0\rang{1\over\sqrt{2}}(|0\rang-|1\rang)\to|0\rang{1\over\sqrt{2}}(|0\rang-|1\rang)\to|0\rang|1\rang,$

$|1\rang|0\rang\to|1\rang{1\over\sqrt{2}}(|0\rang+i|1\rang)\to|1\rang{1\over\sqrt{2}}(|0\rang+i^2|1\rang)=|1\rang{1\over\sqrt{2}}(|0\rang-|1\rang)\to|1\rang|1\rang,$

$|1\rang|1\rang\to|1\rang{1\over\sqrt{2}}(|0\rang-i|1\rang)\to|1\rang{1\over\sqrt{2}}(|0\rang-i^2|1\rang)\to|1\rang|0\rang.$

A single qubit operation NOT can be performed via a C-NOT gate if the control qubit is set to $|1\rangle$ and viewed as an auxiliary qubit. This is not to say that we want to do it in practice. The C-NOT gate is much more difficult to build than a single qubit NOT. Right now we are looking into the mathematical structure of quantum Boolean networks and do not care about practicalities. Our two elementary gates also allow us to construct a very useful gate called the controlled-controlled-NOT gate ( $c 2$ -NOT) or the Toffoli gate Tof81. The construction is given by the following network,

This gate has two control qubits (the top two wires on the diagram) and one target qubit which is negated only when the two controls are in the state $|1\rangle |1\rangle$ . The $c 2$ -NOT gate gives us the logical connectives we need for arithmetic. If the target is initially set to $|0\rangle$ the gate acts as a reversible AND gate - after the gate operation the target becomes the logical AND of the two control qubits.

$|x_1,x_2\rangle|0\rangle\mapsto |x_1,x_2\rangle|x_1\wedge x_2\rangle$

Once we have in our repertoire operations such as NOT, AND, and C-NOT, all of them implemented as unitary operations, we can, at least in principle, evaluate any Boolean function $\{0,1\}^{n}\rightarrow \{0,1\}^{m}$ which map $n$ bits of input into $m$ bits of output. A simple concatenation of the Toffoli gate and the C-NOT gives a simplified quantum adder, shown below, which is a good starting point for constructing full adders, multipliers and more elaborate networks.

We can view the Toffoli gate and the evolution given by Eq.~(\ref{andgate}) as a quantum implementation of a Boolean function $f:\{0,1\}^{2}\rightarrow\{0,1\}$ defined by $f(x_1,x_2) = x_1 \wedge x_2$ . The operation AND is not reversible, so we had to embed it in the reversible operation $c 2$ -NOT. If the third bit is initially set to $1$ rather than $0$ then the value of $x_1\wedge x_2$ is negated. In general we write the action of the Toffoli gate as the function evaluation,

$|x_1,x_2\rangle|y\rangle\mapsto|x_1,x_2\rangle|(y+(x_1\wedge x_2))\bmod 2\rangle.$

This is how we compute any Boolean function $\{0,1\}^{n}\rightarrow\{0,1\}^{m}$ on a quantum computer. We require at least two quantum registers; the first one, of size $n$ , to store the arguments of $f$ and the second one, of size $n$ , to store the values of $f$ . The function evaluation is then a unitary evolution of the two registers,

$|x,y\rangle \mapsto |x,(y+f(x))\bmod 2^{m}\rangle .$

for any $y\in\{0,1\}^m$ . (In the following, if there is no danger of confusion, we may simplify the notation and omit the $mod$ suffix.)

For example, a network computing $f:\{0,1\}^{2}\rightarrow \{0,1\}^{3}$ such that $f (x) = x 2$ acts as follows

which can be written as

$|x,0\rangle \mapsto |x,x^{2}\bmod 8\rangle ,$

e.g. $32 mod 2 3 = 1$ which explains why $|11\rangle |000\rangle \mapsto |11\rangle |001\rangle$ .

In fact, for these kind of operations we also need a third register with the so-called working bits which are set to zero at the input and return to zero at the output but which can take non-zero values during the computation.

What makes quantum function evaluation really interesting is its action on a superposition of different inputs $x$ , for example, $\sum_{x}|x,0\rangle \mapsto \sum_{x}|x,f(x)\rangle$ produces $f (x)$ for all $x$ in a single run. The snag is that we cannot get them all from the entangled state $\sum_{x}|x,f(x)\rangle$ because any bit by bit measurement on the first register will yield one particular value $x^{\prime}\in\{0,1\}^n$ and the second register will then be found with the value $f(x^{\prime })\in\{0,1\}^m$ .

Algorithms and their complexity

In order to solve a particular problem, computers, be it classical or quantum, follow a precise set of instructions that can be mechanically applied to yield the solution to any given instance of the problem. A specification of this set of instructions is called an algorithm. Examples of algorithms are the procedures taught in elementary schools for adding and multiplying whole numbers; when these procedures are mechanically applied, they always yield the correct result for any pair of whole numbers. Any algorithm can be represented by a family of Boolean networks $(N 1, N 2, N 3,...)$ , where the network $N n$ acts on all possible input instances of size $n$ bits. Any useful algorithm should have such a family specified by an example network $N n$ and a simple rule explaining how to construct the network $N n + 1$ from the network $N n$ . These are called uniform families of networks Pap94.\footnote{This means that the network model is not a self-contained model of computation. We need an algorithm, a Turing machine, which maps each $n$ into an explicit description of $N n$ .}

The quantum Hadamard transform defined by Eq.(\ref{Had}) has a uniform family of networks whose size is growing as $n$ with the number of input qubits. Another good example of a uniform family of networks is the quantum Fourier transform (QFT) Cop94 defined in the computational basis as the unitary operation

$|y\rangle\mapsto 2^{-n/2} \sum_x e^{i \frac{2\pi}{2^n} yx}|x\rangle,$

Suppose we want to construct such a unitary evolution of $n$ qubits using our repertoire of quantum logic gates. We can start with a single qubit and notice that in this case the QFT is reduced to applying a Hadamard gate. Then we can take two qubits and notice that the QFT can be implemented with two Hadamard gates and the controlled phase shift $B (π)$ in between. Progressing this way we can construct the three qubit QFT and the four qubit QFT, whose network looks like this:

(N.B. there are three different types of the $B (φ)$ gate in the network above: $B (π)$ , $B (π / 2)$ and $B (π / 4)$ .)

The general case of $n$ qubits requires a trivial extension of the network following the same sequence pattern of gates $H$ and $B$ . The QFT network operating on $n$ qubits contains $n$ Hadamard gates $H$ and $n (n - 1) / 2$ phase shifts $B$ , in total $n (n + 1) / 2$ elementary gates.

The big issue in designing algorithms or their corresponding families of networks is the optimal use of physical resources required to solve a problem. Complexity theory is concerned with the inherent cost of computation in terms of some designated elementary operations, memory usage, or network size. An algorithm is said to be fast or efficient if the number of elementary operations taken to execute it increases no faster than a polynomial function of the size of the input. We generally take the input size to be the total number of bits needed to specify the input (for example, a number $N$ requires $log 2 N$ bits of binary storage in a computer). In the language of network complexity - an algorithm is said to be efficient if it has a uniform and polynomial-size network family ( $O (n d)$ for some constant $d$ )Pap94. For example, the quantum Fourier transform can be performed in an efficient way because it has a uniform family of networks whose size grows only as a quadratic function of the size of the input, i.e. $O (n 2)$ . Changing from one set of gates to another, e.g. constructing the QFT out of the Hadamard and the controlled- $V$ gates with a prescribed precision $ε$ , can only affect the network size by a multiplicative constant which does not affect the quadratic scaling with $n$ . Thus the complexity of the QFT is $O (n 2)$ no matter which set of adequate gates we use. Problems which do not have efficient algorithms are known as hard problems.

Elementary arithmetic operations taught at schools, such as long addition, multiplication or division of <math>n</math> bit numbers require $O (n 2)$ operations. For example, to multiply $x = (x n - 1 ... x 1 x 0)$ and $y = (y n - 1 ... y 1 y 0)$ we successively multiply $y$ by $x 0$ , $x 1$ and so on, shift, and then add the result. Each multiplication of $y$ by $x k$ takes about $n$ single bit operations, the addition of the $n$ products takes of the order of $n 2$ bit operations, which adds to the total $O (n 2)$ operations. Knowing the complexity of elementary arithmetic one can often assess the complexity of other algorithms. For example, the greatest common divisor of two integers $x$ and $y < x$ can be found using Euclid's algorithm; the oldest nontrivial algorithm which has been known and used since 300 BC.\footnote{This truly `classical' algorithm is described in Euclid's Elements, the oldest Greek treatise in mathematics to reach us in its entirety. Knuth (1981) provides an extensive discussion of various versions of Euclid's algorithm.} First divide $x$ by $y$ obtaining remainder $r 1$ Then divide $y$ by $r 1$ obtaining remainder $r 2$ then divide $r 1$ by $r 2$ obtaining remainder $r 3$ etc., until the remainder is zero. The last non-zero remainder is $gcd(x, y)$ because it divides all previous remainders and hence also $x$ and $y$ (it is obvious from the construction that it is the greatest common divisor). For example, here is a sequence or remainders $(r j, r j + 1)$ when we apply Euclid's algorithm to compute $gcd(12378,3054) = 6$ (12378,3054), (3054,162), (162, 138), (138, 24), (24, 18), (18,6), (6,0). What is the complexity of this algorithm? It is easy to see that the largest of the two numbers is at least halved every two steps, so every two steps we need one bit less to represent the number, and so the number of steps is at most $2 n$ where $n$ is the number of bits in the two integers. Each division can be done with at most $O (n 2)$ operations hence the total number of operations is $O (n 3)$

There are basically three different types of Boolean networks: classical deterministic, classical probabilistic, and quantum. They correspond to, respectively, deterministic, randomised, and quantum algorithms.

Classical deterministic networks are based on logical connectives such as AND, OR, and NOT and are required to always deliver correct answers. If a problem admits a deterministic uniform network family of polynomial size, we say that the problem is in the class $P$ Pap94.

Probabilistic networks have additional ``coin flip" gates which do not have any inputs and emit one uniformly-distributed random bit when executed during a computation. Despite the fact that probabilistic networks may generate erroneous answers they may be more powerful than deterministic ones. A good example is primality testing -- given an $n$ bit number $x$ decide whether or not $x$ is prime. The smallest known uniform deterministic network family that solves this problem is of size $O (n d loglog n)$ which is not polynomially bounded. However, there is a probabilistic algorithm, due to Solovay and Strassen SS77, that can solve the same problem with a uniform probabilistic network family of size $O (n 3 log(1 / ε))$ where $ε$ is the probability of error. N.B. $ε$ does not depend on $n$ and we can choose it as small as we wish and still get an efficient algorithm.

The $log(1 / ε)$ part can be explained as follows. Imagine a probabilistic network that solves a decision problem~\footnote{A decision problem is a problem that admits only two answers: YES or NO} and that errs with probability smaller than $\frac{1}{2}+\delta$ for fixed $δ > 0$ If you run $r$ of these networks in parallel (so that the size of the overall network is increased by factor $r$ and then use the majority voting for the final YES or NO answer your overall probability of error will bounded by $ε = exp( - δ 2 r)$ (This follows directly from the Chernoff bound- see for instance, MR95 Hence $r$ is of the order $log(1 / ε)$ If a problem admits such a family of networks then we say the problem is in the class $B P P$ (stands for ``bounded-error probabilistic polynomial")Pap94

Last but not least we have quantum algorithms, or families of quantum networks, which are more powerful than their probabilistic counterparts. The example here is the factoring problem -- given an $n$ bit number $x$ find a list of prime factors of $x$ The smallest known uniform probabilistic network family which solves the problem is of size $O(2^{d\sqrt{n\log n}})$ One reason why quantum computation is such a fashionable field today is the discovery, by Peter Shor, of a uniform family of quantum networks of $O (n 2 loglog n log(1 / ε))$ in size, that solve the factoring problem Sho94. If a problem admits a uniform quantum network family of polynomial size that for any input gives the right answer with probability larger than $\frac{1}{2}+\delta$ for fixed $δ > 0$ then we say the problem is in the class $B Q P$ (stands for ``bounded-error quantum probabilistic polynomial").

We have

$P\subseteq BPP \subseteq BQP$

Quantum networks are potentially more powerful because of multiparticle quantum interference, an inherently quantum phenomenon which makes the quantum theory radically different from any classical statistical theory.

Richard Feynman Fey82 was the first to anticipate the unusual power of quantum computers. He observed that it appears to be impossible to simulate a general quantum evolution on a classical probabilistic computer in an {\em efficient} way i.e. any classical simulation of quantum evolution appears to involve an exponential slowdown in time as compared to the natural evolution since the amount of information required to describe the evolving quantum state in classical terms generally grows exponentially in time. However, instead of viewing this fact as an obstacle, Feynman regarded it as an opportunity. Let us then follow his lead and try to construct a computing device using inherently quantum mechanical effects.

From interferometers to computers

A single particle interference in the Mach-Zehnder interferometer works as follows. A particle, in this case a photon, impinges on a beam-splitter (BS1), and, with some probability amplitudes, propagates via two different paths to another beam-splitter (BS2) which directs the particle to one of the two detectors. Along each path between the two beam-splitters, is a phase shifter (PS).

If the lower path is labeled as state $\left | \, 0\right\rangle$ and the upper one as state $\left |\, 1 \right \rangle$ then the particle, initially in path $\left |\, 0 \right \rangle$ undergoes the following sequence of transformations

$\left| \,0\right\rangle \mapsto \frac{ 1}{\sqrt{2}}\left( \left| \,0\right\rangle +\left| \,1\right\rangle \right) \mapsto \frac{1}{\sqrt{2}}(e^{i\phi _{0}}\left| \,0\right\rangle +e^{i\phi _{1}}\left| \,1\right\rangle )$

$= e^{i\frac{\phi _{0}+\phi _{1}}{2}}\frac{1}{\sqrt{2}}(e^{i\frac{\phi _{0}-\phi _{1}}{2} }\left| \,0\right\rangle +e^{i\frac{-\phi _{0}+\phi _{1}}{2}}\left| \,1\right\rangle )$

$\mapsto e^{i\frac{\phi _{1}+\phi _{2} }{2}}(\cos \frac{1}{2}(\phi _{0}-\phi _{1})\left| \,0\right\rangle +i\sin \frac{1}{2}(\phi _{0}-\phi _{1})\left| \,1\right\rangle ),$

where $φ 0$ and $φ 1$ are the settings of the two phase shifters and the action of the beam-splitters is defined as

$\left| \,0\right\rangle {\mapsto }\frac{1}{\sqrt{2}} (\left| \,0\right\rangle +\left| \,1\right\rangle ),\quad \left| \,1\right\rangle {\mapsto }\frac{1}{\sqrt{2}} (\left| \,0\right\rangle -\left| \,1\right\rangle ).$

(We have ignored the phase shift in the reflected beam.) The global phase shift $e^{i\frac{\phi _{0}+\phi _{0}}{2}}$ is irrelevant as the interference pattern depends on the difference between the phase shifts in different arms of the interferometer. The phase shifters in the two paths can be tuned to effect any prescribed relative phase shift $φ = φ 0 - φ 1$ and to direct the particle with probabilities

respectively to detectors ``0 and ``1.

The roles of the three key ingredients in this experiment are clear. The first beam splitter prepares a superposition of possible paths, the phase shifters modify quantum phases in different paths and the second beam-splitter combines all the paths together erasing all information about which path was actually taken by the particle between the two beam-splitters. This erasure is very important as we shall see in a moment.

Needless to say, single particle interference experiments are not restricted to photons. One can go for a different ``hardware and repeat the experiment with electrons, neutrons, atoms or even molecules. When it comes to atoms and molecules both external and internal degrees of freedom can be used.

Although single particle interference experiments are worth discussing in their own right, here we are only interested in their generic features simply because they are all ``isomorphic and once you know and understand one of them you, at least for our purposes, understand them all (modulo experimental details, of course). Let us now describe any single particle interference experiment in more general terms. It is very convenient to view this experiment in a diagramatic way as a quantum network with three quantum logic gates CEMM98. The beam-splitters will be now called the Hadamard gates and the phase shifters the phase shift gates. In particular any single particle quantum interference can be represented by the following simple network,

In order to make a connection with a quantum function evaluation let us now describe an alternative construction which simulates the action of the phase shift gate. This construction introduces a phase factor $φ$ using a controlled- $U$ gate. The phase shift $φ$ is ``computed with the help of an auxiliary qubit in a prescribed state $\left| \,u\right\rangle$ such that $U\left|\,u\right\rangle =e^{i\phi }\left|\,u\right\rangle$

In our example, shown above, we obtain the following sequence of transformations on the two qubits

$\left | \, 0 \right \rangle\left | \, u \right \rangle \mapsto \frac{1}{\sqrt 2}(\left | \, 0 \right \rangle + \left | \, 1 \right \rangle)\left | \, u \right \rangle \mapsto \frac{1}{\sqrt 2}(\left | \, 0 \right \rangle + e^{i\phi}\left | \, 1 \right \rangle) \left | \, u \right \rangle$

$\mapsto (\cos\frac{\phi }{2}\left | \, 0 \right \rangle + i \sin \frac{\phi }{2}\left | \, 1 \right \rangle) \left | \, u \right \rangle.$

We note that the state of the auxiliary qubit $\left| \,u\right\rangle$ being an eigenstate of $U$ is not altered along this network, but its eigenvalue $e i φ$ is ``kicked back in front of the $\left| \,1\right\rangle$ component in the first qubit. The sequence (\ref{sequ}) is the exact simulation of the Mach-Zehnder interferometer and, as we shall see later on, the kernel of quantum algorithms.

Some of the controlled- $U$ operations are special - they represent quantum function evaluations! Indeed, a unitary evolution which computes $f:\, \{0,1\}^n\mapsto \{0,1\}^m$

$|x\rangle|y\rangle\mapsto|x\rangle|(y+f(x))\bmod 2^m\rangle,$

is of the controlled- $U$ type. The unitary transformation of the second register, specified by

$|y\rangle\mapsto|(y+f(x))\bmod 2^m\rangle,$

depends on $x$ -- the state of the first register. If the initial state of the second register is set to

$\left| \,u\right\rangle = \frac{1}{2^{m/2}} \sum_{y=0}^{2^{m}-1}\exp \left( -\frac{2\pi i}{2^{m}}y\right) |y\rangle,$

by applying the QFT to the state $|111...1\rangle$ then the function evaluation generates

where we have relabelled the summation index in the sum containing $2 m$ terms

$\sum_{y=0}^{2^{m}-1}\exp \left( -\frac{2\pi i}{2^{m}}(f(x)+y)\right) |f(x)+y\rangle =\sum_{y=0}^{2^{m}-1}\exp \left( -\frac{2\pi i}{2^{m}} y\right) |y\rangle .$

Again, the function evaluation effectively introduces the phase factors in front of the $|x\rangle$ terms in the first register.

$|x\rangle \left| \,u\right\rangle \mapsto \exp \left( \frac{2\pi i}{2^{m} }f(x)\right) |x\rangle \left| \,u\right\rangle$

Please notice that the resolution in $\phi (x)=\frac{2\pi }{2^{m}}f(x)$ is determined by the size $m$ of the second register. For $m = 1$ we obtain $φ(x) = π f (x)$ i.e. the phase factors are $( - 1) f (x)$ Let us see how this approach explains the internal working of quantum algorithms.

The first quantum algorithms

The first quantum algorithms showed advantages of quantum computation without referring to computational complexity measured by the scaling properties of network sizes. The computational power of quantum interference was discovered by counting how many times certain Boolean functions have to be evaluated in order to find the answer to a given problem. Imagine a ``black box" (also called an oracle) computing a Boolean function and a scenario in which one wants to learn about a given property of the Boolean function but has to pay for each use of the ``black box" (often referred to as a query). The objective is to minimise number of queries.

Consider, for example, a ``black box" computing a Boolean function $f:\, \{0,1\}\mapsto\{0,1\}$ There are exactly four such functions: two constant functions ( $f (0) = f (1) = 0$ and $f (0) = f (1) = 1$ and two ``balanced functions ( $f (0) = 0, f (1) = 1$ and $f (0) = 1, f (1) = 0$ The task is to deduce, by queries to the ``black box", whether $f$ is constant or balanced (in other words, whether $f (0)$ and $f (1)$ are the same or different).

Classical intuition tells us that we have to evaluate both $f (0)$ and $f (1)$ which involves evaluating $f$ twice (two queries). We shall see that this is not so in the setting of quantum information, where we can solve this problem with a single function evaluation (one query), by employing an algorithm that has the same mathematical structure as the Mach-Zehnder interferometer. The quantum algorithm that accomplishes this is best represented as the quantum network shown below, where the middle operation is the ``black box" representing the function evaluation CEMM98.

Image:Img286.png

The initial state of the qubits in the quantum network is $\left| \,0\right\rangle (\left| \,0\right\rangle -\left| \,1\right\rangle )$ (apart from a normalization factor, which will be omitted in the following). After the first Hadamard transform, the state of the two qubits has the form $(\left| \,0\right\rangle +\left| \,1\right\rangle )(\left| \,0\right\rangle-\left| \,1\right\rangle )$ . To determine the effect of the function evaluation on this state, first recall that, for each $x\in \{0,1\}$ ,

$\left| \,x\right\rangle (\left| \,0\right\rangle -\left| \,1\right\rangle ) \mapsto \,(-1)^{f(x)}\left| \,x\right\rangle (\left| \,0\right\rangle -\left| \,1\right\rangle ).$

Therefore, the state after the function evaluation is

$\lbrack (-1)^{f(0)}\left| \,0\right\rangle +(-1)^{f(1)}\left| \,1\right\rangle ](\left| \,0\right\rangle -\left| \,1\right\rangle )\;.$

That is, for each $x$ the $\left| \,x\right\rangle$ term acquires a phase factor of $( - 1) f (x)$ which corresponds to the eigenvalue of the state of the auxiliary qubit under the action of the operator that sends $\left| \,y\right\rangle$ to $\left| \,y+f(x)\right\rangle$ The second qubit is of no interest to us any more but the state of the first qubit

$(-1)^{f(0)}\left| \,0\right\rangle +(-1)^{f(1)}\left| \,1\right\rangle$

is equal either to

$\pm \left( \left| \,0\right\rangle +\left| \,1\right\rangle \right) ,$

when $f (0) = f (1),$ or

$\pm \left( \left| \,0\right\rangle -\left| \,1\right\rangle \right) ,$

when $f(0)\neq f(1).$ Hence, after applying the second Hadamard gate the state of the first qubit becomes $\left| \,0\right\rangle$ if the function $f$ is constant and $\left| \,1\right\rangle$ if the function is balanced! A bit-value measurement on this qubit distinguishes these cases with certainty.

This example CEMM98 is an improved version of the first quantum algorithm proposed by Deutsch Deu85 (The original Deutsch algorithm provides the correct answer with probability 50\%.) Deutsch's result laid the foundation for the new field of quantum computation, and was followed by several other quantum algorithms.

Deutsch's original problem was subsequently generalised to cover ``black boxes" computing Boolean functions $f :\{0,1\}^n\mapsto\{0,1\}$ Assume that, for one of these functions, it is ``promised that it is either constant or balanced (i.e. has an equal number of 0's outputs as 1's), and the goal is to determine which of the two properties the function actually has. How many queries to $f$ are required to do this? Any classical algorithm for this problem would, in the worst-case, require $2 n - 1 + 1$ queries before determining the answer with certainty. There is a quantum algorithm that solves this problem with a single evaluation of $f$

The algorithm is illustrated by a simple extension of the network which solves Deutsch's problem.

The control register, now composed out of $n$ qubits ( $n = 3$ in the diagram above), is initially in state $|00\cdots 0\rangle$ and an auxiliary qubit in the second register starts and remains in the state $|0\rangle-|1\rangle$

Stepping through the execution of the network, the state after the first $n$ -qubit Hadamard transform is applied is

$\sum_{x}|x\rangle(|0\rangle-|1\rangle)\;,$

which, after the function evaluation, is

$\sum_{x}(-1)^{f(x)}|x\rangle(|0\rangle-|1\rangle).$

Finally, after the last Hadamard transform, the state is

$\sum_{x,y}(-1)^{f(x)+(x \cdot y)}|y\rangle(|0\rangle-|1\rangle).$

Note that the amplitude of $|00\cdots 0\rangle$ is $\sum_{x} \frac{(-1)^{f(x)}}{2^n}$ which is $( - 1) f (0)$ when $f$ is constant and $0$ when $f$ is balanced. Therefore, by measuring the first $n$ qubits, it can be determined with certainty whether $f$ is constant or balanced. The algorithm follows the same pattern as Deutsch's algorithm: the Hadamard transform, a function evaluation, the Hadamard transform (the H-f-H sequence). We recognize it as a generic interference pattern.

Quantum search

The generic H-f-H sequence may be repeated several times. This can be illustrated, for example, with Grover's data base search algorithm Gro96. Suppose we are given, as an oracle, a Boolean function $f k$ which maps ${0,1} n$ to ${0,1}$ such that $f k (x) = δ x k$ for some $k$ . Our task is to find $k$ . Thus in a set of numbers from $0$ to $2 n - 1$ one element has been "tagged" and by evaluating $f k$ we have to find which one. In order to find $k$ with probability of $50\%$ any classical algorithm, be it deterministic or randomised, will need to evaluate $f k$ a minimum of $2 n - 1$ times. In contrast, a quantum algorithm needs only $O (2 n / 2)$ evaluations.

Unlike the algorithms studied so far, Grover's algorithm consists of repeated applications of the same unitary transformation many ( $O (2 n / 2)$ ) times. The initial state is chosen to be the one that has equal overlap with each of the computational basis states: $|S\rangle = 2^{-n/2}\sum_{i=0}^{2^n} |i\rangle$ . The operation applied at each individual iteration, referred to as the Grover iterate, can be best represented by the following network:

The components of the network are by now familiar: Hadamard transforms ( $H$ ) and controlled- $f$ gates. It is important to notice that in drawing the network we have used a shorthand notation: the first register (with the $|\psi\rangle$ input) actually consists of $n$ qubits. The Hadamard transform is applied to each of those qubits and the controlled- $f$ gates act on all of them simultaneously. Also, the input to the second register is always $|0\rangle-|1\rangle$ but the input to the first register, denoted $|\psi\rangle$ changes from iteration from iteration, as the calculation proceeds. As usual, the second register will be ignored since it remains constant throughout the computation.

To begin, consider only the controlled- $f k$ gate. This is just the phase-kickback construction that was introduced in Section 4 but for the specific function $f k$ . In particular, the transformation does nothing to any basis elements except for $|k\rangle$ , which goes to $-|k\rangle$ . Geometrically, this is simply a reflection in the hyperplane perpendicular to $|k\rangle$ so let us call it $R k$ .

Similarly, with respect to the first register only, the controlled- $f 0$ operation sends $|0\rangle$ to $-|0\rangle$ and fixes all other basis elements, so it can be written $R 0$ . Now consider the sequence of operations $H R 0 H$ . Since $H 2 = I$ , we can rewrite the triple as $H R 0 H - 1$ which is simply $R 0 < 7$ performed in a different basis. More specifically, it is reflection about the hyperplane perpendicular to

$H |0\rangle = \frac{1}{2^{n/2}} \sum_{x=0}^{2^n-1} |x\rangle = |S\rangle$

so we will simply write the triple as $R S$ .

We can therefore rewrite the Grover iterate in the simple form $G = R S R k$ . Now, since each reflection is an orthogonal transformation with negative determinant, their composition must be an orthogonal transformation with unit determinant, in other words, a rotation. The question, of course, is which rotation. To find the answer it suffices to consider rotations in the plane spanned by $|k\rangle$ and $|S\rangle$ since all other vectors are fixed by the Grover iterate. The generic geometrical situation is then illustrated in the following diagram.

If the vector $|a\rangle$ is reflected through the line $L 1$ to produce the vector $|a'\rangle$ and then reflected a second time through line $L 2$ to produce the vector $|a''\rangle$ , then the net effect is a rotation by the total subtended angle between $|a\rangle$ and $|a''\rangle$ , which is $2 x + 2 y = 2(x + y) = 2θ$ .

Therefore, writing $|k^\perp\rangle$ and $|S^\perp\rangle$ for plane vectors perpendicular to $|k\rangle$ and $|S\rangle$ respectively, the Grover iterate performs a rotation of twice the angle from $|k^\perp\rangle$ to $S^\perp\rangle$ . Setting, $\sin \phi = \frac{1}{2^{n/2}}$ , this is easily seen to be a rotation by

$2( 3 \frac{\pi}{2} - \phi) = \pi - 2 \phi \bmod 2 \pi.$

Thus, up to phases, the Grover iterate rotates the state vector by an angle $2φ$ towards the desired solution $|k\rangle$ . Normally, the initial state for the first register is chosen to be $|S\rangle$ . Since this initial state $|S\rangle$ is already at an angle $φ$ to $|k\rangle$ , the iterate should be repeated $m$ times, where

$(2 m + 1) \phi \approx \frac{\pi}{2},$

giving

$m \approx \frac{\pi}{4 \phi} - \frac{1}{4}$

to get a probability of success bounded below by $cos 2 (2φ)$ , which goes to 1 as $n \mapsto \infty$ . For large $n$ , $\frac{1}{2^{n/2}} = \sin \phi \approx \phi$ , so

$m \approx \frac{\pi}{4} \frac{1}{2^{n/2}}.$

This is an astounding result: any search of an unstructured database can be performed in time proportional to the square-root of the number of entries in the database. Subsequent work extended the result to searches for multiple items Boy96, searches of structured databases Hog98, and many other situations. Also, Zalka Zal99, Boyer et. al Boy96 and others have demonstrated that Grover's algorithm is optimal, in the sense that any other quantum algorithm for searching an unstructured database must take time at least $O (2 n / 2)$ .

Optimal phase estimation

Query models of quantum computation provided a natural setting for subsequent discoveries of ``real quantum algorithms". The most notable example is Shor's quantum factoring algorithm Sho94 which evolved from the the order-finding problem, which was originally formulated in the language of quantum queries. Following our "interferometric approach" we will describe this algorithm in the terms of multiparticle quantum interferometry. We start with a simple eigenvalue or phase estimation problem.

Suppose that $U$ is any unitary transformation on $m$ qubits and $\left | \, u \right \rangle$ is an eigenvector of $U$ with eigenvalue $e i φ$ and consider the following scenario. We do not explicitly know $U$ or $\left | \, u\right \rangle$ or $; e i φ$ , but instead we are given devices that perform controlled- $U$ , controlled- $U^{2^1}$ controlled- $U^{2^2}$ and so on until we reach controlled- $U^{2^{n-1}}$ . Also, assume that we are given a single preparation of the state $\left | \, u\right\rangle$ . Our goal is to obtain an $n$ -bit estimator of $φ$ . We start by constructing the following network,

The second register of $m$ qubits is initially prepared in state $|u\rangle$ and remains in this state after the computation, whereas the first register of $n$ qubits evolves into the state,

$(\left | \, 0 \right \rangle + e^{i 2^{n-1} \phi}\left | \, 1 \right \rangle) (\left | \, 0 \right \rangle + e^{i 2^{n-2} \phi}\left | \, 1 \right \rangle) \cdots (\left | \, 0 \right \rangle + e^{i \phi}\left | \, 1 \right \rangle)=\sum_{y=0}^{2^n-1} e^{ 2\pi i \frac{\phi y}{2^n}} |y\rangle.$

Consider the special case where $φ = 2π x / 2 n$ for $x=\sum_{i=0}^{n-1}2^i x_i$ , and recall the quantum Fourier transform (QFT) introduced in Section 2. The state which gives the binary representation of $x$ , namely, $\left |\, x_{n-1}\cdots x_0 \right\rangle$ (and hence $φ$ ) can be obtained by applying the inverse of the QFT , that is by running the network for the QFT in the backwards direction (consult the diagram of the QFT). If $x$ is an $n$ -bit number this will produce the exact value $φ$ .

However, $φ$ does not have to be a fraction of a power of two (and may not even be a rational number). For such a $φ$ , it turns out that applying the inverse of the QFT produces the best $n$ -bit approximation of $φ$ with probability at least $4 / \pi^2\approx 0.405$ .

To see why this is so, let us write $φ = 2π(a / 2 n + δ)$ , where $a=(a_{n-1}\ldots a_{0})$ is the best $n$ -bit estimate of $\frac{\phi}{2\pi}$ and $0 < |\delta| \le 1/2^{n+1}$ . Applying the inverse QFT to the state in Eq.~(\ref{qftphi}) now yields the state

${1\over 2^n} \sum_{x=0}^{2^n-1} \sum_{y=0}^{2^n-1} e^{\frac{2\pi i}{2^n} (a-x) y} e^{2\pi i \delta y}|x\rangle$

and the coefficient in front of $|x=a\rangle$ in the above is the geometric series

${1 \over 2^n} \sum_{y=0}^{2^n-1} (e^{2\pi i \delta})^y = {1 \over 2^n} \left({1 - (e^{2\pi i \delta})^{2^n} \over 1 - e^{2\pi i \delta}}\right)\;.$

Since $|\delta| \le {1 \over 2^{n+1}}$ , it follows that $2^n|\delta| \le 1/2$ , and using the inequality $2 z \leq \sin \pi z \leq \pi z$ holding for any $z\in[0,1/2]$ , we get $|1 - e^{2\pi i \delta 2^n}| = 2|\sin (\pi\delta 2^n)| \ge 4 |\delta| 2^n$ . Also, $|1 - e^{2 \pi i \delta}|=2|\sin \pi\delta| \le 2 \pi \delta$ . Therefore, the probability of observing $a_{n-1} \cdots a_0$ when measuring the state is

$\left|{1 \over 2^n} \left({1 - (e^{2\pi i \delta})^{2^n} \over 1 - e^{2\pi i \delta}}\right)\right|^2 \ge \left({1 \over 2^n} \left({4 \delta 2^n \over 2 \pi \delta}\right)\right)^2 = {4 \over \pi^2},$

which proves our assertion. In fact, the probability of obtaining the best estimate can be made $1 - δ$ for any $0 < δ < 1$ , by creating the state in Eq.(\ref{qftphi}) but with $n + O (log(1 / δ))$ qubits and rounding the answer off to the nearest $n$ bits CEMM98.

Periodicity and quantum factoring

Amazingly, the application of optimal phase estimation to a very particular unitary operator will allow us to factor integers efficiently. In fact, it will allow us to solve a more general class of problems related to the periodicity of certain integer functions.

Let $N$ be an $m$ -bit integer, and let $a$ be an integer smaller than $N$ , and coprime to $N$ . Define a unitary operator $U a$ acting on $m$ qubits such that for all $y < N$

$\quad |y\rangle \mapsto U_a |y\rangle = | a y \bmod N\rangle.$

This unitary operation can be called multiplication by $a$ modulo $N$ . Since $a$ is coprime to $N$ , as discussed in Section 2, there exists a least strictly positive $r$ such that $a r = 1mod N$ . This $r$ is called the order of $a$ modulo $N$ . Equivalently, $r$ is the period of the function $f (x) = a x mod N$ , i.e. the least $r > 0$ such that $f (x) = f (x + r)$ for all $x$ . We are after the optimal $n$ -bit estimate of this period, given some specified precision $n$ .

Now let the vectors $|u_k\rangle$ ( $k\in\{1,\ldots,r\}$ ) be defined by

$| u_{k}\rangle = r^{-1/2} \sum_{j=0}^{r-1} e^{-\frac{2\pi i k j}{r}}|a^j \bmod N\rangle.$

It is easy to check Kit95 that for each $k\in\{1,\ldots,r\}$ , $|u_k\rangle$ is an eigenvector with eigenvalue $e^{2 \pi i {\frac{k}{r}} }$ of the modular multiplication operator $U a$ defined above.

It is important to observe that one can efficiently construct a quantum network for controlled multiplication modulo some number $N$ . Moreover, for any $j$ , it is possible to efficiently implement a controlled- $U^{2^j}_a$ gate VBE96,BCDP96. Therefore, we can apply the techniques for optimal phase estimation discussed in Section 7. For any $k\in\{1,\ldots,r \}$ , given the state $|u_k\rangle$ we can obtain the best $n$ -bit approximation to $\frac{k}{r}$ . This is tantamount to determining $r$ itself. Unfortunately, there is a complication.

Our task is: given an $m$ bit long number $N$ and randomly chosen $a < N$ coprime with $N$ , find the order of $a$ modulo $N$ . The problem with the above method is that we are aware of no straightforward efficient way to prepare any of the states $\left | \, u_k\right \rangle$ . However, the state

$\left | \, 1 \right \rangle = r^{-1/2} \sum_{k=1}^{r} \left | \, u_k \right \rangle$

is most definitely an easy state to prepare.

If we start with $|1\rangle$ in place of the eigenvector $|u_k\rangle$ , apply the phase estimation network and measure the first register bit by bit we will obtain $n$ binary digits of $x$ such that, with probability exceeding $4 / π 2$ , $\frac{x}{2^n}$ is the best $n$ -bit estimate of ${\frac{k}{r}}$ for a randomly chosen $k$ from $\{1,\ldots,r\}$ . The question is: given $x$ how to compute $r$ ? Let us make few observations: \renewcommand{\labelenumi}{ $\bullet$ \begin{enumerate} \item \emph{ $k / r$ is unique, given $x$ \\ Value $x / 2 n$ being the $n$ bit estimate, differs by at most $1 / 2 n$ from $k / r$ Hence, as long as $n > 2 m$ the $n$ bit estimate $x$ determines a unique value of ${\frac{k}{r}}$ since $r$ is an $m$ bit number. \item \emph{Candidate values for $k / r$ are all convergents to $x / 2 m$ \\ For any real number $θ$ there is a unique sequence of special rationals $(\frac{p_n}{q_n})_{n\in N}$ ( $gcd(p n, q n) = 1$ called the \emph{convergents} to $θ$ that tend to $θ$ as $n$ grows. A theorem HW79 states that if $p$ and $q$ are integers with $\left|\theta-\frac{p}{q}\right| < \frac{1}{2q^2}$ then $p / q$ is a convergent to $θ$ Since we have $\frac{1}{2^n} \leq \frac{1}{2 (2^m)^2} \leq \frac{1}{2 r^2}$ this implies $\left|\frac{x}{2^n}-\frac{k}{r}\right| < \frac{1}{2 r^2}$ and $k / r$ is a convergent to $x / 2 n$ \item \emph{Only one convergent is eligible.} \\ It is easy to show that there is at most one fraction $a / b$ satisfying both $b \leq r$ and $\left|\frac{x}{2^n}-\frac{a}{b}\right| < \frac{1}{2 r^2}$ \end{enumerate}

Convergents can be found efficiently using the well-known continued fraction method HW79. Thus we employ continued fractions and our observations above to find a fraction $a / b$ such that $b\leq 2^m$ and $\left|\frac{x}{2^n}-\frac{a}{b}\right| < \frac{1}{2^n}$ . We get the rational $k / r$ , and $k = a, r = b$ , provided $k$ and $r$ are coprime. For randomly chosen $k$ , this happens with probability greater than or equal to $1 / ln r$ EJ96.

Finally, we show how order-finding can be used to factor a composite number $N$ . Let $a$ be a randomly chosen positive integer smaller than $N$ such that $gcd(a, N) = 1$ . Then the order of $a$ modulo $N$ is defined, and we can find it efficiently using the above algorithm. If $r$ is even, then we have:

$a r = 1mod N$

$\Leftrightarrow \quad (a^{r/2})^2 -1^2 = 0\bmod N$

$\Leftrightarrow \quad (a^{r/2}-1)(a^{r/2}+1) = 0\bmod N.$

The product $(a r / 2 - 1)(a r / 2 + 1)$ must be some multiple of $N$ , so unless $a^{r/2}=\pm 1\bmod N$ at least one of terms must have a nontrivial factor in common with $N$ . By computing the greatest common divisor of this term and $N$ , one gets a non-trivial factor of $N$ .

Furthermore, if $N$ is odd with prime factorisation

$N=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_s^{\alpha_s},$

then it can be shown EJ96 that if $a < N$ is chosen at random such that $gcd(a, N) = 1$ then the probability that its order modulo $N$ is even and that $a^{r/2}\neq \pm 1\bmod N$ is:

$\Pr(r \mbox{ is even AND } a^{r/2}\neq \pm 1 \bmod N) \ge 1-\frac{1}{2^{s-1}}.$

Thus, combining our estimates of success at each step, with probability greater than or equal to

$\frac{4}{\pi^2} \frac{1}{\ln r} \left( 1 - \frac{1}{2^{s-1}} \right) \ge \frac{2}{\pi^2} \frac{1}{\ln N}$

we find a factor of $N$ ~\footnote{N.B. by Eq.(\ref{prob}), the method fails if $N$ is a prime power, $N = p α$ , but prime powers can be efficiently recognised and factored by classical means.}. (Here we have used that $N$ is composite and $r < N$ .) If $N$ is $log N = n$ bits long then by repeating the whole process $O (n)$ times, or by a running $O (n)$ computations in parallel by a suitable extension of a quantum factoring network, we can then guarantee that we will find a factor of $N$ with a fixed probability greater than $\frac{1}{2}$ . This, and the fact that the quantum network family for controlled multiplication modulo some number is uniform and of size $O (n 2)$ , tells us that factoring is in the complexity class $B Q P$ .

But why should anybody care about efficient factorisation?

Cryptography

Human desire to communicate secretly is at least as old as writing itself and goes back to the beginnings of our civilisation. Methods of secret communication were developed by many ancient societies, including those of Mesopotamia, Egypt, India, and China, but details regarding the origins of cryptology\footnote{The science of secure communication is called cryptology from Greek kryptos hidden and logos word. Cryptology embodies cryptography, the art of code-making, and cryptanalysis, the art of code-breaking.} remain unknown Kah67.

Originally the security of a cryptosystem or a cipher depended on the secrecy of the entire encrypting and decrypting procedures; however, today we use ciphers for which the algorithm for encrypting and decrypting could be revealed to anybody without compromising their security. In such ciphers a set of specific parameters, called a key, is supplied together with the plaintext as an input to the encrypting algorithm, and together with the cryptogram as an input to the decrypting algorithm Sti95. This can be written as

$\hat E_{k}(P) = C, \; \mathrm{and\; conversely,}\; \hat D_{k}(C)=P,$

where $P$ stands for plaintext, $C$ for cryptotext or cryptogram, $k$ for cryptographic key, and $\hat E$ and $\hat D$ denote an encryption and a decryption operation respectively.

The encrypting and decrypting algorithms are publicly known; the security of the cryptosystem depends entirely on the secrecy of the key, and this key must consist of a randomly chosen, sufficiently long string of bits. Probably the best way to explain this procedure is to have a quick look at the Vernam cipher, also known as the one-time pad Ver26.

If we choose a very simple digital alphabet in which we use only capital letters and some punctuation marks such as

A	B	C	D	E	...		...	X	Y	Z		?	,	.
00	01	02	03	04	...		...	23	24	25	26	27	28	29

we can illustrate the secret-key encrypting procedure by the following simple example (we refer to the dietary requirements of 007):

S	H	A	K	E	N		N	O	T		S	T	I	R	R	E	D
18	07	00	10	04	13	26	13	14	19	26	18	19	08	17	17	04	03
15	04	28	13	14	06	21	11	23	18	09	11	14	01