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:cs/0511017

Short Quantum Games

Gus Gutoski

Published Jan 1, 2005• 3 citations
arXivHTMLPDF

Abstract

In this thesis we introduce quantum refereed games, which are quantum interactive proof systems with two competing provers. We focus on a restriction of this model that we call "short quantum games" and we prove an upper bound and a lower bound on the expressive power of these games. For the lower bound, we prove that every language having an ordinary quantum interactive proof system also has a short quantum game. An important part of this proof is the establishment of a quantum measurement that reliably distinguishes between quantum states chosen from disjoint convex sets. For the upper bound, we show that certain types of quantum refereed games, including short quantum games, are decidable in deterministic exponential time by supplying a separation oracle for use with the ellipsoid method for convex feasibility.

DOI
10.11575/prism/175

Related papers

A study of one-turn quantum refereed games

Soumik Ghosh

This thesis studies one-turn quantum refereed games, which are abstract zero-sum games with two competing computationally unbounded quantum provers and a computationally bounded quantum referee. The provers send quantum states to the referee, who plugs the two states into his quantum circuit, measures the output of the circuit in the standard basis, and declares one of the two players as the winner depending on the outcome of the measurement. The complexity class QRG(1) comprises of those promise problems for which there exists a one-turn quantum refereed game such that one of the players wins with high probability for the yes-instances, and the other player wins with high probability for the no-instances, irrespective of the opponent’s strategy. QRG(1) is a generalization of QMA (or co-QMA), and can informally be viewed as QMA with a no-prover (or co-QMA with a yes-prover). \n \nWe have given a full characterization of QRG(1), starting with appropriate definitions and known results, and building on to two new results about this class. Previously, the best known upper bound on QRG(1) was PSPACE. We have proved that if one of the provers is completely classical, sending a classical probability distribution instead of a quantum state, the new class, which we name CQRG(1), is contained in Ǝ · PP (non- deterministic polynomial-time operator applied to the class PP). We have also defined another restricted version of QRG(1) where both provers send quantum states, but the referee measures one of the quantum states first, and plugs the classical outcome into the measurement, along with the other prover’s quantum state, into a quantum circuit, before measuring the output of the quantum circuit in the standard basis. The new class, which we name MQRG(1), is contained in P · PP (the probabilistic polynomial time operator applied to PP). Ǝ · PP is contained in P · PP, which is, in turn, contained in PSPACE. Hence, our results give better containments than PSPACE for restricted versions of QRG(1).

•Jul 13, 2020•0 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

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 Information and Variants of Interactive Proof Systems

Sarvagya Upadhyay

For nearly three decades, the model of interactive proof systems and its variants have been central to many important and exciting developments in computational complexity theory such as exact characterization of some well known complexity classes, development of probabilistically checkable proof systems and theory of hardness of approximation, and formalization of fundamental cryptographic primitives. \n \nOn the other hand, the theory of quantum information, which is primarily concerned with harnessing quantum mechanical features for algorithmic, cryptographic, and information processing tasks has found many applications. In the past three decades, quantum information has been used to develop unconditionally secure quantum cryptography protocols, efficient quantum algorithms for certain problems that are believed to be intractable in classical world, and communication efficient protocols. \n \nIn this thesis, we study the impact of quantum information on the models of interactive proof systems and their multi-prover variants. We study various quantum models and explore two questions. The first question we address pertains to the expressive power of such models with or without resource constraints. The second question is related to error reduction technique of such proof systems via parallel repetition. \n \nThe question related to the expressive power of models of quantum interactive proof systems and their variants lead us to the following results. \n \n(1) We show that the expressive power of quantum interactive proof systems is exactly PSPACE, the class of problems that can be solved by a polynomial-space deterministic Turing machines and that also admit a classical interactive proof systems. This result shows that in terms of complexity-theoretic characterization, both the models are equivalent. The result is obtained using an algorithmic technique known as the matrix multiplicative weights update method to solve a semidefinite program that characterizes the success probability of the quantum prover. \n\t \n(2) We show that polynomially many logarithmic-size unentangled quantum proofs are no more powerful than a classical proof if the verifier has the ability to process quantum information. This result follows from an observation that logarithmic-size quantum states can be efficiently represented classically and such classical representation can be used to efficiently generate the quantum state. \n\t \n(3) We also establish that the model of multi-prover quantum Merlin Arthur proof system, where the verifier is only allowed to apply nonadaptive unentangled measurement on each proof and then a quantum circuit on the classical outcomes, is no more powerful than QMA under the restriction that there are only polynomial number of outcomes per proof. This result follows from showing that such proof systems also admit a QMA verification procedure. \n \nThe question related to error reduction via parallel repetition lead us to following results on a class of two-prover one-round games with quantum provers and a class of multi-prover QMA proof systems. \n \n(1) We establish that for a certain class of two-prover one-round games known as XOR games, admit a perfect parallel repetition theorem in the following sense. When the provers play a collection of XOR games, an optimal strategy of the provers is to play each instance of the collection independently and optimally. In particular, the success probability of the quantum provers in the n-fold repetition of an XOR game G with quantum value w(G) is exactly (w(G))^n. \n\t \n(2) We show a parallel repetition theorem for two-prover one-round unique games. More specifically, we prove that if the quantum value of a unique game is 1-e, then the quantum value of n-fold repetition of the game is at most (1-e^2/49)^n. We also establish that for certain class of unique games, the quantum value of the n-fold repetition of the game is at most (1-e/4)^n. For the special case of XOR games, our proof technique gives an alternate proof of result mentioned above. \n\t \n3. Our final result on parallel repetition is concerned with SepQMA(m) proof systems, where the verifier receives m unentangled quantum proofs and the measurement operator corresponding to outcome "accept" is a fully separable operator. We give an alternate proof of a result of Harrow and Montanaro [HM10] that states that perfect parallel repetition theorem holds for such proof systems. \n \nThe first two results follow from the duality of semidefinite programs and the final result follows from cone programming duality.

