Related papers: En Route to a Standard QMA1 vs. QCMA Oracle Separation

En Route to a Standard QMA1 vs. QCMA Oracle Separation

URL: http://arxiv.org/abs/2604.26921v1
Date: Wed, 29 Apr 2026 17:38:20 GMT
Title: En Route to a Standard QMA1 vs. QCMA Oracle Separation
Abstract summary: We study the power of quantum witnesses under perfect completeness.<n>We construct a classical oracle relative to which a language lies in $mathsfQMA$ but not in $mathsfQCMA$.
Score: 0.25489046505746704
License: http://creativecommons.org/licenses/by/4.0/
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.

Related papers

A quantum oracle separation between QMA(2) and QMA [0.9068953081227296]
We find a quantum relative to which $mathsfQMA neq mathsfQMA(2)$.<n>We resolve the no-disentanglers conjecture of Watrous: for every $+1$, any $(, symmetric)$-disentangler requires input size exponential in the number of output qubits.
arXiv Detail & Related papers (2026-09-02T17:50:05Z)
Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning [51.820005667020354]
We study a simple but effective Q-learning algorithm for average-reward MDPs with finite state and action spaces under the weakly communicating assumption.<n>We prove that collaboration reduces the per-agent sample complexity to $widetildeOleft(frac|mathcalA||hstar|_mathsfsp3Mvarepsilon3right)$, with only $widetildeOleft(frac|hstar|_mathsfsp3Mvareps
arXiv Detail & Related papers (2026-01-20T06:21:54Z)
Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
$Phi$-equilibria is a powerful and flexible framework at the heart of online learning and game theory.<n>We show that an efficient online algorithm incurs average $Phi$-regret at most $epsilon$ using $textpoly(d, k)/epsilon2$ rounds.<n>We also show nearly matching lower bounds in the online setting, thereby obtaining for the first time a family of deviations that captures the learnability of $Phi$-regret.
arXiv Detail & Related papers (2025-02-25T19:08:26Z)
QMA vs. QCMA and Pseudorandomness [5.483786291093505]
We show that such an oracle exists if a certain quantum pseudorandomness conjecture holds.<n>Our result can be viewed as establishing a "win-win" scenario.
arXiv Detail & Related papers (2024-11-21T18:50:12Z)
Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
We provide evidence that existing learning algorithms, such as multiplicative weights update, are close to optimal. Our results are obtained in the algorithmic framework put forward by Kothari and Mehta.
arXiv Detail & Related papers (2024-11-04T00:39:52Z)
A distribution testing oracle separation between QMA and QCMA [0.6144680854063939]
It is a long-standing open question in quantum complexity theory whether the definition of $textitnon-deterministic$ quantum computation requires quantum witnesses. We make progress on this question by constructing a randomized classical oracle separating the respective computational complexity classes.
arXiv Detail & Related papers (2022-10-27T12:43:56Z)
Quantum Depth in the Random Oracle Model [57.663890114335736]
We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
arXiv Detail & Related papers (2022-10-12T17:54:02Z)
An optimal oracle separation of classical and quantum hybrid schemes [0.0]
We show that for any depth parameter $d$, there exists an oracle that separates quantum depth $d$ and $2d+1$, when computation-time classical is allowed. This gives an optimal oracle separation of classical and quantum hybrid schemes.
arXiv Detail & Related papers (2022-05-10T02:31:19Z)
On Submodular Contextual Bandits [92.45432756301231]
We consider the problem of contextual bandits where actions are subsets of a ground set and mean rewards are modeled by an unknown monotone submodular function. We show that our algorithm efficiently randomizes around local optima of estimated functions according to the Inverse Gap Weighting strategy.
arXiv Detail & Related papers (2021-12-03T21:42:33Z)
Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
We study the efficient learnability of high-dimensional Gaussian mixtures in the adversarial-robust setting. We provide an algorithm that learns the components of an $epsilon$-corrupted $k$-mixture within information theoretically near-optimal error proofs of $tildeO(epsilon)$. Our main technical contribution is a new robust identifiability proof clusters from a Gaussian mixture, which can be captured by the constant-degree Sum of Squares proof system.
arXiv Detail & Related papers (2020-05-13T16:44:12Z)
On the complexity of zero gap MIP* [0.11470070927586014]
We show that the class $mathsfMIP*$ is equal to $mathsfRE$. In particular this shows that the complexity of approximating the quantum value of a non-local game $G$ is equivalent to the complexity of the Halting problem.
arXiv Detail & Related papers (2020-02-24T19:11:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.