NOVEMBER 2021
|
VOL. 64
|
NO. 11
|
COMMUNICATIONS OF THE ACM
131
MIP* = RE
By Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen
DOI:10.1145/3485628
Note from the Research Highlights Co-Chairs:
A Research Highlights paper appearing in
Communications
is usually peer-reviewed prior to publication. The following
paper is unusual in that it is still under review. However, the
result has generated enormous excitement in the research
community, and came strongly nominated by SIGACT, a
nomination seconded by external reviewers.
Abstract
The complexity class
NP
characterizes the collection of com
-
putational problems that have
efficiently verifiable solu
-
tions
. With the goal of classifying computational problems
that seem to lie beyond
NP
, starting in the 1980s complexity
theorists have considered extensions of the notion of effi
-
cient verification that allow for the use of
randomness
(the
class
MA
),
interaction
(the class
IP
), and the possibility to
interact with
multiple
proofs, or
provers
(the class
MIP
). The
study of these extensions led to the celebrated PCP theorem
and its applications to hardness of approximation and the
design of cryptographic protocols.
In this work, we study a fourth modification to the notion
of efficient verification that originates in the study of
quan
-
tum entanglement
. We prove the surprising result that
every problem that is recursively enumerable, including the
Halting problem, can be efficiently verified by a classical
probabilistic polynomial-time verifier interacting with two
all-powerful but noncommunicating provers sharing entan
-
glement. The result resolves long-standing open problems
in the foundations of quantum mechanics (Tsirelson’s prob
-
lem) and operator algebras (Connes’ embedding problem).
1. INTERACTIVE PROOF SYSTEMS
An
interactive proof system
is an abstraction that generalizes the
intuitively familiar notion of
proof.
Given a formal statement
z
(e.g., “this graph admits a proper 3-coloring”), a proof
π
for
z
is information that enables one to check the validity of
z
more
efficiently than without access to the proof (in this example,
π
could be an explicit assignment of colors to each vertex of the
graph, which is generally easier to verify than to find).
Complexity theory formalizes the notion of proof in a way
that emphasizes the role played by the verification proce
-
dure. To explain this, first recall that a
language L
is identified
with a subset of {0, 1}
*
, the set of all bit strings of any length,
that represents all problem instances to which the answer
should be “yes.” For example, the language
L =
3-C
oloring
contains all strings
z
such that
z
is the description (accord
-
ing to some prespecified encoding scheme) of a 3-colorable
graph
G
. We say that a language
L
admits
efficiently verifiable
The original version of this paper appeared on the quant-ph
arXiv as arXiv:2001.04383.
proofs if there exists an algorithm
V
(formally, a polynomial-
time Turing machine) that satisfies the following two prop
-
erties: (i) for any
z
∈
L
there is a string
π
such that
V
(
z
,
π
)
returns 1 (we say that
V
“accepts” the proof
π
for input
z
) and
(ii) for any
z
∉
L
, there is no string
π
such that
V
(
z
,
π
) accepts.
Property (i) is generally referred to as the
completeness
prop
-
erty and (ii) is the
soundness.
The set of all languages
L
such
that there exists a verifier satisfying both completeness and
soundness is the class
NP
.
Research in complexity and cryptography in the 1980s
and 1990s led to a significant generalization of this notion
of “efficiently verifiable proof.” The first modification is to
allow
randomized
verification procedures by relaxing (i) and
(ii) to
high probability
statements: every
z
∈
L
should have a
proof
π
that is accepted
with probability at least c
(the com
-
pleteness parameter), and for no
z
∉
L
should there be a
proof
π
that is accepted
with probability larger than s
(the
soundness parameter). A common setting is to take
and
standard amplification techniques reveal that the
exact values do not significantly affect the class of languages
that admit such proofs, provided that they are chosen within
reasonable bounds.
The second modification is to allow
interactive
verifica
-
tion. Informally, instead of receiving a proof string
π
in its
entirety and making a decision based on it, the verification
algorithm (called the “verifier”) now communicates with
another algorithm called a “prover,” and based on the inter
-
action decides whether
z
∈
L
. There are no restrictions on the
computational power of the prover, whereas the verifier is
required to run in polynomial time.
a
We let
IP
(for “Interactive
Proofs”) denote the class of languages having interactive,
randomized polynomial-time verification procedures.
The third and final modification is to consider interac
-
tions with
two
(or more) provers. In this setting, the provers
are not allowed to communicate with each other and the ver
-
ifier may “cross-interrogate” them in order to decide if
z
∈
L
.
The provers are allowed to coordinate a joint strategy ahead
of time, but once the protocol begins, they can only interact
with the verifier. The condition that the provers cannot com
-
municate with each other is a powerful constraint that can
be leveraged by the verifier to detect attempts at making it
accept a false claim, that is whenever
z
∉
L
.
a
The reader may find the following mental model useful: in an interac
-
tive proof, an all-powerful prover is trying to convince a skeptical, but
computationally limited, verifier that a string
z
(known to both) lies in
the set
L
, even when it may be that in fact
z
∉
L
. By interactively inter
-
rogating the prover, the verifier can reject false claims, i.e. determine
with high statistical confidence whether
z
∈
L
or not. Importantly, the
verifier is allowed to probabilistically and adaptively choose its mes
-
sages to the prover.
research highlights
132
COMMUNICATIONS OF THE ACM
| NOVEMBER 2021
|
VOL. 64
|
NO. 11
reason that no time-bounded upper bound holds in a self-
evident manner is because there is no a priori bound on the
complexity of near-optimal provers in an
MIP
* interactive
proof system. This is in contrast to
MIP
where any prover can
be represented by its question–answer response function,
an exponential-size object.)
In
13
the first nontrivial lower bound on
MIP
* was obtained,
establishing that
MIP
=
NEXP
⊆
MIP
*. This was shown by
arguing that the completeness and soundness properties of
the proof system of Babai
1
are maintained in the presence
of shared entanglement between the provers. Following
13
a
sequence of works established progressively stronger lower
bounds, culminating in
18
which showed the inclusion
NEEXP
⊆
MIP
*, where
NEEXP
stands for nondeterminist doubly
exponential time. Since it is known that
NEXP
NEEXP
it fol
-
lows that
MIP
≠
MIP
*.
Our main result takes this line of work to its limit to show
the exact characterization
MIP
*
=
RE.
A complete problem for
RE
is the Halting problem. Thus a
surprising consequence of the equality
MIP
*
=
RE
is that
there exists a (classical) polynomial-time transformation
that takes as input any Turing machine
M
and returns the
description of a classical randomized polynomial-time (in
the description size of
M
) verification procedure such that
the existence of quantum provers sharing entanglement
that are accepted by this verification procedure is equivalent
to the fact that the Turing machine halts. Since the actions
of quantum provers are (in principle) physically realizable,
the verification procedure can be interpreted as the specifi
-
cation of a physical experiment that could be used to certify
that a Turing machine halts. The reason that this is surpris
-
ing is because the Halting problem does not refer to any
notion of time bound (and, as shown by Turing, is in fact
undecidable), whereas the verification procedure is time-
bounded. Yet all true statements (halting Turing machines)
have valid proofs in this model, while false statements (non
-
halting Turing machines) do not.
Before proceeding with a description of the main ideas
that go in the proof of this result, we highlight some con
-
sequences and describe open questions. Our result is
motivated by a connection with Tsirelson’s problem from
quantum information theory, itself related to Connes’
Embedding Problem in the theory of von Neumann alge
-
bras.
8
In a celebrated sequence of papers, Tsirelson
22
initi
-
ated the systematic study of quantum correlation sets, for
which he gave two natural definitions. The first definition,
referred to as the “tensor product model,” constrains iso
-
lated systems to be in tensor product with one another: if
two parties Alice and Bob are space-time isolated, then any
measurement performed by Alice can be modeled using an
operator
A
on Alice’s Hilbert space
H
A
, while any measure
-
ment performed by Bob can be modeled using an operator
B
on Bob’s Hilbert space
H
B
; studying the correlations between
Alice and Bob then involves forming the tensor product
H
A
⊗
H
B
and studying operators such as
A
⊗
B
. The second
definition, referred to as the “commuting model,” is more
Work in the 1980s and 1990s in complexity theory has
shown that the combination of randomness, interaction,
and multiple provers leads to an
exponential
increase in
verification power. Concretely, the class of problems that
can be verified with all three ingredients together, denoted
MIP
(for Multiprover Interactive Proofs), was shown to equal
the class
NEXP
1
of languages that admit exponentially long
“traditional” proofs verifiable in exponential time.
2. OUR RESULTS
We now introduce a fourth modification to the class
MIP
,
leading to the class
MIP
* that is the focus of our work.
Informally the class
MIP
* contains all languages that can
be decided by a classical polynomial-time verifier interact
-
ing with multiple
quantum
provers sharing
entanglement.
To
be clear: compared with
MIP
, the only difference is that the
provers may use entanglement, both in the case when
z
∈
L
(completeness) and when
z
∉
L
(soundness).
The study of
MIP
* is motivated by a long line of works in
the foundations of quantum mechanics around the topic
of
Bell inequalities.
Informally, a Bell inequality is a linear
function that separates two convex sets: on the one hand,
the convex set of all families of distributions that can be
generated locally by two isolated parties using shared ran
-
domness; on the other hand, the convex set of all families of
distributions that can be generated locally by two isolated
parties using quantum entanglement. (In neither case is
there any computational restriction; the only difference is in
the kind of shared resource available.) The most famous Bell
inequality is the
CHSH inequality
5
; we will describe another
example later, in Section 4.1. The study of Bell inequalities
is relevant not only to quantum foundations, where they are
a tool to study the nonlocal properties of entanglement, but
also in quantum cryptography, where they form the basis
for cryptographic protocols, for example, quantum key dis
-
tribution,
9
and in the study of entangled states of matter in
physics. The connection with complexity theory was first
made by Cleve
6
using the language of two-player games.
The introduction of entanglement in the setting of inter
-
active proofs has interesting consequences for complexity
theory; indeed, it is not
a priori
clear how the class
MIP
* com
-
pares to
MIP
. This is because in general the use of entangle
-
ment may increase the odds of the provers to convince the
verifier of the validity of any given statement, true or false.
Such an increase may render a previously sound proof sys
-
tem unsound, because the provers are able to make the
verifier accept false statements. Conversely, it is conceivable
that new proof systems may be designed for which the com
-
pleteness property (valid statements have proofs) holds only
when the provers are allowed to use entanglement. As a con
-
sequence,
MIP
* could a priori be smaller, larger, or incompa
-
rable to
MIP
. The only clear inclusions are
IP
⊆
MIP
*, because
if the verifier chooses to interact with a single prover, then
entanglement does not play any role, and
MIP
*
⊆
RE
, the class
of recursively enumerable languages, that is languages
L
such that there exists a Turing machine
M
such that
z
∈
L
if
and only if
M
halts and accepts on input
z
. (The inclusion
MIP
*
⊆
RE
will be justified once we introduce the model
more formally. At the moment we only point out that the
NOVEMBER 2021
|
VOL. 64
|
NO. 11
|
COMMUNICATIONS OF THE ACM
133
general because it only makes use of a single Hilbert space
H
on which both Alice’s operators
A
and Bob’s operators
B
act simultaneously; the constraint of “isolation” is enforced
by requiring that
A
and
B
commute,
AB =
BA
, so that neither
operation can have a causal influence on the other.
b
The ques
-
tion of equality between the families of distributions that can
be generated in either model is known as
Tsirelson’s prob
-
lem
.
23
As already noted by Fritz,
10
the undecidability of
MIP
*
implies that Tsirelson’s two models are finitely separated
(i.e., there is a constant-size family of distributions that can be
realized in the second model but is within a constant distance
of any distribution that can be realized in the first model);
thus, our result that
RE
⊆
MIP
* resolves Tsirelson’s problem
in the negative. Through a sequence of previously known
equivalences,
19
we also resolve Connes’ Embedding Problem
in the negative. As a consequence, our result may lead to the
construction of interesting objects in other areas of math
-
ematics. In particular an outstanding open question that may
now be within reach is the problem of constructing a finitely
presented group that is not sofic, or even not hyperlinear.
3. PROOF OVERVIEW
For simplicity, we focus on the class
MIP
* (2,1), which corre
-
sponds to the setting of one-round protocols with two prov
-
ers sharing entanglement. (A consequence of our results is
that this setting has equal verification power to the general
setting of polynomially many provers and rounds of interac
-
tion.) The verifier in such a protocol can be described as the
combination of two procedures: a
question sampling
proce
-
dure
S
that samples a pair of questions (
x
,
y
) for the provers
according to a distribution
μ
and a
decision
procedure that
takes as input the provers’ questions and their respective
answers
a
,
b
and evaluates a predicate
D
(
x
,
y
,
a
,
b
)
∈
{0, 1} to
determine the verifier’s acceptance or rejection. (In general,
both procedures also take the problem instance
z
as input.)
Our results establish the existence of transformations
on
families
of two-prover one-round protocols having cer
-
tain properties. In order to keep track of efficiency (and
ultimately, computability) properties, it is important to
have a way to specify such families in a uniform manner.
Toward this we introduce the following formalism. A
nor
-
mal form verifier
is specified by a pair of Turing machines
V
=
(
S
,
D
) that satisfy certain conditions. The Turing
machine
S
(called a
sampler
) takes as input an index
n
∈
and returns the description of a procedure that can be used
to sample questions (
x, y
) (this procedure itself obeys a cer
-
tain format associated with “conditionally linear” distribu
-
tions, defined in Section 4.3 below). The Turing machine
D
(called a
decider
) takes as input an index
n
, questions (
x
,
y
),
and answers (
a
,
b
) and returns a single-bit decision. The sam
-
pling and decision procedures are required to run in time
polynomial in the index
n
. Note that normal form verifiers
do not take any input other than the index
n
; we explain later
in this section how the actual problem instance
z
is taken
into account. Given a normal form verifier
V
=
(
S
,
D
) and an
b
Precisely, commutation implies that the joint distribution of outcomes
obtained by performing one measurement and then the other is indepen
-
dent of the order chosen.
index
n
∈
, there is a natural two-prover one-round proto
-
col
V
n
associated to it. We let val* (
V
n
) denote the maximum
success probability of quantum provers sharing entangle
-
ment in this protocol.
Our main technical result is a
gap-preserving compres
-
sion
transformation on normal form verifiers. The following
theorem presents an informal summary of the properties of
this transformation. For a verifier
V
n
and a probability 0
≤
p
≤
1, we let
(
V
n
, p
) denote the minimum local dimension
of an entangled state shared by provers that succeed in the
protocol executed by
V
n
with probability at least
p
.
T
heorem
3.1 (G
ap
-
preserving compression
).
There exists
a polynomial-time Turing machine
Compress
that, when given as
input the description of a normal form verifier
V
=
(
S
,
D
)
, returns
the description of another normal form verifier
V
′
=
(
S
′
,
D
′
)
that
satisfies the following properties: for all n
∈
, letting N =
2
n
1.
2.
3.
The terminology
compression
is motivated by the fact,
implicit in the (informal) statement of the theorem, that
the time complexity of the verifier’s sampling and decision
procedures in the protocol
, which (as required in the def
-
inition of a normal form verifier) is polynomial in
n
, is expo
-
nentially smaller than the time complexity of the verifier
V
N
, which is polynomial in
N
and thus exponential in
n
. As
such our result can be understood as an efficient delegation
procedure for (normal form) interactive proof verifiers. In
the next section, we describe how the presence of entangle
-
ment between the provers enables such a procedure. First,
we sketch how the existence of a Turing machine
Compress
with the properties stated in the theorem implies the inclu
-
sion
RE
⊆
MIP
*.
To show this, we give an
MIP
*
(2, 1)
protocol for the Halting
problem, which is a complete problem for
RE
. Precisely, we
give a procedure that given a Turing machine
M
as input
returns the description of a normal form verifier
V
M
=
(
S
M
,
D
M
) with the following properties. First, if
M
does eventu
-
ally halt on an empty input tape, then it holds that for all
n
∈
,
. Second, if
M
does not halt then for all
n
∈
,
. It follows that
is a valid
MIP
*
(2, 1)
proof system for the Halting problem.
We describe the procedure that achieves this. Informally,
the procedure returns the specification of a verifier
V
M
=
(
S
M
,
D
M
) such that
D
M
proceeds as follows: on input (
n
,
x
,
y
,
a
,
b
)
it first executes the Turing machine
M
for
n
steps. If
M
halts,
then
D
M
accepts. Otherwise,
D
M
computes the description
of the compressed verifier
V
′
=
(
S
′
,
D
′
) that is the output of
Compress
on input
V
M
, then executes the decision procedure
D
′
(
n
,
x
,
y
,
a
,
b
) and accepts if and only if
D
′
accepts.
c
c
The fact that the decider
D
M
can invoke the
Compress
procedure on it
-
self follows from a well-known result in computability theory known as
Kleene’s recursion theorem
(also called
Roger’s fixed point theorem
).
15, 21
research highlights
134
COMMUNICATIONS OF THE ACM
| NOVEMBER 2021
|
VOL. 64
|
NO. 11
To show that this procedure achieves the claimed trans
-
formation, consider two cases. First, observe that if
M
eventually halts in some number of time steps
T
, then by def
-
inition
for all
n
≥
T
. Using Theorem 3.1 along
with an inductive argument it follows that
for
all
n
≥
1. Second, if
M
never halts, then observe that for any
n
≥
1 Theorem 3.1 implies two separate lower bounds on
the amount of entanglement required to win the protocol
with probability at least
: the dimension is (a) at
least
and (b) at least the dimension needed to succeed
in the protocol
with probability at least
. By induc-
tion, it follows that an
infinite
amount of entanglement is
needed to succeed in the protocol
V
n
with any probability
greater than
. By continuity, a sequence of finite-dimension
prover strategies for
V
n
cannot lead to a limiting value larger
than
, and
.
4. USING ENTANGLEMENT TO COMPRESS QUANTUM
INTERACTIVE PROOFS
In the language introduced in the previous section, the inclu
-
sion
NEXP
⊆
MIP
implies that for any
NEXP
-complete lan
-
guage
L,
there is a pair of polynomial-time Turing machines
V
=
(
S
,
D
) such that the following hold. The Turing machine
S
takes as input an integer
n
∈
and returns a (probabilistic)
circuit that can be used to sample questions (
x
,
y
)
∈
X
×
Y
according to some distribution
S
n
.
The Turing machine
D
on
input
n
∈
as well as an instance
z
∈
{0, 1}
n
and (
x, y, a, b
)
∈
X
×
Y
×
A
×
B
returns a decision bit in {0, 1}. This proof sys
-
tem is such that whenever
z
∈
L
there are “proofs”
f
A
:
X
→
A
and
f
B
:
Y
→
B
and such that for all (
x
,
y
) in the support of
S
n
,
D
(1
n
,
z, x, y, f
A
(
x
),
f
B
(
y
))
=
1
,
and whenever
z
∉
L
then for any
purported “proofs”
f
A
:
X
→
A
and
f
B
:
Y
→
B
it holds that
(1)
While the definition of
MIP
allows for more general proof
systems, for example, the sampling of questions may
depend on the input
z
and there may be multiple rounds of
interaction, subsequent refinements of the original proof
that
NEXP
⊆
MIP
imply that proof systems of the form above
are sufficient to capture the entire class.
The maximum of the expression on the left-hand side
of (1) can be computed exactly in nondeterministic expo
-
nential time by guessing an optimal choice of (
f
A
,
f
B
) and
evaluating the expression. Therefore, the class
MIP
does not
allow verification of languages beyond
NEXP
. In particular,
Theorem 3.1 is clearly not possible in this model, because
by applying it to the verifier for
NEXP
described in the pre
-
ceding paragraph one would obtain a polynomial-time veri
-
fier with the ability to decide a complete language for
NEEXP
;
however, it is known that
NEXP
NEEXP
. To go beyond
NEXP
and prove Theorem 3.1, we must find ways for the verifier to
constrain the provers to make use of entanglement so that
even more complex computations can be delegated to them.
To prove Theorem 3.1, we will show how the actions of
both the sampler
S
and the decider
D
can be delegated to
the provers and their correct execution verified in time poly
-
logarithmic in the sampler and decider’s time complex
-
ity. This will enable a polynomial-time verifier to force the
provers to “simulate” the action of
S
and
D
on inputs of size
N =
2
n
using polynomial resources, as required by Theorem
3.1. While the techniques for delegating deterministic pro
-
cedures such as
D
are already present, to some extent, in
the proof of
MIP
=
NEXP
(whose implications for delegated
computation are well-known, see, e.g., Goldwasser
12
), for
the inherently probabilistic procedure
S
, we are faced with
an entirely new challenge: the delegation of
randomness gen
-
eration
. In particular, it is clearly not reasonable to give the
provers access to the random seed used by
S
, as this would
provide them perfect knowledge of both questions and
therefore allow them to easily defeat the protocol. In order to
ensure that the provers sample from the correct distribution
while each obtaining exactly the right amount of information
about their respective input, we leverage entanglement in an
essential way. In the next section, we give a classic example
of how randomness can be certified by using entanglement.
In Section 4.2, we introduce an asymptotically efficient
entanglement test that builds on the example. In Section 4.3,
we describe a class of question distribution that can be del
-
egated (we will say “introspected”) by making use of the
entanglement test. In Section 4.5, we explain a final step of
parallel repetition, and in Section 4.6, we conclude.
4.1. The Magic Square game
We introduce a two-player game known as the “Magic Square
game.” To specify the rules of the game, we first describe a
(classical) constraint satisfaction problem that consists of 6
linear equations defined over 9 variables that take values in
the binary field
F
2
. The variables are associated with the cells
of a 3 × 3 grid, as depicted in Figure 1. Five of the equations
correspond to the constraint that the sum of the variables in
each row and the first two columns must be equal to 0, and
the last equation imposes that the sum of the variables in
the last column must be equal to 1.
This system of equations is clearly unsatisfiable. Now
consider the following game associated to it. In the game,
the trusted referee first samples one of the 6 equations uni
-
formly at random and then one of the three variables appear
-
ing in the constraint uniformly at random. It asks one prover
for an assignment of values to all variables in the chosen
constraint, and the other prover for the selected variable. It
is not hard to see that no deterministic or randomized strat
-
egy can succeed in this game with probability larger than
,
since there are 18 pairs of questions in total and any deter
-
ministic or randomized strategy that succeeds with a strictly
larger probability is easily seen to imply a satisfying assign
-
ment to the Magic Square.
What makes the game “magic” is the surprising fact, first
demonstrated by Mermin and Peres,
16, 20
that this game has
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
Figure 1. The Magic Square game.
NOVEMBER 2021
|
VOL. 64
|
NO. 11
|
COMMUNICATIONS OF THE ACM
135
a perfect quantum strategy: two noncommunicating players
sharing entanglement can win with probability 1. Moreover,
this can be achieved by sharing a simple 4-dimensional
quantum state (two EPR pairs) and making local measure
-
ments on it (i.e., each prover only makes an observation on
their local share of the state; see Section 4.2 for the mathe
-
matical formalism of quantum strategies). The outcomes of
local measurements are not causally related and entangle
-
ment does not allow the provers to communicate informa
-
tion. However, their outcome distribution can be correlated:
in the Mermin-Peres quantum strategy for the Magic Square
game, for any pair of questions selected by the referee the
joint distribution of the player’s answers happens to be uni
-
form over all pairs of possible answers.
d
The Magic Square game is an example of a Bell inequality
(specifically, the inequality is that classical strategies cannot
win with probability larger than
). The game can be inter
-
preted as a two-prover verification protocol for the satisfi
-
ability of the underlying system of 9 equations, in which case
the protocol is sound with classical provers but unsound
with quantum provers. However, for our purposes, this is
not a productive observation—we are interested in finding
positive
uses for entanglement. Is there anything useful that
can be certified using this game?
We reproduce a crucial observation due to
7
: the
only
way that quantum provers are able to succeed in the Magic
Square game beyond what is possible classically is by gener
-
ating answers that are
intrinsically random.
This is because
an intrinsically random strategy (by which we mean that the
computation of each answer
must
involve injecting fresh
randomness, that was not determined prior to the questions
being generated) is the only possibility for evading the clas
-
sical impossibility (the aforementioned “Bell inequality”).
Indeed if the two players always give a deterministic and
valid answer to their questions then listing those 18 pairs
of answers will lead to a satisfying assignment for the magic
square constraints. Since this is not possible it must be that
each pair of answers is generated “on the fly,” so that any two
answers are correlated in the right way but there is no mean
-
ingful correlation between pairs of answers obtained to dif
-
ferent pairs of questions (e.g., in different runs of the game).
In other words, quantum randomness cannot be “fixed,” and
this is what allows quantum provers to succeed in the game.
Based on this observation and with further technical
work, it is possible to use the Magic Square game to develop
a simple two-prover test (i.e., a small self-contained protocol
that can be used as a building block towards a larger
MIP
*
protocol) that constrains the provers to obtain, and report
to the verifier, identical uniformly random outcomes. Note
that this is stronger than merely allowing the provers to use
shared randomness, in the sense that it is
verifiable
: upon
seeing either prover’s answer, the verifier has the guaran
-
tee that it has been chosen near-uniformly at random—the
provers cannot bias the randomness in any way (unless they
pay a price by failing in the test with positive probability).
d
Not every game has such a perfect quantum strategy. For example, a game
in which the second player has to answer the first player’s question: this
would violate the nonsignaling principle.
While this is already a genuinely quantum possibility
that transforms the realm of achievable protocols, it does
not suffice for our purposes, for two reasons. First of all the
distributions that we aim to sample from, that is the dis
-
tributions
S
n
, are more complicated than uniform shared
randomness. We discuss this point in detail in Section 4.3.
Second, executing as many copies of the Magic Square game
as there are bits of randomness required to sample from
S
n
would not lead to the complexity savings that we are aiming
to achieve. This problem can be solved by employing a more
efficient means of randomness and entanglement genera
-
tion that builds simultaneously on the Magic Square game
and on a quantum version of the classical low-degree test, a
key component in the proof of
NEXP
⊆
MIP
, which we repur
-
pose for this new goal. We explain this in the next section.
4.2. The quantum low-degree test
The quantum low-degree test, first introduced by Natarajan
17
and analyzed by Ji,
14
is one of the core technical components
behind the proof of Theorem 3.1. The test provides an effi
-
cient means of certifying entanglement (and, as a corollary,
randomness generation) between two provers. The test
builds upon classical results in the property testing and
probabilistically checkable proofs literature for testing low-
degree polynomials, a line of work initiated by Gemmel
11
building upon the multilinearity test by Babai.
1
In this sec
-
tion, we first state the “quantum” version of these results and
then explain its use for delegating the sampling procedure.
To state the quantum low-degree test in sufficient tech
-
nical depth, we introduce the standard formalism used to
model quantum strategies. A strategy for two quantum prov
-
ers (in a one-round protocol) consists of (i) a quantum state
shared by the provers, which is represented by a unit vec
-
tor
⏐
ψ
〉 ∈
H
A
⊗
H
B
where
H
A
and
H
B
are finite-dimensional
Hilbert spaces associated with each prover (e.g., if
⏐
ψ
〉
con
-
sists of
n
EPR pairs then
H
A
=
H
B
=
C
2
n
) and (ii) for each ques
-
tion to a prover, say
x
∈
X
to the first prover, a measurement
that the prover performs on their share of the quan
-
tum state to produce an answer
a
∈
A
. Mathematically each
is a positive semidefinite operator acting on
H
A
such that
. The measurement rule states that two provers
modeled in this way generate answers (
a
,
b
) in response to
questions (
x
,
y
) with probability
Clearly two strategies generate the same distributions if
they are unitarily equivalent, that is, exchanging
⏐
ψ
〉
for
U
A
⊗
U
B
⏐
ψ
〉
for unitaries
U
A
on
H
A
and
U
B
on
H
B
and conjugat
-
ing all operators by
U
A
or
U
B
leads to the same strategy. So
any characterization of near-optimal strategies will only be
“up to local unitaries.” More generally, the provers may
have access to a larger space that is not directly used in
their strategy. For this reason, a characterization of near-
optimal quantum strategies is generally formulated “up to
local isometries,” where a local isometry is a linear map
φ
A
:
H
A
→
H
A
′
⊗
H
A
′′
(resp.
φ
B
:
H
B
→
H
B
′
⊗
H
B
′′
).
The quantum low-degree test comes in the form of a
rigid
-
ity
result, which guarantees that any near-optimal strategy
research highlights
136
COMMUNICATIONS OF THE ACM
| NOVEMBER 2021
|
VOL. 64
|
NO. 11
in a certain two-prover protocol is essentially unique—up
to local isometries. The test is parametrized by a tuple
qldparams
= (
q
,
m
,
d
) where
q
is a field size,
m
a number of
variables, and
d
a degree satisfying some conditions that
we omit from this abstract. We denote the associated two-
prover one-round verifier
. In the associated proto
-
col, whose exact description we also omit, the provers are
expected to (i) measure 2
m
log
q
shared EPR pairs in a cer
-
tain basis (either the computational basis or the Hadamard
basis, which is its Fourier transform), obtaining an outcome
; (ii) interpolate a polynomial
of individ-
ual degree at most
d
; and (iii) return the restriction of
g
a
to
a line or point in
that is provided to them as their ques
-
tion. This is almost exactly the same as the classic test from
Babai
1
and Gemmel
11
; the “quantum” part of the test lies in
the fact that the specification
a
for the polynomial
g
a
used by
the provers should be obtained as a result of a measurement
on an entangled state. This measurement can be required
to be made in different, incompatible bases (depending on
the question), and thus its outcome cannot be fixed a priori,
before the protocol starts. (In contrast, in the classical case,
it is assumed that
a
is a fixed string on which the provers
pre-agree.) Tests based on the Magic Square game are per
-
formed in addition to the above to enforce that the provers
make their measurements in the right bases.
T
heorem
4.1.
There exists a function
for universal constants a
≥
1
and
0 <
b
< 1
such that the fol
-
lowing holds. For all admissible parameter tuples
qldparams
=
(
q
,
m
,
d
)
and for all strategies
=
(
⏐
ψ
〉
,
A
,
B
)
for
that
succeed with probability at least
1
–
ε
, there exist local isom
-
etries
φ
A
:
H
A
→
H
A
′
⊗
H
A
′′
,
φ
B
:
H
B
→
H
B
′
⊗
H
B
′′
and a state
⏐
AUX
〉 ∈
H
A
′
⊗
H
B
′
such that
where |
EPR
〉
denotes an EPR pair. Moreover, letting
and
we have for W
∈
{
X, Z
}
In the theorem statement, the approximation
is
measured in a norm that depends on the sate shared by the
provers and is appropriate for arguing that the two measure
-
ment operators on the left and right of the approximation
sign lead to similar outcome distributions, even when some
other operator is applied by the other prover. The measure
-
ment operators
and
on the left-hand side are the
provers’ measurement operators associated with a desig
-
nated pair of questions
W = X
,
Z
in the protocol. The opera-
tors
that appear on the right-hand side denote tensor
products of singlequbit Pauli measurements in the basis
W
, which is the computational basis in case
W = Z
and the
Hadamard basis in case
W = X.
Here
u
is an element of
,
which can be interpreted as an (2
m
log
q
)-bit string.
Informally, the theorem guarantees that any prover strat
-
egy that achieves a high probability of success in the test is
“locally equivalent” to a strategy that consists in measuring
2
m
log
q
EPR pairs in the appropriate basis, which is a strategy
of the “honest” form described above. Crucially, the number
of EPR pairs tested is exponential in the verifier complexity,
which scales polynomially in log
q
,
m
, and
d
.
We turn our attention back to the problem of delegat
-
ing the sampling from the distribution
S
n
to the provers.
Referring to the provers producing their own questions,
we call this procedure “introspection.” In general, it is not
known how to introspect arbitrary unstructured distribu
-
tions
S
n
.
The verifier that underlies the protocol from Babai
1
chooses most of its question from the “line-point” distri
-
bution
S
n
, which is the distribution over pairs (
x
,
y
) such
that
x
is the description of a uniformly random line
and
y
is a uniformly random point on
l
. It is natural to first
consider introspection of this distribution. This is done by
Natarajan
18
to “compress” the protocol from Babai
1
and
thereby show the inclusion
NEEXP
⊆
MIP
*. The compressed
protocol relies on the test from Theorem 4.1 to efficiently
sample its questions to the provers; the randomness used
by the provers for sampling is based on their measurement
outcomes in the test, which are bitstrings of length 2
m
log
q
.
Unfortunately the distribution used to sample the ques
-
tions in the compressed protocol no longer has such a nice
form as the lines-point distribution. In particular, it includes
the question distribution from the quantum low-degree test,
which itself incorporates the Magic Square game question
distribution. Since our goal is to compress protocols itera
-
tively (recall the end of Section 3), it is essential to identify a
class of distributions that is sufficiently general and “closed
under introspection” in the sense that any distribution
from the family can be tested using a distribution from the
same family with reduced randomness complexity. For this,
we introduce the class of
conditionally linear distributions
,
which generalizes the low-degree test distribution. We show
that conditionally linear distributions can be “introspected”
using conditionally linear distributions only, enabling recur
-
sive introspection. (As we will see later, other closure prop
-
erties of conditionally linear distributions, such as taking
direct products, play an important role as well.) We describe
this family of distributions next.
4.3. Conditionally linear distributions
Fix a vector space
V
that is identified with
, for a finite
field
F
q
and integer
m.
Informally, a function
L
on
V
is
condi
-
tionally linear
(CL for short) if it can be evaluated by a proce
-
dure that takes the following form: (i) read a substring
z
(1)
of
z
; (ii) evaluate a linear function
L
1
on
z
(1)
; and (iii) repeat steps
(i) and (ii) with the remaining coordinates
z
z
(1)
, such that
the next steps are allowed to depend in an arbitrary way on
L
1
(
z
(1)
) but not directly on
z
(1)
itself. What distinguishes a func
-
tion of this form from an arbitrary function is that we restrict
the number of iterations of (i)—(ii) to a constant number (at
most 9, in our case). (One may also think of CL functions as
“adaptively linear” functions, where the number of “levels”
of adaptivity is the number of iterations of (i)—(ii).) A distri
-
bution
μ
over pairs (
x
,
y
)
∈
V
×
V
is called conditionally linear
NOVEMBER 2021
|
VOL. 64
|
NO. 11
|
COMMUNICATIONS OF THE ACM
137
in the Hadamard, instead of computational, basis; due to
the uncertainty principle, this has the effect of “erasing”
the outcome in the computational basis. The case of the
“line” prover is a little more complex: the goal is to ensure
that, conditioned on the specification of the line
l
received
by the “line” prover, the point
x
received by the “point”
prover is uniformly random within
l
. This was shown to be
possible in [18].
4.4. Answer reduction
The previous section sketches how we are able to use entan
-
glement testing techniques to delegate the sampling of
questions directly to the provers, with an exponential
savings in the verifier’s effort. Let
denote the result
-
ing “question-
reduced” verifier. However, the players still
respond with poly (
N
)-length answers, which the verifier has
to check satisfies the decision predicate of the original
protocol. We explain how to obtain a similar exponential
savings in the verification of the answers.
For this, we use probabilistically checkable proofs (PCPs)
as follows. The verifier in
samples questions as
would and sends them to the players. Instead of receiving
the introspected questions and answers (
x
,
y
,
a
,
b
) for the
original verifier
V
N
and running the decision procedure
D
(
N
,
x
,
y
,
a
,
b
), the verifier instead asks the provers to compute
a PCP
Π
for the statement that the original decider
D
accepts
the input (
N
,
x
,
y
,
a
,
b
) in time
T
= poly (
N
). The verifier then
samples additional questions for the provers that ask them
to return specific entries of the proof
Π
. Finally, upon receipt
of the provers’ answers, the verifier executes the PCP verifi
-
cation procedure. Because of the efficiency of the PCP, both
the sampling of the additional questions and the decision
procedure can be executed in time poly (
n
).
e
This sketch presents some difficulties. A first difficulty
is that in general no prover by themselves has access to the
entire input (
N
,
x
,
y
,
a
,
b
) to
D
, so no prover can compute
the entire proof n. This issue is addressed using oracular
-
ization, which is a classical technique and so we omit the
details (there are some subtleties specific to the quantum
case). A second difficulty is that a black-box application of
an existing PCP, as done by Natarajan,
18
results in a question
distribution for
(i.e., the sampling of the proof locations
to be queried) that is rather complex—and in particular,
it may no longer fall within the framework of CL distribu
-
tions for which we can do introspection. To avoid this, we
design a bespoke PCP based on the classical MIP for NEXP
(in particular, we borrow and adapt techniques from Ben-
Sasson
3,4
). Two essential properties for us are that (i) the PCP
proof is a collection of several low-degree polynomials, two
of which are low-degree encodings of each prover’s uncom
-
pressed answers, and (ii) verifying the proof only requires
(a) running low-degree tests, (b) querying all polynomials at
a uniformly random point, and (c) performing simple con
-
sistency checks. Property (i) allows us to eliminate the extra
layer of encoding by Natarajan,
18
who had to consider a PCP
e
This idea is inspired by the technique of composition in the PCP litera
-
ture, in which the complexity of a verification procedure can be reduced
by composing a proof system (often a PCP itself) with another PCP.
if it is the image under a pair of conditionally linear func
-
tions
L
A
,
L
B
:
V
→
V
of the uniform distribution on
V
, that is,
(
x
,
y
)
∼
(
L
A
(
z
),
L
B
(
z
)) for uniformly random
z
∈
V
.
An important class of CL distributions are low-degree test
distributions, which are distributions over question pairs
(
x
,
y
) where
y
is a randomly chosen affine subspace of
and
x
is a uniformly random point on
y
. We explain this for
the case where the random subspace
y
is one-dimensional
(i.e., a line). Let
V
=
V
X
⊗
V
V
where
. Let
L
A
be the
projection onto
V
X
(i.e., it maps (
x
,
υ
)
→
(
x
, 0) where
x
∈
V
X
and
υ
∈
V
V
). Define
L
B
:
V
→
V
as the map
where
is a linear map that, for every
υ
∈
V
V
, proj
-
ects onto a complementary subspace to the one-dimen
-
sional subspace of
V
X
spanned by
υ
(one can think of this
as an “orthogonal subspace” to the span of {
υ
}).
L
B
is con
-
ditionally linear because it can be seen as first reading the
substring
υ
∈
V
V
(which can be interpreted as specifying the
direction
of a line), and then applying a linear map
to
x
∈
V
X
(which can be interpreted as specifying a canonical
point on the line
. It is not hard to see that
the distribution of (
L
A
(
z
),
L
B
(
z
)) for
z
uniform in
V
is identi
-
cal (up to relabeling) to the low-degree test distribution (
x
,
l
)
where
l
is a uniformly random affine line in
, and
x
is a
uniformly random point on
l
.
We show that any CL distribution
m
, associated with a
pair of CL functions (
L
A
,
L
B
) over a linear space
, can
be “introspected” using a CL distribution that is “exponen
-
tially smaller” than the initial distribution. Slightly more
formally, to any CL distribution
m
,
we associate a two-prover
test in which questions from the verifier are sampled from
a CL distribution
m
′
over
for some
m
′
= poly log (
m
) and
such that in any successful strategy, when the provers are
queried on a special question labeled
I
ntro
they must
respond with a pair (
x
,
y
) that is approximately distributed
according to
m
. (The test allows us to do more: it allows us
to conclude how the provers obtained (
x
,
y
)—by measur
-
ing shared EPR pairs in a specific basis—and this will be
important when using the test as part of a larger protocol
that involves other checks.) Crucially for us, the distribution
m
′
only depends on a size parameter associated with (
L
A
,
L
B
)
(essentially, the integer
m
together with the number of “lev
-
els” of adaptivity of
L
A
and
L
B
), but not on any other structural
property of (
L
A
,
L
b
).
Only the decision predicate for the asso
-
ciated protocol depends on the entire description of (
L
A
,
L
B
).
We say a few words about the design of
m
′
and the associ
-
ated test, which borrow heavily from Natarajan.
18
Building
on the quantum low-degree test introduced in Section 4.2,
we already known how a verifier can force a pair of prov
-
ers to measure
m
EPR pairs in either the computational
or Hadamard basis and report the (necessarily identical)
outcome
z
obtained, all the while using questions of length
polylogarithmic in m only. The added difficulty is to ensure
that a prover obtains, and returns, precisely the informa
-
tion about
z
that is contained in
L
A
(
z
) (resp.
L
B
(
z
)), and
not more. A simple example is the line-point distribution
described earlier: there, the idea to ensure that, for exam
-
ple, the “point” prover only obtains the first component,
x
of (
x
,
υ
)
∈
V
X
⊗
V
V
, the verifier demands that the “point”
prover measures their qubits associated with the space
V
V
research highlights
138
COMMUNICATIONS OF THE ACM
| NOVEMBER 2021
|
VOL. 64
|
NO. 11
of proximity for a circuit applied to the low-degree encod
-
ings of the provers’ uncompressed answers. Property (ii)
allows us to ensure the question distribution employed by
the verifier remains conditionally linear.
4.5. Parallel repetition
The combined steps of question reduction (via introspection)
and answer reduction (via PCP composition) result in a protocol
whose verifier
has complexity poly (
n
). Furthermore, the
property of having a perfect quantum strategy is preserved
by the reduction. Unfortunately, the sequence of transforma
-
tions incurs a loss in the soundness parameters: if
,
then we can only establish that
for some
positive constant
(we call
C
the soundness gap). Such a
loss would prevent us from recursively applying the compres
-
sion procedure
Compress
an arbitrary number of times, which
is needed to obtain the desired complexity results for
MIP
*.
To overcome this, we need a final transformation to
restore the soundness gap after answer reduction to a con
-
stant larger than
. To achieve this, we use the technique
of parallel repetition. The parallel repetition of a two-prover
one-round protocol
G
is another protocol
G
k
, for some num
-
ber of repetitions
k
, which consists of executing
k
indepen
-
dent and simultaneous instances of
G
and accepting if and
only if all
k
instances accept. Intuitively, parallel repetition
is meant to decrease the prover’s maximum success prob
-
ability in a protocol
G
exponentially fast in
k
, provided
to begin with. However, it is an open question
of whether this is generally true for the entangled value val*.
Nevertheless, some variants of parallel repetition are known
to achieve exponential amplification. We use a variant called
“anchored parallel repetition” introduced by Bavarian.
2
This
allows us to devise a transformation that efficiently amplifies
the soundness gap to a constant. The resulting protocol
has the property that if
, then
(and moreover this is achieved using a commuting and
consistent strategy), whereas if
for some
universal constant
C
> 0, then
. Furthermore,
we have the additional property, essential for us, that good
strategies in
require as much entanglement as good
strategies in
(which in turn require as much entangle
-
ment as good strategies in
V
N
). The complexity of the verifier
in
remains poly (
n
).
The anchored parallel repetition procedure, when applied
to a normal form verifier, also yields a normal form verifier:
this is because the direct product of CL distributions is still
conditionally linear.
4.6. Putting it all together
This completes the overview of the transformations performed
by the compression procedure
Compress
of Theorem 3.1.
To summarize, given an input normal form verifier
V
, ques
-
tion and answer reduction are applied to obtain
, and
anchored parallel repetition is applied to obtain
, which is
returned by the compression procedure. Each of these trans
-
formations preserves completeness (including the commut
-
ing and consistent properties of a value-1 strategy) as well as
the entanglement requirements of each protocol; moreover,
the overall transformation preserves soundness.
1.
Babai, L., Fortnow, L., Lund, C. Non-
deterministic exponential time has
two-prover interactive protocols.
Comput. Complex.
1
, 1 (1991), 3–40.
2.
Bavarian, M., Vidick, T., Yuen, H.
Hardness amplification for entangled
games via anchoring. In
Proceedings
of the 49
th
Annual ACM SIGACT
Symposium on Theory of Computing
,
ACM, New York, NY, USA, 2017,
303–316.
3.
Ben-Sasson, E., Goldreich, O.,
Harsha, P., Sudan, M., Vadhan, S.
Robust PCPs of proximity, shorter
PCPs, and applications to coding.
SIAM J. Comput.
36
, 4 (2006),
889–974.
4.
Ben-Sasson, E., Sudan, M. Simple
PCPs with poly-log rate and query
complexity. In
Proceedings of
the Thirty-seventh Annual ACM
Symposium on Theory of Computing,
ACM, New York, NY, USA, 2005,
266–275.
5.
Clauser, J.F., Horne, M.A., Shimony, A.,
Holt, R.A. Proposed experiment to
test local hidden-variable theories.
Phys. Rev. Lett.
23
, 15 (1969), 880.
6. Cleve, R., Hoyer, P., Toner, B., Watrous, J.
Consequences and limits of nonlocal
strategies. In
Proceedings. 19
th
IEEE
Annual Conference on Computational
Complexity, 2004
, IEEE, Washington,
DC, USA, 2004, 236–249.
7.
Colbeck, R. Quantum and relativistic
protocols for secure multi-party
computation. Ph. D. Thesis, 2009.
8.
Connes, A. Classification of injective
factors cases
II
1
,
II
•
,
III
λ
,
λ
≠
1.
Ann. Math. 104
(1976), 73–115.
9.
Ekert, A.K. Quantum cryptography
based on bell’s theorem.
Phys. Rev.
Lett.
67,
6 (1991), 661.
10.
Fritz, T., Netzer, T., Thom, A. Can
you compute the operator norm?
Proc. Am. Math. Soc.
142
, 12 (2014),
4265–4276.
11.
Gemmel, P., Lipton, R., Rubinfeld, R.,
Sudan, M., Wigderson, A. Self testing/
correcting for polynomials and for
approximate functions. In
Proceedings
of the 23
rd
STOC.
ACM, New York, NY,
USA, 1991, 32–42.
12.
Goldwasser, S., Kalai, Y.T., Rothblum, G.N.
Delegating computation: interactive
proofs for muggles.
J. ACM
62
, 4
(2015), 1–64.
13.
Ito, T., Vidick, T. A multi-prover
interactive proof for NEXP sound against
entangled provers. In
2012 IEEE 53
rd
Annual Symposium on Foundations of
Computer Science,
IEEE, Washington,
DC, USA, 2012, 243–252.
14.
Ji, Z., Natarajan, A., Vidick, T., Wright, J.,
Yuen, H. Quantum soundness of the
classical low individual degree test.
arXiv preprint arXiv:2009.12982
(2020).
15.
Kleene, S.C. Introduction to
Metamathematics.
J. Symb. Log.
19
, 3
(1954), 215–216.
16.
Mermin, D. Simple unified form for
the major no-hidden-variables
theorems.
Phys. Rev. Lett.
65
, 27
(1990), 3373.
17.
Natarajan, A., Vidick, T. Two-
player entangled games are
NP-hard. In
Proceedings of the
33
rd
Computational Complexity
Conference
, Schloss Dagstuhl–
Leibniz-Zentrum fuer Informatik,
Dagstuhl, Germany, 2018, 20.
18.
Natarajan, A., Wright, J.
NEEXP
⊆
MIP*. arXiv preprint
arXiv:1904.05870v3 (2019).
19.
Ozawa, N. About the Connes
embedding conjecture.
Jpn. J.
Math.
8
, 1 (2013), 147–183.
20.
Peres, A. Incompatible results of
quantum measurements.
Phys. Lett.
A
151
, 3–4 (1990), 107–108.
21.
Rogers Jr., H.
Theory of Recursive
Functions and Effective Computability
.
MIT Press, Cambridge, MA, USA, 1987.
22.
Tsirelson, B.S. Some results and
problems on quantum bell-type
inequalities.
Hadronic J. Suppl.
8, 4
(1993), 329–345.
23.
Tsirelson, B.S. Bell inequalities and
operator algebras, 2006. Problem
statement from website of open
problems at TU Braunschweig, 2006.
Available at http://web.archive.org/
web/20090414083019/ http://
www.imaph.tu-bs.de/qi/problems/
33.html.
Zhengfeng Ji
(zhengfeng.ji@uts.edu.au),
School of Computer Science, University of
Technology Sydney, Sydney, Australia.
Anand Natarajan
(anandn@caltech.edu),
Department of EECS, Massachusetts
Institute of Technology, Cambridge, MA,
USA.
Thomas Vidick
(vidick@caltech.edu),
Department of Computing and
Mathematical Sciences, California Institute
of Technology, Pasadena, CA, USA.
John Wright
(wright@cs.utexas.edu),
Department of Computer Science,
University of Texas at Austin, Austin, TX,
USA.
Henry Yuen
(hyuen@cs.columbia.edu),
Department of Computer Science,
Colombia University, New York, NY, USA.
References
© 2021 ACM 0001-0782/21/11 $15.00