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

Nonlocal games, compression theorems, and the arithmetical hierarchy

Hamoon Mousavi, Seyed Sajjad Nezhadi, Henry Yuen

Published Jun 9, 2022• 11 citations
arXivHTMLPDF

Abstract

We investigate the connection between the complexity of nonlocal games and the arithmetical hierarchy, a classification of languages according to the complexity of arithmetical formulas defining them. It was recently shown by Ji, Natarajan, Vidick, Wright and Yuen that deciding whether the (finite-dimensional) quantum value of a nonlocal game is 1 or at most 1/2 is complete for the class Σ1 (i.e., ). A result of Slofstra implies that deciding whether the commuting operator value of a nonlocal game is equal to 1 is complete for the class Π1 (i.e., coRE).

DOI
10.1145/3519935.3519949

Related papers

On the Complexity of Zero Gap MIP*

Hamoon Mousavi, Seyed Sajjad Nezhadi, Henry Yuen

The class $\mathsf{MIP}^*$ is the set of languages decidable by multiprover interactive proofs with quantum entangled provers. It was recently shown by Ji, Natarajan, Vidick, Wright and Yuen that $\mathsf{MIP}^*$ is equal to $\mathsf{RE}$, the set of recursively enumerable languages. In particular this shows that the complexity of approximating the quantum value of a non-local game $G$ is equivalent to the complexity of the Halting problem. In this paper we investigate the complexity of deciding whether the quantum value of a non-local game $G$ is exactly $1$. This problem corresponds to a complexity class that we call zero gap $\mathsf{MIP}^*$, denoted by $\mathsf{MIP}^*_0$, where there is no promise gap between the verifier's acceptance probabilities in the YES and NO cases. We prove that $\mathsf{MIP}^*_0$ extends beyond the first level of the arithmetical hierarchy (which includes $\mathsf{RE}$ and its complement $\mathsf{coRE}$), and in fact is equal to $Π_2^0$, the class of languages that can be decided by quantified formulas of the form $\forall y \, \exists z \, R(x,y,z)$. Combined with the previously known result that $\mathsf{MIP}^{co}_0$ (the commuting operator variant of $\mathsf{MIP}^*_0$) is equal to $\mathsf{coRE}$, our result further highlights the fascinating connection between various models of quantum multiprover interactive proofs and different classes in computability theory.

arXiv:2002.10490•Leibniz international proceedings in informatics•Jan 1, 2020•1 citation

On the Complexity of Zero Gap MIP*

Hamoon Mousavi, Seyed Sajjad Nezhadi, Henry Yuen

The class MIP^* is the set of languages decidable by multiprover interactive proofs with quantum entangled provers. It was recently shown by Ji, Natarajan, Vidick, Wright and Yuen that MIP^* is equal to RE, the set of recursively enumerable languages. In particular this shows that the complexity of approximating the quantum value of a non-local game G is equivalent to the complexity of the Halting problem. In this paper we investigate the complexity of deciding whether the quantum value of a non-local game G is exactly 1. This problem corresponds to a complexity class that we call zero gap MIP^*, denoted by MIP₀^*, where there is no promise gap between the verifier’s acceptance probabilities in the YES and NO cases. We prove that MIP₀^* extends beyond the first level of the arithmetical hierarchy (which includes RE and its complement coRE), and in fact is equal to Π₂⁰, the class of languages that can be decided by quantified formulas of the form ∀ y ∃ z R(x,y,z). Combined with the previously known result that MIP₀^{co} (the commuting operator variant of MIP₀^*) is equal to coRE, our result further highlights the fascinating connection between various models of quantum multiprover interactive proofs and different classes in computability theory.

•Jan 1, 2020•2 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

Survey on nonlocal games and operator space theory

Carlos Palazuelos, Thomas Vidick

This review article is concerned with a recently uncovered connection between operator spaces, a noncommutative extension of Banach spaces, and quantum nonlocality, a striking phenomenon which underlies many of the applications of quantum mechanics to information theory, cryptography, and algorithms. Using the framework of nonlocal games, we relate measures of the nonlocality of quantum mechanics to certain norms in the Banach and operator space categories. We survey recent results that exploit this connection to derive large violations of Bell inequalities, study the complexity of the classical and quantum values of games and their relation to Grothendieck inequalities, and quantify the nonlocality of different classes of entangled states.

