Skip to content
DraconiticResearch
Search Sources API
185,139 studies31 sourcesUpdated 29 min ago
PreprintarXiv licencearXiv

QMA has perfect completeness

  • Sabee Grewal
  • Dorian Rudolph
Open at sourcePDFDOICite

Abstract

We prove QMA = QMA1, i.e., every quantum Merlin-Arthur proof system can be made perfectly complete. Our construction uses only Hadamard, Toffoli, and X gates, yielding a universal gate set for QMA1. As a consequence, quantum $3$-SAT is QMA-complete. The construction relativizes to classical oracles, so known classical-oracle separations of QMA from QCMA extend to QMA1.

Related

  1. Achieving perfect completeness for one- and two-message quantum proof systems
    Yupan Liu, Thomas Vidick
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  2. Global hyperbolicity meets order completeness
    E. Minguzzi
    arXivPreprintarXiv licenceFull textGravitation & general relativityarXiv
  3. On the Completeness of Quantum Mechanics: Sources, Records and Probabilities
    Mustafa Bakr
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  4. On the completeness of gravitational pp-wave spacetimes: A counterexample to the {Ehlers--Kundt} conjecture
    Hannah Cairo
    arXivPreprintarXiv licenceFull textGeometry & topologyGravitation & general relativityarXiv
  5. Why Multi-Layer Message Passing Works: Completeness Theory for Graph Neural Network Interatomic Potentials
    Pingbing Ming, Han Wang
    arXivPreprintCC BY-NC-SA 4.0Full textPhysical chemistryMathematical physicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{grewal2026perfect,
  title = {{QMA has perfect completeness}},
  author = {Sabee Grewal and Dorian Rudolph},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.13032},
  eprint = {2609.13032},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.13032},
}
RIS
TY  - UNPB
TI  - QMA has perfect completeness
AU  - Sabee Grewal
AU  - Dorian Rudolph
PY  - 2026
DA  - 2026/09/11
PB  - arXiv
DO  - 10.48550/arxiv.2609.13032
UR  - https://arxiv.org/abs/2609.13032
AB  - We prove QMA = QMA_1, i.e., every quantum Merlin-Arthur proof system can be made perfectly complete. Our construction uses only Hadamard, Toffoli, and X gates, yielding a universal gate set for QMA_1. As a consequence, quantum $3$-SAT is QMA-complete. The construction relativizes to classical oracles, so known classical-oracle separations of QMA from QCMA extend to QMA_1.
ER  -