Quantum soundness of testing tensor codes

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.