Separating ClonableQMA and QCMA Relative to a Classical Oracle

Abstract

Since the introduction of the complexity class QMA as a quantum-verifier analogue of NP (Kitaev, 1997), many have wondered whether quantum proofs are necessary or classical proofs suffice - that is, whether QMA = QCMA or QCMA != QMA (Aharonov and Naveh, 2002; Aaronson and Kuperberg, CCC '07). This longstanding question was recently answered by works of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC '26) and Bostanci, Huang, and Vaikuntanathan (FOCS '26), which showed that quantum proofs are more powerful than classical ones in the classical-oracle setting. However, it remains unclear what exactly makes quantum proofs more powerful than classical ones. In the information-theoretic setting, a family of quantum states is not classicalizable if and only if it is unclonable. Indeed, these recent works also explicitly highlight the unclonability of their quantum proofs as a key mechanism behind their separations, and their arguments crucially rely on this property. This raises the question of whether unclonability is necessary for quantum proofs to be more powerful than classical ones. In this work, we show that even clonable quantum proofs can be more powerful than classical ones relative to a classical oracle by constructing a classical oracle O such that QCMA^O != ClonableQMA^O. This resolves the open question of Nehoran and Zhandry (ITCS '24), who established the analogous separation relative to a quantum oracle. We also show a classical-oracle separation between BQP/clonableqpoly and BQP/poly, and give applications of our results to quantum cryptography.

A classical oracle separation between QMA and QMA(2)
Sabee Grewal, Saachi Mutreja, Kabir Tomer
arXiv5 Oct 2026PreprintCC BY-NC-SA 4.0Full textQuantum physics & quantum informationarXiv
A Quantum/Classical Example Oracle Separation for Making Things Up
Kenny Chen
arXiv22 Sep 2026PreprintCC BY 4.0Full textStatistics Quantum physics & quantum informationarXiv
Practical Considerations for Processing Massive Classical Data via Quantum Oracle Sketching
Stefano Markidis
arXiv11 Sep 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Distinguishing and separating in-plane hall responses
Soumya Sankar, Xingkai Cheng, Junwei Liu +1
Physical Review Research6 Nov 2026Peer-reviewedCC BY 4.0Atomic, molecular & optical physicsCrossref
Separating energy scales in hadron scattering
S. M. Troshin, N. E. Tyurin
arXiv6 Oct 2026PreprintCC BY 4.0Full textHigh-energy & particle physicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{cakan2026separating,
  title = {{Separating ClonableQMA and QCMA Relative to a Classical Oracle}},
  author = {Alper Cakan and Kai-Min Chung and Wei-Hsiang Hung and Tzu-Yi Yang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.06740},
  eprint = {2610.06740},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.06740},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Separating ClonableQMA and QCMA Relative to a Classical Oracle
AU  - Alper Cakan
AU  - Kai-Min Chung
AU  - Wei-Hsiang Hung
AU  - Tzu-Yi Yang
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2610.06740
UR  - https://arxiv.org/abs/2610.06740
AB  - Since the introduction of the complexity class QMA as a quantum-verifier analogue of NP (Kitaev, 1997), many have wondered whether quantum proofs are necessary or classical proofs suffice - that is, whether QMA = QCMA or QCMA != QMA (Aharonov and Naveh, 2002; Aaronson and Kuperberg, CCC '07). This longstanding question was recently answered by works of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC '26) and Bostanci, Huang, and Vaikuntanathan (FOCS '26), which showed that quantum proofs are more powerful than classical ones in the classical-oracle setting. However, it remains unclear what exactly makes quantum proofs more powerful than classical ones. In the information-theoretic setting, a family of quantum states is not classicalizable if and only if it is unclonable. Indeed, these recent works also explicitly highlight the unclonability of their quantum proofs as a key mechanism behind their separations, and their arguments crucially rely on this property. This raises the question of whether unclonability is necessary for quantum proofs to be more powerful than classical ones. In this work, we show that even clonable quantum proofs can be more powerful than classical ones relative to a classical oracle by constructing a classical oracle O such that QCMA^O != ClonableQMA^O. This resolves the open question of Nehoran and Zhandry (ITCS '24), who established the analogous separation relative to a quantum oracle. We also show a classical-oracle separation between BQP/clonableqpoly and BQP/poly, and give applications of our results to quantum cryptography.
ER  -

Abstract

Related

Cite