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:2609.39318

A Dichotomy for MIP* in the Presence of Unital Noise

Yangjing Dong, Zhenyu Jiang, Minglong Qin, Penghui Yao, Haigang Zhou

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

A recent work studied quantum two-prover one-round proof systems $\mathsf{MIP}^ψ[\text{poly},O(1)]$. It showed that when $ψ$ is a noisy EPR state with quantum maximal correlation $ρ_{\max}(ψ)<1$, the resulting complexity class is equivalent to $\mathsf{NEXP}=\mathsf{MIP}$. In contrast, $\mathsf{MIP}^{\text{EPR}}[\text{poly},O(1)]=\mathsf{RE}$. Not all noise, however, decreases quantum maximal correlation. A basic example is dephasing noise: a dephased EPR pair retain quantum maximal correlation $1$. In this work, we remove the constant-answer restriction and establish a complete dichotomy for $\mathsf{MIP}^ψ[\text{poly},\text{poly}]$, where the provers share arbitrarily many copies of EPR pairs subject to unital noise. Equivalently, let $ψ$ be a fixed two-qubit state with maximally mixed marginals. We prove that \[\mathsf{MIP}^ψ[\text{poly},\text{poly}]=\mathsf{MIP} =\mathsf{NEXP},~\text{if $ψ$ is separable or $ρ_{\max}(ψ)<1$};\]\[\mathsf{MIP}^ψ[\text{poly},\text{poly}]=\mathsf{MIP}^ψ[\text{poly},O(1)]=\mathsf{RE},\text{if $ψ$ is entangled and $ρ_{\max}(ψ)=1$.}\] Beyond the complexity classification, our proof develops two techniques that may be useful more broadly in quantum information and quantum complexity. First, we introduce a positivity-preserving low-degree approximation framework for quantum measurements: instead of truncating positive operators directly in the Pauli basis, we approximate suitable square-root factorizations, simultaneously achieving low Pauli degree, positivity, and global control over an entire POVM. Second, we develop a new dimension-reduction method, called Pauli folding, for low-degree positive operators. Its key ingredient is an almost-multiplicativity theorem for randomized Pauli hashing, which allows noncommutative products, positivity, and normalization to survive compression with controlled error.

AI Summary

The paper asks how noise in shared EPR pairs changes the computational power of two-prover, one-round interactive proofs when provers may use arbitrarily many copies of a fixed resource state. Earlier results identified $\mathsf{NEXP}$ for constant-length answers when quantum maximal correlation is below one; this paper treats polynomial-length answers and the maximal-correlation-one boundary. For every fixed two-qubit state $\psi$ with maximally mixed marginals, it establishes a dichotomy: $\mathsf{MIP}^{\psi}[\mathrm{poly},\mathrm{poly}]=\mathsf{NEXP}$ if $\psi$ is separable or $\rho_{\max}(\psi)<1$, while the class equals $\mathsf{RE}$ if $\psi$ is entangled and $\rho_{\max}(\psi)=1$. The latter equality already holds with constant-length answers. Thus partially dephased EPR pairs retain $\mathsf{RE}$ power unless dephasing destroys entanglement. The $\mathsf{NEXP}$ upper bound combines collective POVM smoothing, low-degree approximation of square-root measurement blocks, randomized “Pauli folding,” and polar-decomposition rounding. For fixed error and resource, approximation requires $D=\mathrm{poly}(t)$ copies and Pauli degree $k=\mathrm{poly}(\log t)$, where $t$ is the answer-alphabet size; low-degree coefficients yield exponentially sized, exponentially verifiable certificates. Folding approximately preserves multiplication with dimension-independent error polynomial in degree. At maximal correlation one, local unitaries reduce the resource to a dephased EPR state with coherence $\lambda>0$. A Hamming-code construction and bilateral Pauli twirling extract an unflagged exact $m$-EPR component of weight at least $\lambda^2$, using $2^m-1+2m$ copies. Parallel repetition and OR amplification then establish $\mathsf{RE}$. The classification concerns fixed, known-parameter two-qubit resources with maximally mixed marginals; it does not classify general bipartite noise or provide efficient entanglement extraction.

Little sign of AI-generated textAI use disclosed
OpenAI's GPT-5.6 and GPT-6 Astra provided valuable help in verifying our ideas and improving the writing.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

The Computational Advantage of MIP* Vanishes in the Presence of Noise

Yangjing Dong, Honghao Fu, Anand Natarajan +3 more

