Quantum proofs outperform classical hierarchies despite equal classical computing power
Classical Oracle Separation of QMA from the QCMA Hierarchy and Quantum Cryptography Even When P = QCMA
Cryptography and Security
Summary
Some problems can be checked easier if you have a quantum proof rather than a classical one, even when classical computers are just as powerful as quantum ones for many tasks. The authors created a new problem that shows quantum proofs have an advantage over any classical proof system no matter how many layers of classical verification you stack. They also demonstrated that certain quantum cryptography methods can exist even if classical and quantum computers are equally powerful. This challenges previous assumptions about how classical and quantum computing relate to one another.
What this means in practice
- •For quantum cryptographers: Develop quantum cryptographic schemes that remain secure even when classical computers match quantum verification power.
- •For quantum algorithm designers: Design verification protocols that utilize quantum proofs to outperform classical proof hierarchies despite similar computational capabilities.
A theory result. No direct application yet.
Authors
Alper Cakan
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}$ hierarchy $\mathsf{QCMAH} = \bigcup_{d\geq1}\mathsf{QCMA}^{\mathsf{QCMA}^{\cdots^{\mathsf{QCMA}}}}$, the classical-witness quantum-verifier analogue of $\mathsf{PH}=\bigcup_{d\ge1}\mathsf{NP}^{\mathsf{NP}^{\cdots^{\mathsf{NP}}}}$. Using this problem, we show that there exists a classical oracle ${O}$ such that $\mathsf{P}^{O}=\mathsf{BQP}^{O}=\mathsf{QCMA}^{O} =\mathsf{QCMAH}^{O} \subset \mathsf{QMA}^{O} \text{ but } \mathsf{QMA}^{O}\not\subseteq\mathsf{QCMAH}^{O},$ thus showing that quantum state or quantum proof advantage could exist even if classical computers can efficiently solve any problem that can be quantumly verified with a classical proof. Further, using our problem, we show that various quantum cryptographic primitives can exist even when $\mathsf{P} = \mathsf{QCMA}$ and thus neither quantum-computable one-way functions nor (verifiable) quantum computational advantage exist. In particular, relative to a classical oracle ${O}$ with $\mathsf{P}^{O}=\mathsf{BQP}^{O}=\mathsf{QCMA}^{O}=\mathsf{QCMAH}^{O}$, there exist pseudorandom states with classical keys and public-key encryption with copy-protected quantum decryption keys and classical public keys and ciphertexts, among other primitives, answering an open question of Kretschmer, Qian, and Tal (STOC 2025).