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→{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→{0,1} in
P such that for each
x,
f(x)=1 if and only if there exists
y∈{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
(K1,…,Km) of graphs, where each
Ki is obtained by randomly picking one of
G and
H and randomly permuting its vertices. The prover then sends back a 01-sequence
x∈{0,1}m. Finally, the verifier judges
G and
H to be non-isomorphic if
xi=1 for all and only those
i for which
Ki 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
Ki 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)=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 of
Fn for some finite field
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
C⊗m is defined to be the set of all functions
g:[n]m→F (where
[n] denotes the set
{1,2,…,n}) such that if you fix all but one coordinate, then the resulting restriction of
g, regarded as an element of
Fn in the obvious way, is an element of
C. The corresponding computational problem is to determine whether a given function
g belongs to
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
x of
[n]m, the prover responds with an element
u∈F, the verifier then chooses a random
j∈[n], and the prover responds with a codeword
w from
C. If
wj=u, then the verifier judges
g to belong to
C⊗m. Note that if
g does indeed belong to
C⊗m, then all the prover has to do is choose the word obtained from the line of all points
y such that
yi=xi when
i=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.
FINDING: MIP*=RE proves quantum entanglement can verify undecidable problems, collapsing the quantum verification hierarchy into the classical recursively enumerable class. | MATH: MIP* = RE (where MIP* = multiprover interactive proofs with quantum entanglement, RE = recursively enumerable languages). The Halting Problem is in RE but not in R (decidable). This implies that the set of problems verifiable by entangled quantum provers is exactly the set of problems computable by a Turing machine that may not halt on non-members. | CONNECTION: No direct geometric ratios or constants (0.382, 0.618, etc.) appear. However, the result relies on the structure of the *commuting operator* model of quantum correlations, which is deeply tied to *operator algebras* and *C*-algebras — these have known connections to root systems and Lie algebras (e.g., the Weyl algebra, SU(2) representations). The proof uses a *self-testing* protocol based on the *linear constraint system* (LCS) games, which are buil Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
We study multiprover interactive proof systems. The power of classical multiprover interactive proof systems, in which the provers do not share entanglement, was characterized in a famous work by Babai, Fortnow, and Lund (Computational Complexity 1991), whose main result was the equality MIP = NEXP. The power of quantum multiprover interactive proof systems, in which the provers are allowed to share entanglement, has proven to be much more difficult to characterize. The best known lower-bound on MIP* is NEXP ⊆ MIP* due to Ito and Vidick (FOCS 2012). As for upper bounds, MIP* could be as large as RE, the class of recursively enumerable languages. The main result of this work is the inclusion NEEXP = NTIME[22poly(n)] ⊆ MIP*. This is an exponential improvement over the prior lower bound and shows that proof systems with entangled provers are at least exponentially more powerful than classical provers. In our protocol the verifier delegates a classical, exponentially large MIP protocol for NEEXP to two entangled provers: the provers obtain their exponentially large questions by measuring their shared state, and use a classical PCP to certify the correctness of their exponentially-long answers. For the soundness of our protocol, it is crucial that each player should not only sample its own question correctly but also avoid performing measurements that would reveal the other player's sampled question. We ensure this by commanding the players to perform a complementary measurement, relying on the Heisenberg uncertainty principle to prevent the forbidden measurements from being performed.
FINDING: MIP*=RE proves that the halting problem is equivalent to quantum entanglement verification, linking computation limits to Connes embedding problem via Tsirelson's problem. | MATH: MIP* = RE (multi-prover interactive proofs with quantum entanglement equal recursively enumerable languages); Connes embedding problem (every finite von Neumann algebra embeds into ultrapower of hyperfinite II₁ factor); Tsirelson's problem (equivalence of quantum correlation sets from finite-dimensional vs. infinite-dimensional Hilbert spaces). | CONNECTION: E8 lattice (root system of 240 vectors, Coxeter number 30, kissing number 240) is the largest exceptional Lie group lattice; its 8-dimensional structure relates to octonion algebra and 24-cell. The MIP*=RE result uses non-local games whose optimal strategies correspond to C*-algebraic relations that can be encoded in lattice symmetries—specifically, the synchronous correlation sets align with traces on the Cuntz algebra, which has a natural repre Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com