Case Study 1: What Factoring 15 Does Not Prove

DataField.Dev

Case Study 1: What Factoring 15 Does Not Prove

The demonstration

§23.4 factored 15 on a simulator. The circuit worked, the continued fractions worked, the reduction worked, and $15 = 3 \times 5$ came out the other end. Every number in that section is real.

And it proves almost nothing about factoring anything larger, for a reason worth being precise about — because "quantum computer factors $N$" headlines have appeared repeatedly, for $N = 15$, $N = 21$, and $N = 143$, and the gap between those demonstrations and RSA is not what the numbers suggest.

What the demonstration actually contained

Look at the modular multiplication used in §23.4:

def controlled_mult_mod_15(a, power):
    if a not in (2, 4, 7, 8, 11, 13):
        raise ValueError("a must be coprime to 15")
    U = QuantumCircuit(4)
    for _ in range(power):
        if a in (2, 13):  U.swap(2,3); U.swap(1,2); U.swap(0,1)
        if a in (7, 8):   U.swap(0,1); U.swap(1,2); U.swap(2,3)
        if a in (4, 11):  U.swap(1,3); U.swap(0,2)
        if a in (7,11,13):
            for q in range(4): U.x(q)

That is a lookup table. It is not an implementation of "multiply by $a$ modulo 15" — it is a hard-coded permutation for each of the six valid values of $a$, derived by someone who already knew the answer.

The vqelab version is explicit about this:

if N != 15:
    raise ShorError(
        "this build only implements modular multiplication for N=15; "
        "general modular exponentiation is the hard part (section 23.6)")

It raises rather than pretending to generalize, which is the honest thing for a teaching implementation to do.

Why this matters

The hard part of Shor's algorithm is the part that was skipped.

§23.6 measured where the cost lives:

    n bits    QFT gates    mod-exp Toffolis      ratio
      2048    2,096,128       2,576,980,377     1,229x

Modular exponentiation is 99.92% of a real Shor circuit. The demonstration implemented the other 0.08% — the phase estimation and the QFT — and replaced the expensive part with a lookup.

So a working factorization of 15 demonstrates:

✅ phase estimation works,
✅ continued fractions recover the period,
✅ the classical reduction is correct,
❌ nothing about the component that dominates the cost.

The sharper version of the objection

There is a stronger form, and it applies to several published demonstrations.

If you know the answer, you can compile the circuit down to almost nothing.

The permutation above is small because $a$'s order modulo 15 is known in advance. A compiler given that knowledge can simplify the circuit dramatically — and in the limit, a "quantum factorization" becomes a circuit whose structure already encodes the factors.

The test that separates a real demonstration from a compiled one: would the circuit still work if the answer were unknown? For a genuine implementation, modular exponentiation is built from reversible arithmetic that does not depend on $r$. For a compiled one, the construction requires $r$, which is what you were trying to find.

🔬 This is not an accusation of dishonesty. Compiled demonstrations are legitimate and useful — they validate the phase-estimation machinery on real hardware, which is a genuine result. The problem is in the reporting: "quantum computer factors 143" and "quantum computer implements the non-trivial part of Shor's algorithm at scale" are very different claims, and press coverage reliably conflates them.

Read any factoring demonstration for its modular arithmetic, not its output. If the paper does not describe a general reversible modular multiplier, it has demonstrated something else.

What a real implementation needs

The component that was skipped:

Reversible modular multiplication. Multiply two $n$-bit numbers modulo $N$, reversibly, with ancillas that are properly uncomputed (Chapter 19 §19.4). This is built from reversible adders, comparators, and conditional subtractions — hundreds of lines of careful arithmetic, and the subject of a substantial research literature.

Controlled versions of it, since phase estimation needs controlled-$U^{2^j}$.

And it must be correct for every input, not just the ones you tested — which is where Chapter 19's ancilla hygiene becomes load-bearing, because a dirty ancilla in a modular multiplier produces a wrong answer that looks like noise.

$$\mathcal{O}(n^3) \text{ Toffolis} \quad\Longrightarrow\quad 2.6 \times 10^9 \text{ at } n = 2048$$

That is the algorithm. Everything else in this chapter is scaffolding around it.

The honest framing of the demonstration

§23.4's factorization of 15 is worth doing, and here is what it is worth:

It validates the machinery you can validate. Phase estimation returns four sharp peaks at exactly the predicted positions; continued fractions recovers $r = 4$; the reduction gives $3 \times 5$. Every one of those would break if the surrounding logic were wrong, and none of them can be checked by inspection.

It teaches the structure. The two levels of randomization, the retry loop, the verification at every stage — those are the same at any $N$, and they are where implementations actually go wrong.

And it establishes the scale of what remains. The circuit that factors 15 has 12 qubits. The circuit that factors RSA-2048 needs 24.9 million physical qubits and 10.5 billion T gates. Having built the small one, the gap becomes concrete rather than abstract.

The lessons

A demonstration proves what it implements, not what it is called. Factoring 15 with a hand-built permutation demonstrates phase estimation, not modular exponentiation — and modular exponentiation is 99.92% of the algorithm.

Ask what was compiled away. If the circuit's construction required knowing the answer, it cannot be evidence about finding the answer. This test is cheap and it settles most of these claims.

Teaching implementations should refuse to generalize rather than appear to. vqelab.shor raises for $N \neq 15$ with a message naming what is missing. A version that silently produced wrong circuits for other $N$ would be worse than useless.

And a small demonstration is still worth building. It validates the parts that can be validated and makes the remaining gap concrete — which is a better outcome than either dismissing it or overselling it.

The recurring theme, in a new register: this book has repeatedly found that the interesting part and the expensive part are not the same part (§23.6). Here the demonstration implemented the interesting part and skipped the expensive one — and the reporting described the whole.

Reproduce it: code/example-02-factoring-15.py is the demonstration; code/example-03-where-the-cost-is.py measures what it left out; order_finding_circuit in code/project-checkpoint.py raises for $N \neq 15$.