Research
Classical Oracle Separation of QMA from the QCMA Hierarchy and Quantum Cryptography Even When P = QCMA
A classical oracle separates QMA from the whole QCMA hierarchy and preserves quantum cryptography even if P=QCMA, resetting complexity-theory expectations.
- arXiv
- 2611.26574
- Published
- 2026-11-19
- Authors
- Alper Cakan
AI summary
Overview
Research area: Quantum complexity theory and quantum cryptography (specifically the "MicroCrypt" line of work — cryptography relative to oracles where classical cryptography is impossible).
Technical level: Advanced. The paper assumes fluency in query complexity, oracle separations, interactive proof hierarchies, and black-box cryptographic constructions.
Scope: A single-author theory paper (Alper Cakan, Carnegie Mellon University; arXiv:2611.26574v1 [quant-ph], 19 Nov 2026; CC BY 4.0) that introduces one new oracle problem, uses it to separate QMA from the entire QCMA hierarchy relative to a classical oracle, and then reuses it to build quantum cryptographic primitives in a world where P = QCMA.
What This Paper Is About
The paper asks whether quantum proofs (states that a quantum verifier can check) are more powerful than classical proofs (strings a quantum verifier can check) — not just against QCMA itself, but against the whole QCMA hierarchy, the classical-witness analogue of the polynomial hierarchy PH. Previous oracle separations of QMA from QCMA produced languages that lie in AM, which sits inside the second level QCMA^QCMA of that hierarchy, so they could not show QMA is outside the hierarchy or that quantum advantage survives when P = QCMA.
The goal is to build a problem that is easy for a QMA verifier holding a quantum witness but hard for every constant level of the QCMA hierarchy, and then to leverage it so that quantum cryptography — pseudorandom states, copy-protected public-key encryption, quantum-key signatures, quantum money — can exist even in an oracle world where P = BQP = QCMA = QCMAH.
Key Contributions
-
A new problem, Codeword-Hash pairs in Noise (CHN). Inspired by the Codeword-Hash Structure (CHS) problem that Cakan introduced in a 2026 arXiv paper to separate QMA from QCIP, CHN plants constant-1 values on top of sparse Bernoulli noise at locations that are codewords paired with their symbol-wise Yamakawa–Zhandry hashes. Putting noise into both the planted and the noise distributions removes the counting gap that placed CHS in BB-coNP.
-
A query-complexity separation from the whole hierarchy. The paper proves CHN ∈ BB-QMA \ BB-QCMAH in the query complexity (black-box) model, where BB-QCMAH = ⋃_{d≥1} BB-QCMAH_d, the classical-witness quantum-verifier analogue of PH. A small extension converts this into a classical oracle relative to which P^O = QCMA^O = QCMAH^O ⊂ QMA^O, with an explicit unary language L ∈ QMA^O \ QCMAH^O.
-
Quantum cryptography with no quantum computational advantage. The paper constructs a classical oracle O with P^O = QCMA^O = QCMAH^O (and, in the abstract's statement, P^O = BQP^O = QCMA^O = QCMAH^O) relative to which PRS with classical keys, copy-protected PKE, copy-protected PRF (and hence PRU with quantum secret keys), signature schemes with quantum signing keys, and collusion-resistant public-key quantum money all exist. This answers an open question of Kretschmer, Qian, and Tal (STOC 2025).
-
A stronger average-case separation. Corollary 3 strengthens the oracle separation to the promise classes: PromiseP^O = PromiseQCMA^O = PromiseQCMAH^O, yet there is a language in QMA^O that is hard even on average for QCMAH^O machines.
Main Findings
-
CHN separates QMA from the QCMA hierarchy in the query model. Theorem 4 (informal; Theorems 8 and 10) states that a BB-QMA machine accepts planted samples and rejects noise samples except on a negligible fraction, while for every constant d and every query-efficient BB-QCMAH_d machine M_d that almost surely does not output ⊥, the acceptance probability difference between the planted and noise distributions is at most negl(λ). Because the two distributions have overlapping supports, discarding the negligible exceptional sets yields an actual promise problem in BB-QMA \ BB-QCMAH.
-
Oracle collapse of the QCMA hierarchy below QMA. Theorem 2 (informal; Theorem 11): there is a classical oracle O: {0,1}* → {0,1} and a unary language L with P^O = QCMA^O = QCMAH^O ⊂ QMA^O and L ∈ QMA^O \ QCMAH^O. The abstract states the stronger chain P^O = BQP^O = QCMA^O = QCMAH^O ⊂ QMA^O with QMA^O ⊄ QCMAH^O.
-
Why prior separations could not do this. The languages constructed in Bostanci–Haferkamp–Nirkhe–Zhandry (BHNZ26) and Bostanci–Huang–Vaikuntanathan (BHV26) both lie in AM, which is contained in the second level QCMA^QCMA of the QCMA hierarchy, so they give no separation from QCMAH. (The paper notes that the Spectral Forrelation problem studied in BHNZ26 is not necessarily in AM; the language used in their oracle separation lies in AM.) The CHS problem, meanwhile, is in BB-coNP ⊆ BB-(NP^NP), since a coNP machine can check that no codeword is accepted for two distinct targets y ≠ y′, and small tweaks fail because a noticeable relative gap in the number of accepted targets N_O(v) can be attacked by Stockmeyer's approximate-counting algorithm, placing the problem in BB-(BPP^NP) ⊆ BB-QCMAH₂.
-
How noise closes the gap. With β = 2^{-⌈√λ⌉}, the noise contributes exponentially many accepted targets for any fixed codeword v in both the planted and noise cases, while the planted codeword-hash relation P_H adds at most one, so the extra pair has only an exponentially small relative effect on N_O(v).
-
Cryptographic primitives under P = QCMA. Theorem 3 (informal; Theorem 19): relative to an oracle with P^O = QCMA^O = QCMAH^O, there exist pseudorandom states with classical keys secure for any polynomial number of copies; copy-protected PKE with quantum decryption keys and classical public keys and ciphertexts; copy-protected PRF with quantum secret keys, pseudorandom against quantum evaluation queries; and signature schemes with quantum signing keys and either classical verification keys and quantum signatures or quantum verification keys and classical signatures. The abstract additionally lists PRU with quantum secret keys and collusion-resistant PKQM with classical verification keys.
-
The PKE construction is stronger than prior work. Unlike Kretschmer–Qian–Tal (KQT24), the PKE construction here also satisfies copy-protection.
-
Corollaries via known black-box constructions. Relative to the same oracle, the paper obtains: collusion-resistant PKQM with classical verification keys (via AC13); bounded-collusion-resistant copy-protected PKE and PRF (via CGK+26); pseudorandom unitaries with a quantum key (via MH25); (inefficient-verifier) one-way puzzles (via KT24); one-way state generators with a classical key (via MY22); and a signature scheme with quantum verification keys plus classical signing keys and signatures, secure against a bounded number of signing queries (via MY24). The paper points to the Microcrypt Zoo for further implications.
-
No quantum computational advantage is present. When P = QCMA, any problem solvable efficiently by a quantum computer is solvable efficiently classically, and any efficient quantum computational (even interactive) process holding no quantum memory can be efficiently simulated classically — so the cryptography here comes from quantum state advantage, not computational advantage. The paper notes a caveat that some efficient quantum sampling processes can be inefficiently distinguished.
-
Contrast with earlier MicroCrypt results. The results of KQST23 and KQT24 necessarily have quantum computational advantage: existence of quantum-computable one-way functions implies BQP ≠ QCMA, and since they also have P = NP, their oracle world has P ≠ BQP. The present work removes that requirement.
-
Not reported: The provided text contains no experimental data, no dataset sizes, no benchmarks, and no empirical measurements of any kind. The only numerical parameters are the oracle-distribution constants (λ^{-4}, β = 2^{-⌈√λ⌉}, δ = 2^{-⌈λ/12⌉}, t_inc(λ, c(λ)) = ⌈2(c(λ) + 8λ²)/√λ⌉ with failure probability 2^{-8λ²}, and a simulation error bound of 1/100).
Methodology in Plain English
The argument proceeds in three stages.
Stage 1 — Make quantum verifiers look classical. A QCMA verifier is a quantum algorithm that gets a classical witness string. Quantum queries are hard to reason about with classical combinatorial tools, so the author shows that, for most oracles drawn from either the planted or the noise distribution, such a verifier can be simulated to within 1/100 error by a simulator that makes only deterministic classical queries and then does randomized computation without further oracle access. This works simultaneously for every input and every witness, and even when the verifier's description depends on some suffix predicates H_i — a generality needed later for repeated depth reduction. The key ingredient is contractive simultaneous incompressibility (imported from the earlier CHS paper): a short classical witness, even chosen by an all-seeing sender and decoded by an all-seeing receiver sharing randomness, cannot be used to name many distinct elements of the oracle's 1-set.
Stage 2 — Eliminate the witness with a switching lemma. Because the simulator's queries are deterministic, classical, and polynomially many, the event "there exists an accepting witness" can be written as a small-width DNF over the oracle's bits. The author notes that even a single quantum query can require exponential-width DNF, which is exactly why Stage 1 was necessary. A switching lemma (Hås86, Kel21) then removes the existential quantifier, morally converting a BB-QCMA machine into a BB-P machine — with the caveat that the resulting machine depends on some sections of the oracle.
Stage 3 — Peel off one level at a time. Replacing the deepest BB-QCMA machine with a witness-less algorithm drops the hierarchy depth by one. Because each BB-QCMAH machine has only a constant number of levels, iterating the simulation-plus-switching step (handling the new oracle dependence each time) collapses the whole hierarchy to the base case, proving the separation.
For the cryptography, the paper introduces a function encoding, a PKE construction, and a collapse oracle. The proof overview first assumes the required quantum states are supplied, then explains how to prepare them using classical oracles. A separate short argument (given in Appendix J) converts the query-complexity result into the oracle separation of Theorem 11, though the cryptography theorem subsumes that separation (with small caveats) and yields the stronger promise-class statement.
Why This Matters
Impact on research. The paper closes a gap that survived the two recent breakthrough classical-oracle separations of QMA from QCMA. It shows that the separation is not an artifact of the second level of the hierarchy: QMA sits strictly above the entire QCMA hierarchy relative to a classical oracle, with all of P, BQP, QCMA, and QCMAH collapsed to the same class. It also shows that "quantum state advantage" can exist with no quantum computational advantage at all, which the earlier MicroCrypt results (KQST23, KQT24) could not achieve. The author frames CHN as a quantum-state analogue of Forrelation, which played the same role for quantum computational advantage in Raz–Tal (RT22) and Aaronson–Ingram–Kretschmer (AIK22). It also answers the open question of Kretschmer, Qian, and Tal (STOC 2025).
Potential real-world applications (long-term, as suggested by the primitives constructed):
- Quantum money with classical verification keys and collusion resistance, which could support unforgeable tokens verified by ordinary classical infrastructure.
- Copy-protected public-key encryption with classical public keys and ciphertexts, relevant to protecting quantum software and quantum-produced content.
- Signature schemes with quantum signing keys and classical verification, relevant to long-lived signing authority.
- Pseudorandom states with classical keys, a basic building block for quantum-secure symmetric cryptography.
Industry relevance. The paper is a strong theoretical caution: the security of quantum-era cryptography need not be underwritten by a computational speedup. Vendors and standards bodies that tie "quantum-safe" claims to assumptions like quantum-computable one-way functions or BQP ≠ QCMA should note that the separation here holds precisely in a world where those assumptions fail. The constructions are oracle-relative, not deployable schemes, so the relevance is to assumption selection and cryptographic design philosophy rather than to immediate implementation.
Future Directions
- De-relativize the separation. Everything here is relative to a classical oracle. Whether QMA ⊆ QCMAH, or QMA ⊄ QCMA when P = QCMA, in the unrelativized world remains open; the paper's oracle and query-complexity results are evidence, not proof.
- Remove the copy-protection and structural caveats. The paper explicitly notes that the cryptography theorem subsumes the oracle separation theorem only "with small caveats," leaving room to tighten the relationship between the two results. The author also states that Section 2.7 discusses future directions, but that section's content is not included in the provided text.
- Extend beyond constant-depth hierarchies and toward broader classes. The depth-reduction argument handles constant levels d. Whether the techniques reach further classes — or whether CHN can be adapted to separate QMA from larger classical-witness classes — is not settled here.
- Relate to fully black-box separations. The paper cites Gulati, Khurana, and Tomer (GKT26), who ruled out fully black-box constructions of quantum-computable one-way functions from PRUs, but who do not show PRUs can exist without quantum-computable one-way functions or when P = QCMA. The paper points to BBF13 and GKT26 for the distinction between fully black-box separations and oracle separations, which is the natural next frontier.
Target Audience
Quantum complexity theorists and quantum cryptographers working on oracle separations, the QMA/QCMA question, and MicroCrypt. It is also relevant to researchers tracking the polynomial-hierarchy analogue in the quantum setting and to cryptographers who want to understand which assumptions genuinely underlie quantum-era security. Graduate students with background in quantum complexity and black-box cryptography will find the technical overview (Section 2) the most accessible entry point; the paper is not suitable for beginners. The author notes the work is in submission at STOC'27, with the full manuscript publicly posted on the conference website since November 3rd, 2026.
Authors’ abstract
Remark: This work is in submission at STOC'27 and thus the full manuscript has been publicly posted on the conference website since November 3rd, 2026. Inspired by the Codeword-Hash Structure problem recently introduced by Cakan (arXiV, 2026) to separate $\mathsf{QMA}$ from $\mathsf{QCIP}$, we introduce a new problem called Codeword-Hash pairs in Noise ($\mathsf{CHN}$) and prove that, in the query complexity model, it is in $\mathsf{QMA}$ but hard for the $\mathsf{QCMA}$…
The full abstract on arXiv