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:2302.04322 · ACM Symposium on Theory of Computing (STOC)

Quantum Free Games

Anand Natarajan, Tina Zhang

Published May 16, 2023• 5 citations
arXivHTMLPDF

Abstract

The complexity of free games with two or more classical players was essentially settled by Aaronson, Impagliazzo, and Moshkovitz (CCC’14). In the quantum world, there are two complexity classes that can be considered quantum analogues of classical free games: (1) AM*, the multiprover interactive proof class corresponding to free games with entangled players, and, somewhat less obviously, (2) BellQMA(2), the class of quantum Merlin-Arthur proof systems with two unentangled Merlins, whose proof states are separately measured by Arthur. In this work, we make significant progress towards a tight characterization of both of these classes. (1) We show a BellQMA(2) protocol for 3SAT on n variables, where the total amount of communication is Õ(√n). This answers an open question of Chen and Drucker (2010) and also shows, conditional on ETH, that the algorithm of Brandão, Christandl and Yard (STOC’11) for optimizing over separable states is tight up to logarithmic factors. (2) We show that AM* with nprovers = 2, question length O(1), and answer-length log(n) is equal to RE, i.e. that free entangled games with constant-sized questions are as powerful as general entangled games. (In contrast, Aaronson, Impagliazzo and Moshkovitz show that classical free games are much weaker than general classical games.) We show this using a question “hyper-compression” theorem that iteratively applies the introspection technique of Ji et al. (2020). Our result is a significant improvement over the headline result of Ji et al., whose MIP* protocol for the halting problem has (n)-sized questions and answers. (3) By the same techniques, we obtain a zero-gap AM* protocol for a Π2 complete language with constant-size questions and almost logarithmically (O(logn · log* n)) large answers, improving on the headline result of Mousavi, Nezhadi and Yuen (STOC’22). (4) Using a connection to the nonuniform complexity of the halting problem we show that any MIP* protocol for RE requires Ω(logn) bits of communication. It follows that our results in item 3 are optimal up to an O(log* n) factor, and that the gapless compression theorems of Mousavi, Nezhadi and Yuen are asymptotically optimal. We conjecture that these bounds can be saturated in the gapped case as well.

DOI
10.1145/3564246.3585208

Related papers

AM with Multiple Merlins

Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz

We introduce and study a new model of interactive proofs: AM(k), or Arthur-Merlin with k non-communicating Merlins. Unlike with the better-known MIP, here the assumption is that each Merlin receives an independent random challenge from Arthur. One motivation for this model (which we explore in detail) comes from the close analogies between it and the quantum complexity class QMA(k), but the AM(k) model is also natural in its own right. We illustrate the power of multiple Merlins by giving an AM(2) protocol for 3SAT, in which the Merlins' challenges and responses consist of only n1/2+o(1)bits each. Our protocol has the consequence that, assuming the Exponential Time Hypothesis (ETH), any algorithm for approximating a dense CSP with a polynomial-size alphabet must take n(log n)1-o(1)time. Algorithms nearly matching this lower bound are known, but their running times had never been previously explained. Brandao and Harrow have also recently used our 3SAT protocol to show quasipolynomial hardness for approximating the values of certain entangled games. In the other direction, we give a simple quasipolynomial-time approximation algorithm for free games, and use it to prove that, assuming the ETH, our 3SAT protocol is essentially optimal. More generally, we show that multiple Merlins never provide more than a polynomial advantage over one: that is, AM(k) = AM for all k=poly(n). The key to this result is a sub sampling theorem for free games, which follows from powerful results by Alon et al. And Barak et al. On sub sampling dense CSPs, and which says that the value of any free game can be closely approximated by the value of a logarithmic-sized random subgame.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2014•26 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. 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.

Leibniz international proceedings in informatics•Jan 1, 2015•3 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

Quasi-Polynomial Time Algorithms for Free Quantum Games in Bounded Dimension

Hyejung H. Jee, Carlo Sparaciari, Omar Fawzi +1 more

In a recent landmark result [Ji et al., arXiv:2001.04383 (2020)], it was shown that approximating the value of a two-player game is undecidable when the players are allowed to share quantum states of unbounded dimension. In this paper, we study the computational complexity of two-player games when the dimension of the quantum systems is bounded by T. More specifically, we give a semidefinite program of size exp(𝒪(T^{12}(log²(AT)+log(Q)log(AT))/ε²)) to compute additive ε-approximations on the value of two-player free games with T× T-dimensional quantum entanglement, where A and Q denote the number of answers and questions of the game, respectively. For fixed dimension T, this scales polynomially in Q and quasi-polynomially in A, thereby improving on previously known approximation algorithms for which worst-case run-time guarantees are at best exponential in Q and A. For the proof, we make a connection to the quantum separability problem and employ improved multipartite quantum de Finetti theorems with linear constraints that we derive via quantum entropy inequalities.

