Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.06740

Separating ClonableQMA and QCMA Relative to a Classical Oracle

Alper Cakan, Kai-Min Chung, Wei-Hsiang Hung, Tzu-Yi Yang

cs.CCquant-phSubmitted Oct 5, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

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.

Little sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Separating QMA from QCIP with a Classical Oracle, or, the Power of Quantum Proofs over Classical Interaction for Quantum Verifiers

Alper Çakan

Whether some problems require quantum proofs has been a central question in quantum complexity (Aharonov and Naveh, 2002; Aaronson and Kuperberg, CCC 2007). Recently, breakthrough work of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC 2026), followed by a simpler separation due to Bostanci, Huang, and Vaikuntanathan (FOCS 2026), established a classical oracle separation between $\mathsf{QMA}$ and $\mathsf{QCMA}$. However, while they are not in $\mathsf{QCMA}$, the problems used in both separations still lie in $\mathsf{AM}$: they admit a two-message public-coin proof system with a classical verifier. In this work, we ask whether some problems truly require quantum proofs. More formally, we consider the complexity class $\mathsf{QCIP}$, introduced by Buhrman, Le Gall, and Weggemans (2024), where an efficient quantum verifier interacts with an unbounded prover over a classical channel for an arbitrary polynomial number of rounds. We construct a classical oracle $\mathcal{O}$ such that $\mathsf{QMA}^{\mathcal{O}}\not\subseteq\mathsf{QCIP}^{\mathcal{O}}$, thus showing that some languages indeed require quantum proofs, with no classical replacements. Since $\mathsf{QCMA}=\mathsf{QCIP}[1]$, this strengthens the earlier $\mathsf{QMA}$--$\mathsf{QCMA}$ separations, which now follow as a special case of our result. As a technical contribution, we extend to the complexity theory setting the techniques developed by Cakan, Goyal, and Shmueli (CRYPTO 2026) in the context of cryptography for analyzing classically interacting quantum machines. We believe this may be of independent interest.

arXiv:2610.03648•Oct 2, 2026•1 citation

Classical vs Quantum Advice and Proofs Under Classically-Accessible Oracle

Xingjian Li, Liu, Qipeng, Angelos Pelecanos +1 more

It is a long-standing open question to construct a classical oracle relative to which BQP/qpoly $\neq$ BQP/poly or QMA $\neq$ QCMA. In this paper, we construct classically-accessible classical oracles relative to which BQP/qpoly $\neq$ BQP/poly and QMA $\neq$ QCMA. Here, classically-accessible classical oracles are oracles that can be accessed only classically even for quantum algorithms. Based on a similar technique, we also show an alternative proof for the separation of QMA and QCMA relative to a distributional quantumly-accessible classical oracle, which was recently shown by Natarajan and Nirkhe.

arXiv:2303.04298•Leibniz international proceedings in informatics•Mar 8, 2023•16 citations

Separating Quantum and Classical Advice with Good Codes

John Bostanci, Andrew Huang, Vinod Vaikuntanathan

We show an unconditional classical oracle separation between the class of languages that can be verified using a quantum proof ($\mathsf{QMA}$) and the class of languages that can be verified with a classical proof ($\mathsf{QCMA}$). Compared to the recent work of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC 2026), our proof is conceptually and technically simpler, and readily extends to other oracle separations. In particular, our techniques yield the first unconditional classical oracle separation between the class of languages that can be decided with quantum advice ($\mathsf{BQP}/\mathsf{qpoly}$) and the class of languages that can be decided with classical advice ($\mathsf{BQP}/\mathsf{poly}$), improving on the quantum oracle separation of Aaronson and Kuperberg (CCC 2007) and the classically-accessible classical oracle separation of Li, Liu, Pelecanos and Yamakawa (ITCS 2024). Our oracles are based on the code intersection problem introduced by Yamakawa and Zhandry (FOCS 2022), combined with codes that have extremely good list-recovery properties.

quant-pharXiv:2602.09385•Feb 11, 2026•10 citations

Quantum versus Classical Proofs and Advice

Scott Aaronson, Greg Kuperberg

This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA = QCMA.We prove three results about this question.First, we give a "quantum oracle separation" between QMA and QCMA.More concretely, we show that any quantum algorithm needs Ω 2 n m+1 queries to find an n-qubit "marked state" |ψ , even if given an m-bit classical description of |ψ together with a quantum black box that recognizes |ψ .Second, we give an explicit QCMA protocol that nearly achieves this lower bound.Third, we show that, in the one previously-known case where quantum proofs seemed to provide an exponential advantage, classical proofs are basically just as powerful.In particular, Watrous gave a QMA protocol for verifying non-membership in finite groups.Under plausible group-theoretic assumptions, we give a QCMA protocol for the same problem.Even with no assumptions, our protocol makes only polynomially many queries to the group oracle.We end with some conjectures about quantum versus classical oracles, and about the possibility of a classical oracle separation between QMA and QCMA.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2007•53 citations

