Some curious facts about quantum factoring

As explained in my Reference Frame column of April 2007 (page 8), a key to factoring the product N = pq of two prime numbers, each hundreds of digits long, is being able to find the smallest power r for which a^r (mod N) = 1 for random integers a. (Two numbers are equal modulo N if they differ by a multiple of N.) Peter Shor’s 1994 discovery that a quantum computer would be superefficient at this cryptographically crucial task underlies today’s wide-spread interest in quantum computation. Shor’s period-finding algorithm—so called because the function f(x) = a^x (mod N) is periodic with period r—illustrates in striking ways the novel basis quantum mechanics provides for computation.

In a quantum computer, a nonnegative integer x less than 2 ⁿ is represented by the product state $|x{〉}_n=|x_{n-1}〉\cdot \cdot \cdot |x_0〉$ of n two-state systems (called Qbits—if you prefer the vulgar spelling qubit , please regard Qbit as an abbreviation), where x_n-1, …, x ₀ are the bits (0 or 1) in the binary expansion of x. Quantum-computational architecture executes a function f that takes n-bit integers to m-bit integers, with a linear subroutine U _f that takes an n-Qbit “input register” initially in the state $|x{〉}_n$ and an m-Qbit “output register” initially in the state $|0{〉}_m$ into the state $|x{〉}_n|f\left(x\right){〉}_m$ .

Suppose the initial state of the input register is the superposition of all possible n-Qbit inputs,

$$|\phi 〉=\left(1/2^{n/2}\right)\sum _x|x{〉}_n.$$

(This can be constructed by starting with each Qbit in the state $|0〉$ and applying to each a rotation taking $|0〉$ into $\left(1/\sqrt{2}\right)\left(|0〉+|1〉).\right)$ Since U _f is linear, if the initial state of input and output registers is $|\phi 〉|0{〉}_m$ then their final joint state will be

$$|\Psi 〉=\left(1/2^{n/2}\right)\sum _x|x{〉}_n|f\left(x\right){〉}_m.$$

So it appears that just one application of the subroutine evaluates the function f for all the 2 ⁿ possible values of x. This trick is called “quantum parallelism.”

But appearances can be deceptive. Given a system in a state you know nothing about, there is no way to learn that state. You can only extract information through measurement. If you immediately measure all the Qbits, you acquire a random value x ₀ of x and the value f ₀ of f(x ₀), after which the state becomes $\left|x_0{〉}_n\right|f_0{〉}_m$ from which you can learn nothing more. So you could have accomplished as much with an ordinary classical computer by feeding it a random input.

Ah, but suppose you measure only the m Qbits in the output register. When f(x) is a^x (mod N), you will find with equal probability any one of the r distinct values f ₀ and the input register will be left in a state $|\psi 〉$ proportional to

$$|x_0{〉}_n+|x_0+r{〉}_n+|x_0+2r{〉}_n+\mathrm{\dots },$$

where x ₀ is that random integer less than r at which $a^{x_0}$ (mod N) = f ₀.

This looks promising. By learning only two of the many states $|x〉$ appearing in $|\psi 〉$ , you could learn a multiple of the sought-for period r and be well on the way to learning r itself. With high probability, you could learn such a multiple with two measurements on two sets of Qbits, both in the same state $|\psi 〉$ . But this route to success is thwarted by the “no-cloning” theorem, which establishes the impossibility of duplicating an unknown quantum state. Something more clever is needed.

Fourier to the rescue

The clever move is Fourier analysis, in the form of a spectacularly efficient linear subroutine U _FT that takes the n-Qbit state $|x{〉}_n$ into

$$U_{\text{FT}}|x{〉}_n=\left(1/2^{n/2}\right)\sum _y{e}^{2\pi ixy/2^n}|y{〉}_n.$$

Here the eyes of the quantum physicist tend to glaze over. Ah yes, if you go from position to momentum states, then measurement probabilities become sharply peaked at integral multiples j/r of the inverse period, from which the period r itself can be learned. Ho-hum.

But things are not ho-hummish. To lose interest at this stage is to overlook two crucial differences from boring everyday quantum mechanics. First, x has nothing to do with the position of anything, concrete or abstract. It is an arithmetically useful numerical construction out of the states $|x_i〉$ of n independent two-state systems, devoid of physical content: $x=x_0+2x_1+4x_2+\mathrm{\dots }+2^{n-1}{x}_{n-1}.$ . Second, “sharply peaked” normally means sharply enough that widths are smaller than the resolution of any detectors. But here one wants an integer r that could be hundreds of digits long. An error of only one part in 10¹⁰ would get all but a few digits wrong. Such precision lends to the word “sharp” new meaning that no physicist ever dreamed of. All the folklore has to be reexamined.

Reexamination shows that when n Qbits in the state $U_{\text{FT}}|\psi 〉$ are measured, the resulting integer $0\le y<2^n$ has a significant (over 40%) chance of being within ½ of—that is, as close as possible to—an integral multiple of 2 ⁿ /r. So with a little luck, y/2 ⁿ is going to be within ½ ^{n + 1} of j/r for some random integer j. Does this pin down a unique rational number j/r? Suppose there is a second candidate $j\prime /r\prime \ne j/r.$ The difference between them is $\left(j\prime r-jr\prime \right)/rr\prime .$ Since the candidates are different, the integer $j\prime r-jr\prime$ can’t be zero, and since the possible periods r and r’ are both less than N, the difference between the candidates is at least 1/N ². So if 2 ⁿ > N ², such an integer y does indeed determine a unique rational number j/r.