arXiv:2005.08883•Leibniz international proceedings in informatics•May 18, 2020•4 citations

MIP*=RE

Zhengfeng Ji, Anand Natarajan, Thomas Vidick +2 more

We show that the class MIP* of languages that can be decided by a classical verifier interacting with multiple all-powerful quantum provers sharing entanglement is equal to the class RE of recursively enumerable languages. Our proof builds upon the quantum low-degree test of (Natarajan and Vidick, FOCS 2018) and the classical low-individual degree test of (Ji, et al., 2020) by integrating recent developments from (Natarajan and Wright, FOCS 2019) and combining them with the recursive compression framework of (Fitzsimons et al., STOC 2019). An immediate byproduct of our result is that there is an efficient reduction from the Halting Problem to the problem of deciding whether a two-player nonlocal game has entangled value $1$ or at most $1/2$. Using a known connection, undecidability of the entangled value implies a negative answer to Tsirelson's problem: we show, by providing an explicit example, that the closure $C_{qa}$ of the set of quantum tensor product correlations is strictly included in the set $C_{qc}$ of quantum commuting correlations. Following work of (Fritz, Rev. Math. Phys. 2012) and (Junge et al., J. Math. Phys. 2011) our results provide a refutation of Connes' embedding conjecture from the theory of von Neumann algebras.

arXiv:2001.04383•Jan 13, 2020•25 citations

MIP*=RE

Zhengfeng Ji, Anand Natarajan, Thomas Vidick +2 more

We show that the class MIP* of languages that can be decided by a classical verifier interacting with multiple all-powerful quantum provers sharing entanglement is equal to the class RE of recursively enumerable languages. Our proof builds upon the quantum low-degree test of (Natarajan and Vidick, FOCS 2018) and the classical low-individual degree test of (Ji, et al., 2020) by integrating recent developments from (Natarajan and Wright, FOCS 2019) and combining them with the recursive compression framework of (Fitzsimons et al., STOC 2019). An immediate byproduct of our result is that there is an efficient reduction from the Halting Problem to the problem of deciding whether a two-player nonlocal game has entangled value $1$ or at most $1/2$. Using a known connection, undecidability of the entangled value implies a negative answer to Tsirelson's problem: we show, by providing an explicit example, that the closure $C_{qa}$ of the set of quantum tensor product correlations is strictly included in the set $C_{qc}$ of quantum commuting correlations. Following work of (Fritz, Rev. Math. Phys. 2012) and (Junge et al., J. Math. Phys. 2011) our results provide a refutation of Connes' embedding conjecture from the theory of von Neumann algebras.

