The mathematics behind quantum computing

The second of two feature columns on this subject.

The Fast Fourier Transform is fast, but not fast enough for realistic factorization of large numbers. Factoring an n-bit number would require 3n·2n operations; that number increases exponentially with n. This month's column will examine how for a quantum computer this growth could be made polynomial, and the factorization problem could become tractable.

Quantum computers

Data in a quantum computer are stored in qubits, and manipulated by gates.


A typical element of the tensor product of the qubit state space (basis |0>, |1>) and the qubit state space (basis |0>, |1>) will have the form:

c0,0|0> tensor |0>  +   c0,1|0> tensor |1>  +   c1,0|1> tensor |0>  +   c1,1|1> tensor |1>,
or, written in matrix notation,
( c0,0   c0,1
c1,0   c1,1
subject to the condition |c0,0|2 + |c1,0|2 + |c0,1|2 + |c1,1|2 = 1.

Such an element will in general not be the tensor product atensorb of   a = a0|0> + a1|1>   and   b = b0|0> + b1|1>.  In fact, we can write a matrix as a tensor product

( c0,0   c0,1
c1,0   c1,1
( a0b0   a0b1
a1b0   a1b1

only when the determinant c0,0 c1,1c1,0 c0,1 is 0.

A state in the 2-qubit state space which is not of the form atensorb is called an entangled state. Here is why:

Parallel processing in a quantum computer

The Quantum Fourier Transform

A quantum Fourier transform was first worked out by Peter Shor, in 1994. This refinement (which corresponds exactly to the the Radix-2 Cooley-Tukey algorithm) was discovered, almost immediately afterwards and independently, by Richard Cleve, Don Coppersmith and David Deutsch. Working with a register of q qubits

qubit0, qubit1, ..., qubitq–1,

it uses a combination of the gates Rj (the R-gate applied to qubitj) with a set of reversible gates called Sj,k in Shor's notation. The gate Sj,k operates on the pair qubitj, qubitk, with j < k, as follows:
Sj,k gate:    
   |0>   |0>
   |0>   |1>
   |1>   |0>
   |1>   |1>
qubitj  qubitk
   |0>     |0>
   |0>     |1>
   |1>     |0>
ωkj|1>  ωkj|1>
where ωkj = e i π /2kj. This number is a primitive (2kj)-th root of –1.

The Shor Factorization Algorithm

As set out in last month's column, we are working to discover the two prime factors of a number N by choosing an arbitrary number x smaller than N and detecting by Fourier analysis the periodicity of the sequence of remainders xa mod N, a= 0, 1, 2, etc.

We follow Shor, and work with a register L of length q, where N2 < 2q < 2N2, and a second register R large enough to hold N. Initially every qubit in L is in state |0>.

Step 1. We load into L an equiprobable superposition of all the numbers between 0 and 2q–1. This means applying the quantum gate Rj to qubitj, for j = 0, ... , q–1. These gates can be applied simultaneously.

Step 2. For each number a in L, we calculate xa mod N and write it in register R. This can be done simultaneously for all a in L. Now in registers L,R we have the superposition

(1/(sqrt 2^q))\sum_{a=0}^{2^q–1} |a> |x^a mod N>

Notation: Here and in what follows |k> in register L stands for |bq–1> tensor ... tensor |b1> tensor |b0>, where bq–1 ... b1b0 is the binary representation of k, with a similar convention for register R.

Step 3. We apply the Quantum Fourier Transform to register L. This replaces each |a> by (1/sqrt 2^q)\su{c=0}^{2^q-1}e^{2 i pi a c/2^q} |c>.. In Fig. 1, each column in the matrix corresponds to a standard basis state for L, whereas the right-most column represents the contents of register R; the state of LtensorR is the superposition

(1/(sqrt q))\sum_{a=0}^{2^q-1}(1/sqrt 2^q)\sum{c=0}^{2^q-1}e^{2 i pi a c/2^q} |c>|x^a mod N>
Step 3

Fig. 1. Step 3 of the Shor Factorization Algorithm illustrated with N = 85, x = 19 and q = 4. Now the LtensorR register holds a superposition of 162 states, each weighted by 1/16. Reading from the top left, the first one is e2 π 0·0/16|0> tensor |1>, i.e.

(e2 π 0·0/16 |0> tensor |0> tensor |0> tensor |0>) tensor (|0> tensor |0> tensor |0> tensor |0> tensor |0> tensor |0> tensor |1>);

the state corresponding to the last entry in the fourth row is e2 π 3·15/16|15> tensor |59>, i.e.

(e2 π 3·15/16 |1> tensor |1> tensor |1> tensor |1>) tensor (|0> tensor |1> tensor |1> tensor |1> tensor |0> tensor |1> tensor |1>).

Before going to Step 4, let us note that the registers are set up to carry out a Discrete Fourier Transform. But that algorithm would require 2q multiplications for each of 2q rows: many too many operations. Shor's intuition was that superposition and entanglement could be harnessed to do all the work in a couple of steps, by first reading register R and then reading register L.

Step 4. We examine register R. One of the values will appear (they all have equal probability), and the others will be lost. Suppose that value is xα mod N. During the readout the contents of register L collapse to those states which were coupled with xα mod N (compare Example 2 above).


Fig. 2. Step 4 of Shor's Factorization Algorithm illustrated with N = 85, x = 19 and q = 4. We suppose that register R reads 59 (so α, as above, was 3 or 11). Register L now only contains the superposition of states which were entangled with |59>; these are set off by the green boxes.


Fig. 3. Step 4 of Shor's Factorization Algorithm illustrated with N = 85, x = 33 and q = 4; conventions as above. We suppose that register R reads 67.

Step 5. We now read out register L. In the two examples we have considered, the readout will be an exact multiple of p = 2q/r. Repeating the experiment with the same x a small number of times leads with very high probability to a set of readouts whose only common divisor is p; so r can be determined and the problem is solved.

These examples are untypically simple in that r (8 and 4 in these two cases) was a power of 2, and therefore divided 2q exactly.

The general case requires a subtler analysis. Now 2q/r is not an integer. The readout in general cannot be an exact multiple of the frequency. But using a long enough sample (here is where the condition 2q > N2 comes into play --to analyze 85 "realistically" we would have had to use q = 13 and an 8192 x 8192 table of coefficients) guarantees, with high probability, a useful approximation. Complete details are in Shor's article referenced below.

distribution from Shor

The calculated probabilities of a readout of c, with r = 10 and 2q = 256. As Shor remarks, the value r = 10 could occur when factoring 33 if x were chosen to be 5, for example; 256 is chosen instead of the required 211 to get a legible picture. With high probability the observed value of c is near an integral multiple of 2q/r = 256/10. Image courtesy Peter Shor.


General reference:

Peter W. Shor, Algorithms for Quantum Computation: In: Proceedings, 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, November 20--22, 1994, IEEE Computer Society Press, pp. 124--134.
An expanded version is available under the title
Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, as arXiv:quant-ph/9508027.

History of the Quantum Fourier Transform:

R. Cleve, A note on computing Fourier transforms by quantum programs, unpublished, available as postscript file

D. Coppersmith, An Approximate Fourier Transform Useful in Quantum Factoring, IBM Research Report 07/12/94, available as arXiv:quant-ph/0201067.

A. Ekert and R. Jozsa, Quantum computation and Shor's factoring algorithm, Reviews of Modern Physics 68 (1996) 733-753