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

En Route to a Standard QMA1 vs. QCMA Oracle Separation

David Miloschewsky, Supartha Podder, Dorian Rudolph

quant-phcs.CCSubmitted Apr 29, 2026• Announced Apr 30, 2026• 1 citation
arXivHTMLPDF

Abstract

We study the power of quantum witnesses under perfect completeness. We construct a classical oracle relative to which a language lies in $\mathsf{QMA}_1$ but not in $\mathsf{QCMA}$ when the $\mathsf{QCMA}$ verifier is only allowed polynomially many adaptive rounds and exponentially many parallel queries per round. Additionally, we derandomize the permutation-oracle separation of Fefferman and Kimmel, obtaining an in-place oracle separation between $\mathsf{QMA}_1$ and $\mathsf{QCMA}$. Furthermore, we focus on $\mathsf{QCMA}$ and $\mathsf{QMA}$ with an exponentially small gap, where we show a separation assuming the gap is fixed, but not when it may be arbitrarily small. Finally, we derive consequences for approximate ground-state preparation from sparse Hamiltonian oracle access, including a bounded-adaptivity frustration-free variant.

Comments
25 pages

Related papers

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

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

Quantum vs Classical Proofs and Subset Verification

Bill Fefferman, Shelby Kimmel

We study the ability of efficient quantum verifiers to decide properties of exponentially large subsets given either a classical or quantum witness. We develop a general framework that can be used to prove that QCMA machines, with only classical witnesses, cannot verify certain properties of subsets given implicitly via an oracle. We use this framework to prove an oracle separation between QCMA and QMA using an "in-place" permutation oracle, making the first progress on this question since Aaronson and Kuperberg in 2007. We also use the framework to prove a particularly simple standard oracle separation between QCMA and AM.

arXiv:1510.06750•Leibniz international proceedings in informatics•Oct 22, 2015•36 citations

Toward Separating QMA from QCMA with a Classical Oracle

Mark Zhandry

QMA is the class of languages that can be decided by an efficient quantum verifier given a quantum witness, whereas QCMA is the class of such languages where the efficient quantum verifier only is given a classical witness. A challenging fundamental goal in quantum query complexity is to find a classical oracle separation for these classes. In this work, we offer a new approach towards proving such a separation that is qualitatively different than prior work, and show that our approach is sound assuming a natural statistical conjecture which may have other applications to quantum query complexity lower bounds.

arXiv:2411.01718•Leibniz international proceedings in informatics•Nov 4, 2024•10 citations

Quantum State Search with Classical Interactive Advice

Mohammed Barhoush