Quantum Versus Classical Proofs and Advice

Scott Aaronson, Greg Kuperberg

This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA=QCMA. We prove three results about this question. First, we give a "quantum oracle separation" between QMA and QCMA. More concretely, we show that any quantum algorithm needs $Ω(\sqrt{2^n/(m+1)})$ queries to find an $n$-qubit "marked state" $\lvertψ\rangle$, even if given an $m$-bit classical description of $\lvertψ\rangle$ together with a quantum black box that recognizes $\lvertψ\rangle$. Second, we give an explicit QCMA protocol that nearly achieves this lower bound. Third, we show that, in the one previously-known case where quantum proofs seemed to provide an exponential advantage, classical proofs are basically just as powerful. In particular, Watrous gave a QMA protocol for verifying non-membership in finite groups. Under plausible group-theoretic assumptions, we give a QCMA protocol for the same problem. Even with no assumptions, our protocol makes only polynomially many queries to the group oracle. We end with some conjectures about quantum versus classical oracles, and about the possibility of a classical oracle separation between QMA and QCMA.

arXiv:quant-ph/0604056•Electronic colloquium on computational complexity•Apr 10, 2006•29 citations

A Computational Separation Between Quantum No-Cloning and No-Telegraphing

Barak Nehoran, Mark Zhandry

Two of the fundamental no-go theorems of quantum information are the no-cloning theorem (that it is impossible to make copies of general quantum states) and the no-teleportation theorem (the prohibition on telegraphing, or sending quantum states over classical channels without pre-shared entanglement). They are known to be equivalent, in the sense that a collection of quantum states is telegraphable if and only if it is clonable. Our main result suggests that this is not the case when computational efficiency is considered. We give a collection of quantum states and quantum oracles relative to which these states are efficiently clonable but not efficiently telegraphable. Given that the opposite scenario is impossible (states that can be telegraphed can always trivially be cloned), this gives the most complete quantum oracle separation possible between these two important no-go properties. We additionally study the complexity class clonableQMA, a subset of QMA whose witnesses are efficiently clonable. As a consequence of our main result, we give a quantum oracle separation between clonableQMA and the class QCMA, whose witnesses are restricted to classical strings. We also propose a candidate oracle-free promise problem separating these classes. We finally demonstrate an application of clonable-but-not-telegraphable states to cryptography, by showing how such states can be used to protect against key exfiltration.

