Paper 2026/2958

Classical Oracle Separation of QMA from the QCMA Hierarchy and Quantum Cryptography Even When P = QCMA

Alper Cakan, Carnegie Mellon University
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.