The class MIP* of quantum multiprover interactive proof systems with entanglement is much more powerful than its classical counterpart MIP [ 8 , 31 , 32 ]: while MIP = NEXP, the quantum class MIP * is equal to RE, a class including the halting problem. This is because the provers in MIP * can share unbounded quantum entanglement. However, recent works [ 53 , 54 ] have shown that this advantage is significantly reduced if the provers’ shared state contains noise. This article attempts to exactly characterize the effect of noise on the computational power of quantum multiprover interactive proof systems. We investigate the quantum two-prover one-round interactive system MIP * [poly, O (1)], where the verifier sends polynomially many bits to the provers and the provers send back constantly many bits. We show that noise completely destroys the computational advantage given by shared entanglement in this model. Specifically, we show that if the provers are allowed to share arbitrarily many EPR states, where each EPR state is affected by an arbitrarily small constant amount of noise, the resulting complexity class is equivalent to NEXP = MIP. This improves significantly on the previous best-known bound of NEEEXP (nondeterministic triply exponential time) [ 53 ]. We also show that this collapse in power is due to noise, rather than the O (1) answer size, by showing that allowing for noiseless EPR states gives the class the full power of RE = MIP * [poly, poly]. Along the way, we develop two technical tools of independent interest. First, we give a new, deterministic tester for the positivity of an exponentially large matrix, provided that it has a low-degree Fourier decomposition in terms of Pauli matrices. Secondly, we develop a new invariance principle for smooth matrix functions having bounded third-order Fréchet derivatives or which are Lipschitz continuous.

arXiv:2312.04360•Journal of the ACM•Aug 16, 2025•12 citations

A doubly exponential upper bound on noisy EPR states for binary games

Penghui Yao

This paper initiates the study of a class of entangled games, mono-state games, denoted by $(G,ψ)$, where $G$ is a two-player one-round game and $ψ$ is a bipartite state independent of the game $G$. In the mono-state game $(G,ψ)$, the players are only allowed to share arbitrary copies of $ψ$. This paper provides a doubly exponential upper bound on the copies of $ψ$ for the players to approximate the value of the game to an arbitrarily small constant precision for any mono-state binary game $(G,ψ)$, if $ψ$ is a noisy EPR state, which is a two-qubit state with completely mixed states as marginals and maximal correlation less than $1$. In particular, it includes $(1-ε)|Ψ\rangle\langleΨ|+ε\frac{I_2}{2}\otimes\frac{I_2}{2}$, an EPR state with an arbitrary depolarizing noise $ε>0$.The structure of the proofs is built the recent framework about the decidability of the non-interactive simulation of joint distributions, which is completely different from all previous optimization-based approaches or "Tsirelson's problem"-based approaches. This paper develops a series of new techniques about the Fourier analysis on matrix spaces and proves a quantum invariance principle and a hypercontractive inequality of random operators. This novel approach provides a new angle to study the decidability of the complexity class MIP$^*$, a longstanding open problem in quantum complexity theory.

arXiv:1904.08832•Apr 18, 2019•4 citations

Two Prover Perfect Zero Knowledge for MIP*

Kieran Mastel, William Slofstra

The recent MIP*=RE theorem of Ji, Natarajan, Vidick, Wright, and Yuen shows that the complexity class MIP* of multiprover proof systems with entangled provers contains all recursively enumerable languages. Prior work of Grilo, Slofstra, and Yuen [FOCS '19] further shows (via a technique called simulatable codes) that every language in MIP* has a perfect zero knowledge (PZK) MIP* protocol. The MIP*=RE theorem uses two-prover one-round proof systems, and hence such systems are complete for MIP*. However, the construction in Grilo, Slofstra, and Yuen uses six provers, and there is no obvious way to get perfect zero knowledge with two provers via simulatable codes. This leads to a natural question: are there two-prover PZK-MIP* protocols for all of MIP*? In this paper, we show that every language in MIP* has a two-prover one-round PZK-MIP* protocol, answering the question in the affirmative. For the proof, we use a new method based on a key consequence of the MIP*=RE theorem, which is that every MIP* protocol can be turned into a family of boolean constraint system (BCS) nonlocal games. This makes it possible to work with MIP* protocols as boolean constraint systems, and in particular allows us to use a variant of a construction due to Dwork, Feige, Kilian, Naor, and Safra [Crypto '92] which gives a classical MIP protocol for 3SAT with perfect zero knowledge. To show quantum soundness of this classical construction, we develop a toolkit for analyzing quantum soundness of reductions between BCS games, which we expect to be useful more broadly. This toolkit also applies to commuting operator strategies, and our argument shows that every language with a commuting operator BCS protocol has a two prover PZK commuting operator protocol.

arXiv:2404.00926•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•14 citations

Quantum soundness of testing tensor codes

Zhengfeng Ji, Anand Natarajan, Thomas Vidick +2 more