arXiv:1512.00419•Journal of Mathematical Physics•Jan 1, 2016•56 citations

Complexity lower bounds for computing the approximately-commuting operator value of non-local games to high precision

Matthew Coudron, William Slofstra

We study the problem of approximating the commuting-operator value of a two-player non-local game. It is well-known that it is $\mathrm{NP}$-complete to decide whether the classical value of a non-local game is 1 or $1- ε$. Furthermore, as long as $ε$ is small enough, this result does not depend on the gap $ε$. In contrast, a recent result of Fitzsimons, Ji, Vidick, and Yuen shows that the complexity of computing the quantum value grows without bound as the gap $ε$ decreases. In this paper, we show that this also holds for the commuting-operator value of a game. Specifically, in the language of multi-prover interactive proofs, we show that the power of $\mathrm{MIP}^{co}(2,1,1,s)$ (proofs with two provers, one round, completeness probability $1$, soundness probability $s$, and commuting-operator strategies) can increase without bound as the gap $1-s$ gets arbitrarily small. Our results also extend naturally in two ways, to perfect zero-knowledge protocols, and to lower bounds on the complexity of computing the approximately-commuting value of a game. Thus we get lower bounds on the complexity class $\mathrm{PZK}$-$\mathrm{MIP}^{co}_δ(2,1,1,s)$ of perfect zero-knowledge multi-prover proofs with approximately-commuting operator strategies, as the gap $1-s$ gets arbitrarily small. While we do not know any computable time upper bound on the class $\mathrm{MIP}^{co}$, a result of the first author and Vidick shows that for $s = 1-1/\text{poly}(f(n))$ and $δ= 1/\text{poly}(f(n))$, the class $\mathrm{MIP}^{co}_δ(2,1,1,s)$, with constant communication from the provers, is contained in $\mathrm{TIME}(\exp(\text{poly}(f(n))))$. We give a lower bound of $\mathrm{coNTIME}(f(n))$ (ignoring constants inside the function) for this class, which is tight up to polynomial factors assuming the exponential time hypothesis.

arXiv:1905.11635•May 28, 2019•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.

