-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.

DOI: 10.4230/lipics.ccc.2015.488

Related papers

Generalized Quantum Arthur-Merlin Games

Hirotada Kobayashi, 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. 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, 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 ≥ 2, 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.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. 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, 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 ≥ 2, 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.

Jan 1, 20143 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.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.4673SIAM Journal on ComputingJan 1, 20193 citations

Quantum Arthur-Merlin games

Chris Marriott, John Watrous

This paper studies quantum Arthur-Merlin games, which are a restricted form of quantum interactive proof system in which the verifier's messages are given by unbiased coin-flips. The following results are proved. For one-message quantum Arthur-Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin's message. Previous constructions for reducing error required a polynomial increase in the length of Merlin's message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that QMA /spl sube/ PP. In the case of three or more messages, quantum Arthur-Merlin games are equivalent in power to ordinary quantum interactive proof systems. In fact, for any language having a quantum interactive proof system there exists a three-message quantum Arthur-Merlin game in which Arthur's only message consists of just a single coin-flip that achieves perfect completeness and soundness error exponentially close to 1/2. Any language having a two-message quantum Arthur-Merlin game is contained in BP /spl middot/ PP. This gives some suggestion that three messages are stronger than two in the quantum Arthur-Merlin setting.This paper studies quantum Arthur-Merlin games, which are a restricted form of quantum interactive proof system in which the verifier's messages are given by unbiased coin-flips. The following results are proved. For one-message quantum Arthur-Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin's message. Previous constructions for reducing error required a polynomial increase in the length of Merlin's message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that QMA /spl sube/ PP. In the case of three or more messages, quantum Arthur-Merlin games are equivalent in power to ordinary quantum interactive proof systems. In fact, for any language having a quantum interactive proof system there exists a three-message quantum Arthur-Merlin game in which Arthur's only message consists of just a single coin-flip that achieves perfect completeness and soundness error exponentially close to 1/2. Any language having a two-message quantum Arthur-Merlin game is contained in BP /spl middot/ PP. This gives some suggestion that three messages are stronger than two in the quantum Arthur-Merlin setting.

IEEE Conference on Computational Complexity (CCC)Nov 12, 200429 citations

Quantum Arthur–Merlin games

Chris Marriott, John Watrous

This paper studies quantum Arthur–Merlin games, which are Arthur–Merlin games in which Arthur and Merlin can perform quantum computations and Merlin can send Arthur quantum information. As in the classical case, messages from Arthur to Merlin are restricted to be strings of uniformly generated random bits. It is proved that for one-message quantum Arthur–Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin’s message. Previous constructions for reducing error required a polynomial increase in the length of Merlin’s message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that ${\text{QMA}} \subseteq {\text{PP}}.$ Other facts that are proved include the equivalence of three (or more) message quantum Arthur–Merlin games with ordinary quantum interactive proof systems and some basic properties concerning two-message quantum Arthur–Merlin games.This paper studies quantum Arthur–Merlin games, which are Arthur–Merlin games in which Arthur and Merlin can perform quantum computations and Merlin can send Arthur quantum information. As in the classical case, messages from Arthur to Merlin are restricted to be strings of uniformly generated random bits. It is proved that for one-message quantum Arthur–Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin’s message. Previous constructions for reducing error required a polynomial increase in the length of Merlin’s message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that $$ {\text{QMA}} \subseteq {\text{PP}}. $$ Other facts that are proved include the equivalence of three (or more) message quantum Arthur–Merlin games with ordinary quantum interactive proof systems and some basic properties concerning two-message quantum Arthur–Merlin games.

Computational ComplexityJun 1, 2005240 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.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.15926Sep 15, 20260 citations

Quantum Arthur-Merlin Games

Chris Marriott, John Watrous

This paper studies quantum Arthur-Merlin games, which are Arthur-Merlin games in which Arthur and Merlin can perform quantum computations and Merlin can send Arthur quantum information. As in the classical case, messages from Arthur to Merlin are restricted to be strings of uniformly generated random bits. It is proved that for one-message quantum Arthur-Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin's message. Previous constructions for reducing error required a polynomial increase in the length of Merlin's message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that QMA is contained in PP. Other facts that are proved include the equivalence of three (or more) message quantum Arthur-Merlin games with ordinary quantum interactive proof systems and some basic properties concerning two-message quantum Arthur-Merlin games.This paper studies quantum Arthur-Merlin games, which are Arthur-Merlin games in which Arthur and Merlin can perform quantum computations and Merlin can send Arthur quantum information. As in the classical case, messages from Arthur to Merlin are restricted to be strings of uniformly generated random bits. It is proved that for one-message quantum Arthur-Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin's message. Previous constructions for reducing error required a polynomial increase in the length of Merlin's message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that QMA is contained in PP. Other facts that are proved include the equivalence of three (or more) message quantum Arthur-Merlin games with ordinary quantum interactive proof systems and some basic properties concerning two-message quantum Arthur-Merlin games.

arXiv:cs/0506068Jun 15, 20055 citations

m

{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.

{\text{QMA}} \subseteq {\text{PP}}.

Other facts that are proved include the equivalence of three (or more) message quantum Arthur–Merlin games with ordinary quantum interactive proof systems and some basic properties concerning two-message quantum Arthur–Merlin games.

\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.