•Aug 24, 2011•1 citation

On quantum interactive proofs with short messages

Attila Pereszlényi

This paper proves one of the open problem posed by Beigi et al. in arXiv:1004.0411v2. We consider quantum interactive proof systems where in the beginning the verifier and prover send messages to each other with the combined length of all messages being at most logarithmic (in the input length); and at the end the prover sends a polynomial-length message to the verifier. We show that this class has the same expressive power as QMA.

arXiv:1109.0964•Sep 5, 2011•2 citations

On the Power of Quantum Multi-Prover Interactive Proof Systems

Hirotada Kobayashi, Keiji Matsumoto

In this paper we introduce a quantum analogue of multi-prover interactive proof systems by naturally extending the model of single-prover quantum interactive proof systems defined by Watrous. It is proved that the class of languages having quantum multi-prover interactive proof systems is equal to NEXP. It implies that the quantum analogue has no gain to the classical counterpart in the setting of multi-prover interactive proof systems. Another interesting result shown in this paper is that, in case the prover does not have his private qubits, the class of languages having single-prover quantum interactive proof systems is also equal to NEXP. To our knowledge, our results give the first exact characterizations of a classical time complexity class in quantum computational terms.

•Feb 19, 2001•1 citation
In this thesis we introduce quantum refereed games, which are quantum interactive proof systems with two competing provers. We focus on a restriction of this model that we call "short quantum games" and we prove an upper bound and a lower bound on the expressive power of these games. For the lower bound, we prove that every language having an ordinary quantum interactive proof system also has a short quantum game. An important part of this proof is the establishment of a quantum measurement that reliably distinguishes between quantum states chosen from disjoint convex sets. For the upper bound, we show that certain types of quantum refereed games, including short quantum games, are decidable in deterministic exponential time by supplying a separation oracle for use with the ellipsoid method for convex feasibility.
This thesis studies one-turn quantum refereed games, which are abstract zero-sum games with two competing computationally unbounded quantum provers and a computationally bounded quantum referee. The provers send quantum states to the referee, who plugs the two states into his quantum circuit, measures the output of the circuit in the standard basis, and declares one of the two players as the winner depending on the outcome of the measurement. The complexity class QRG(1) comprises of those promise problems for which there exists a one-turn quantum refereed game such that one of the players wins with high probability for the yes-instances, and the other player wins with high probability for the no-instances, irrespective of the opponent’s strategy. QRG(1) is a generalization of QMA (or co-QMA), and can informally be viewed as QMA with a no-prover (or co-QMA with a yes-prover). \n \nWe have given a full characterization of QRG(1), starting with appropriate definitions and known results, and building on to two new results about this class. Previously, the best known upper bound on QRG(1) was PSPACE. We have proved that if one of the provers is completely classical, sending a classical probability distribution instead of a quantum state, the new class, which we name CQRG(1), is contained in Ǝ · PP (non- deterministic polynomial-time operator applied to the class PP). We have also defined another restricted version of QRG(1) where both provers send quantum states, but the referee measures one of the quantum states first, and plugs the classical outcome into the measurement, along with the other prover’s quantum state, into a quantum circuit, before measuring the output of the quantum circuit in the standard basis. The new class, which we name MQRG(1), is contained in P · PP (the probabilistic polynomial time operator applied to PP). Ǝ · PP is contained in P · PP, which is, in turn, contained in PSPACE. Hence, our results give better containments than PSPACE for restricted versions of QRG(1).
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.
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.
For nearly three decades, the model of interactive proof systems and its variants have been central to many important and exciting developments in computational complexity theory such as exact characterization of some well known complexity classes, development of probabilistically checkable proof systems and theory of hardness of approximation, and formalization of fundamental cryptographic primitives. \n \nOn the other hand, the theory of quantum information, which is primarily concerned with harnessing quantum mechanical features for algorithmic, cryptographic, and information processing tasks has found many applications. In the past three decades, quantum information has been used to develop unconditionally secure quantum cryptography protocols, efficient quantum algorithms for certain problems that are believed to be intractable in classical world, and communication efficient protocols. \n \nIn this thesis, we study the impact of quantum information on the models of interactive proof systems and their multi-prover variants. We study various quantum models and explore two questions. The first question we address pertains to the expressive power of such models with or without resource constraints. The second question is related to error reduction technique of such proof systems via parallel repetition. \n \nThe question related to the expressive power of models of quantum interactive proof systems and their variants lead us to the following results. \n \n(1) We show that the expressive power of quantum interactive proof systems is exactly PSPACE, the class of problems that can be solved by a polynomial-space deterministic Turing machines and that also admit a classical interactive proof systems. This result shows that in terms of complexity-theoretic characterization, both the models are equivalent. The result is obtained using an algorithmic technique known as the matrix multiplicative weights update method to solve a semidefinite program that characterizes the success probability of the quantum prover. \n\t \n(2) We show that polynomially many logarithmic-size unentangled quantum proofs are no more powerful than a classical proof if the verifier has the ability to process quantum information. This result follows from an observation that logarithmic-size quantum states can be efficiently represented classically and such classical representation can be used to efficiently generate the quantum state. \n\t \n(3) We also establish that the model of multi-prover quantum Merlin Arthur proof system, where the verifier is only allowed to apply nonadaptive unentangled measurement on each proof and then a quantum circuit on the classical outcomes, is no more powerful than QMA under the restriction that there are only polynomial number of outcomes per proof. This result follows from showing that such proof systems also admit a QMA verification procedure. \n \nThe question related to error reduction via parallel repetition lead us to following results on a class of two-prover one-round games with quantum provers and a class of multi-prover QMA proof systems. \n \n(1) We establish that for a certain class of two-prover one-round games known as XOR games, admit a perfect parallel repetition theorem in the following sense. When the provers play a collection of XOR games, an optimal strategy of the provers is to play each instance of the collection independently and optimally. In particular, the success probability of the quantum provers in the n-fold repetition of an XOR game G with quantum value w(G) is exactly (w(G))^n. \n\t \n(2) We show a parallel repetition theorem for two-prover one-round unique games. More specifically, we prove that if the quantum value of a unique game is 1-e, then the quantum value of n-fold repetition of the game is at most (1-e^2/49)^n. We also establish that for certain class of unique games, the quantum value of the n-fold repetition of the game is at most (1-e/4)^n. For the special case of XOR games, our proof technique gives an alternate proof of result mentioned above. \n\t \n3. Our final result on parallel repetition is concerned with SepQMA(m) proof systems, where the verifier receives m unentangled quantum proofs and the measurement operator corresponding to outcome "accept" is a fully separable operator. We give an alternate proof of a result of Harrow and Montanaro [HM10] that states that perfect parallel repetition theorem holds for such proof systems. \n \nThe first two results follow from the duality of semidefinite programs and the final result follows from cone programming duality.
In this paper we introduce a quantum analogue of multi-prover interactive proof systems by naturally extending the model of single-prover quantum interactive proof systems defined by Watrous. It is proved that the class of languages having quantum multi-prover interactive proof systems is equal to NEXP. It implies that the quantum analogue has no gain to the classical counterpart in the setting of multi-prover interactive proof systems. Another interesting result shown in this paper is that, in case the prover does not have his private qubits, the class of languages having single-prover quantum interactive proof systems is also equal to NEXP. To our knowledge, our results give the first exact characterizations of a classical time complexity class in quantum computational terms.