Quantum soundness of testing tensor codes, Discrete Analysis 2022:17, 73 pp. This paper proves an essential component of a major recent result in complexity theory, known as the MIP*=RE theorem, which was proved by the same authors. MIP* and RE are two important complexity classes with completely different definitions, and the fact that they are equal is a very deep and surprising fact, with implications not just for complexity theory but also for parts of pure mathematics, and in particular operator theory. RE is the class of recursively enumerable functions -- that is, Boolean functions $f$ for which there is an algorithm such that if $f(x)=1$, then the algorithm can establish this in finite time. Here there are no restrictions on how long the algorithm takes or how much memory it uses. The definition of MIP* is quite a lot less straightforward, but can be understood in a sequence of steps. First, the class P consists of Boolean functions that can be computed in polynomial time (in the length of the input). NP consists of Boolean functions $f:\{0,1\}^n\to\{0,1\}$ such that if $f(x)=1$ then this fact can be _verified_ in polynomial time. That is, for each $n$ there is some $m$ that depends polynomially on $n$ and a function $g:\{0,1\}^{n+m}\to\{0,1\}$ in $P$ such that for each $x$, $f(x)=1$ if and only if there exists $y\in\{0,1\}^m$ with $g(x,y)=1$. We can think of such a $y$ as a "certificate" that guarantees that $f(x)=1$. (For example, if $f$ detects whether there is a Hamilton cycle in a graph, $g$ could be the function that takes a graph and an ordering on the vertices and outputs 1 if and only if that ordering defines a Hamilton cycle.) We can think of NP in a slightly different way as a collaboration between two agents, a powerful prover and a much less powerful verifier. They can collaborate as follows. The verifier presents the prover with a string $x$. The prover, unconstrained by any time or space limitations, responds with a string $y$. The verifier then calculates $g(x,y)$. If $g(x,y)=1$ then $f(x)=1$ and otherwise $f(x)=0$. For this to work two properties of their protocol are needed. The first is _completeness_: that whenever $f(x)=1$ there is a suitable certificate $y$. The second is _soundness_: that whenever $f(x)=0$ there is no such certificate. We can imagine this as a situation where the prover always wants to convince the verifier that $f(x)=1$, regardless of whether that is actually true. If the protocol is both complete and sound, then in fact the verifier will always correctly determine the value of $f$. To obtain the class IP (which stands for "interactive proof") we modify the above situation slightly, allowing the verifier access to a string of random bits, allowing communication between the verifier and prover to take place over several rounds, and requiring at the end only that that verifier is _almost_ certain that $f(x)=1$. Rather than give a formal definition, we present here an example due to Goldreich, Micali and Wigderson of a protocol that shows that non-isomorphism of graphs is in IP (which is not obvious, since while it is easy to see that graph isomorphism belongs to NP, there is no particular reason to suppose that graph _non_-isomorphism does). The idea is simple: the verifier takes two graphs $G$ and $H$ and sends to the prover a sequence $(K_1,\dots,K_m)$ of graphs, where each $K_i$ is obtained by randomly picking one of $G$ and $H$ and randomly permuting its vertices. The prover then sends back a 01-sequence $x\in\{0,1\}^m$. Finally, the verifier judges $G$ and $H$ to be non-isomorphic if $x_i=1$ for all and only those $i$ for which $K_i$ is isomorphic to $G$ (which the verifier knows). If $G$ and $H$ are indeed non-isomorphic, the prover can ensure that the verifier will agree that this is the case, but otherwise the prover has no idea which $K_i$ came from which graph and can therefore do so with probability only $2^{-m}$. It turns out that IP is equal to the complexity class PSPACE, which consists of functions that can be computed with only a polynomial amount of memory (but with no restriction on time). This is already an indication of the power of interactive proofs. However, it turns out that with some simple modifications they can be made considerably more powerful. One modification is to have more than one prover and not to allow the provers to communicate. This makes it harder for the provers to fool the verifier if $f(x)\ne 1$, since the verifier can be on the lookout for inconsistencies in their answers. The resulting class MIP (for "multiprover interactive proof") turns out to be equivalent to the complexity class NEXPTIME, which is like NP except that the verification is now allowed to take an exponential amount of time, so it is a huge class. Finally, we come to MIP*. Here quantum entanglement comes into play. Before the computation starts the provers are allowed to share entangled quantum bits, which have the potential to create correlations between their responses to the verifier. Potentially at least, this greatly enlarges the set of possible strategies for the provers, and therefore greatly enlarges the class of functions that can be computed. And this potential turns out to be realized: the statement that MIP*=RE is telling us the extraordinary fact that every recursively enumerable function belongs to MIP*. That is, if you are given a Turing machine and asked whether it halts, there is some protocol involving multiple provers using entangled bits such that if the Turing machine halts, the provers will convince the verifer of that fact, and otherwise the verifier will be almost certain that it does not halt. Note that there is no algorithm that will establish (in general) that a Turing machine does _not_ halt, but the fact that MIP*=RE tells us that if we are satisfied with being _almost_ certain that it does not halt, then for each instance of the problem there is an MIP* protocol that will give that to us. This paper concerns a particular problem from coding theory. A _linear code_ is a subspace $\mathcal C$ of $\mathbb F^n$ for some finite field $\mathbb F$ such that any two elements, or _codewords_, differ in at least $d$ coordinates. (The bigger $d$ is, the better the code.) Given such a code, the tensor code $\mathcal C^{\otimes m}$ is defined to be the set of all functions $g:[n]^m\to\mathbb F$ (where $[n]$ denotes the set $\{1,2,\dots,n\}$) such that if you fix all but one coordinate, then the resulting restriction of $g$, regarded as an element of $\mathbb F^n$ in the obvious way, is an element of $\mathbb C$. The corresponding computational problem is to determine whether a given function $g$ belongs to $\mathcal C^{\otimes m}$. Such codes are called _locally testable_ because there is a simple protocol that allows an interactive proof based on only local information. It works as follows. The verifier chooses a random element $x$ of $[n]^m$, the prover responds with an element $u\in\mathbb F$, the verifier then chooses a random $j\in[n]$, and the prover responds with a codeword $w$ from $\mathcal C$. If $w_j=u$, then the verifier judges $g$ to belong to $\mathcal C^{\otimes m}$. Note that if $g$ does indeed belong to $\mathcal C^{\otimes m}$, then all the prover has to do is choose the word obtained from the line of all points $y$ such that $y_i=x_i$ when $i\ne j$. Soundness of the protocol is less obvious (and requires a further technical condition on the code called interpolability) but follows quickly from a result of Babai, Fortnow and Lund. The main result of this paper can be thought of as saying that two interative provers cannot do significantly better for this problem if they are allowed to use entangled bits than if they are restricted to classical computation. For more details about tensor codes, this result, and how it relates to the MIP*=RE theorem, the extensive introduction to the paper itself is highly recommended.