Of course, j/r determines not r, but r after any factors it has in common with the random integer j have been divided out. So what our quantum computer gives us is a 40% shot at learning a divisor r ₀ of r. The odds that j and r have any really big factors in common are small, so chances are that r will be a fairly small multiple of r ₀. You can easily check with a classical computer to see if a^x = 1 (mod N) when x = r ₀. If so, r = r ₀. If not, try $2r_0,3r_0,\mathrm{\dots },$ and with a little luck one of them will work. If you get up to 1000 r ₀ without success, then either you were in the unlucky 60%, or the j you got did indeed share a large factor with r. In that case try the whole thing over again. After not enormously many runs, you’re quite likely to succeed. And that is how Shor’s “factoring” algorithm actually works.

Troublesome phases

But wait a minute! Looking more closely at the crucial subroutine U _FT, one finds it to be cunningly constructed out of operations that apply conditional phase shifts $e^{2\pi i\phi }$ to Qbits, where the values of φ are inverse powers of 2, ranging from ½ to ½ ⁿ . Since 2 ⁿ must exceed N ², and N is hundreds of digits long, most of those phase shifts are absurdly tiny—far too tiny for real hardware, with its inevitable imperfections, to produce. All a real quantum computer can execute is an approximate U _FT, grotesquely crude on the scale of parts in 10³⁰⁰, the scale on which one needs to learn the period r.

When this dawned on me, I concluded that all the hoopla rested on a silly failure to notice that you can’t turn fields on and off for durations you control to parts in 10³⁰⁰. But I was the silly one. I failed to appreciate the exquisite interplay between digital and analog in a quantum computation. Subroutines like U _FT depend on parameters that vary continuously, as in analog computation. But readout through measurement produces an unambiguous sequence of 0s and 1s, as in digital computation. Reading out a thousand Qbits gives you a thousand bits of a definite integer—about 300 digits of the decimal representation of that integer. You learn every one of those 300 digits. The question is whether they are the right 300 digits.

Those “huge” (perhaps parts in 10⁴) uncontrollable phase errors lead to comparable errors in the probability that that 300-digit integer will be one of the ones you’re looking for. So realistic phase errors might change the probability of getting what you’d like from a little over 40% to a little under 40%. They hardly matter!

A nice illustration of how quantum and classical programming styles differ is provided by the actual calculation of a^x (mod N). Start with a, square it to get a ² (here I stop writing “(mod N)”—all multiplications are modulo N), square that to get a ⁴, continuing in this way to get all the powers of the form $a^{2^j}$ for 0 < j < n. Then to get a^x , you simply form the product of all those powers of $a^{2^j}$ for which x_j = 1 in the binary expansion of x. But now there is a parting of the quantum and classical ways.

In a classical computer, the two-state systems used to represent 0 and 1, called Cbits, are cheap and time is precious. If you want to calculate a^x for 2 ⁿ different values of x, you use n groups of Cbits to make a table of all the n different $a^{2^j}$ and you look up the various entries going into a^x for each value of x, thereby removing the need to recompute those squares each time you turn to a new value of x.

But in a quantum computer, Qbits are precious and time is cheap. The multiplication of the appropriate $a^{2^j}$ into a^x is not applied 2 ⁿ different times to an input register in each of the states $|x{〉}_n$ , but only once, to an input register in the state $|\phi 〉$ in which all 2 ⁿ possible $|x{〉}_n$ are superposed. Each $a^{2^j}$ is used just once. In some terms in the superposition it’s multiplied in, and in others it isn’t, depending on whether the jth bit of x is 1 or 0. After that single conditional multiplication is carried out, you can square $a^{2^j}$ to get the next power $a^{2^{(j+1)}}$ $a^{2\left(j+1\right)}$ and store the result in the same group of Qbits that formerly held $a^{2^j}$ , at a huge saving in Qbits.

Why factoring 15 is too easy

There is another saving in Qbits to watch out for, because it is misleading. The period r of a^x (mod pq) can easily be shown to be a divisor of $\left(p-1\right)\left(q-1\right).$ So if p − 1 and q − 1 are both powers of 2, as with the primes 3, 5, 17, 257, …, then so is r. But when r is 2 ^m , then 2 ^n/r is itself an integer, and measuring the output of the subroutine U _FT can, again easily, be shown to give an integral multiple of 2n/r with probability 1, even when 2 ⁿ merely exceeds N but not N ². Therefore factoring $N=15=\left(2+1\right)\times \left(4+1\right)$ with a 4-Qbit input register does not provide a serious test of the real Shor algorithm. The smallest number that demonstrates the full subtlety of the procedure is 21, which requires an input register of 9 Qbits, big enough to accommodate (21)².

Another subtlety, only recently pointed out, ¹ reduces that irritating 60% chance of not getting a divisor of r. When N is the product of two distinct primes, one can (again easily) show that r is not only less than N but less than ½N. As a result, besides getting a divisor of r when the measurement yields a y as close as possible to an integral multiple of 2n/r, second, third, and even fourth closest also work. This increase in the number of useful outcomes lowers the probability of failure from 60% to 10%, greatly simplifying the subsequent classical detective work.

Features of Shor’s “factoring” algorithm like those mentioned here are usually buried in the technical details. By exposing them to the light, I hope to have revealed some of the subtlety and charm of that remarkable procedure.