Metraipolis › archive › dc_bc63f63b76bd

Achieving perfect completeness for one- and two-message quantum proof systems — arXiv:2609.15926

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.15926
License (as archived): CC0-1.0
Archived: 2026-10-16T02:16:29.487Z
SHA-256 of the archived text: 978b2d85eb73353ec8477ab82025bb8b72f4b9d42a8fb2401e1625f4d8a03779
Stable URL of this page: https://metraipolis.com/documento/dc_bc63f63b76bd

How to cite

Achieving perfect completeness for one- and two-message quantum proof systems — arXiv:2609.15926 — arXiv (en), https://arxiv.org/abs/2609.15926 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bc63f63b76bd (Metraipolis archive dc_bc63f63b76bd, sha256 978b2d85eb73353ec8477ab82025bb8b72f4b9d42a8fb2401e1625f4d8a03779)

BibTeX

@misc{dcbc63f63b76bd,
  title = {Achieving perfect completeness for one- and two-message quantum proof systems — arXiv:2609.15926},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.15926},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bc63f63b76bd; sha256 978b2d85eb73353ec8477ab82025bb8b72f4b9d42a8fb2401e1625f4d8a03779},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.15926. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

While quantum interactive proof systems using at least three messages can achieve perfect completeness, as shown by Kitaev and Watrous (STOC 2000), whether perfect completeness is achievable for one- and two-message quantum proof systems has remained open. For the one-message case, whether $\sf QMA$ can achieve perfect completeness was posed as an open problem in Watrous (FOCS 2000) and Aharonov and Naveh (2002); for the two-message case, the corresponding problems were (implicitly) posed in Jain, Upadhyay, and Watrous~(FOCS 2009) and Kobayashi, Le Gall, and Nishimura (SICOMP, 2019). In this work, we establish that ${\sf QIP}(2)$, ${\rm qq}\text{-}{\sf QAM}$, $\sf QAM$, and $\sf QMA$ can achieve perfect completeness. Here ${\rm qq}\text{-}{\sf QAM}$ denotes the class of promise problems admitting two-message quantum-public-coin quantum interactive proof systems in which the verifier's only message consists of half-EPR pairs. Our main technical contributions are the follows: 1. For $\sf QMA$ (and directly for $\sf QAM$), an exactly constructible block-encoded matrix whose kernel certifies yes instances, constructed from the acceptance operator induced by the verification circuit. This also yields an alternative proof of ${\sf QCMA}={\sf QCMA}_1$. 2. For ${\sf QIP}(2)$ (and implicitly ${\rm qq}\text{-}{\sf QAM}$), a new turn-halving transformation that preserves completeness and ensures that the resulting proof system retains at least two messages, provided that the terminal state before the final measurement is efficiently preparable.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-15 in cs.CC).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.15926 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T01:56:43.437Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).