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

A classical oracle separation between QMA and QMA(2)

Sabee Grewal, Saachi Mutreja, Kabir Tomer

quant-phSubmitted Oct 5, 2026• Announced Oct 6, 2026• 2 citations
arXivHTMLPDF

Abstract

We exhibit a classical oracle relative to which QMA \neq QMA(2). The separation is based on a separable Hamiltonian problem defined by signed edge constraints on a graph. The YES instances have zero-energy product states, while the NO instances, constructed using the antisymmetric subspace, have entangled zero-energy states but no low-energy product states. For the QMA lower bound, we use compressed-oracle techniques to track the information learned by a quantum computation making few queries to a YES instance. The key step is to map the resulting superpositions of partial oracle records to the NO family without significantly changing the verifier's behavior.

AI Summary

Does requiring two quantum proofs to be unentangled increase verification power even relative to a classical oracle? This paper establishes a classical oracle $A$ for which $\mathrm{QMA}^A\neq\mathrm{QMA}(2)^A$, strengthening the previously known quantum-oracle separation. It does not establish an unrelativized separation. The separating problem minimizes a signed-graph Hamiltonian’s energy over product states across a prescribed bipartition. The graph is accessed through forward and inverse adjacency queries returning neighbors and edge signs. Hard YES instances have zero-energy product states. Hard NO instances also have entangled zero-energy states, but every product state has energy at least $1/4$, with probability $1-\exp(-\Omega(N))$, where $N=2^k$. The promise problem uses thresholds $3/16$ and $1/4$ and admits a one-query $\mathrm{QMA}(2)$ test with a constant completeness–soundness gap, followed by standard amplification. The NO construction groups vertices using hidden pair-labels and chooses signed constraints whose ideal satisfying subspace is locally isometric to the four-register antisymmetric subspace. Its maximum product-state squared overlap is at most $1/3$; concentration bounds establish the energy gap. The QMA lower bound combines compressed permutation oracles and Fourier-encoded signs with a coherent transfer of short YES-oracle records to NO parameters. An acceptance-operator powering argument handles arbitrary oracle-dependent quantum witnesses, ruling out polynomial witness length and query complexity. The separating problem is nevertheless in $\mathrm{SBQP}$, so this construction cannot establish a classical-oracle separation of $\mathrm{QMA}(2)$ from $\mathrm{SBQP}$. Whether such a separation exists remains open.

Likely largely AI-generatedAI use disclosed
The original proof of this result was obtained through approximately 10 rounds of interaction with ChatGPT 6 Astra in Work mode.

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

Related papers

A quantum oracle separation between QMA(2) and QMA

John Bostanci, Sabee Grewal, Jonas Haferkamp +4 more

