Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
We establish a classical oracle separation between Quantum Merlin-Arthur (QMA) and QMA with two provers (QMA(2)) by constructing a problem instance where a quantum verifier with two provers can distinguish YES from NO instances, but a verifier with a single prover cannot. The separation hinges on a separable Hamiltonian problem where YES instances admit zero-energy product states, while NO instances, utilizing the antisymmetric subspace, possess entangled zero-energy states but lack low-energy product states. This is achieved by employing compressed-oracle techniques to bound the information gained by a single-prover quantum computation on YES instances and mapping resulting superpositions of partial oracle records to the NO family without altering verifier behavior.
QMA(2) is strictly more powerful than QMA in the presence of a classical oracle, shattering the assumption of equivalence for certain complexity classes.
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.