Exact quantum factoring over a fixed finite gate set

The explanation

Factor N = 15 the quantum way. Pick a = 7 and look at its powers modulo 15. They run 7, 4, 13, 1, so the order of 7 is r = 4. The order is the least power that gives 1. Half the order gives 7² ≡ 4, a square root of 1 that is not ±1. Then gcd(4 − 1, 15) = 3 and gcd(4 + 1, 15) = 5. So 15 = 3 × 5.

Shor's algorithm finds orders quickly with a quantum computer. It factors in polynomial time with bounded errorSource 1. Bounded error means each run can fail with some small chance. Checking a proposed answer makes reruns reliable. But a procedure that retries until success need not have a polynomial worst-case running timeSource 2. Exact versions existed only in stronger models. Mosca's exact algorithm allowed gate settings computed during the runSource 3. The obstacle with a fixed gate set is that rotations by arbitrary angles cannot be built exactly. Approximating them ever more finely does not give probability-one answersSource 4.

The paper proves a uniform family of polynomial-size quantum circuitsSource 5. Uniform means an ordinary computer can write out each circuit in polynomial time. The circuits output the complete prime factorization of every N ≥ 2 with probability oneSource 5. One fixed finite gate set suffices: NOT, CNOT, Toffoli, Hadamard, diag(1, i), their inverses and singly controlled versionsSource 6. The gate and qubit counts are bounded by a fixed polynomial in the bit length of NSource 7.

The key trick ends with amplitude amplification, a step that boosts the chance of a good outcome. Suppose a good outcome has probability exactly 1/4. Write this as sin²θ = 1/4, so θ = 30°. One amplification step turns the probability into sin²(3θ) = sin²(90°) = 1. So the whole difficulty is making the success probability exactly 1/4Source 8. The paper does this with dyadic numbers, fractions whose denominators are powers of two. Its order trial hits the true order with an exact dyadic probabilitySource 9. Along the way, each run also factors p − 1 for its primes p, recursively. A deterministic primality test, adapted from Agrawal, Kayal and Saxena, checks the prime labelsSource 10.

The constructions are not meant to save resources. Their large polynomial sizes are not offered as practical improvementsSource 11. The paper makes no claim of a classical polynomial-time factoring algorithmSource 12.

How sure is this? Lean, a computer proof checker, has a formal proof of the main theorem. It covers the uniform polynomial-size circuit family, the fixed gate set and the exact probability one. No specialist review of the paper has been published.

What it doesn't show. This does not give a practical speed-up, a classical factoring method, or circuits small enough for any foreseeable quantum computer.