arXiv:2302.01858•Leibniz international proceedings in informatics•Feb 3, 2023•17 citations
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.
The paper asks whether quantum proofs can outperform classical proofs even when the honest quantum witnesses are efficiently clonable. It constructs a classical oracle OOO such that ClonableQMAO⊈QCMAO\mathrm{ClonableQMA}^O\not\subseteq\mathrm{QCMA}^OClonableQMAO⊆QCMAO, 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−negl⁡(λ)1-\operatorname{negl}(\lambda)1−negl(λ); 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 LLL valid solutions without queries by 2t(1−λ−4)nL/22^t(1-\lambda^{-4})^{nL/2}2t(1−λ−4)nL/2 for ttt bits of classical side information, with n≥λ5n\geq\lambda^5n≥λ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.
Whether some problems require quantum proofs has been a central question in quantum complexity (Aharonov and Naveh, 2002; Aaronson and Kuperberg, CCC 2007). Recently, breakthrough work of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC 2026), followed by a simpler separation due to Bostanci, Huang, and Vaikuntanathan (FOCS 2026), established a classical oracle separation between QMA\mathsf{QMA}QMA and QCMA\mathsf{QCMA}QCMA. However, while they are not in QCMA\mathsf{QCMA}QCMA, the problems used in both separations still lie in AM\mathsf{AM}AM: they admit a two-message public-coin proof system with a classical verifier. In this work, we ask whether some problems truly require quantum proofs. More formally, we consider the complexity class QCIP\mathsf{QCIP}QCIP, introduced by Buhrman, Le Gall, and Weggemans (2024), where an efficient quantum verifier interacts with an unbounded prover over a classical channel for an arbitrary polynomial number of rounds. We construct a classical oracle O\mathcal{O}O such that QMAO⊈QCIPO\mathsf{QMA}^{\mathcal{O}}\not\subseteq\mathsf{QCIP}^{\mathcal{O}}QMAO⊆QCIPO, thus showing that some languages indeed require quantum proofs, with no classical replacements. Since QCMA=QCIP[1]\mathsf{QCMA}=\mathsf{QCIP}[1]QCMA=QCIP[1], this strengthens the earlier QMA\mathsf{QMA}QMA--QCMA\mathsf{QCMA}QCMA separations, which now follow as a special case of our result. As a technical contribution, we extend to the complexity theory setting the techniques developed by Cakan, Goyal, and Shmueli (CRYPTO 2026) in the context of cryptography for analyzing classically interacting quantum machines. We believe this may be of independent interest.
It is a long-standing open question to construct a classical oracle relative to which BQP/qpoly ≠\neq= BQP/poly or QMA ≠\neq= QCMA. In this paper, we construct classically-accessible classical oracles relative to which BQP/qpoly ≠\neq= BQP/poly and QMA ≠\neq= QCMA. Here, classically-accessible classical oracles are oracles that can be accessed only classically even for quantum algorithms. Based on a similar technique, we also show an alternative proof for the separation of QMA and QCMA relative to a distributional quantumly-accessible classical oracle, which was recently shown by Natarajan and Nirkhe.
We show an unconditional classical oracle separation between the class of languages that can be verified using a quantum proof (QMA\mathsf{QMA}QMA) and the class of languages that can be verified with a classical proof (QCMA\mathsf{QCMA}QCMA). Compared to the recent work of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC 2026), our proof is conceptually and technically simpler, and readily extends to other oracle separations. In particular, our techniques yield the first unconditional classical oracle separation between the class of languages that can be decided with quantum advice (BQP/qpoly\mathsf{BQP}/\mathsf{qpoly}BQP/qpoly) and the class of languages that can be decided with classical advice (BQP/poly\mathsf{BQP}/\mathsf{poly}BQP/poly), improving on the quantum oracle separation of Aaronson and Kuperberg (CCC 2007) and the classically-accessible classical oracle separation of Li, Liu, Pelecanos and Yamakawa (ITCS 2024). Our oracles are based on the code intersection problem introduced by Yamakawa and Zhandry (FOCS 2022), combined with codes that have extremely good list-recovery properties.
This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA = QCMA.We prove three results about this question.First, we give a "quantum oracle separation" between QMA and QCMA.More concretely, we show that any quantum algorithm needs Ω 2 n m+1 queries to find an n-qubit "marked state" |ψ , even if given an m-bit classical description of |ψ together with a quantum black box that recognizes |ψ .Second, we give an explicit QCMA protocol that nearly achieves this lower bound.Third, we show that, in the one previously-known case where quantum proofs seemed to provide an exponential advantage, classical proofs are basically just as powerful.In particular, Watrous gave a QMA protocol for verifying non-membership in finite groups.Under plausible group-theoretic assumptions, we give a QCMA protocol for the same problem.Even with no assumptions, our protocol makes only polynomially many queries to the group oracle.We end with some conjectures about quantum versus classical oracles, and about the possibility of a classical oracle separation between QMA and QCMA.
This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA=QCMA. We prove three results about this question. First, we give a "quantum oracle separation" between QMA and QCMA. More concretely, we show that any quantum algorithm needs Ω(2n/(m+1))Ω(\sqrt{2^n/(m+1)})Ω(2n/(m+1)​) queries to find an nnn-qubit "marked state" ∣ψ⟩\lvertψ\rangle∣ψ⟩, even if given an mmm-bit classical description of ∣ψ⟩\lvertψ\rangle∣ψ⟩ together with a quantum black box that recognizes ∣ψ⟩\lvertψ\rangle∣ψ⟩. Second, we give an explicit QCMA protocol that nearly achieves this lower bound. Third, we show that, in the one previously-known case where quantum proofs seemed to provide an exponential advantage, classical proofs are basically just as powerful. In particular, Watrous gave a QMA protocol for verifying non-membership in finite groups. Under plausible group-theoretic assumptions, we give a QCMA protocol for the same problem. Even with no assumptions, our protocol makes only polynomially many queries to the group oracle. We end with some conjectures about quantum versus classical oracles, and about the possibility of a classical oracle separation between QMA and QCMA.
Two of the fundamental no-go theorems of quantum information are the no-cloning theorem (that it is impossible to make copies of general quantum states) and the no-teleportation theorem (the prohibition on telegraphing, or sending quantum states over classical channels without pre-shared entanglement). They are known to be equivalent, in the sense that a collection of quantum states is telegraphable if and only if it is clonable. Our main result suggests that this is not the case when computational efficiency is considered. We give a collection of quantum states and quantum oracles relative to which these states are efficiently clonable but not efficiently telegraphable. Given that the opposite scenario is impossible (states that can be telegraphed can always trivially be cloned), this gives the most complete quantum oracle separation possible between these two important no-go properties. We additionally study the complexity class clonableQMA, a subset of QMA whose witnesses are efficiently clonable. As a consequence of our main result, we give a quantum oracle separation between clonableQMA and the class QCMA, whose witnesses are restricted to classical strings. We also propose a candidate oracle-free promise problem separating these classes. We finally demonstrate an application of clonable-but-not-telegraphable states to cryptography, by showing how such states can be used to protect against key exfiltration.