Order finding and the arithmetic of Shor

Factoring is order finding, and most choices of a work

To factor an odd composite N, pick a coprime to N and let r be the order of a mod N. If r is even and a^r/2 ≢ −1 (mod N), then (a^r/2 − 1)(a^r/2 + 1) ≡ 0 (mod N) with neither factor ≡ 0, so gcd(a^r/2 ± 1, N) are nontrivial divisors. Shor's lemma says a random a fails with probability at most 1/2^k−1, where k is the number of distinct odd prime factors: the multiplicative group mod a prime power is cyclic, so each prime power has probability at most 1/2 of giving any particular power of 2 dividing its order, and the algorithm fails only when all k powers agree. The quantum computer's only job is to find r.

What the measurement distribution is

Take q with N² ≤ q < 2N². Prepare Σ_x|x〉|a^x mod N〉, measure the second register and get a^k for some k < r: the first register is now uniform over x ≡ k (mod r). A QFT of size q and a measurement give c with probability

P(c, k)  =  | (1/q) sum_{x = k mod r}  exp(2 pi i x c / q) |^2      =  | (1/q) sum_{b=0}^{floor((q-k-1)/r)} exp(2 pi i b {rc}_q / q) |^2

where {rc}_q is the residue of rc mod q in (−q/2, q/2]. The second form is a geometric sum, peaked when {rc}_q is small, i.e. when c/q is close to a multiple of 1/r. Shor shows P(c, k) ≥ 4/(π²r²), at least 1/(3r²) for large N, whenever |{rc}_q| ≤ r/2. In that case |c/q − d/r| ≤ 1/(2q) for some d, and because q > N² at most one fraction with denominator below N is that close, so continued fractions of c/q find d/r in lowest terms; if gcd(d, r) = 1 that reveals r. There are rφ(r) such good (c, k) pairs, giving success probability at least φ(r)/(3r).

Shor's own example, and three more

The checker simulates the periodic state and its DFT exactly for four cases (the first is Shor's Figure 5.1 example: N = 33, a = 5, r = 10, q = 256), and checks that the squared amplitudes sum to 1 and equal the closed form to 10⁻⁹.

case                       r    q      total prob   min P over good c   >= 1/(3r^2)    P(recover r, 1 run)   bound phi(r)/3r
N=33  a=5   (Shor Fig 5.1) 10   256    1.000000     0.005618            0.003333       0.3637                0.1333
N=15  a=7                   4   256    1.000000     0.062500            0.020833       0.5000                0.1667
N=21  a=2                   6   512    1.000000     0.018909            0.009259       0.3282                0.1111
N=35  a=2                  12   2048   1.000000     0.004727            0.002315       0.3281                0.1111

The N = 33 row uses q = 256, below N² = 1089, because that is Shor's plotting example (his text says q is taken smaller “so as to make the values of c in the plot distinguishable”); the other three satisfy N² ≤ q < 2N². With q = 16 for N = 33 the same computation recovers r with probability 0.0000: the condition on q is not decoration.

The classical half, exhaustively. For all 110 odd composite non-prime-power N ≤ 400, the failing fraction of a never exceeds 1/2^k−1, and it reaches it (worst ratio 1.000), so Shor's bound is tight, not merely true. Over 956 pairs (N, a) for twenty odd composites, a factor comes out exactly when r is even and a^r/2 ≢ −1, and the factors found divide N (708 gave factors). Controls: q = 16; the 106 pairs with odd order, where a^r/2 is not an integer; N = 15, a = 14, where a^r/2 = −1; and using period r+1 in the closed form no longer matches the simulation.

Run it: python3 quantum-maths/qm4-verify.py (standard library only; the sourcing block says SKIP, never PASS, if the source PDF is not in ~/Downloads).