A quantum oracle separation between QMA(2) and QMA

• URL: http://arxiv.org/abs/2609.02865v1
• Date: Wed, 02 Sep 2026 17:50:05 GMT
• Title: A quantum oracle separation between QMA(2) and QMA
• Abstract summary: 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.
• Score: 0.9068953081227296
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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}$.

Related papers

• PureSuperQMA(exp) = BellPureSymQMA(poly) = QMA via Dimension-Free Bosonic Argmax [36.23068106699028]
  Pure-state consistency problems naturally lead to quantum proof systems in which a single witness must satisfy many acceptance constraints.<n>$mathsfBellPureSymQMA(textpoly)$ is a related model that requires the prover to give the verifierly many copies of a pure state.<n>We show that exact $k$-local pure-state consistency is $mathsfQMA$-complete for every fixed $kge2$, and so are the corresponding exact bosonic and fermionic pure $N$-representability problems.
  arXiv  Detail & Related papers  (2026-09-10T17:37:22Z)
• The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems [46.657699628769336]
  Entanglement and interference are among the most fundamental properties of quantum mechanics.<n>We prove that entanglement gives no additional power to stoquastic verification.
  arXiv  Detail & Related papers  (2026-05-15T17:52:33Z)
• En Route to a Standard QMA1 vs. QCMA Oracle Separation [0.25489046505746704]
  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$.
  arXiv  Detail & Related papers  (2026-04-29T17:38:20Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• A slightly improved upper bound for quantum statistical zero-knowledge [11.384500557173867]
  The complexity class Quantum Statistical Zero-Knowledge ($mathsfQSZK$) has the best known upper bound $mathsfQIP(2) cap textco-mathsfQIP(2)$.<n>We improve this to $mathsfQIP(2) cap textco-mathsfQIP(2)$ with a quantum linear-space honest prover.<n>Our main techniques are an algorithmic version of the Holevo-Helstrom measurement complexity and the Uhlmann transform, both implementable in quantum linear space
  arXiv  Detail & Related papers  (2025-12-12T14:33:20Z)
• Scaling of symmetry-restricted quantum circuits [42.803917477133346]
  In this work, we investigate the properties of $mathcalMSU(2N)$, $mathcalM$-invariant subspaces of the special unitary Lie group $SU(2N)$.
  arXiv  Detail & Related papers  (2024-06-14T12:12:15Z)
• Geometry of degenerate quantum states, configurations of $m$-planes and invariants on complex Grassmannians [55.2480439325792]
  We show how to reduce the geometry of degenerate states to the non-abelian connection $A$. We find independent invariants associated with each triple of subspaces. Some of them generalize the Berry-Pancharatnam phase, and some do not have analogues for 1-dimensional subspaces.
  arXiv  Detail & Related papers  (2024-04-04T06:39:28Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• SQ Lower Bounds for Learning Bounded Covariance GMMs [46.289382906761304]
  We focus on learning mixtures of separated Gaussians on $mathbbRd$ of the form $P= sum_i=1k w_i mathcalN(boldsymbol mu_i,mathbf Sigma_i)$. We prove that any Statistical Query (SQ) algorithm for this problem requires complexity at least $dOmega (1/epsilon)$.
  arXiv  Detail & Related papers  (2023-06-22T17:23:36Z)
• 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)
• Stochastic behavior of outcome of Schur-Weyl duality measurement [45.41082277680607]
  We focus on the measurement defined by the decomposition based on Schur-Weyl duality on $n$ qubits. We derive various types of distribution including a kind of central limit when $n$ goes to infinity.
  arXiv  Detail & Related papers  (2021-04-26T15:03:08Z)
• Quasi-polynomial time algorithms for free quantum games in bounded dimension [11.56707165033]
  We give a semidefinite program of size $exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big)) to compute additive $epsilon$-approximations on the values of two-player free games. We make a connection to the quantum separability problem and employ improved multipartite quantum de Finetti theorems with linear constraints.
  arXiv  Detail & Related papers  (2020-05-18T16:55:08Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.