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

Leibniz international proceedings in informatics

Generalized Quantum Arthur-Merlin Games

Hirotada Kobayashi, François Le Gall, Harumichi Nishimura

Published Jan 1, 2015• 4 citations
Publisher

Abstract

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

DOI
10.4230/lipics.ccc.2015.488

Related papers

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

IEEE Conference on Computational Complexity (CCC)•Nov 12, 2004•32 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.

arXiv:cs/0506068•Computational Complexity•Jun 1, 2005•306 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•3 citations

Public-qubits versus private-coins.

Abuzer Yakaryılmaz

We introduce a new public quantum interactive proof system, namely qAM, by augmenting the verifier with a fixed-size quantum register in Arthur-Merlin game. We focus on spacebounded verifiers, and compare our new public system with private-coin interactive proof (IP) system in the same space bounds. We show that qAM systems not only can simulate all known space-bounded private-coin protocols, but also implements some protocols that are either not implementable by IP systems or currently not known to be simulated by IP systems. More specifically, we show that for any Turing-recognizable language, there exists a constant-space weak-qAM system (the nonmembers do not need to be rejected with high probability), and, different from the classical case, our protocol has perfect-completeness (the members are accepted exactly). For strong proof system, where the nonmembers must be rejected with high probability, we show that the known space-bounded private-coin protocols can also be simulated by qAM systems with the same space bound. In case of constant-space and log-space IP systems, the best known lower bounds are ASPACE(n) and EXP, respectively. We obtain better lower bounds for the corresponding qAM systems: Each language in NP has a constant-space (exp-time) qAM system, there is an NEXP-complete language having a constant-space qAM system, and each language in NEXP has a log-space qAM system.

Electronic colloquium on computational complexity•Jan 1, 2012•16 citations

Space-efficient Simulations of Quantum Interactive Proofs.

Xiaodi Wu

Interactive proof systems form an important complexity model that has been central to many prominent results in computational complexity theory, such as those on probabilistically checkable proofs, hardness of approximation, and fundamental cryptographic primitives. In this thesis, we study the quantum-enhanced version of interactive proof systems, in which each party has access to quantum computing resources. We focus on its power and limitations, which lead us to the following results. (*) We provide an alternative and conceptually simpler proof of Jain et al.’s recent breakthrough result, which demonstrates that the expressive power of quantum interactive proof systems coincides with that of its classical counterpart, and therefore PSPACE. (*) We determine the complexity of several variants of quantum competing-prover interactive proof systems, which introduce zero-sum games into interactive proof systems. In particular, we prove that the complexity class of two-turn quantum refereed games coincides with PSPACE, answering an important open problem of Jain et al.’s. Our result suggests that a more general model called double quantum interactive proof systems coincides with PSPACE, which subsumes and unifies all previous results on short refereed games. (*) We contribute to the study of two-prover quantum Merlin-Arthur games (QMA(2)), which exhibit an intriguing tradeoff between an intrinsic quantum ingredient, entanglement, and computational power. We prove a PSPACE upper bound for a variant of QMA(2) that is to date the most general one known in PSPACE. We also provide a quasi-polynomial time algorithm for optimizing linear functions over separable states, giving an alternative to the one proposed by Brandao et al. Our main technical contribution behind the above results is the equilibrium value method for obtaining space-efficient algorithms for a class of optimization problems that arise naturally in quantum computation. We also contribute to QMA-complete problems, where we demonstrate that the “Non-Identity Check” problem remains QMA-complete on circuits of poly-logarithmic depths, improving upon polynomial depths from previous results.

•Jan 1, 2013•0 citations
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-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 >= 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.
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.
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 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⊆PP. {\text{QMA}} \subseteq {\text{PP}}. QMA⊆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.
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.
We introduce a new public quantum interactive proof system, namely qAM, by augmenting the verifier with a fixed-size quantum register in Arthur-Merlin game. We focus on spacebounded verifiers, and compare our new public system with private-coin interactive proof (IP) system in the same space bounds. We show that qAM systems not only can simulate all known space-bounded private-coin protocols, but also implements some protocols that are either not implementable by IP systems or currently not known to be simulated by IP systems. More specifically, we show that for any Turing-recognizable language, there exists a constant-space weak-qAM system (the nonmembers do not need to be rejected with high probability), and, different from the classical case, our protocol has perfect-completeness (the members are accepted exactly). For strong proof system, where the nonmembers must be rejected with high probability, we show that the known space-bounded private-coin protocols can also be simulated by qAM systems with the same space bound. In case of constant-space and log-space IP systems, the best known lower bounds are ASPACE(n) and EXP, respectively. We obtain better lower bounds for the corresponding qAM systems: Each language in NP has a constant-space (exp-time) qAM system, there is an NEXP-complete language having a constant-space qAM system, and each language in NEXP has a log-space qAM system.
Interactive proof systems form an important complexity model that has been central to many prominent results in computational complexity theory, such as those on probabilistically checkable proofs, hardness of approximation, and fundamental cryptographic primitives. In this thesis, we study the quantum-enhanced version of interactive proof systems, in which each party has access to quantum computing resources. We focus on its power and limitations, which lead us to the following results. (*) We provide an alternative and conceptually simpler proof of Jain et al.’s recent breakthrough result, which demonstrates that the expressive power of quantum interactive proof systems coincides with that of its classical counterpart, and therefore PSPACE. (*) We determine the complexity of several variants of quantum competing-prover interactive proof systems, which introduce zero-sum games into interactive proof systems. In particular, we prove that the complexity class of two-turn quantum refereed games coincides with PSPACE, answering an important open problem of Jain et al.’s. Our result suggests that a more general model called double quantum interactive proof systems coincides with PSPACE, which subsumes and unifies all previous results on short refereed games. (*) We contribute to the study of two-prover quantum Merlin-Arthur games (QMA(2)), which exhibit an intriguing tradeoff between an intrinsic quantum ingredient, entanglement, and computational power. We prove a PSPACE upper bound for a variant of QMA(2) that is to date the most general one known in PSPACE. We also provide a quasi-polynomial time algorithm for optimizing linear functions over separable states, giving an alternative to the one proposed by Brandao et al. Our main technical contribution behind the above results is the equilibrium value method for obtaining space-efficient algorithms for a class of optimization problems that arise naturally in quantum computation. We also contribute to QMA-complete problems, where we demonstrate that the “Non-Identity Check” problem remains QMA-complete on circuits of poly-logarithmic depths, improving upon polynomial depths from previous results.