•Dec 1, 2022•3 citations

Quantum soundness of the classical low individual degree test

Zhengfeng Ji, Anand Natarajan, Thomas Vidick +2 more

Low degree tests play an important role in classical complexity theory, serving as basic ingredients in foundational results such as $\mathsf{MIP} = \mathsf{NEXP}$ [BFL91] and the PCP theorem [AS98,ALM+98]. Over the last ten years, versions of these tests which are sound against quantum provers have found increasing applications to the study of nonlocal games and the complexity class~$\mathsf{MIP}^*$. The culmination of this line of work is the result $\mathsf{MIP}^* = \mathsf{RE}$ [arXiv:2001.04383]. One of the key ingredients in the first reported proof of $\mathsf{MIP}^* = \mathsf{RE}$ is a two-prover variant of the low degree test, initially shown to be sound against multiple quantum provers in [arXiv:1302.1242]. Unfortunately a mistake was recently discovered in the latter result, invalidating the main result of [arXiv:1302.1242] as well as its use in subsequent works, including [arXiv:2001.04383]. We analyze a variant of the low degree test called the low individual degree test. Our main result is that the two-player version of this test is sound against quantum provers. This soundness result is sufficient to re-derive several bounds on~$\mathsf{MIP}^*$ that relied on [arXiv:1302.1242], including $\mathsf{MIP}^* = \mathsf{RE}$.

arXiv:2009.12982•Sep 27, 2020•24 citations

MIPco=coRE

J. F. Lin

In 2020, a landmark result by Ji, Natarajan, Vidick, Wright, and Yuen showed that MIP*, the class of languages that can be decided by a classical verifier interacting with multiple computationally unbounded provers sharing entanglement in the tensor product model, is equal to RE. We show that the class MIPco, a complexity class defined similarly to MIP* except with provers sharing the commuting operator model of entanglement, is equal to the class coRE. This shows that giving the provers two different models of entanglement leads to two completely different computational powers for interactive proof systems. Our proof builds upon the compression theorem used in the proof of MIP*=RE, and we use the tracially embeddable strategies framework to show that the same compression procedure in MIP* =RE also has the same desired property in the commuting operator setting. We also give a more streamlined proof of the compression theorem for non-local games by incorporating the synchronous framework used by Mousavi et al. [STOC 2022], as well as the improved Pauli basis test introduced by de la Salle [ArXiv:2204.07084]. We introduce a new equivalence condition for RE/coRE-complete problems, which we call the weakly compressible condition. We show that both MIP* and MIPco satisfy this condition through the compression theorem, and thereby establish that the uncomputability for MIP* and MIPco can be proved under a unified framework (despite these two complexity classes being different). Notably, this approach also gives an alternative proof of the MIP*=RE theorem, which does not rely on the preservation of the entanglement bound. In addition to non-local games, this new condition could also potentially be applicable to other decision problems.