We find a quantum oracle relative to which $\mathsf{QMA} \neq \mathsf{QMA}(2)$. As a consequence, we resolve the no-disentanglers conjecture of Watrous: for every $ε+δ<1$, any $(ε,δ)$-disentangler requires input size exponential in the number of output qubits. Our proof combines the unitarily invariant polynomial method of She and Yuen (ITCS '23) with a new construction based on the symmetric and antisymmetric subspace projectors, reducing the $\mathsf{QMA}$ lower bound to the approximate degree of $\mathrm{OR}$.

quant-pharXiv:2609.02865•Sep 3, 2026•4 citations

A distribution testing oracle separation between QMA and QCMA

Anand Natarajan, Chinmay Nirkhe

It is a long-standing open question in quantum complexity theory whether the definition of non−deterministic quantum computation requires quantum witnesses (QMA) or if classical witnesses suffice (QCMA). We make progress on this question by constructing a randomized classical oracle separating the respective computational complexity classes. Previous separations \cite{ak-oracle}, \cite{fefferman-kimmel} required a quantum unitary oracle. The separating problem is deciding whether a distribution supported on regular un-directed graphs either consists of multiple connected components (yes instances) or consists of one expanding connected component (no instances) where the graph is given in an adjacency-list format by the oracle. Therefore, the oracle is a distribution over n -bit boolean functions.

Quantum•Jun 17, 2024•9 citations

Separating QMA from QCMA with a classical oracle

John Bostanci, Jonas Haferkamp, Chinmay Nirkhe +1 more

We construct a classical oracle proving that, in a relativized setting, the set of languages decidable by an efficient quantum verifier with a quantum witness (QMA) is strictly bigger than those decidable with access only to a classical witness (QCMA). The separating classical oracle we construct is for a decision problem we coin spectral Forrelation -- the oracle describes two subsets of the boolean hypercube, and the computational task is to decide if there exists a quantum state whose standard basis measurement distribution is well supported on one subset while its Fourier basis measurement distribution is well supported on the other subset. This is equivalent to estimating the spectral norm of a "Forrelation" matrix between two sets that are accessible through membership queries. Our lower bound derives from a simple observation that a query algorithm with a classical witness can be run multiple times to generate many samples from a distribution, while a quantum witness is a "use once" object. This observation allows us to reduce proving a QCMA lower bound to proving a sampling hardness result which does not simultaneously prove a QMA lower bound. To prove said sampling hardness result for QCMA, we observe that quantum access to the oracle can be compressed by expressing the problem in terms of bosons -- a novel "second quantization" perspective on compressed oracle techniques, which may be of independent interest. Using this compressed perspective on the sampling problem, we prove the sampling hardness result, completing the proof.

quant-pharXiv:2511.09551•ACM Symposium on Theory of Computing (STOC)•Nov 13, 2025•12 citations

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

A Distribution Testing Oracle Separating QMA and QCMA

Anand Natarajan, Chinmay Nirkhe

It is a long-standing open question in quantum complexity theory whether the definition of $\textit{non-deterministic}$ quantum computation requires quantum witnesses $(\textsf{QMA})$ or if classical witnesses suffice $(\textsf{QCMA})$. We make progress on this question by constructing a randomized classical oracle separating the respective computational complexity classes. Previous separations [Aaronson-Kuperberg (CCC'07), Fefferman-Kimmel (MFCS'18)] required a quantum unitary oracle. The separating problem is deciding whether a distribution supported on regular un-directed graphs either consists of multiple connected components (yes instances) or consists of one expanding connected component (no instances) where the graph is given in an adjacency-list format by the oracle. Therefore, the oracle is a distribution over $n$-bit boolean functions.

arXiv:2210.15380•Leibniz international proceedings in informatics•Oct 27, 2022•9 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 exhibit a classical oracle relative to which QMA \neq QMA(2). The separation is based on a separable Hamiltonian problem defined by signed edge constraints on a graph. The YES instances have zero-energy product states, while the NO instances, constructed using the antisymmetric subspace, have entangled zero-energy states but no low-energy product states. For the QMA lower bound, we use compressed-oracle techniques to track the information learned by a quantum computation making few queries to a YES instance. The key step is to map the resulting superpositions of partial oracle records to the NO family without significantly changing the verifier's behavior.
Does requiring two quantum proofs to be unentangled increase verification power even relative to a classical oracle? This paper establishes a classical oracle AAA for which QMAA≠QMA(2)A\mathrm{QMA}^A\neq\mathrm{QMA}(2)^AQMAA=QMA(2)A, strengthening the previously known quantum-oracle separation. It does not establish an unrelativized separation.
The separating problem minimizes a signed-graph Hamiltonian’s energy over product states across a prescribed bipartition. The graph is accessed through forward and inverse adjacency queries returning neighbors and edge signs. Hard YES instances have zero-energy product states. Hard NO instances also have entangled zero-energy states, but every product state has energy at least 1/41/41/4, with probability 1−exp⁡(−Ω(N))1-\exp(-\Omega(N))1−exp(−Ω(N)), where N=2kN=2^kN=2k. The promise problem uses thresholds 3/163/163/16 and 1/41/41/4 and admits a one-query QMA(2)\mathrm{QMA}(2)QMA(2) test with a constant completeness–soundness gap, followed by standard amplification.
The NO construction groups vertices using hidden pair-labels and chooses signed constraints whose ideal satisfying subspace is locally isometric to the four-register antisymmetric subspace. Its maximum product-state squared overlap is at most 1/31/31/3; concentration bounds establish the energy gap. The QMA lower bound combines compressed permutation oracles and Fourier-encoded signs with a coherent transfer of short YES-oracle records to NO parameters. An acceptance-operator powering argument handles arbitrary oracle-dependent quantum witnesses, ruling out polynomial witness length and query complexity.
The separating problem is nevertheless in SBQP\mathrm{SBQP}SBQP, so this construction cannot establish a classical-oracle separation of QMA(2)\mathrm{QMA}(2)QMA(2) from SBQP\mathrm{SBQP}SBQP. Whether such a separation exists remains open.
We find a quantum oracle relative to which QMA≠QMA(2)\mathsf{QMA} \neq \mathsf{QMA}(2)QMA=QMA(2). As a consequence, we resolve the no-disentanglers conjecture of Watrous: for every ε+δ<1ε+δ<1ε+δ<1, any (ε,δ)(ε,δ)(ε,δ)-disentangler requires input size exponential in the number of output qubits. Our proof combines the unitarily invariant polynomial method of She and Yuen (ITCS '23) with a new construction based on the symmetric and antisymmetric subspace projectors, reducing the QMA\mathsf{QMA}QMA lower bound to the approximate degree of OR\mathrm{OR}OR.
It is a long-standing open question in quantum complexity theory whether the definition of non−deterministic quantum computation requires quantum witnesses (QMA) or if classical witnesses suffice (QCMA). We make progress on this question by constructing a randomized classical oracle separating the respective computational complexity classes. Previous separations \cite{ak-oracle}, \cite{fefferman-kimmel} required a quantum unitary oracle. The separating problem is deciding whether a distribution supported on regular un-directed graphs either consists of multiple connected components (yes instances) or consists of one expanding connected component (no instances) where the graph is given in an adjacency-list format by the oracle. Therefore, the oracle is a distribution over n -bit boolean functions.
We construct a classical oracle proving that, in a relativized setting, the set of languages decidable by an efficient quantum verifier with a quantum witness (QMA) is strictly bigger than those decidable with access only to a classical witness (QCMA). The separating classical oracle we construct is for a decision problem we coin spectral Forrelation -- the oracle describes two subsets of the boolean hypercube, and the computational task is to decide if there exists a quantum state whose standard basis measurement distribution is well supported on one subset while its Fourier basis measurement distribution is well supported on the other subset. This is equivalent to estimating the spectral norm of a "Forrelation" matrix between two sets that are accessible through membership queries. Our lower bound derives from a simple observation that a query algorithm with a classical witness can be run multiple times to generate many samples from a distribution, while a quantum witness is a "use once" object. This observation allows us to reduce proving a QCMA lower bound to proving a sampling hardness result which does not simultaneously prove a QMA lower bound. To prove said sampling hardness result for QCMA, we observe that quantum access to the oracle can be compressed by expressing the problem in terms of bosons -- a novel "second quantization" perspective on compressed oracle techniques, which may be of independent interest. Using this compressed perspective on the sampling problem, we prove the sampling hardness result, completing the proof.
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.
It is a long-standing open question in quantum complexity theory whether the definition of non-deterministic\textit{non-deterministic}non-deterministic quantum computation requires quantum witnesses (QMA)(\textsf{QMA})(QMA) or if classical witnesses suffice (QCMA)(\textsf{QCMA})(QCMA). We make progress on this question by constructing a randomized classical oracle separating the respective computational complexity classes. Previous separations [Aaronson-Kuperberg (CCC'07), Fefferman-Kimmel (MFCS'18)] required a quantum unitary oracle. The separating problem is deciding whether a distribution supported on regular un-directed graphs either consists of multiple connected components (yes instances) or consists of one expanding connected component (no instances) where the graph is given in an adjacency-list format by the oracle. Therefore, the oracle is a distribution over nnn-bit boolean functions.
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.