Shor's algorithm

In plain terms

Multiply two large prime numbers together and you have the answer at once, but recover the two primes from their product and, with the best classical methods, you wait effectively forever once the numbers are large enough. That one-way street isn't a theorem, but it's the working assumption, and most of the public-key cryptography protecting the internet leans on it.

Shor's 1994 algorithm breaks the street. A quantum computer can factor in polynomial time, meaning the running time grows only as a modest power of the number of digits rather than exploding with each digit added. The route is indirect and elegant. Classical number theory reduces factoring to finding the period of a repeating sequence, as the remainders left when successive powers of a chosen number are divided by the number to be factored eventually repeat, and the length of the repeat reveals a factor. Period-finding is exactly what quantum interference does well. A quantum register can hold every input value at once, in what's called a superposition, and the quantum Fourier transform, the quantum version of the mathematical tool that picks the frequencies out of a signal, makes the period stand out the way a single note stands out from a struck bell.

Machines large enough to run the algorithm on numbers that matter don't yet exist, and the conclusion for current cryptography is nonetheless already settled, as it's living on borrowed time.

In CSD

Shor's algorithm is the most demanding of the corpus's algorithm witnesses. A witness is a known algorithm carried through the formalised framework to show the framework can support it, and witnesses mark scope and don't support foundations. What makes this one heavy is the plumbing, as the reversible modular arithmetic beneath the algorithm, the adders and multipliers built from steps that can each be run backwards as quantum logic requires, is built and verified in full, because that's where a formalisation either survives or quietly cheats.

The corpus makes no cryptographic claims, and the cost-model work bearing on real machines was deliberately moved to a separate repository. What remains here is an existence proof, as the formalised dynamics carries a complete, real algorithm from end to end.

Mathematically

Quantum order-finding extracts the period of modular exponentiation in polynomial time via the quantum Fourier transform, and a classical reduction, essentially Legendre-era number theory, converts the period into a factor with high probability.

The quantum content is entirely the period-finding, and the corpus's labour is mostly the verified reversible arithmetic underneath it.

The name

Peter Shor (b. 1959) was an Olympiad medallist, took degrees at Caltech and MIT, and was at Bell Labs when he announced the algorithm in 1994. The community's reaction was unusually theatrical, as word spread from a small talk before the paper existed, and within weeks half of physics had opinions about a result almost nobody had read.

The objection came instantly, that decoherence, the loss of quantum behaviour through contact with the surroundings, would kill any real machine. Shor answered it himself in 1995 with the first quantum error-correcting code, dispatching the counterargument to his own revolution. He moved to MIT in 2003, and few people have built both a field's central promise and its central defence.

Related entries

• quantum Fourier transformThe quantum Fourier transform runs Fourier's transform as a single reversible motion of a quantum register, and it's the lens that turns hidden periods and phases into outcomes a measurement can land on.
• phase estimationPhase estimation, the workhorse subroutine of quantum computing, carries a guarantee, as if you read the dial at the nearest tick you're right at least four divided by pi squared of the time, a little over forty percent, however fine the dial.
• Grover's algorithmGrover's algorithm finds one marked item in an unsorted list in a number of steps proportional to the square root of the list size, and a separate theorem shows that no quantum algorithm can do better.
• Simon's algorithmSimon's algorithm was the exponential separation that convinced Shor, as a hidden bitwise mask, unfindable classically without exponential work, falls to a handful of quantum queries and some linear algebra.
• Shor codeShor's nine-qubit code was the first proof that quantum information can be protected against any error on any single qubit without ever being read, and the corpus verifies that protection as explicit constructed operations, including the subtle case where two different errors share one repair.
• reversible adderA reversible adder has to return its scratch space clean, and the carry-clean ripple-carry design does it with a single spare qubit, which is what makes arithmetic affordable inside a quantum algorithm.
• Toffoli gateThe Toffoli gate flips its target only when both controls are set, which is enough to compute anything classically while remaining reversible, and its count is the currency in which the cost of a quantum algorithm is quoted.