Shor's 1994 algorithm proves that a quantum Turing machine can factor an n-bit integer using O(n³) gates, establishing FACTORING ∈ BQP. However, the widely propagated claim that this constitutes a "quantum advantage" or that "RSA is broken" requires the additional premise FACTORING ∉ BPP — that no polynomial-time classical factoring algorithm exists. This premise is unproven after 30 years and is equivalent to separating complexity classes (BPP vs. BQP) whose relationship remains open. This paper systematically decomposes Shor's claim architecture into nine assumptions spanning number theory, computational complexity, and quantum physics. We find that while the mathematical core (FACTORING ∈ BQP) is rigorous, the practical interpretation (quantum computers will break cryptography) rests on a chain of contingent assumptions linked by the unproven FACTORING ∉ BPP. Through executable simulation (shor_crossover.py v1.0), an abelian HSP classification audit, a GNFS constant trajectory analysis, a surface code resource model, and a meta-scientific review of NIST PQC documents and expert surveys, we demonstrate that: (1) RSA-2048 requires 2.1–7.9 million physical qubits at 99.9–99.999% gate fidelity, with crossover to quantum advantage occurring ~2040 under optimistic roadmap projections [CODE-EXECUTED]; (2) a significant majority of known exponential quantum speedups (when counted by problem instances solved) reduce to abelian hidden subgroup problem variants [LLM-INFERRED], suggesting quantum advantage is architecturally narrow rather than general; (3) the GNFS complexity constant c ≈ 1.923 has been stable for 30 years with no evidence of a polynomial-time trend [LLM-INFERRED]; (4) NIST PQC documents and expert surveys systematically underrepresent the FACTORING ∉ BPP uncertainty [LLM-INFERRED]. We conclude that Shor's algorithm is better understood as an existence proof that abelian algebraic periodicity is efficiently detectable via quantum interference — a narrow but genuine discovery — rather than as a general proof of quantum computational supremacy. Full text and updates: https://papers.qnfo.org/papers/shor-assumptions-audit/
Shor's 1994 algorithm proves that a quantum Turing machine can factor an n-bit integer using O(n³) gates, establishing FACTORING ∈ BQP. However, the widely propagated claim that this constitutes a "quantum advantage" or that "RSA is broken" requires the additional premise FACTORING ∉ BPP — that no polynomial-time classical factoring algorithm exists. This premise is unproven after 30 years and is equivalent to separating complexity classes (BPP vs. BQP) whose relationship remains open. This paper systematically decomposes Shor's claim architecture into nine assumptions spanning number theory, computational complexity, and quantum physics. We find that while the mathematical core (FACTORING ∈ BQP) is rigorous, the practical interpretation (quantum computers will break cryptography) rests on a chain of contingent assumptions linked by the unproven FACTORING ∉ BPP. Through executable simulation (shor_crossover.py v1.0), an abelian HSP classification audit, a GNFS constant trajectory analysis, a surface code resource model, and a meta-scientific review of NIST PQC documents and expert surveys, we demonstrate that: (1) RSA-2048 requires 2.1–7.9 million physical qubits at 99.9–99.999% gate fidelity, with crossover to quantum advantage occurring ~2040 under optimistic roadmap projections [CODE-EXECUTED]; (2) a significant majority of known exponential quantum speedups (when counted by problem instances solved) reduce to abelian hidden subgroup problem variants [LLM-INFERRED], suggesting quantum advantage is architecturally narrow rather than general; (3) the GNFS complexity constant c ≈ 1.923 has been stable for 30 years with no evidence of a polynomial-time trend [LLM-INFERRED]; (4) NIST PQC documents and expert surveys systematically underrepresent the FACTORING ∉ BPP uncertainty [LLM-INFERRED]. We conclude that Shor's algorithm is better understood as an existence proof that abelian algebraic periodicity is efficiently detectable via quantum interference — a narrow but genuine discovery — rather than as a general proof of quantum computational supremacy. Full text and updates: https://papers.qnfo.org/papers/shor-assumptions-audit/
Systematic audit decomposing Shor's 1994 algorithm into nine assumptions spanning number theory, computational complexity, and quantum physics. The central finding: Shor proved FACTORING ∈ BQP (factoring is in quantum polynomial time), but the claim "quantum computers break RSA" additionally requires FACTORING ∉ BPP — a premise unproven after 30 years. Delivers 17 artifacts: manuscript, Shor-Crossover Simulator (Python + HTML dashboard), policy brief, abelian HSP classification audit, GNFS constant trajectory analysis, NIST PQC narrative analysis, expert survey synthesis, formal claim gap analysis, Shor failure probability bounds, classical ORDER-FINDING analysis, and Knowledge Graph cross-reference against 611 QNFO publications. RSA-2048 requires 2.1-7.9M physical qubits; crossover at ~2040 under optimistic projections.
A systematic epistemic-hygiene audit of quantum computational advantage claims (1985-2025). Surveying 29 major claims across five regimes (oracle separations, sampling-based, query-complexity, communication-complexity, Shor's algorithm), we find zero unconditional proofs that BQP != BPP. Every surveyed claim depends on at least one unverified assumption: unproven cryptographic hardness, untestable average-case conjectures, or oracle-relative constructions that do not transfer to the uniform model. Published 2026-07-11. Live at https://8d0a2a5c.qwav.pages.dev/
Factoring large integers has long been a computationally difficult problem in classical computing, forming the foundation of widely used encryption methods like RSA. In 1994, Shor’s quantum algorithm introduced a revolutionary method for factoring integers exponentially faster than classical algorithms, laying the groundwork for quantum cryptography. Despite numerous attempts to enhance Shor’s algorithm over the last three decades, significant breakthroughs remained elusive until Regev’s discovery in 2023. Regev introduced a novel, multi-dimensional version of the quantum factoring algorithm, achieving a substantial improvement by reducing the required number of quantum gates to O(n^2 lo gn )(n^(3/2) logn ), compared to Shor’s originalO(n^2 lo gn )original O(n^2 logn ) gate complexity. Although Regev’s approach offers a significant speedup, it comes with increased qubit requirements and relies on an unproven number theory assumption. This paper presents an overview of Regev’s factoring algorithm, including a review of Shor’s work for context, followed by an examination of key recent developments and follow-up research. These include efforts to reduce the qubit count, improve error resilience, generalizegeneralise Regev’s algorithm to related problems, and validate the number theory assumption. This review serves as an accessible entry point for researchers interested in the rapidly evolving field of quantum computing and factoring algorithms.
Shor's algorithm factors an n-bit integer in time polynomial in n, which would break RSA. Its asymptotic gate complexity, however, says little about what a real machine must provide, because the dominant cost is the overhead of quantum error correction. This report evaluates the computational complexity of Shor's algorithm in three layers: the logical algorithm (gate count, depth and qubits of order finding and modular exponentiation), the surface-code layer (code distance, logical error suppression, lattice surgery and magic-state production) and the physical resource layer (qubits and wall-clock time). We present a compact analytic resource model, calibrated to the published Gidney-Ekerå estimate for RSA-2048, and use it to study scaling with key size, physical error rate and reaction time. For RSA-2048 the model gives about 2.6 billion Toffoli gates, roughly 6,200 logical qubits, a code distance near 29 and about 20 million physical qubits for a runtime of about seven hours at a 0.1% physical error rate. Resource requirements grow as n3 in gates and runtime, while physical-qubit overhead is dominated by the code distance, which rises steeply as the physical error rate approaches the threshold. We also summarize how algorithmic and code improvements through 2026 have reduced published estimates by orders of magnitude.
The execution cost of quantum algorithms is typically quantified through asymptotic gate counts and qubit register sizes, yet these metrics do not directly capture which genuinely quantum resources, and in what amount, must be created and maintained for the computation to succeed. The systematic quantification of such information-theoretic requirements in quantum computing protocols remains an extremely challenging open problem, despite their direct role in establishing quantum advantage. To address this gap, we investigate the generation of non-stabilizerness (or magic), one of the key resources, in the paradigmatic Shor's factoring algorithm, revealing a deep connection between intrinsic quantum complexity and the computational hardness of the underlying number-theoretic problem. By developing an explicit analytic theory, we demonstrate the fundamental role of magic in the successful execution of the algorithm, and show that Shor's routine maximally exploits the quantum resource in practically relevant regimes. Our findings create a concise conceptual link between the classical algorithmic difficulty of a task and the non-stabilizer price to solve it on quantum hardware, complementing standard circuit-cost analyses with a resource-based metric that is naturally aligned with the real bottlenecks of fault-tolerant quantum computing.
Quantum integer factorization is a groundbreaking field that explores the use of quantum algorithms, notably Shor's algorithm, to efficiently factorize large integers into their prime components. Its potential implications on modern encryption techniques, such as the Rivest-Shamir-Adleman (RSA) algorithm, are of considerable interest. This paper's central aim is to contrast the computational time and implementation of the Integer Factorization Problem (IFP) between classical and quantum computers. The inner workings of Quantum Shor's algorithm are broken down step by step, and the estimated processing time is contrasted with the classical General Number Field Sieve (GNFS) approach. Given the exponential speedup provided by quantum computing, this comparison helps assess Shor's algorithm's possible advantage over GNFS in factoring large numbers. Direct comparisons with GNFS are currently difficult due to Shor's algorithm's reliance on large-scale quantum computer development for practical execution speeds. This paper focuses on solving integer factorization up to2nbits.