We study whether a quantum verifier can find a hidden quantum state by exchanging classical messages with an unbounded prover who knows the state. The verifier has access to a reflection oracle about the target. For a Haar-random $n$-qubit target, we prove that achieving constant average fidelity with the target requires $(q+1)^2(B+1)=Ω(2^n)$, where $q$ is the number of verifier queries and $B$ is the total prover-to-verifier communication. The bound allows arbitrary classical interaction and unrestricted computation between queries. Our proof extends the lower bound of Aaronson and Kuperberg (ToC'07) from a single classical proof to an arbitrary classical interaction. As a result, we obtain a quantum-oracle separation of QMA from QCIP. In particular, we give a unitary oracle $\mathcal{U}$ such that there exists a language $L\in\mathrm{QMA}^{\mathcal{U}}$ but $L\notin\mathrm{QCIP}^{\mathcal{U}}$. Our separation holds even for UniqueQMA, the restriction of QMA to verification with a unique quantum witness, which is known to be strictly weaker than QMA in the quantum black-box setting. We further give an oracle construction for a notion known as QMA--QCIP[2] gap problem. This gives average case hardness for a QMA language under classical access to a QCIP[2] decision oracle and is used in establishing negative results on witness encryption and quantum indistinguishability obfuscation.

quant-pharXiv:2610.25657•Oct 20, 2026•0 citations

Quantum Advantage with Sign-Free Proofs: An Oracle Separation between $\mathsf{StoqMA}$ and $\mathsf{MA}$

Yassine Hamoudi, Yvan Le Borgne, Shrinidhi Teganahally Sridhara

Several landmark oracle results (FOCS 2000, FOCS 2025, STOC 2026) establish strict separations along the chain $\mathsf{MA} \subseteq \mathsf{QCMA} \subseteq \mathsf{QMA}$, showing that quantum verification and quantum witnesses can each provide additional power over classical proof systems. These separations, however, use substantial coherent quantum computation, often through the quantum Fourier transform. We prove that a minimal quantum resource already suffices to outperform every classical verifier. Namely, we show the separation $$\mathsf{MA} \subsetneq \mathsf{StoqMA}$$ relative to a classical oracle. The class $\mathsf{StoqMA}$, introduced by Bravyi, Bessen, and Terhal (arXiv 2006), restricts the verifier to classical reversible computation, followed by a single Hadamard-basis measurement. Its power is closely tied to the complexity of stoquastic Hamiltonians, a sign-problem-free and seemingly more tractable class of quantum Hamiltonians. Our separating problem is to determine whether a sparse high-girth graph, given via an adjacency-list oracle, has a large or small Perron--Frobenius eigenvalue. This amounts to a ground-energy estimation task for a related stoquastic Hamiltonian. Our construction builds on a line of work on graph exploration problems with exponential quantum speedups, from welded trees (STOC 2003) to recent constructions (STOC 2021, arXiv 2026).

arXiv:2611.08180•Nov 5, 2026•0 citations
We study the power of quantum witnesses under perfect completeness. We construct a classical oracle relative to which a language lies in QMA1\mathsf{QMA}_1QMA1​ but not in QCMA\mathsf{QCMA}QCMA when the QCMA\mathsf{QCMA}QCMA verifier is only allowed polynomially many adaptive rounds and exponentially many parallel queries per round. Additionally, we derandomize the permutation-oracle separation of Fefferman and Kimmel, obtaining an in-place oracle separation between QMA1\mathsf{QMA}_1QMA1​ and QCMA\mathsf{QCMA}QCMA. Furthermore, we focus on QCMA\mathsf{QCMA}QCMA and QMA\mathsf{QMA}QMA with an exponentially small gap, where we show a separation assuming the gap is fixed, but not when it may be arbitrarily small. Finally, we derive consequences for approximate ground-state preparation from sparse Hamiltonian oracle access, including a bounded-adaptivity frustration-free variant.
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.
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.
We study the ability of efficient quantum verifiers to decide properties of exponentially large subsets given either a classical or quantum witness. We develop a general framework that can be used to prove that QCMA machines, with only classical witnesses, cannot verify certain properties of subsets given implicitly via an oracle. We use this framework to prove an oracle separation between QCMA and QMA using an "in-place" permutation oracle, making the first progress on this question since Aaronson and Kuperberg in 2007. We also use the framework to prove a particularly simple standard oracle separation between QCMA and AM.
QMA is the class of languages that can be decided by an efficient quantum verifier given a quantum witness, whereas QCMA is the class of such languages where the efficient quantum verifier only is given a classical witness. A challenging fundamental goal in quantum query complexity is to find a classical oracle separation for these classes. In this work, we offer a new approach towards proving such a separation that is qualitatively different than prior work, and show that our approach is sound assuming a natural statistical conjecture which may have other applications to quantum query complexity lower bounds.
We study whether a quantum verifier can find a hidden quantum state by exchanging classical messages with an unbounded prover who knows the state. The verifier has access to a reflection oracle about the target. For a Haar-random nnn-qubit target, we prove that achieving constant average fidelity with the target requires (q+1)2(B+1)=Ω(2n)(q+1)^2(B+1)=Ω(2^n)(q+1)2(B+1)=Ω(2n), where qqq is the number of verifier queries and BBB is the total prover-to-verifier communication. The bound allows arbitrary classical interaction and unrestricted computation between queries. Our proof extends the lower bound of Aaronson and Kuperberg (ToC'07) from a single classical proof to an arbitrary classical interaction. As a result, we obtain a quantum-oracle separation of QMA from QCIP. In particular, we give a unitary oracle U\mathcal{U}U such that there exists a language L∈QMAUL\in\mathrm{QMA}^{\mathcal{U}}L∈QMAU but L∉QCIPUL\notin\mathrm{QCIP}^{\mathcal{U}}L∈/QCIPU. Our separation holds even for UniqueQMA, the restriction of QMA to verification with a unique quantum witness, which is known to be strictly weaker than QMA in the quantum black-box setting. We further give an oracle construction for a notion known as QMA--QCIP[2] gap problem. This gives average case hardness for a QMA language under classical access to a QCIP[2] decision oracle and is used in establishing negative results on witness encryption and quantum indistinguishability obfuscation.
Quantum Advantage with Sign-Free Proofs: An Oracle Separation between StoqMA\mathsf{StoqMA}StoqMA and MA\mathsf{MA}MA
Several landmark oracle results (FOCS 2000, FOCS 2025, STOC 2026) establish strict separations along the chain MA⊆QCMA⊆QMA\mathsf{MA} \subseteq \mathsf{QCMA} \subseteq \mathsf{QMA}MA⊆QCMA⊆QMA, showing that quantum verification and quantum witnesses can each provide additional power over classical proof systems. These separations, however, use substantial coherent quantum computation, often through the quantum Fourier transform. We prove that a minimal quantum resource already suffices to outperform every classical verifier. Namely, we show the separation MA⊊StoqMA\mathsf{MA} \subsetneq \mathsf{StoqMA}MA⊊StoqMA relative to a classical oracle. The class StoqMA\mathsf{StoqMA}StoqMA, introduced by Bravyi, Bessen, and Terhal (arXiv 2006), restricts the verifier to classical reversible computation, followed by a single Hadamard-basis measurement. Its power is closely tied to the complexity of stoquastic Hamiltonians, a sign-problem-free and seemingly more tractable class of quantum Hamiltonians. Our separating problem is to determine whether a sparse high-girth graph, given via an adjacency-list oracle, has a large or small Perron--Frobenius eigenvalue. This amounts to a ground-energy estimation task for a related stoquastic Hamiltonian. Our construction builds on a line of work on graph exploration problems with exponential quantum speedups, from welded trees (STOC 2003) to recent constructions (STOC 2021, arXiv 2026).