Shor's Algorithm and the Unproven Premise: An Assumption Audit of the Quantum Factoring Narrative

In the paper's words

Shor's 1994 algorithm proves FACTORING ∈ BQP, but the claim that this constitutes a quantum advantage requires the additional unproven premise FACTORING ∉ BPP. This paper decomposes Shor's claim architecture into nine assumptions spanning number theory, computational complexity, and quantum physics. Key findings: RSA-2048 requires 2.1–7.9M physical qubits at 99.9–99.999% fidelity with crossover ~2040; ≥80% of exponential quantum speedups reduce to abelian HSP; Shor's algorithm is better understood as detection of abelian algebraic periodicity via quantum interference rather than a general proof of quantum computational supremacy.

The abstract, verbatim, and its opening sentence is the claim. Every line below is quoted from the text.

Numbers it reports

1. 2026 5,000 7.9M (at 99.9% fid.) NO 2030 50,000 2.7M (at 99.98% fid.) NO 2035 500,000 1.6M (at 99.995% fid.) NO 2040 1,000,000 820K (at 99.999% fid.) YES Crossover finding: Under optimistic IBM/Google roadmap projections (2× qubits every 3 years, fidelity asymptoting to 99.999%), quantum hardware first has sufficient physical qubits for RSA-2048 factoring around 2040.

   from 4.1 Shor-Crossover Simulator Results

2. The physical-to-logical qubit ratio depends critically on the physical gate error rate: Physical Error Rate Code Distance Phys/Logical Ratio Phys Qubits for RSA-2048 $10^{-2}$ 1000 2,000,000 $8.2\times 10^{9}$ (infeasible) $10^{-3}$ 31 1,922 $7.9\times 10^{6}$ $10^{-4}$ 16 512 $2.1\times 10^{6}$ $10^{-5}$ 10 200 $8.2\times 10^{5}$ A single order-of-magnitude improvement in gate fidelity ($10^{-3} \to 10^{-4}$) reduces physical qubit requirements by ~4×.

   from 4.2 Surface Code Overhead Sensitivity

3. If LDPC codes prove practical at scale, RSA-2048 could require as few as ~41,000 physical qubits — a 50× reduction from the surface code estimate and within reach of 2030-era hardware.

   from 4.2 Surface Code Overhead Sensitivity

4. (→ Assumption A6) rq-011 : Adelic QEC Synthesis (→ Assumption A6) Relevant KG Findings: finding-braid-compilation : 12,000× compilation speedup vs.

   from 5. Knowledge Graph Cross-Reference

5. The physical resource analysis demonstrates that even under optimistic projections, RSA-2048 factoring remains at least 15 years away and highly sensitive to gate fidelity assumptions.

   from 6. Conclusion

6. This premise is unproven after 30 years and is equivalent to separating complexity classes (BPP vs.

   from Abstract

How it is done

1. Shor's 1994 algorithm proves that a quantum Turing machine can factor an n-bit integer using $O(n^{3})$ gates, establishing FACTORING ∈ BQP.

   from Abstract

2. The claim "quantum computers provide an advantage over classical computers for factoring" additionally requires FACTORING ∉ BPP — that factoring has no polynomial-time classical algorithm.

   from 1. Introduction

3. Shor's algorithm reduces factoring to order-finding through a classical reduction due to Miller (1976) [2], then solves order-finding using a quantum circuit.

   from 2. Background: Shor's Algorithm Decomposed

4. The converse — that FACTORING ∈ BPP — would be established by discovering a polynomial-time classical factoring algorithm, which would collapse the quantum advantage claim for factoring without saying anything about BQP's power for other problems.

   from 3.2 What Proving $P_{4}$ Would Require

What would falsify it

The paper's text states no explicit falsification criterion; the limits below are what it says about where the claim stops.

Where the claim stops

1. The cryptographic panic surrounding it rests on the unproven empirical assumption that classical computers cannot also exploit the same algebraic structure with sufficient ingenuity.

   from 6. Conclusion

2. The physical resource analysis demonstrates that even under optimistic projections, RSA-2048 factoring remains at least 15 years away and highly sensitive to gate fidelity assumptions.

   from 6. Conclusion

3. Recommendations: (1) Cryptographic migration timelines should explicitly model the FACTORING ∉ BPP uncertainty as a Bayesian prior, not as a settled fact.

   from 6. Conclusion

Where to read

1. Abstract290 words · 1 min
2. 1. Introduction195 words · 1 min
3. 2. Background: Shor's Algorithm Decomposed180 words · 1 min
4. 3. The Central Gap: FACTORING ∈ BQP vs. FACTORING ∉ BPP254 words · 1 min
5. 4. Physical Resource Analysis344 words · 1 min
6. 5. Knowledge Graph Cross-Reference122 words · 1 min
7. 6. Conclusion190 words · 1 min