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:2602.09385

Separating Quantum and Classical Advice with Good Codes

John Bostanci, Andrew Huang, Vinod Vaikuntanathan

quant-phcs.CCSubmitted Feb 10, 2026• Announced Feb 11, 2026• 10 citations• Revised Apr 12, 2026 (v2)
v1 · Feb 10, 2026v2 · Apr 12, 2026
arXivHTMLPDF

Abstract

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.

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 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

Are uncloneable proof and advice states strictly necessary?

Chatterjee, Rohit, Srijita Kundu, Supartha Podder

Yes, we show that they are. We initiate the study of languages that necessarily need uncloneable quantum proofs and advice. We define strictly uncloneable versions of the classes QMA, BQP/qpoly and FEQP/qpoly (which is the class of relational problems solvable exactly with polynomial-sized quantum advice). Strictly uncloneable QMA is defined to be the class of languages in QMA that only have uncloneable proofs, i.e., given any family of candidate proof states, a polynomial-time cloning algorithm cannot act on it to produce states that are jointly usable by $k$ separate polynomial-time verifiers, for arbitrary polynomial $k$. This is a stronger notion of uncloneable proofs and advice than those considered in previous works, which only required the existence of a single family of proof or advice states that are uncloneable. We show that in the quantum oracle model, there exist languages in strictly uncloneable QMA and strictly uncloneable BQP/qpoly. The language in strictly uncloneable QMA also gives a quantum oracle separation between QMA and the class cloneableQMA introduced by Nehoran and Zhandry (2024). We also show without using any oracles that the language, used by Aaronson, Buhrman and Kretschmer (2024) to separate FEQP/qpoly and FBQP/poly, is in strictly uncloneable FEQP/qpoly.

arXiv:2410.11827•Oct 15, 2024•3 citations

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

Non-Standard Oracles for Bounded-Error Complexity Classes

Avantika Agarwal, Srijita Kundu

In recent years, the quantum oracle model introduced by Aaronson and Kuperberg (2007) has found a lot of use in showing oracle separations between complexity classes and cryptographic primitives. It is generally assumed that proof techniques that do not relativize with respect to quantum oracles will also not relativize with respect to classical oracles. Aaronson (2009) showed that this is not the case by showing a complexity class containment that relativizes with respect to classical oracles but not with quantum oracles. However, their result only works for zero-error quantum complexity classes and they leave open the problem for bounded-error complexity classes. We show that there is a quantum oracle problem that is contained in the class QMA, but not in a class we call polyQCPH. However, with respect to classical oracles, QMA is contained in polyQCPH, because polyQCPH is equal to PSPACE with respect to classical oracles. Our result works for polyQCPH, which is a bounded-error complexity class, thus it resolves the open problem from Aaronson (2009). We also show that the same separation holds relative to a distributional oracle, which is a model introduced by Natarajan and Nirkhe (2024). We believe our findings show the need for some caution when using these non-standard oracle models, particularly when showing separations between quantum and classical resources.

arXiv:2504.19470•Apr 28, 2025•7 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
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.
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.
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.
Yes, we show that they are. We initiate the study of languages that necessarily need uncloneable quantum proofs and advice. We define strictly uncloneable versions of the classes QMA, BQP/qpoly and FEQP/qpoly (which is the class of relational problems solvable exactly with polynomial-sized quantum advice). Strictly uncloneable QMA is defined to be the class of languages in QMA that only have uncloneable proofs, i.e., given any family of candidate proof states, a polynomial-time cloning algorithm cannot act on it to produce states that are jointly usable by kkk separate polynomial-time verifiers, for arbitrary polynomial kkk. This is a stronger notion of uncloneable proofs and advice than those considered in previous works, which only required the existence of a single family of proof or advice states that are uncloneable. We show that in the quantum oracle model, there exist languages in strictly uncloneable QMA and strictly uncloneable BQP/qpoly. The language in strictly uncloneable QMA also gives a quantum oracle separation between QMA and the class cloneableQMA introduced by Nehoran and Zhandry (2024). We also show without using any oracles that the language, used by Aaronson, Buhrman and Kretschmer (2024) to separate FEQP/qpoly and FBQP/poly, is in strictly uncloneable FEQP/qpoly.
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.
In recent years, the quantum oracle model introduced by Aaronson and Kuperberg (2007) has found a lot of use in showing oracle separations between complexity classes and cryptographic primitives. It is generally assumed that proof techniques that do not relativize with respect to quantum oracles will also not relativize with respect to classical oracles. Aaronson (2009) showed that this is not the case by showing a complexity class containment that relativizes with respect to classical oracles but not with quantum oracles. However, their result only works for zero-error quantum complexity classes and they leave open the problem for bounded-error complexity classes. We show that there is a quantum oracle problem that is contained in the class QMA, but not in a class we call polyQCPH. However, with respect to classical oracles, QMA is contained in polyQCPH, because polyQCPH is equal to PSPACE with respect to classical oracles. Our result works for polyQCPH, which is a bounded-error complexity class, thus it resolves the open problem from Aaronson (2009). We also show that the same separation holds relative to a distributional oracle, which is a model introduced by Natarajan and Nirkhe (2024). We believe our findings show the need for some caution when using these non-standard oracle models, particularly when showing separations between quantum and classical resources.
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.