arXiv:2610.06760
A classical oracle separation between QMA and QMA(2)
Sabee Grewal, Saachi Mutreja, Kabir Tomer
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.
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.