arXiv:2510.07162•Oct 8, 2025•14 citations
A recent work studied quantum two-prover one-round proof systems MIPψ[poly,O(1)]\mathsf{MIP}^ψ[\text{poly},O(1)]MIPψ[poly,O(1)]. It showed that when ψψψ is a noisy EPR state with quantum maximal correlation ρmax⁡(ψ)<1ρ_{\max}(ψ)<1ρmax​(ψ)<1, the resulting complexity class is equivalent to NEXP=MIP\mathsf{NEXP}=\mathsf{MIP}NEXP=MIP. In contrast, MIPEPR[poly,O(1)]=RE\mathsf{MIP}^{\text{EPR}}[\text{poly},O(1)]=\mathsf{RE}MIPEPR[poly,O(1)]=RE. Not all noise, however, decreases quantum maximal correlation. A basic example is dephasing noise: a dephased EPR pair retain quantum maximal correlation 111. In this work, we remove the constant-answer restriction and establish a complete dichotomy for MIPψ[poly,poly]\mathsf{MIP}^ψ[\text{poly},\text{poly}]MIPψ[poly,poly], where the provers share arbitrarily many copies of EPR pairs subject to unital noise. Equivalently, let ψψψ be a fixed two-qubit state with maximally mixed marginals. We prove that [\mathsf{MIP}^ψ[\text{poly},\text{poly}]=\mathsf{MIP} =\mathsf{NEXP},~\text{if ψψψ is separable or ρmax⁡(ψ)<1ρ_{\max}(ψ)<1ρmax​(ψ)<1};][\mathsf{MIP}^ψ[\text{poly},\text{poly}]=\mathsf{MIP}^ψ[\text{poly},O(1)]=\mathsf{RE},\text{if ψψψ is entangled and ρmax⁡(ψ)=1ρ_{\max}(ψ)=1ρmax​(ψ)=1.}] Beyond the complexity classification, our proof develops two techniques that may be useful more broadly in quantum information and quantum complexity. First, we introduce a positivity-preserving low-degree approximation framework for quantum measurements: instead of truncating positive operators directly in the Pauli basis, we approximate suitable square-root factorizations, simultaneously achieving low Pauli degree, positivity, and global control over an entire POVM. Second, we develop a new dimension-reduction method, called Pauli folding, for low-degree positive operators. Its key ingredient is an almost-multiplicativity theorem for randomized Pauli hashing, which allows noncommutative products, positivity, and normalization to survive compression with controlled error.
The paper asks how noise in shared EPR pairs changes the computational power of two-prover, one-round interactive proofs when provers may use arbitrarily many copies of a fixed resource state. Earlier results identified NEXP\mathsf{NEXP}NEXP for constant-length answers when quantum maximal correlation is below one; this paper treats polynomial-length answers and the maximal-correlation-one boundary.
For every fixed two-qubit state ψ\psiψ with maximally mixed marginals, it establishes a dichotomy: MIPψ[poly,poly]=NEXP\mathsf{MIP}^{\psi}[\mathrm{poly},\mathrm{poly}]=\mathsf{NEXP}MIPψ[poly,poly]=NEXP if ψ\psiψ is separable or ρmax⁡(ψ)<1\rho_{\max}(\psi)<1ρmax​(ψ)<1, while the class equals RE\mathsf{RE}RE if ψ\psiψ is entangled and ρmax⁡(ψ)=1\rho_{\max}(\psi)=1ρmax​(ψ)=1. The latter equality already holds with constant-length answers. Thus partially dephased EPR pairs retain RE\mathsf{RE}RE power unless dephasing destroys entanglement.
The NEXP\mathsf{NEXP}NEXP upper bound combines collective POVM smoothing, low-degree approximation of square-root measurement blocks, randomized “Pauli folding,” and polar-decomposition rounding. For fixed error and resource, approximation requires D=poly(t)D=\mathrm{poly}(t)D=poly(t) copies and Pauli degree k=poly(log⁡t)k=\mathrm{poly}(\log t)k=poly(logt), where ttt is the answer-alphabet size; low-degree coefficients yield exponentially sized, exponentially verifiable certificates. Folding approximately preserves multiplication with dimension-independent error polynomial in degree.
At maximal correlation one, local unitaries reduce the resource to a dephased EPR state with coherence λ>0\lambda>0λ>0. A Hamming-code construction and bilateral Pauli twirling extract an unflagged exact mmm-EPR component of weight at least λ2\lambda^2λ2, using 2m−1+2m2^m-1+2m2m−1+2m copies. Parallel repetition and OR amplification then establish RE\mathsf{RE}RE. The classification concerns fixed, known-parameter two-qubit resources with maximally mixed marginals; it does not classify general bipartite noise or provide efficient entanglement extraction.
The class MIP* of quantum multiprover interactive proof systems with entanglement is much more powerful than its classical counterpart MIP [ 8 , 31 , 32 ]: while MIP = NEXP, the quantum class MIP * is equal to RE, a class including the halting problem. This is because the provers in MIP * can share unbounded quantum entanglement. However, recent works [ 53 , 54 ] have shown that this advantage is significantly reduced if the provers’ shared state contains noise. This article attempts to exactly characterize the effect of noise on the computational power of quantum multiprover interactive proof systems. We investigate the quantum two-prover one-round interactive system MIP * [poly, O (1)], where the verifier sends polynomially many bits to the provers and the provers send back constantly many bits. We show that noise completely destroys the computational advantage given by shared entanglement in this model. Specifically, we show that if the provers are allowed to share arbitrarily many EPR states, where each EPR state is affected by an arbitrarily small constant amount of noise, the resulting complexity class is equivalent to NEXP = MIP. This improves significantly on the previous best-known bound of NEEEXP (nondeterministic triply exponential time) [ 53 ]. We also show that this collapse in power is due to noise, rather than the O (1) answer size, by showing that allowing for noiseless EPR states gives the class the full power of RE = MIP * [poly, poly]. Along the way, we develop two technical tools of independent interest. First, we give a new, deterministic tester for the positivity of an exponentially large matrix, provided that it has a low-degree Fourier decomposition in terms of Pauli matrices. Secondly, we develop a new invariance principle for smooth matrix functions having bounded third-order Fréchet derivatives or which are Lipschitz continuous.
This paper initiates the study of a class of entangled games, mono-state games, denoted by (G,ψ)(G,ψ)(G,ψ), where GGG is a two-player one-round game and ψψψ is a bipartite state independent of the game GGG. In the mono-state game (G,ψ)(G,ψ)(G,ψ), the players are only allowed to share arbitrary copies of ψψψ. This paper provides a doubly exponential upper bound on the copies of ψψψ for the players to approximate the value of the game to an arbitrarily small constant precision for any mono-state binary game (G,ψ)(G,ψ)(G,ψ), if ψψψ is a noisy EPR state, which is a two-qubit state with completely mixed states as marginals and maximal correlation less than 111. In particular, it includes (1−ε)∣Ψ⟩⟨Ψ∣+εI22⊗I22(1-ε)|Ψ\rangle\langleΨ|+ε\frac{I_2}{2}\otimes\frac{I_2}{2}(1−ε)∣Ψ⟩⟨Ψ∣+ε2I2​​⊗2I2​​, an EPR state with an arbitrary depolarizing noise ε>0ε>0ε>0.The structure of the proofs is built the recent framework about the decidability of the non-interactive simulation of joint distributions, which is completely different from all previous optimization-based approaches or "Tsirelson's problem"-based approaches. This paper develops a series of new techniques about the Fourier analysis on matrix spaces and proves a quantum invariance principle and a hypercontractive inequality of random operators. This novel approach provides a new angle to study the decidability of the complexity class MIP∗^*∗, a longstanding open problem in quantum complexity theory.
The recent MIP*=RE theorem of Ji, Natarajan, Vidick, Wright, and Yuen shows that the complexity class MIP* of multiprover proof systems with entangled provers contains all recursively enumerable languages. Prior work of Grilo, Slofstra, and Yuen [FOCS '19] further shows (via a technique called simulatable codes) that every language in MIP* has a perfect zero knowledge (PZK) MIP* protocol. The MIP*=RE theorem uses two-prover one-round proof systems, and hence such systems are complete for MIP*. However, the construction in Grilo, Slofstra, and Yuen uses six provers, and there is no obvious way to get perfect zero knowledge with two provers via simulatable codes. This leads to a natural question: are there two-prover PZK-MIP* protocols for all of MIP*? In this paper, we show that every language in MIP* has a two-prover one-round PZK-MIP* protocol, answering the question in the affirmative. For the proof, we use a new method based on a key consequence of the MIP*=RE theorem, which is that every MIP* protocol can be turned into a family of boolean constraint system (BCS) nonlocal games. This makes it possible to work with MIP* protocols as boolean constraint systems, and in particular allows us to use a variant of a construction due to Dwork, Feige, Kilian, Naor, and Safra [Crypto '92] which gives a classical MIP protocol for 3SAT with perfect zero knowledge. To show quantum soundness of this classical construction, we develop a toolkit for analyzing quantum soundness of reductions between BCS games, which we expect to be useful more broadly. This toolkit also applies to commuting operator strategies, and our argument shows that every language with a commuting operator BCS protocol has a two prover PZK commuting operator protocol.
Quantum soundness of testing tensor codes, Discrete Analysis 2022:17, 73 pp. This paper proves an essential component of a major recent result in complexity theory, known as the MIP*=RE theorem, which was proved by the same authors. MIP* and RE are two important complexity classes with completely different definitions, and the fact that they are equal is a very deep and surprising fact, with implications not just for complexity theory but also for parts of pure mathematics, and in particular operator theory. RE is the class of recursively enumerable functions -- that is, Boolean functions fff for which there is an algorithm such that if f(x)=1f(x)=1f(x)=1, then the algorithm can establish this in finite time. Here there are no restrictions on how long the algorithm takes or how much memory it uses. The definition of MIP* is quite a lot less straightforward, but can be understood in a sequence of steps. First, the class P consists of Boolean functions that can be computed in polynomial time (in the length of the input). NP consists of Boolean functions f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} such that if f(x)=1f(x)=1f(x)=1 then this fact can be _verified_ in polynomial time. That is, for each nnn there is some mmm that depends polynomially on nnn and a function g:{0,1}n+m→{0,1}g:\{0,1\}^{n+m}\to\{0,1\}g:{0,1}n+m→{0,1} in PPP such that for each xxx, f(x)=1f(x)=1f(x)=1 if and only if there exists y∈{0,1}my\in\{0,1\}^my∈{0,1}m with g(x,y)=1g(x,y)=1g(x,y)=1. We can think of such a yyy as a "certificate" that guarantees that f(x)=1f(x)=1f(x)=1. (For example, if fff detects whether there is a Hamilton cycle in a graph, ggg could be the function that takes a graph and an ordering on the vertices and outputs 1 if and only if that ordering defines a Hamilton cycle.) We can think of NP in a slightly different way as a collaboration between two agents, a powerful prover and a much less powerful verifier. They can collaborate as follows. The verifier presents the prover with a string xxx. The prover, unconstrained by any time or space limitations, responds with a string yyy. The verifier then calculates g(x,y)g(x,y)g(x,y). If g(x,y)=1g(x,y)=1g(x,y)=1 then f(x)=1f(x)=1f(x)=1 and otherwise f(x)=0f(x)=0f(x)=0. For this to work two properties of their protocol are needed. The first is _completeness_: that whenever f(x)=1f(x)=1f(x)=1 there is a suitable certificate yyy. The second is _soundness_: that whenever f(x)=0f(x)=0f(x)=0 there is no such certificate. We can imagine this as a situation where the prover always wants to convince the verifier that f(x)=1f(x)=1f(x)=1, regardless of whether that is actually true. If the protocol is both complete and sound, then in fact the verifier will always correctly determine the value of fff. To obtain the class IP (which stands for "interactive proof") we modify the above situation slightly, allowing the verifier access to a string of random bits, allowing communication between the verifier and prover to take place over several rounds, and requiring at the end only that that verifier is _almost_ certain that f(x)=1f(x)=1f(x)=1. Rather than give a formal definition, we present here an example due to Goldreich, Micali and Wigderson of a protocol that shows that non-isomorphism of graphs is in IP (which is not obvious, since while it is easy to see that graph isomorphism belongs to NP, there is no particular reason to suppose that graph _non_-isomorphism does). The idea is simple: the verifier takes two graphs GGG and HHH and sends to the prover a sequence (K1,…,Km)(K_1,\dots,K_m)(K1​,…,Km​) of graphs, where each KiK_iKi​ is obtained by randomly picking one of GGG and HHH and randomly permuting its vertices. The prover then sends back a 01-sequence x∈{0,1}mx\in\{0,1\}^mx∈{0,1}m. Finally, the verifier judges GGG and HHH to be non-isomorphic if xi=1x_i=1xi​=1 for all and only those iii for which KiK_iKi​ is isomorphic to GGG (which the verifier knows). If GGG and HHH are indeed non-isomorphic, the prover can ensure that the verifier will agree that this is the case, but otherwise the prover has no idea which KiK_iKi​ came from which graph and can therefore do so with probability only 2−m2^{-m}2−m. It turns out that IP is equal to the complexity class PSPACE, which consists of functions that can be computed with only a polynomial amount of memory (but with no restriction on time). This is already an indication of the power of interactive proofs. However, it turns out that with some simple modifications they can be made considerably more powerful. One modification is to have more than one prover and not to allow the provers to communicate. This makes it harder for the provers to fool the verifier if f(x)≠1f(x)\ne 1f(x)=1, since the verifier can be on the lookout for inconsistencies in their answers. The resulting class MIP (for "multiprover interactive proof") turns out to be equivalent to the complexity class NEXPTIME, which is like NP except that the verification is now allowed to take an exponential amount of time, so it is a huge class. Finally, we come to MIP*. Here quantum entanglement comes into play. Before the computation starts the provers are allowed to share entangled quantum bits, which have the potential to create correlations between their responses to the verifier. Potentially at least, this greatly enlarges the set of possible strategies for the provers, and therefore greatly enlarges the class of functions that can be computed. And this potential turns out to be realized: the statement that MIP*=RE is telling us the extraordinary fact that every recursively enumerable function belongs to MIP*. That is, if you are given a Turing machine and asked whether it halts, there is some protocol involving multiple provers using entangled bits such that if the Turing machine halts, the provers will convince the verifer of that fact, and otherwise the verifier will be almost certain that it does not halt. Note that there is no algorithm that will establish (in general) that a Turing machine does _not_ halt, but the fact that MIP*=RE tells us that if we are satisfied with being _almost_ certain that it does not halt, then for each instance of the problem there is an MIP* protocol that will give that to us. This paper concerns a particular problem from coding theory. A _linear code_ is a subspace C\mathcal CC of Fn\mathbb F^nFn for some finite field F\mathbb FF such that any two elements, or _codewords_, differ in at least ddd coordinates. (The bigger ddd is, the better the code.) Given such a code, the tensor code C⊗m\mathcal C^{\otimes m}C⊗m is defined to be the set of all functions g:[n]m→Fg:[n]^m\to\mathbb Fg:[n]m→F (where [n][n][n] denotes the set {1,2,…,n}\{1,2,\dots,n\}{1,2,…,n}) such that if you fix all but one coordinate, then the resulting restriction of ggg, regarded as an element of Fn\mathbb F^nFn in the obvious way, is an element of C\mathbb CC. The corresponding computational problem is to determine whether a given function ggg belongs to C⊗m\mathcal C^{\otimes m}C⊗m. Such codes are called _locally testable_ because there is a simple protocol that allows an interactive proof based on only local information. It works as follows. The verifier chooses a random element xxx of [n]m[n]^m[n]m, the prover responds with an element u∈Fu\in\mathbb Fu∈F, the verifier then chooses a random j∈[n]j\in[n]j∈[n], and the prover responds with a codeword www from C\mathcal CC. If wj=uw_j=uwj​=u, then the verifier judges ggg to belong to C⊗m\mathcal C^{\otimes m}C⊗m. Note that if ggg does indeed belong to C⊗m\mathcal C^{\otimes m}C⊗m, then all the prover has to do is choose the word obtained from the line of all points yyy such that yi=xiy_i=x_iyi​=xi​ when i≠ji\ne ji=j. Soundness of the protocol is less obvious (and requires a further technical condition on the code called interpolability) but follows quickly from a result of Babai, Fortnow and Lund. The main result of this paper can be thought of as saying that two interative provers cannot do significantly better for this problem if they are allowed to use entangled bits than if they are restricted to classical computation. For more details about tensor codes, this result, and how it relates to the MIP*=RE theorem, the extensive introduction to the paper itself is highly recommended.
Low degree tests play an important role in classical complexity theory, serving as basic ingredients in foundational results such as MIP=NEXP\mathsf{MIP} = \mathsf{NEXP}MIP=NEXP [BFL91] and the PCP theorem [AS98,ALM+98]. Over the last ten years, versions of these tests which are sound against quantum provers have found increasing applications to the study of nonlocal games and the complexity class~MIP∗\mathsf{MIP}^*MIP∗. The culmination of this line of work is the result MIP∗=RE\mathsf{MIP}^* = \mathsf{RE}MIP∗=RE [arXiv:2001.04383]. One of the key ingredients in the first reported proof of MIP∗=RE\mathsf{MIP}^* = \mathsf{RE}MIP∗=RE is a two-prover variant of the low degree test, initially shown to be sound against multiple quantum provers in [arXiv:1302.1242]. Unfortunately a mistake was recently discovered in the latter result, invalidating the main result of [arXiv:1302.1242] as well as its use in subsequent works, including [arXiv:2001.04383]. We analyze a variant of the low degree test called the low individual degree test. Our main result is that the two-player version of this test is sound against quantum provers. This soundness result is sufficient to re-derive several bounds on~MIP∗\mathsf{MIP}^*MIP∗ that relied on [arXiv:1302.1242], including MIP∗=RE\mathsf{MIP}^* = \mathsf{RE}MIP∗=RE.
In 2020, a landmark result by Ji, Natarajan, Vidick, Wright, and Yuen showed that MIP*, the class of languages that can be decided by a classical verifier interacting with multiple computationally unbounded provers sharing entanglement in the tensor product model, is equal to RE. We show that the class MIPco, a complexity class defined similarly to MIP* except with provers sharing the commuting operator model of entanglement, is equal to the class coRE. This shows that giving the provers two different models of entanglement leads to two completely different computational powers for interactive proof systems. Our proof builds upon the compression theorem used in the proof of MIP*=RE, and we use the tracially embeddable strategies framework to show that the same compression procedure in MIP* =RE also has the same desired property in the commuting operator setting. We also give a more streamlined proof of the compression theorem for non-local games by incorporating the synchronous framework used by Mousavi et al. [STOC 2022], as well as the improved Pauli basis test introduced by de la Salle [ArXiv:2204.07084]. We introduce a new equivalence condition for RE/coRE-complete problems, which we call the weakly compressible condition. We show that both MIP* and MIPco satisfy this condition through the compression theorem, and thereby establish that the uncomputability for MIP* and MIPco can be proved under a unified framework (despite these two complexity classes being different). Notably, this approach also gives an alternative proof of the MIP*=RE theorem, which does not rely on the preservation of the entanglement bound. In addition to non-local games, this new condition could also potentially be applicable to other decision problems.