Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1111.5306 · Quantum Information and Computation

Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems

Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj, Harumichi Nishimura

Published May 1, 2012• 37 citations
arXivHTMLPDF

Abstract

This paper proves that classical-witness quantum Merlin-Arthur proof systems can achieve perfect completeness. That is, ${\QCMA = \QCMA_1}$. This holds under any gate set with which the Hadamard and arbitrary classical reversible transformations can be exactly implemented, \emph{e.g.}, ${\{\textrm{Hadamard, Toffoli, NOT}\}}$. The proof is quantumly nonrelativizing, and uses a simple but novel quantum technique that \emph{additively} adjusts the success probability, which may be of independent interest.

DOI
10.26421/qic12.5-6-7

Related papers

QMA has perfect completeness

Sabee Grewal, Dorian Rudolph

We prove $\mathsf{QMA} = \mathsf{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 $\mathsf{QMA_1}$. As a consequence, quantum $3$-SAT is $\mathsf{QMA}$-complete. The construction relativizes to classical oracles, so known classical-oracle separations of $\mathsf{QMA}$ from $\mathsf{QCMA}$ extend to $\mathsf{QMA_1}$.

quant-pharXiv:2609.13032•Sep 14, 2026•0 citations

Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?

Hirotada Kobayashi, Keiji Matsumoto, Tomoyuki Yamakami

This paper introduces quantum ``multiple-Merlin''-Arthur proof systems in which Arthur receives multiple quantum proofs that are unentangled with each other. Although classical multi-proof systems are obviously equivalent to classical single-proof systems (i.e., usual Merlin-Arthur proof systems), it is unclear whether or not quantum multi-proof systems collapse to quantum single-proof systems (i.e., usual quantum Merlin-Arthur proof systems). This paper presents a necessary and sufficient condition under which the number of quantum proofs is reducible to two. It is also proved that, in the case of perfect soundness, using multiple quantum proofs does not increase the power of quantum Merlin-Arthur proof systems.

arXiv:quant-ph/0306051•Chicago Journal of Theoretical Computer Science•Jun 6, 2003•53 citations

Quantum-Merlin-Arthur Problems Have Perfect Completeness with an Infinite Counter

Stacey Jeffery, Freek Witteveen

A longstanding open problem in quantum complexity theory is whether Quantum Merlin-Arthur (QMA), the quantum analog of nondeterministic polynomial time, is equal to QMA_{1}, its one-sided error variant. We show that QMA=QMA^{∞}=QMA_{1}^{∞}, where QMA_{1}^{∞} is like QMA_{1}, but the verifier has an infinite register, as part of their witness system, in which they can efficiently perform a shift (increment) operation. We call this register an "infinite counter," and compare it to a program counter in a Las Vegas algorithm. The result, QMA=QMA^{∞} means such an infinite register does not increase the power of QMA, but does imply perfect completeness. By truncating our construction to finite dimensions, we get a QMA-amplifier that only amplifies completeness, not soundness, but does so in significantly less time than previous QMA amplifiers. Our new construction achieves completeness 1-2^{-q} using O(1) calls to each of the original verifier and its inverse, and O(logq) other gates, proving that QMA has completeness doubly exponentially close to 1, i.e., QMA=QMA(1-2^{-2^{r}},2^{-r}) for any polynomial r.

Physical Review Letters•Apr 2, 2026•0 citations

On perfect completeness for QMA

Scott Aaronson

Whether the class QMA (Quantum Merlin Arthur)\ is equal to QMA_1, or QMA with one-sided error, has been an open problem for years. This note helps to explain why the problem is difficult,\ by using ideas from real analysis to give a "quantum" relative to which QMA \neq QMA_1. As a byproduct, we find that there are facts about quantum complexity classes that are classically relativizing but not quantumly relativizing, among them such "trivial" containments as BQP \subseteq ZQEXP.

Quantum Information and Computation•Jan 1, 2009•29 citations

Generalized Quantum Arthur--Merlin Games

Hirotada Kobayashi, François Le Gall, Harumichi Nishimura

This paper investigates the role of interaction and coins in quantum Arthur--Merlin games (also called public-coin quantum interactive proof systems). While the existing model restricts the messages from the verifier to be classical even in the quantum setting, the present work introduces a generalized version of quantum Arthur--Merlin games where the messages from the verifier can be quantum as well: the verifier can send not only random bits, but also halves of EPR pairs (to share with the prover). This generalization turns out to provide several novel characterizations of quantum interactive proof systems with a constant number of turns. First, it is proved that the complexity class corresponding to two-turn quantum Arthur--Merlin games where both of the two messages are quantum (denoted qq-QAM in this paper) does not change by adding a constant number of turns of classical interaction prior to the communications of qq-QAM proof systems. This can be viewed as a quantum analogue of the celebrated collapse theorem for AM due to Babai. To prove this collapse theorem, this paper presents a natural complete problem for qq-QAM: deciding whether the output of a given quantum circuit is close to a totally mixed state. This complete problem is on the very line of the previous studies investigating the hardness of checking properties related to quantum circuits, and thus qq-QAM may provide a good measure in computational complexity theory. It is further proved that the class ${qq-QAM}_1$, the perfect-completeness variant of qq-QAM, gives new bounds for standard well-studied classes of two-turn quantum interactive proof systems. Finally, the collapse theorem above is extended to comprehensively classify the role of classical and quantum interactions in quantum Arthur--Merlin games: it is proved that, for any constant $m\geq2$, the class of problems having $m$-turn quantum Arthur--Merlin proof systems is either equal to PSPACE or equal to the class of problems having two-turn quantum Arthur--Merlin proof systems of a specific type, which provides a complete set of quantum analogues of Babai's collapse theorem.

arXiv:1312.4673•SIAM Journal on Computing•Jan 1, 2019•3 citations

Achieving perfect completeness for one- and two-message quantum proof systems

Yupan Liu, Thomas Vidick

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.

quant-pharXiv:2609.15926•Sep 15, 2026•0 citations
This paper proves that classical-witness quantum Merlin-Arthur proof systems can achieve perfect completeness. That is, \QCMA=\QCMA1{\QCMA = \QCMA_1}\QCMA=\QCMA1​. This holds under any gate set with which the Hadamard and arbitrary classical reversible transformations can be exactly implemented, \emph{e.g.}, {Hadamard, Toffoli, NOT}{\{\textrm{Hadamard, Toffoli, NOT}\}}{Hadamard, Toffoli, NOT}. The proof is quantumly nonrelativizing, and uses a simple but novel quantum technique that \emph{additively} adjusts the success probability, which may be of independent interest.
We prove QMA=QMA1\mathsf{QMA} = \mathsf{QMA_1}QMA=QMA1​, i.e., every quantum Merlin-Arthur proof system can be made perfectly complete. Our construction uses only Hadamard, Toffoli, and XXX gates, yielding a universal gate set for QMA1\mathsf{QMA_1}QMA1​. As a consequence, quantum 333-SAT is QMA\mathsf{QMA}QMA-complete. The construction relativizes to classical oracles, so known classical-oracle separations of QMA\mathsf{QMA}QMA from QCMA\mathsf{QCMA}QCMA extend to QMA1\mathsf{QMA_1}QMA1​.
This paper introduces quantum ``multiple-Merlin''-Arthur proof systems in which Arthur receives multiple quantum proofs that are unentangled with each other. Although classical multi-proof systems are obviously equivalent to classical single-proof systems (i.e., usual Merlin-Arthur proof systems), it is unclear whether or not quantum multi-proof systems collapse to quantum single-proof systems (i.e., usual quantum Merlin-Arthur proof systems). This paper presents a necessary and sufficient condition under which the number of quantum proofs is reducible to two. It is also proved that, in the case of perfect soundness, using multiple quantum proofs does not increase the power of quantum Merlin-Arthur proof systems.
A longstanding open problem in quantum complexity theory is whether Quantum Merlin-Arthur (QMA), the quantum analog of nondeterministic polynomial time, is equal to QMA_{1}, its one-sided error variant. We show that QMA=QMA^{∞}=QMA_{1}^{∞}, where QMA_{1}^{∞} is like QMA_{1}, but the verifier has an infinite register, as part of their witness system, in which they can efficiently perform a shift (increment) operation. We call this register an "infinite counter," and compare it to a program counter in a Las Vegas algorithm. The result, QMA=QMA^{∞} means such an infinite register does not increase the power of QMA, but does imply perfect completeness. By truncating our construction to finite dimensions, we get a QMA-amplifier that only amplifies completeness, not soundness, but does so in significantly less time than previous QMA amplifiers. Our new construction achieves completeness 1-2^{-q} using O(1) calls to each of the original verifier and its inverse, and O(logq) other gates, proving that QMA has completeness doubly exponentially close to 1, i.e., QMA=QMA(1-2^{-2^{r}},2^{-r}) for any polynomial r.
Whether the class QMA (Quantum Merlin Arthur)\ is equal to QMA_1, or QMA with one-sided error, has been an open problem for years. This note helps to explain why the problem is difficult,\ by using ideas from real analysis to give a "quantum" relative to which QMA \neq QMA_1. As a byproduct, we find that there are facts about quantum complexity classes that are classically relativizing but not quantumly relativizing, among them such "trivial" containments as BQP \subseteq ZQEXP.
This paper investigates the role of interaction and coins in quantum Arthur--Merlin games (also called public-coin quantum interactive proof systems). While the existing model restricts the messages from the verifier to be classical even in the quantum setting, the present work introduces a generalized version of quantum Arthur--Merlin games where the messages from the verifier can be quantum as well: the verifier can send not only random bits, but also halves of EPR pairs (to share with the prover). This generalization turns out to provide several novel characterizations of quantum interactive proof systems with a constant number of turns. First, it is proved that the complexity class corresponding to two-turn quantum Arthur--Merlin games where both of the two messages are quantum (denoted qq-QAM in this paper) does not change by adding a constant number of turns of classical interaction prior to the communications of qq-QAM proof systems. This can be viewed as a quantum analogue of the celebrated collapse theorem for AM due to Babai. To prove this collapse theorem, this paper presents a natural complete problem for qq-QAM: deciding whether the output of a given quantum circuit is close to a totally mixed state. This complete problem is on the very line of the previous studies investigating the hardness of checking properties related to quantum circuits, and thus qq-QAM may provide a good measure in computational complexity theory. It is further proved that the class qq−QAM1{qq-QAM}_1qq−QAM1​, the perfect-completeness variant of qq-QAM, gives new bounds for standard well-studied classes of two-turn quantum interactive proof systems. Finally, the collapse theorem above is extended to comprehensively classify the role of classical and quantum interactions in quantum Arthur--Merlin games: it is proved that, for any constant m≥2m\geq2m≥2, the class of problems having mmm-turn quantum Arthur--Merlin proof systems is either equal to PSPACE or equal to the class of problems having two-turn quantum Arthur--Merlin proof systems of a specific type, which provides a complete set of quantum analogues of Babai's collapse theorem.
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 QMA\sf QMAQMA 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 QIP(2){\sf QIP}(2)QIP(2), qq-QAM{\rm qq}\text{-}{\sf QAM}qq-QAM, QAM\sf QAMQAM, and QMA\sf QMAQMA can achieve perfect completeness. Here qq-QAM{\rm qq}\text{-}{\sf QAM}qq-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 QMA\sf QMAQMA (and directly for QAM\sf QAMQAM), 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 QCMA=QCMA1{\sf QCMA}={\sf QCMA}_1QCMA=QCMA1​. 2. For QIP(2){\sf QIP}(2)QIP(2) (and implicitly qq-QAM{\rm qq}\text{-}{\sf QAM}qq-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.