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:2303.04298 · Leibniz international proceedings in informatics

Classical vs Quantum Advice and Proofs Under Classically-Accessible Oracle

Xingjian Li, Liu, Qipeng, Angelos Pelecanos, Takashi Yamakawa

Published Mar 8, 2023• 16 citations
arXivHTMLPDF

Abstract

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.

DOI
10.4230/lipics.itcs.2024.72

Related papers

Separating ClonableQMA and QCMA Relative to a Classical Oracle

Alper Cakan, Kai-Min Chung, Wei-Hsiang Hung +1 more

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.

cs.CCCross-listedarXiv:2610.06740•Oct 6, 2026•0 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 $Ω(\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

Oracle Separation of QMA and QCMA with Bounded Adaptivity

Shalev Ben-David, Srijita Kundu

We give an oracle separation between QMA and QCMA for quantum algorithms that have bounded adaptivity in their oracle queries; that is, the number of rounds of oracle calls is small, though each round may involve polynomially many queries in parallel. Our oracle construction is a simplified version of the construction used recently by Li, Liu, Pelecanos, and Yamakawa (2023), who showed an oracle separation between QMA and QCMA when the quantum algorithms are only allowed to access the oracle classically. To prove our results, we introduce a property of relations called \emph{slipperiness}, which may be useful for getting a fully general classical oracle separation between QMA and QCMA.

arXiv:2402.00298•Leibniz international proceedings in informatics•Jan 1, 2024•8 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

A Relativizing MIP for BQP

Scott Aaronson, Anand Natarajan, Avishay Tal +1 more

Complexity class containments involving interactive proof classes are famously nonrelativizing: although $\mathsf{IP} = \mathsf{PSPACE}$, Fortnow and Sipser showed that that there exists an oracle relative to which $\mathsf{coNP} \not\subseteq \mathsf{IP}$. In contrast, the question of whether the containment $\mathsf{BQP} \subseteq \mathsf{IP}$ is relativizing remains wide open. In this work we make progress towards resolving this question by showing that the containment $\mathsf{BQP} \subseteq \mathsf{MIP}$ holds with respect to any classical oracle. We obtain this result by constructing, for any classical oracle $O$, a $\mathsf{PCP}$ proof system for $\mathsf{BQP}^{O}$ where the verifier makes polynomially many classical queries to an exponentially-long proof, and to the oracle $O$. Our construction is inspired by the state synthesis algorithm of Grover and Rudolph, and serves as a complement to the "exponential PCP" constructed by Aharonov, Arad, and Vidick, which achieves similar parameters but which is based on different ideas and does not relativize. We propose relativization as a proxy for prover efficiency, and hope that progress towards an $\mathsf{IP}$ for $\mathsf{BQP}$ in the oracle world will lead to a non-cryptographic interactive protocol for proving any quantum computation to a classical skeptic in the unrelativized world, which is a longstanding open problem in quantum complexity theory.

quant-pharXiv:2604.11952•Apr 15, 2026•2 citations
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.
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.
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 Ω(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.
We give an oracle separation between QMA and QCMA for quantum algorithms that have bounded adaptivity in their oracle queries; that is, the number of rounds of oracle calls is small, though each round may involve polynomially many queries in parallel. Our oracle construction is a simplified version of the construction used recently by Li, Liu, Pelecanos, and Yamakawa (2023), who showed an oracle separation between QMA and QCMA when the quantum algorithms are only allowed to access the oracle classically. To prove our results, we introduce a property of relations called \emph{slipperiness}, which may be useful for getting a fully general 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 Ω 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.
Complexity class containments involving interactive proof classes are famously nonrelativizing: although IP=PSPACE\mathsf{IP} = \mathsf{PSPACE}IP=PSPACE, Fortnow and Sipser showed that that there exists an oracle relative to which coNP⊈IP\mathsf{coNP} \not\subseteq \mathsf{IP}coNP⊆IP. In contrast, the question of whether the containment BQP⊆IP\mathsf{BQP} \subseteq \mathsf{IP}BQP⊆IP is relativizing remains wide open. In this work we make progress towards resolving this question by showing that the containment BQP⊆MIP\mathsf{BQP} \subseteq \mathsf{MIP}BQP⊆MIP holds with respect to any classical oracle. We obtain this result by constructing, for any classical oracle OOO, a PCP\mathsf{PCP}PCP proof system for BQPO\mathsf{BQP}^{O}BQPO where the verifier makes polynomially many classical queries to an exponentially-long proof, and to the oracle OOO. Our construction is inspired by the state synthesis algorithm of Grover and Rudolph, and serves as a complement to the "exponential PCP" constructed by Aharonov, Arad, and Vidick, which achieves similar parameters but which is based on different ideas and does not relativize. We propose relativization as a proxy for prover efficiency, and hope that progress towards an IP\mathsf{IP}IP for BQP\mathsf{BQP}BQP in the oracle world will lead to a non-cryptographic interactive protocol for proving any quantum computation to a classical skeptic in the unrelativized world, which is a longstanding open problem in quantum complexity theory.