•Jan 13, 2020•8 citations
The complexity of free games with two or more classical players was essentially settled by Aaronson, Impagliazzo, and Moshkovitz (CCC’14). In the quantum world, there are two complexity classes that can be considered quantum analogues of classical free games: (1) AM*, the multiprover interactive proof class corresponding to free games with entangled players, and, somewhat less obviously, (2) BellQMA(2), the class of quantum Merlin-Arthur proof systems with two unentangled Merlins, whose proof states are separately measured by Arthur. In this work, we make significant progress towards a tight characterization of both of these classes. (1) We show a BellQMA(2) protocol for 3SAT on n variables, where the total amount of communication is Õ(√n). This answers an open question of Chen and Drucker (2010) and also shows, conditional on ETH, that the algorithm of Brandão, Christandl and Yard (STOC’11) for optimizing over separable states is tight up to logarithmic factors. (2) We show that AM* with nprovers = 2, question length O(1), and answer-length log(n) is equal to RE, i.e. that free entangled games with constant-sized questions are as powerful as general entangled games. (In contrast, Aaronson, Impagliazzo and Moshkovitz show that classical free games are much weaker than general classical games.) We show this using a question “hyper-compression” theorem that iteratively applies the introspection technique of Ji et al. (2020). Our result is a significant improvement over the headline result of Ji et al., whose MIP* protocol for the halting problem has (n)-sized questions and answers. (3) By the same techniques, we obtain a zero-gap AM* protocol for a Π2 complete language with constant-size questions and almost logarithmically (O(logn · log* n)) large answers, improving on the headline result of Mousavi, Nezhadi and Yuen (STOC’22). (4) Using a connection to the nonuniform complexity of the halting problem we show that any MIP* protocol for RE requires Ω(logn) bits of communication. It follows that our results in item 3 are optimal up to an O(log* n) factor, and that the gapless compression theorems of Mousavi, Nezhadi and Yuen are asymptotically optimal. We conjecture that these bounds can be saturated in the gapped case as well.
We introduce and study a new model of interactive proofs: AM(k), or Arthur-Merlin with k non-communicating Merlins. Unlike with the better-known MIP, here the assumption is that each Merlin receives an independent random challenge from Arthur. One motivation for this model (which we explore in detail) comes from the close analogies between it and the quantum complexity class QMA(k), but the AM(k) model is also natural in its own right. We illustrate the power of multiple Merlins by giving an AM(2) protocol for 3SAT, in which the Merlins' challenges and responses consist of only n1/2+o(1)bits each. Our protocol has the consequence that, assuming the Exponential Time Hypothesis (ETH), any algorithm for approximating a dense CSP with a polynomial-size alphabet must take n(log n)1-o(1)time. Algorithms nearly matching this lower bound are known, but their running times had never been previously explained. Brandao and Harrow have also recently used our 3SAT protocol to show quasipolynomial hardness for approximating the values of certain entangled games. In the other direction, we give a simple quasipolynomial-time approximation algorithm for free games, and use it to prove that, assuming the ETH, our 3SAT protocol is essentially optimal. More generally, we show that multiple Merlins never provide more than a polynomial advantage over one: that is, AM(k) = AM for all k=poly(n). The key to this result is a sub sampling theorem for free games, which follows from powerful results by Alon et al. And Barak et al. On sub sampling dense CSPs, and which says that the value of any free game can be closely approximated by the value of a logarithmic-sized random subgame.
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.
In a recent landmark result [Ji et al., arXiv:2001.04383 (2020)], it was shown that approximating the value of a two-player game is undecidable when the players are allowed to share quantum states of unbounded dimension. In this paper, we study the computational complexity of two-player games when the dimension of the quantum systems is bounded by T. More specifically, we give a semidefinite program of size exp(𝒪(T^{12}(log²(AT)+log(Q)log(AT))/ε²)) to compute additive ε-approximations on the value of two-player free games with T× T-dimensional quantum entanglement, where A and Q denote the number of answers and questions of the game, respectively. For fixed dimension T, this scales polynomially in Q and quasi-polynomially in A, thereby improving on previously known approximation algorithms for which worst-case run-time guarantees are at best exponential in Q and A. For the proof, we make a connection to the quantum separability problem and employ improved multipartite quantum de Finetti theorems with linear constraints that we derive via quantum entropy inequalities.
We show that the class MIP* of languages that can be decided by a classical verifier interacting with multiple all-powerful quantum provers sharing entanglement is equal to the class RE of recursively enumerable languages. Our proof builds upon the quantum low-degree test of (Natarajan and Vidick, FOCS 2018) and the classical low-individual degree test of (Ji, et al., 2020) by integrating recent developments from (Natarajan and Wright, FOCS 2019) and combining them with the recursive compression framework of (Fitzsimons et al., STOC 2019). An immediate byproduct of our result is that there is an efficient reduction from the Halting Problem to the problem of deciding whether a two-player nonlocal game has entangled value 111 or at most 1/21/21/2. Using a known connection, undecidability of the entangled value implies a negative answer to Tsirelson's problem: we show, by providing an explicit example, that the closure CqaC_{qa}Cqa​ of the set of quantum tensor product correlations is strictly included in the set CqcC_{qc}Cqc​ of quantum commuting correlations. Following work of (Fritz, Rev. Math. Phys. 2012) and (Junge et al., J. Math. Phys. 2011) our results provide a refutation of Connes' embedding conjecture from the theory of von Neumann algebras.
We show that the class MIP* of languages that can be decided by a classical verifier interacting with multiple all-powerful quantum provers sharing entanglement is equal to the class RE of recursively enumerable languages. Our proof builds upon the quantum low-degree test of (Natarajan and Vidick, FOCS 2018) and the classical low-individual degree test of (Ji, et al., 2020) by integrating recent developments from (Natarajan and Wright, FOCS 2019) and combining them with the recursive compression framework of (Fitzsimons et al., STOC 2019). An immediate byproduct of our result is that there is an efficient reduction from the Halting Problem to the problem of deciding whether a two-player nonlocal game has entangled value 111 or at most 1/21/21/2. Using a known connection, undecidability of the entangled value implies a negative answer to Tsirelson's problem: we show, by providing an explicit example, that the closure CqaC_{qa}Cqa​ of the set of quantum tensor product correlations is strictly included in the set CqcC_{qc}Cqc​ of quantum commuting correlations. Following work of (Fritz, Rev. Math. Phys. 2012) and (Junge et al., J. Math. Phys. 2011) our results provide a refutation of Connes' embedding conjecture from the theory of von Neumann algebras.