Shor's Algorithm

Factor an integer in polynomial time by reducing factoring to order-finding, solved with the quantum phase estimation of a modular-multiplication operator. It turns a problem that underpins modern public-key cryptography into a periodicity question a quantum computer can solve efficiently.

The problem it solves

Factoring a large integer N into its prime factors is a famously hard classical problem. The best known classical method (the general number-field sieve) runs in sub-exponential time — better than purely exponential, but nowhere near polynomial. RSA's security relies on the practical hardness of factoring large semiprimes for classical computers: publish N, and trust that no one can recover its two prime factors in any feasible amount of time.

Shor's algorithm drops the quantum cost of factoring N to a polynomial in the number of bits n = log₂N. This is not a quadratic speedup — it is a jump from sub-exponential to polynomial, and that is exactly why it is so disruptive for cryptography.

Note the classical cost above is sub-exponential, not truly exponential; the point of the comparison is the class of growth — Shor pushes the curve into the polynomial regime.

The key idea — reducing factoring to period-finding

Shor's real trick is a purely classical reduction: factoring N is equivalent to finding the period of a function. Pick any a coprime to N and look at the sequence

a⁰, a¹, a², a³, … (mod N)

This sequence is necessarily periodic. The smallest positive r that brings it back to 1 — the r with a^r ≡ 1 (mod N) — is called the order of a mod N. Once you know r, the rest is schoolbook algebra: if r is even then a^r − 1 = (a^(r/2) − 1)(a^(r/2) + 1) is a multiple of N, so gcd(a^(r/2) ± 1, N) very likely exposes a non-trivial factor.

The hard part has therefore been compressed into one thing: finding the period r. A classical computer cannot do this (finding the period is as hard as factoring), but a quantum computer can — which is where phase estimation enters.

How the quantum part finds the period

Define the unitary U|y⟩ = |a·y mod N⟩, "multiply by a". Its eigenvalues all have the form e^(2πi·s/r), and the denominator of that phase s/r hides exactly the order r we want. So finding the order becomes quantum phase estimation on U.

The circuit prepares a uniform superposition on a counting register, applies a ladder of controlled U^(2^j) — which amount to modular exponentiation a^(2^j) mod N — to kick the phase information onto the counting qubits, and reads it out with an inverse QFT. The measured bitstring approximates 2ⁿ·(s/r). Feeding that fraction to the classical continued-fractions expansion recovers the denominator r from that rational approximation.

Why it works — and why it retries

Shor's algorithm is probabilistic, with a few ways to miss, each of them mild:

• Phase estimation may not return the best approximation to s/r — take more shots.
• The recovered r may be odd, or satisfy a^(r/2) ≡ −1 (mod N) — that round is useless, so pick a new a and start over. (The case a^(r/2) ≡ +1 cannot arise for even r: it would contradict r being the least period, so it is automatically excluded — leaving ≡ −1 as the only extra failure mode.)
• One can prove that a randomly chosen a avoids both bad cases with probability at least 1/2, so only a constant number of rounds is needed on average.

What it is — and isn't — good for

• It genuinely "breaks" factoring. Unlike Grover's quadratic speedup, Shor moves factoring from sub-exponential to polynomial. Shor's integer-factoring version threatens RSA; its discrete-logarithm version threatens Diffie–Hellman, DSA, ECDH, and ECDSA — schemes based on the (elliptic-curve) discrete-logarithm problem.
• It needs fault tolerance. The controlled modular-exponentiation circuit is deep and wide; factoring a real 2048-bit key needs thousands of logical qubits, hence millions of error-corrected physical qubits. That is far beyond today's hardware — which is why "post-quantum cryptography" is being deployed now.
• It is highly specialised. The whole machine is built for periodicity; it is not a general accelerator and does not transfer to unstructured search or generic optimisation.
• It is hybrid by nature. The quantum part only finds the period; the continued-fraction post-processing and gcd are classical.

The algorithm, step by step

1. Pick a random a coprime to N.
2. Use phase estimation to find the order r of a mod N.
3. A randomly chosen a satisfies both conditions (r even and a^(r/2) ≢ −1 (mod N)) with probability ≥ 1/2. Since r is the least positive order of a mod N, an even r automatically gives a^(r/2) ≢ 1 (mod N) (otherwise r/2 would already be a period); the only bad even case is a^(r/2) ≡ −1. When the conditions hold, gcd(a^(r/2) − 1, N) or gcd(a^(r/2) + 1, N) necessarily yields a non-trivial factor of N. Otherwise pick a new a and repeat.

Seeing it in code

The skeleton below shows the structure of the order-finding subroutine. Read it against the theory above: cq is the counting register, and h(cq) puts it in superposition to hold the phase; wq is the work register holding |y⟩, initialised to |1⟩ by x(wq[0]); the commented placeholder for controlled modular exponentiation is exactly the ladder of controlled U^(2^j) operators; an inverse QFT on the counting register and a measurement follow. The measured result is handed to classical continued fractions to recover the order r, and from it the factors of 15.

import qalgora

@qalgora.kernel
def order_finding(counting: int, work: int, a: int, N: int):
    cq = qalgora.qvector(counting)
    wq = qalgora.qvector(work)
    h(cq)
    x(wq[0])
    # controlled modular exponentiation a^(2^j) mod N ...
    # inverse QFT on the counting register
    mz(cq)

counts = qalgora.sample(order_finding, 8, 4, 7, 15)
# classical post-processing: continued fractions -> order r -> factors of 15

This is not a complete Shor implementation — it only shows the structure of the quantum order-finding circuit. A runnable version still needs the controlled modular exponentiation U^(2ʲ), the inverse QFT, and classical continued-fraction post-processing.

References

• P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer," SIAM J. Comput. 26(5), 1484-1509 (1997). arXiv:quant-ph/9508027