arXiv:2610.06740
Separating ClonableQMA and QCMA Relative to a Classical Oracle
Alper Cakan, Kai-Min Chung, Wei-Hsiang Hung, Tzu-Yi Yang
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.
AI Summary
The paper asks whether quantum proofs can outperform classical proofs even when the honest quantum witnesses are efficiently clonable. It constructs a classical oracle $O$ such that $\mathrm{ClonableQMA}^O\not\subseteq\mathrm{QCMA}^O$, resolving the classical-oracle version of a previously established quantum-oracle separation. Cloning algorithms have coherent oracle access and reproduce designated honest witnesses with fidelity $1-\operatorname{negl}(\lambda)$; soundness still holds against arbitrary witnesses. The construction combines biased Yamakawa–Zhandry code-intersection states with a “self-encrypted” oracle: a hash value is released only upon supplying a codeword solving a corresponding code-intersection challenge. An honest state solves these challenges coherently, allowing hash values to be extracted and the computation uncomputed with negligible disturbance. Repeating this process prepares a fresh copy of the state. For the classical-witness lower bound, hybrid arguments repeatedly extract distinct valid solutions from verifier queries. Encoding both the coordinate and symbol in each challenge limits oracle simulation to guessing one additional hash bit per extraction. Codeword diversity bounds the probability of guessing $L$ valid solutions without queries by $2^t(1-\lambda^{-4})^{nL/2}$ for $t$ bits of classical side information, with $n\geq\lambda^5$. The same framework separates clonable quantum advice from classical advice relative to a classical oracle and yields quantum fire with strong cloning correctness and noninteractive untelegraphability without pre-shared entanglement. These are relativized results, not unrelativized class separations. Separating QMA from ClonableQMA using a classical oracle remains open. The cryptographic construction does not claim stronger key-fire or interactive-security guarantees and does not survive a collapse of QCMA to BQP.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.