Skip to content
DraconiticResearch
Search Sources API
190,851 studies31 sourcesUpdated 13 min ago
PreprintCC BY-NC-SA 4.0arXiv

A classical oracle separation between QMA and QMA(2)

  • Sabee Grewal
  • Saachi Mutreja
  • Kabir Tomer
Open at sourcePDFDOICite

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.

Related

  1. A Quantum/Classical Example Oracle Separation for Making Things Up
    Kenny Chen
    arXivPreprintCC BY 4.0Full textStatisticsQuantum physics & quantum informationarXiv
  2. A quantum oracle separation between QMA(2) and QMA
    John Bostanci, Sabee Grewal, Jonas Haferkamp +4
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  3. Quantum Advantage with Sign-Free Proofs: An Oracle Separation between StoqMA and MA
    Yassine Hamoudi, Yvan Le Borgne, Shrinidhi Teganahally Sridhara
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  4. Practical Considerations for Processing Massive Classical Data via Quantum Oracle Sketching
    Stefano Markidis
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  5. A Separation Between Types of Quantum Oracle Separations
    Scott Aaronson, Adam Bouland, Jordan Docter +1
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{grewal2026classical,
  title = {{A classical oracle separation between QMA and QMA(2)}},
  author = {Sabee Grewal and Saachi Mutreja and Kabir Tomer},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.06760},
  eprint = {2610.06760},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.06760},
  note = {CC BY-NC-SA 4.0},
}
RIS
TY  - UNPB
TI  - A classical oracle separation between QMA and QMA(2)
AU  - Sabee Grewal
AU  - Saachi Mutreja
AU  - Kabir Tomer
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2610.06760
UR  - https://arxiv.org/abs/2610.06760
AB  - 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.
ER  -