Paper 2026/2958
Classical Oracle Separation of QMA from the QCMA Hierarchy and Quantum Cryptography Even When P = QCMA
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 $\mathcal{O}$ such that $\mathsf{P}^{\mathcal{O}}=\mathsf{BQP}^{\mathcal{O}}=\mathsf{QCMA}^{\mathcal{O}} =\mathsf{QCMAH}^{\mathcal{O}} \subset \mathsf{QMA}^{\mathcal{O}} \text{ but } \mathsf{QMA}^{\mathcal{O}}\not\subseteq\mathsf{QCMAH}^{\mathcal{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 more detail, we show that there exists a classical oracle $\mathcal{O}$ such that $\mathsf{P}^{\mathcal{O}} = \mathsf{BQP}^{\mathcal{O}} =\mathsf{QCMA}^{\mathcal{O}}=\mathsf{QCMAH}^{\mathcal{O}}$ but the following primitives exist relative to $\mathcal{O}$, answering an open question of Kretschmer, Qian, and Tal (STOC 2025). (1) Pseudorandom states (PRS) with classical keys. (2) Pseudorandom functions (PRF) with (copy-protected) quantum secret keys, and thus also pseudorandom unitaries (PRU) with quantum secret keys, (3) Public-key encryption (PKE) with a (copy-protected) quantum decryption key, classical public keys and ciphertexts, (4) Signature schemes with quantum signing keys and either classical verification keys and quantum signatures or quantum verification keys and classical signatures, (5) Collusion-resistant public-key quantum money (PKQM) with classical verification keys.
Note: In submission to STOC'27.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Quantum complexityQuantum cryptographyMicroCrypt
- Contact author(s)
- acakan @ cs cmu edu
- History
- 2026-11-22: approved
- 2026-11-19: received
- See all versions
- Short URL
- https://ia.cr/2026/2958
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2958,
author = {Alper Cakan},
title = {Classical Oracle Separation of {QMA} from the {QCMA} Hierarchy and Quantum Cryptography Even When P = {QCMA}},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2958},
year = {2026},
url = {https://eprint.iacr.org/2026/2958}
}