•Jan 13, 2020•8 citations
We investigate the connection between the complexity of nonlocal games and the arithmetical hierarchy, a classification of languages according to the complexity of arithmetical formulas defining them. It was recently shown by Ji, Natarajan, Vidick, Wright and Yuen that deciding whether the (finite-dimensional) quantum value of a nonlocal game is 1 or at most 1/2 is complete for the class Σ1 (i.e., ). A result of Slofstra implies that deciding whether the commuting operator value of a nonlocal game is equal to 1 is complete for the class Π1 (i.e., coRE).
The class MIP∗\mathsf{MIP}^*MIP∗ is the set of languages decidable by multiprover interactive proofs with quantum entangled provers. It was recently shown by Ji, Natarajan, Vidick, Wright and Yuen that MIP∗\mathsf{MIP}^*MIP∗ is equal to RE\mathsf{RE}RE, the set of recursively enumerable languages. In particular this shows that the complexity of approximating the quantum value of a non-local game GGG is equivalent to the complexity of the Halting problem. In this paper we investigate the complexity of deciding whether the quantum value of a non-local game GGG is exactly 111. This problem corresponds to a complexity class that we call zero gap MIP∗\mathsf{MIP}^*MIP∗, denoted by MIP0∗\mathsf{MIP}^*_0MIP0∗​, where there is no promise gap between the verifier's acceptance probabilities in the YES and NO cases. We prove that MIP0∗\mathsf{MIP}^*_0MIP0∗​ extends beyond the first level of the arithmetical hierarchy (which includes RE\mathsf{RE}RE and its complement coRE\mathsf{coRE}coRE), and in fact is equal to Π20Π_2^0Π20​, the class of languages that can be decided by quantified formulas of the form ∀y ∃z R(x,y,z)\forall y \, \exists z \, R(x,y,z)∀y∃zR(x,y,z). Combined with the previously known result that MIP0co\mathsf{MIP}^{co}_0MIP0co​ (the commuting operator variant of MIP0∗\mathsf{MIP}^*_0MIP0∗​) is equal to coRE\mathsf{coRE}coRE, our result further highlights the fascinating connection between various models of quantum multiprover interactive proofs and different classes in computability theory.
The class MIP^* is the set of languages decidable by multiprover interactive proofs with quantum entangled provers. It was recently shown by Ji, Natarajan, Vidick, Wright and Yuen that MIP^* is equal to RE, the set of recursively enumerable languages. In particular this shows that the complexity of approximating the quantum value of a non-local game G is equivalent to the complexity of the Halting problem. In this paper we investigate the complexity of deciding whether the quantum value of a non-local game G is exactly 1. This problem corresponds to a complexity class that we call zero gap MIP^*, denoted by MIP₀^*, where there is no promise gap between the verifier’s acceptance probabilities in the YES and NO cases. We prove that MIP₀^* extends beyond the first level of the arithmetical hierarchy (which includes RE and its complement coRE), and in fact is equal to Π₂⁰, the class of languages that can be decided by quantified formulas of the form ∀ y ∃ z R(x,y,z). Combined with the previously known result that MIP₀^{co} (the commuting operator variant of MIP₀^*) is equal to coRE, our result further highlights the fascinating connection between various models of quantum multiprover interactive proofs and different classes in computability theory.
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.
This review article is concerned with a recently uncovered connection between operator spaces, a noncommutative extension of Banach spaces, and quantum nonlocality, a striking phenomenon which underlies many of the applications of quantum mechanics to information theory, cryptography, and algorithms. Using the framework of nonlocal games, we relate measures of the nonlocality of quantum mechanics to certain norms in the Banach and operator space categories. We survey recent results that exploit this connection to derive large violations of Bell inequalities, study the complexity of the classical and quantum values of games and their relation to Grothendieck inequalities, and quantify the nonlocality of different classes of entangled states.
We study the problem of approximating the commuting-operator value of a two-player non-local game. It is well-known that it is NP\mathrm{NP}NP-complete to decide whether the classical value of a non-local game is 1 or 1−ε1- ε1−ε. Furthermore, as long as εεε is small enough, this result does not depend on the gap εεε. In contrast, a recent result of Fitzsimons, Ji, Vidick, and Yuen shows that the complexity of computing the quantum value grows without bound as the gap εεε decreases. In this paper, we show that this also holds for the commuting-operator value of a game. Specifically, in the language of multi-prover interactive proofs, we show that the power of MIPco(2,1,1,s)\mathrm{MIP}^{co}(2,1,1,s)MIPco(2,1,1,s) (proofs with two provers, one round, completeness probability 111, soundness probability sss, and commuting-operator strategies) can increase without bound as the gap 1−s1-s1−s gets arbitrarily small. Our results also extend naturally in two ways, to perfect zero-knowledge protocols, and to lower bounds on the complexity of computing the approximately-commuting value of a game. Thus we get lower bounds on the complexity class PZK\mathrm{PZK}PZK-MIPδco(2,1,1,s)\mathrm{MIP}^{co}_δ(2,1,1,s)MIPδco​(2,1,1,s) of perfect zero-knowledge multi-prover proofs with approximately-commuting operator strategies, as the gap 1−s1-s1−s gets arbitrarily small. While we do not know any computable time upper bound on the class MIPco\mathrm{MIP}^{co}MIPco, a result of the first author and Vidick shows that for s=1−1/poly(f(n))s = 1-1/\text{poly}(f(n))s=1−1/poly(f(n)) and δ=1/poly(f(n))δ= 1/\text{poly}(f(n))δ=1/poly(f(n)), the class MIPδco(2,1,1,s)\mathrm{MIP}^{co}_δ(2,1,1,s)MIPδco​(2,1,1,s), with constant communication from the provers, is contained in TIME(exp⁡(poly(f(n))))\mathrm{TIME}(\exp(\text{poly}(f(n))))TIME(exp(poly(f(n)))). We give a lower bound of coNTIME(f(n))\mathrm{coNTIME}(f(n))coNTIME(f(n)) (ignoring constants inside the function) for this class, which is tight up to polynomial factors assuming the exponential time hypothesis.
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.