Imagine you're a customs inspector. Travelers hand you documents — passports, visas, manifests. You have a perfect scanner (a quantum verifier), but some travelers hand you paper documents (classical witnesses) while others hand you a holographic card whose authenticity you can only verify by shining laser light through it at specific angles (a quantum state). This paper proves that no matter how many layers of paper-document bureaucracy you stack up — supervisor checks, appeals boards, the whole hierarchy — there exist smugglers that only the holographic card can catch. Paper documents, no matter how cleverly layered, fundamentally cannot do what the holographic card does. The committed claim: there exists a classical oracle O under which P = BQP = QCMA = QCMAH ⊂ QMA, and QMA is not contained in QCMAH. Translation: even in a world where quantum computers offer zero speedup over classical ones (P = BQP), and where classical witnesses suffice for everything their own hierarchy can express (P = QCMA = QCMAH), quantum witnesses — quantum states used as proofs — remain strictly more powerful. This is a genuine first. Prior work by Kretschmer (2021) separated QMA from QCMA relative to a quantum oracle, and Natarajan and Nirkhe (2023) achieved a classical oracle separation of QMA from QCMA. But nobody had separated QMA from the entire QCMA hierarchy, nor done so while simultaneously collapsing P = BQP = QCMA. Cakan does both. The technical engine is a new problem called Codeword-Hash pairs in Noise (CHN), extending the author's own prior Codeword-Hash Structure problem (used to separate QMA from QCIP). The construction plants a quantum state witness inside a noisy error-correcting code structure such that any classical witness — even one handed through polynomially many rounds of classical verification — cannot extract the information a quantum state encodes directly. The query complexity proof shows CHN is in QMA but hard for every level of the QCMA hierarchy. The architecture is pure computational complexity theory: oracle constructions, query lower bounds, and reductions. No algorithms run on hardware. No datasets. The compute is mathematical proof, and the hardware property being exploited is the information-theoretic structure of quantum states themselves — specifically, that an exponentially large quantum state can encode correlations that no polynomially-long classical string can replicate, even with adaptive verification. The integrity story is strong for theory: mathematical proof is the gold standard of validation, and the result is relative to a classical oracle (not a quantum one, which would be weaker evidence for real-world implications). The paper answers an explicit open question from Kretschmer, Qian, and Tal (STOC 2025), so this isn't self-selected benchmarking — the target was set by the community. It's in submission at STOC 2027, which means it has been or will be subjected to rigorous peer review by program committee members who know exactly what an oracle separation does and doesn't prove. The standard caveat applies: oracle separations do not resolve unrelativized complexity questions. This tells us the structural relationship between QMA and QCMAH cannot be collapsed by any argument that relativizes. It doesn't prove QMA ≠ QCMAH in the real world. The cryptographic implications are where this gets practical-adjacent. The paper shows that pseudorandom states, public-key encryption with copy-protected quantum decryption keys, and other quantum cryptographic primitives survive even when P = QCMA — meaning even in a world with no quantum computational advantage and no quantum-computable one-way functions. This is a structural result about the foundations of quantum cryptography: the security of these primitives rests on quantum witness power, not quantum speed. If you're building quantum-secure systems, this tells you there's a layer of security that doesn't depend on computational hardness assumptions at all — it depends on the information-theoretic properties of quantum states. The next milestone is converting this oracle separation into evidence toward unrelativized separations. The gap between 'QMA ≠ QCMAH relative to a classical oracle' and 'QMA ≠ QCMAH unconditionally' is one of the central chasms in complexity theory — analogous to the gap between oracle separations of P and NP (which exist since the 1970s) and actually proving P ≠ NP. The honest read: this is likely a 10-20+ year horizon, if achievable at all. But each new structural separation narrows the space of possible collapses and strengthens the evidence. The experiment not run — or more precisely, the proof not attempted — is an unrelativized separation or even a separation relative to a random oracle (which would be stronger than a worst-case classical oracle). Why not? Because nobody knows how to do it. This isn't budget or strategic sandbagging; it's the fundamental hardness of complexity theory. The author has pushed the oracle-separation frontier as far as current techniques allow. The next step requires genuinely new proof techniques, possibly algebraization barriers or natural-proofs-style arguments. The honest read is option (a): the tools don't exist yet.
The analogy
You're a customs inspector with a perfect scanner. Some travelers show paper documents (classical witnesses), others show holographic cards you can only verify with polarized light (quantum witnesses). This paper proves that no matter how many layers of paper-document bureaucracy you stack — supervisors, appeals boards, the whole hierarchy — there are smugglers only the holographic card can catch. Paper can never substitute for the hologram.
Holographic ID
A credential whose authenticity depends on physical structure (light interference patterns) that cannot be photocopied onto paper no matter how many copies or layers you try
Quantum witness
A proof-state whose verification power depends on quantum correlations that cannot be encoded in any classical string, even through polynomially many adaptive rounds of classical verification
Honest assessment
This is a landmark result in structural complexity theory — the first separation of QMA from the entire QCMA hierarchy relative to a classical oracle, answering a community-posed open question. Its practical implications are foundational rather than immediate: it tells us quantum cryptographic primitives can rest on quantum witness power alone, not computational hardness. The limitation is inherent to the method: oracle separations don't resolve the unrelativized question, and that gap may persist for decades. If you work in quantum complexity, quantum cryptography, or foundations of computation, this paper reshapes what you believe is possible. If you need near-term applications, this is structural evidence, not an engineering tool.
What Is CLAIMS?
80
/ 100
BedrockNews applies a structured analytical framework called CLAIMS to academic papers and technical research releases.
How CLAIMS worksClaim
5/5
Ladder
5/5
Architecture
4/5
Integrity
4/5
Milestone
2/5
Successor
4/5
What is this paper actually committing to?
Genuine first: separates QMA from the full QCMA hierarchy (not just one level) via classical oracle, while simultaneously collapsing P = BQP = QCMA = QCMAH. Answers an explicit open question from STOC 2025.
The field fight
Is the power of QMA fundamentally rooted in quantum witnesses, or could classical witnesses with quantum verification suffice?
Side A
Classical witnesses may suffice — QCMA could equal QMA, and quantum witness power might be an artifact of our proof limitations
Held by: Skeptics, P=NP agnostics, some derandomization researchers
Side B
Quantum witnesses are irreducibly more powerful — quantum states encode information classical strings cannot, and this gap persists through all hierarchy levels
Held by: Aaronson-Kuperberg conjecture, Kretschmer, Natarajan-Nirkhe, this paper
Milestone tracker
Unlocks: Unconditional proof that quantum witnesses have computational power classical witnesses lack, with direct implications for quantum cryptography foundations
Current
QCMAH
hierarchy levels
Full hierarchy separated from QMA (oracle)
Next
1
unrelativized level
QMA ≠ QCMA without oracle
10-20+ years — requires fundamentally new proof techniques
Verified Facts (7)
There exists a classical oracle O such that P^O = BQP^O = QCMA^O = QCMAH^O ⊂ QMA^O but QMA^O ⊄ QCMAH^O
QCMAH = ∪_{d≥1} QCMA^{QCMA^{...^{QCMA}}} is the classical-witness quantum-verifier analogue of PH
The new problem is called Codeword-Hash pairs in Noise (CHN)
Extends the Codeword-Hash Structure problem introduced by Cakan (arXiv, 2026) to separate QMA from QCIP
Answers an open question of Kretschmer, Qian, and Tal (STOC 2025)
Relative to the oracle, there exist pseudorandom states with classical keys and public-key encryption with copy-protected quantum decryption keys and classical public keys and ciphertexts
In submission at STOC'27; full manuscript publicly posted on the conference website since November 3rd, 2026
Practical Implications (4)
Quantum cryptographic primitives (pseudorandom states, copy-protected keys) have a theoretical foundation that survives even if P = QCMA — their security doesn't require computational hardness assumptions
Protocol designers can reason about quantum witness-based security as a distinct category from quantum speed-based security
The QCMA hierarchy collapse (P = QCMAH) under the oracle means no amount of layered classical verification catches up to a single quantum proof — relevant for quantum verification protocol design
Provides structural evidence that quantum state certification and quantum money schemes have irreducible security advantages over classical-witness approaches
More latest news
Read all