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/
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/
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.
As quantum computing approaches the threshold where certain tasks demonstrably outpace their classical machines, the need for a precise, clear, consensus-driven definition of quantum advantage becomes essential. Rapid progress in the field has blurred this term across companies, architectures, and application domains. Here, we aim to articulate an operational definition for quantum advantage that is both platform-agnostic and empirically verifiable. Building on this framework, we highlight the algorithmic families most likely to achieve early advantage. Finally, we outline our vision for the near future, in which quantum computers enhance existing high-performance computing platforms, enabling new frontiers in chemistry, materials discovery, optimization, and beyond.
Quantum information processing has moved, within the space of roughly two years, from a discipline defined by extrapolation to one defined by measurement. This review consolidates and critically appraises the technical and commercial state of the field as it stood in mid-2026. Four developments frame the analysis: the demonstration of verifiable computational advantage on superconducting hardware through observable-based echo protocols in April 2026; the extension of advantage claims into the simulation of heterogeneous quantum materials in July 2026; the operation of surface-code memories below the fault-tolerance threshold; and the completion of the first tranche of standardised post-quantum cryptographic primitives. Against these advances the review sets an equally important body of negative evidence — systematic benchmark studies in which classically tractable formulations of putative quantum use cases were solved to proven optimality in seconds, and the withdrawal of at least one major financial institution from quantum research after resource estimation placed its target problem beyond any plausible machine. The paper surveys six physical qubit modalities, evaluates them against criteria that extend well past raw qubit count, examines the principal algorithmic families and their known limitations, assesses the software and cloud-access ecosystem, analyses the cryptographic migration timeline in policy and engineering terms, and reviews error-correction progress from repetition codes through quantum low-density parity-check constructions. The central conclusion is that the field has entered a period in which scientific advantage is demonstrable but economic advantage is not, and that the interval between the two will be governed less by qubit counts than by logical error rates, compilation overheads, and the availability of trained personnel.
We show the following hold, unconditionally unless otherwise stated, relative to a random oracle with probability 1: •There are NP search problems solvable by BQP machines but not BPP machines.•There exist functions that are one-way, and even collision resistant, against classical adversaries but are easily inverted quantumly. Similar separations hold for digital signatures and CPA-secure public key encryption (the latter requiring the assumption of a classically CPA-secure encryption scheme). Interestingly, the separation does not necessarily extend to the case of other cryptographic objects such as PRGs.•There are unconditional publicly verifiable proofs of quantumness with the minimal rounds of interaction: for uniform adversaries, the proofs are non-interactive, whereas for non-uniform adversaries the proofs are two message public coin.•Our results do not appear to contradict the Aaronson-Ambanis conjecture. Assuming this conjecture, there exist publicly verifiable certifiable randomness, again with the minimal rounds of interaction.By replacing the random oracle with a concrete cryptographic hash function such as SHA2, we obtain plausible Minicrypt instantiations of the above results. Previous analogous results all required substantial structure, either in terms of highly structured oracles and/or algebraic assumptions in Cryptomania and beyond.
Public debate on the quantum threat to blockchains—and much of the survey literature—is dominated by chain-level claims that mislocate the risk. We relocate the problem to the level at which an algorithm actually acts, showing that the post-quantum fate of any chain decomposes into three layers: which hardness assumption secures its signatures (Shor-vulnerable discrete-log/factoring, hash, or lattice); that assumption's status under the physically-realizable computational model (classical BPP vs quantum BQP); and the physical floor beneath it—unstructured-search lower bounds and serial-depth constraints, not a claim of unconditional security. At ground zero, the abelian-hidden-subgroup atom is efficiently broken under BQP (Shor), while no efficient BQP break is known for hash or lattice; hash security rests on the most conservative, best-tested conjecture; discrete-log rests on exploitable algebraic structure; and lattice assumptions, though buttressed by worst-case reductions unevenly across the lattice family, carry a much shorter cryptanalytic record. We locate the vulnerability in a single object—the exposed public key—and formalize compromise as a conjunction of exposure, feasibility, and non-revocation. Under a floor assumption (generic, unstructured search stays infeasible) this factors into four conjuncts answering to four distinct authorities—mathematics, the ledger, engineering, and the owner or protocol—with feasibility entailing brokenness. Each per-asset cryptanalytic defense we survey denies the primary one of these four conjuncts—an accounting identity over the four predicates (some defenses touch more than one; we classify by the primary), not a claim of exhaustiveness over an open-ended literature. We give an exposure taxonomy checked against the reference implementations and a first-party, reproducible measurement of the full Bitcoin UTXO set (block 957,269, July 2026): 1.93M BTC (≈9.6% of supply) carries a standing exposed public key—the defensible, structurally unambiguous figure—rising to 5–7M BTC (25–35%) once key-reuse is included, the range's width set by the P2SH/P2WSH script-hash upper bound. This decomposes exactly along the taxonomy's structural-versus-operational axis and quantifies Taproot's hidden-key regression (a directional shift on the exposure axis, minor by value); current resource estimates and a CRQC timeline; and a per-chain migration survey. A recurring result: account and governance architectures migrate most easily while immutable/UTXO chains are hardest—the property prized as a security virtue is the migration handicap. No unconditional security exists; all verdicts are contingent on unproven conjectures and the assumption that BQP is the physical ceiling of computation.