Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

The Conditional Advantage - An Epistemic Hygiene Audit of Quantum Computational Advantage Claims

Rowan Brad Quni-Gudzinas

Published Jul 11, 2026• 0 citations
Publisher

Abstract

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/

DOI
10.5281/zenodo.21304443

Related papers

Shor's Algorithm and the Unproven Premise: An Assumption Audit

Rowan Brad Quni-Gudzinas

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/

•Jul 14, 2026•0 citations

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

QNFO Research, Rowan Brad Quni-Gudzinas

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.

•Jul 14, 2026•0 citations

A Framework for Quantum Advantage

Olivia Lanes, Mourad Beji, Antonio D. Corcoles +12 more

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.

arXiv:2506.20658•Jun 25, 2025•52 citations

Verifiable Quantum Advantage without Structure

Takashi Yamakawa, Mark Zhandry

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.

Annual Symposium on Foundations of Computer Science•Oct 1, 2022•54 citations

Quantum Computing at the Threshold of Utility: A Critical Review of Hardware Platforms, Algorithms, Cryptographic Implications and Commercial Readiness (2024–2026)

Indrajit Sarkar

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.

•Aug 6, 2026•0 citations

Quantum–Classical Drug Discovery after the Advantage Claim: Matching Computational Methods to Problems They Can Credibly Solve

David Thompson, Sarah Mitchell, Rachel Adams +1 more

Quantum computing has become increasingly visible in pharmaceutical research, yet the evidentiary meaning of an “advantage” claim remains unsettled. Drug discovery contains heterogeneous scientific decisions, data structures, computational abstractions, validation standards, and translational consequences. Consequently, improvement in circuit execution, molecular-energy estimation, sampling, classification, or candidate generation cannot by itself establish pharmaceutical usefulness. This Origin

Pharmacophore•Jan 1, 2025•0 citations
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.
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.
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.
Quantum computing has become increasingly visible in pharmaceutical research, yet the evidentiary meaning of an “advantage” claim remains unsettled. Drug discovery contains heterogeneous scientific decisions, data structures, computational abstractions, validation standards, and translational consequences. Consequently, improvement in circuit execution, molecular-energy estimation, sampling, classification, or candidate generation cannot by itself establish pharmaceutical usefulness. This Origin