CoursFSMP Fall20
CoursFSMP Fall20
Thomas Vidick
1 (Thomas: To the reader: feel free to make corrections where appropriate. If you would like me to notice a
correction, use the macro “\typo{· · ·}”. If you would like to insert a comment, use the macro “\com{· · ·}”.)
2
Contents
1 Introduction 7
1.1 Presentation of the course . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 What is a qubit? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1 Observables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.2 First definition of a qubit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.3 Jordan’s lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.4 n qubits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.5 Approximate qubits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2.6 An operational definition? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Testing a qubit 17
2.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Interactive proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 An operational definition of a qubit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 A first test for a qubit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4.1 Entanglement and density matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4.2 The protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5 Scaling it up: a test for quantum memory . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5.1 Uncertainty relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5.2 A test for large quantum memory . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3
4 Testing a qubit under computational assumptions 47
4.1 Simon’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.1.1 The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.1.2 Instantiating the black box . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.2 Computational assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.2.1 PPT and QPT procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.2.2 Claw-free functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2.3 Hardcore bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3 A computational test for a qubit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4
9 Compression of nonlocal games 101
9.1 An overview of the proof of RE ⊆ MIP ∗ . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
9.1.1 A cartoon version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
9.1.2 The Halting problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
9.1.3 Compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
9.1.4 A self-referential verifier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
9.1.5 A game for the halting problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
9.2 The compression procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
9.2.1 A test for n qubits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
9.2.2 How to delegate a nonlocal game . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5
6
Lecture 1
Introduction
7
computational capabilities and can hence solve any computational problem they like, including the
one that the verifier is concerned with. However, it is assumed that the provers are not trusted: they
will always try to convince the verifier that the answer to the problem in question is “yes” (e.g. “yes,
this graph does have a valid 3-coloring”). The verifier has to employ certain tricks, or “tests”, to detect
any malicious behavior by the provers, so as never to make the wrong decision. The class RE denotes
all problems for which there is an algorithm, running in any amount of time, that always eventually
halts with the answer “yes” when this is the case (the algorithm does not need to halt in other cases).
RE is a mind-boglingly large class of problems; it contains any decidable problem and even some
undecidable ones such as the halting problem, which is complete for the class.
The equality MIP ∗ = RE is surprising in that it shows that access to untrusted quantum provers
grants exceedingly large verification power to the polynomial-time verifier. In contrast, it is known
that the same class without entanglement between the provers, denoted MIP, is much smaller, MIP =
NEXP. Other motivations for the result tie it to questions in the foundations of quantum non-locality
(“Tsirelson’s problem”) and the theory of operator algebras (“Connes’ embedding problem”) which
we will discuss in due time.
There is a deep connection between the two papers mentioned above (as well as the many works that led
to them—although the course is not meant to be a comprehensive survey, we will review the most relevant
references in due course). Indeed, at their heart both works identify means by which a classical procedure
is able to certify an appropriate “quantum computation workspace” within one (or two) quantum devices,
using only a classical interaction with it. In this sense, and to borrow the title of one of the important earlier
papers in this area [RUV13], both works provide techniques to tie a “classical leash” around a quantum
system. In order to achieve this, both works ultimately have to tackle the same fundamental problem: what
are classical signatures of quantum processes that can be leveraged to certify an entire computation? Very
informally, we will see that in the case of (a) this signature is provided by the uncertainty principle: the fact
that certain measurements in quantum mechanics are intrinsically incompatible; in the case of (b) it will be
provided by quantum non-locality: the fact that entanglement allows distant parties to generate correlations
that have no classical equivalent.
We have motivated our choice of topics by arguing that they tackle a fundamental problem, that of clas-
sically testing a quantum system. This is a problem of practical relevance (given an experimental quantum
device, does it really do anything quantum?) as well as one that reaches deep to the power and limitations of
the scientific method (for a discussion from an epistemological point of view, I recommend the great presen-
tation by Aharonov and Vazirani [AV12]). It is also a problem that has turned out to stimulate many recent
advances in quantum cryptography and complexity. For example, early works in delegated computation en-
couraged the development of quantum authentication codes, such as the Clifford code, that have found wide
uses in cryptography; the study of quantum entangled-prover interactive proof systems has brought many
discoveries in the foundations of quantum non-locality, such as dimension witnesses. The topics are con-
nected through the common framework of interactive proof systems and share many techniques. Throughout
the course we will make an effort to highlight the many open questions that stimulate research in this area
and hope that our choice of results will provide a compelling entry point to it.
Having set the stage, let us discuss the structure of the course. We will start by tackling arguably the
most fundamental question in this line of work: what is a qubit? How to define it mathematically, and
how does one “certify” its existence? What does it mean to “test a qubit,” and how can it be done? This
question will occupy us for the coming four lectures. Exploring it will give us the opportunity to lay common
foundations for the discussion of results (a) and (b) above. The remaining 6 lectures will be equally divided
in two sets of 3 lectures each. The first set will examine the problem of delegation of polynomial-time
8
quantum computations in general, and then focus on a presentation of Mahadev’s result. The second set will
discuss the theory of multi-prover interactive proof systems and build towards an understanding of the main
ingredients in the result by Ji et al.
We will start the course slowly, so that the first few lectures are accessible to as broad a public as
possible. The content will be mathematically precise and as self-contained as can be, so that it is possible
to follow starting with only an elementary background in quantum computing at the level of the Nielsen &
Chuang textbook [NC02]. Later lectures will be more involved and may require a somewhat more advanced
knowledge of certain topics in cryptography or in complexity theory; I will aim to keep the presentation as
self-contained as possible. My goal is that by the end of the course an assiduous participant may dive into
either paper with a solid understanding of the main steps and key techniques in mind.
unless specified otherwise we consider that Hilbert spaces are always finite dimensional and computation is always performed on
qubits in C2 or possibly higher-dimensional qudits in Cd for d ≥ 1 a (finite) integer.
9
1.2.1 Observables
While the state space of a qubit is generally taken to be C2 , more generally a quantum mechanical state
lies in an arbitrary separable Hilbert space H.3 The term “observable” is used to denote any quantity that
can in principle be obtained as the result of a measurement: for example, position, momentum, spin, energy
(with respect to a certain Hamiltonian), are all observables. In full generality an observable is specified by
a Hermitian operator O on H.4 The interpretation of this is that each eigenvalue of O represents a possible
outcome under a measurement of the observable, and the associated eigenvectors denote states under which
the observable deterministically yields that outcome. Thus if O = ∑i λi Πi is a spectral decomposition of
O, then any state |ψi such that Πi |ψi = |ψi will deterministically yield the outcome λi when measured
according to O. In particular, we see that the important part of an observable is its eigenprojections rather
than the associated eigenvalues: the latter are real numbers that are associated to the different possible
experimental outcomes. These numbers are generally associated to a physical meaning (such as position,
momentum, etc.) but they can easily be changed by post-processing.
A collection of projection operators {Πi } that sum to identity is called a Projector-Valued Measure
(PVM). When the Πi are no longer required to be projections, it is called a Positive Operator-Valued Mea-
sure (POVM). This is the most general kind of measurement that is allowed in quantum mechanics. Given a
POVM {Πi } the Born rule specifies√that a measurement of an arbitrary state |ψi under it will yield measure-
ment outcome i with probability k Πi |ψik2 = hψ|Πi |ψi. Since the Πi form a resolution of the identity
(∑i Πi = Id) and k|ψik2 = 1 we see that these probabilities always sum to √ 1, as they should.
√ When the
outcome
√ i is obtained, the state evolves to a post-measurement state | ψ 0i = Π i | ψ i / k Π i | ψ ik . (Here
Πi is generally taken to be the positive square root of Πi . However, other square roots can be used as
well: since different square roots differ only by a unitary degree of freedom, choosing the one over the other
is analogous to imposing an additional reversible evolution on the post-measurement state, which can be
considered to be part of the measurement itself.)
In case the {Πi } are obtained from some observable O, we may use the associated eigenvalues to
associate a real value to each measurement outcome i. In this case the expectation of the outcome of the
measurement is
∑ λi kΠi |ψik2 = ∑ λi hψ|Πi |ψi = hψ|O|ψi ,
i i
a quantity that is sometimes referred to as the “overlap” of |ψi on O. We will use this formula often.
An observable such that O2 = Id has at most two eigenvalues, which by convention we take to be −1
and +1. Such an observable is called a binary observable; it is the most frequent kind of observable that we
will encounter.
the domain of O. If H is finite-dimensional then a matrix representation of O† is obtained by taking the conjugate-transpose of a
matrix representation of O.
10
Definition 1.1 (Qubit, Take 1). A qubit is a triple (H, X, Z ) consisting of a separable Hilbert space H and
a pair of Hermitian operators X, Z acting on a H such that X 2 = Z2 = Id and { X, Z } = XZ + ZX = 0.
Let’s see why Definition 1.1 captures the intuitive notion of “mutually incompatible” observables. Let
the ‘computational basis’ be an eigenbasis of Z, and the ‘Hadamard basis’ an eigenbasis of X. Then we
claim that the anticommutation relation XZ + ZX = 0 ensures that any vector in the former makes a 45◦
angle with any vector in the latter. To see this, let |ψi be an eigenvector of X with associated eigenvalue
ε ∈ {±1}. Then hψ| XZ + ZX |ψi = 0 immediately implies 2εhψ| Z |ψi = 0. Given that Z only has
−1 and +1 as eigenvalues, this relation implies that the projections of |ψi on the two eigenspaces of Z
have equal length; in other words, |ψi lies exactly between the +1 and −1 eigenspaces of Z. (Yet another
way of saying this is that all principal angles between an eigenspace of X and one of Z are π4 ; we will
make this precise soon.) In this sense any X and Z satisfying the conditions of the definition are “maximally
incompatible”: any definite state for the one is entirely undetermined (i.e. yields uniformly random outcomes
when measured) under the other.
There is a problem with this definition: by allowing the underlying Hilbert space H to be arbitrary we
seem to have all but dropped the earlier requirement that a qubit is a system whose state space is “two-level”
and thus identifiable with the projective space S(C2 ). Luckily, the following lemma allows us to make the
connection with this requirement.
Lemma 1.2. Let (H, X, Z ) be a qubit. Then there is a Hilbert space H0 and an isomorphism H ' C2 ⊗ H0
such that under the same isomorphism, X ' σX ⊗ Id and Z ' σZ ⊗ Id.5 Here, σX and σZ are the usual
Pauli observables on C2 : in matrix form,
0 1 1 0
σX = and σZ = .
1 0 0 −1
Note that a consequence of the lemma is that qubits, as defined in Definition 1.1, only exist in spaces
of even (or infinite) dimension! In particular, qubits don’t exist in dimension 1; indeed, in dimension 1 all
operators commute. This is satisfactory: intuitively, a situation in which all possible observables commute
ought to be considered “classical” (for instance, because there is a complete set of simultaneous eigenvectors
for all observables).
It will be essential for our later goals that Definition 1.1 does not a priori require H to be a two-
dimensional space. Indeed, how would one test such a claim? One does not “see” the dimension of the state
space; while it is possible to probe parts of it it can never be excluded that the state space is larger than what
is accessible to the experimentalist’s setup. In this sense Definition 1.1 has a nice “operational” flavor to it:
it refers to observables of the system and their properties. Although much more work is needed before we
are able to make any of these statements formal, we see the definition as a good step towards giving us the
ability to “test” that a system “is a qubit”. In addition, the definition clearly has meaningful consequences;
in particular it implies that qubits do not have a “classical explanation”, so that a “test for a qubit” can serve
as a “test for quantumness”, i.e. a test that distinguishes quantum from classical behavior.
The proof of the lemma makes use of an elementary but fundamental tool in the analysis of many
quantum information protocols, the CS (for “Cosine-Sine”) decomposition. This decomposition is also
known as “Jordan’s lemma,” after Camille Jordan’s Traité des substitutions et des équations algébriques
from 1870 (see this EHESS PhD thesis [Bre06] for a masterful 730-page account of the history behind the
5 The reader might wonder what happened to σY ... Don’t we need it to define our qubit? Here we are taking the “operator
algebraists”’ perspective, which is that if the system supports X and Z observables then it also supports Y = iXZ. Because Y is
determined by X and Z, we do not include it in the definition.
11
use of Jordan’s name alongside this theorem). Given that we will use the lemma frequently we give it a
self-contained treatment in the next section.
where c = cos θ and s = sin θ for some θ ∈ [0, π/2). (Other values of θ reduce to this case because the
sign of cs can be flipped by negating the second basis vector for the chosen basis of S .) Note finally that
since S is stable by both P and Q it is stable by R = P + Q, so it has a basis made of eigenvectors of
R, the vector | ϕi that we started from and its orthogonal in R. Proceeding in this way inductively this lets
us identify an eigenbasis of R such that its vectors are either isolated (stable by both P and Q) or in pairs
(spanning a 2-dimensional subspace that is stable by both P and Q).
The following lemma summarizes the discussion so far.
Lemma 1.3. Let P, Q be projections on a separable Hilbert space H. Then there exists an orthogonal
decomposition H = ⊕i Si such that each Si is a 1- or 2-dimensional subspace that is stable by P and Q.
Furthermore, whenever Si is 2-dimensional there is a basis for it in which P and Q take the form (1.2), for
some ci and si that may depend on Si .7
This very useful lemma informally says that, when only two projections are concerned, we can reduce
the analysis to a 2-dimensional problem. Let’s apply it to show Lemma 1.2.
Proof of Lemma 1.2. Let H, X, Z be as in the statement of the lemma. Let P = 12 ( Z + Id) and Q =
1
2 ( X + Id). Then P, Q are projections on H so we can decompose them according to Lemma 1.3. Let
(|ei i, | f i i) be a basis for the i-th space Si in which the matrices for P and Q have the form (1.2). Using
XZ + ZX = 0 it follows that (i) there cannot be any 1-dimensional blocks, because these necessarily
6 Here we are using that H is separable.
7 Forthe case of 1-dimensional subspaces, since P and Q are projections they are each either identically 0 or identity in those
subspaces.
12
commute, and (ii) in any two-dimensional block, the angle θ must equal π/4, as this is the only value in
[0, π/2) that leads to anti-commuting operators. Thus in each space Si , Z acts exactly as σZ and X as σX .
Let H0 have canonical basis {|i i}, where i ranges over the block indices in the decomposition of P and Q.
The required isomorphism is obtained by e.g. mapping |ei i ∈ H to |0i ⊗ |i i ∈ C2 ⊗ H 0 and | f i i ∈ H to
|1i ⊗ |i i ∈ C2 ⊗ H0 .
1.2.4 n qubits
Now that we have a working definition of a qubit, how about two, three, or even n qubits? What we mean
when we say that a system “has n qubits” is that (i) it should have n copies of one qubit, so there should be
( X1 , Z1 ), ( X2 , Z2 ), . . . , ( Xn , Zn ) on H such that each pair satisfies the definition of a qubit, and moreover
(ii) the qubits should be “independent”: indeed, we wouldn’t want something like X1 = X2 to happen. How
do we prevent this? Intuitively “independence” of the qubits should be reflected in the fact that they can be
observed “independently”, in any order, such that if e.g. we “ observe” qubits 1 and 2 and then discard the
outcome associated with qubit 1, we should obtain an outcome that is identically distributed as if we had
only observed qubit 2 in the first place. These considerations suggest the following definition.
Definition 1.4 (n qubits, Take 1). A system of n qubits is a tuple (H, X1 , Z1 , . . . , Xn , Zn ) consisting of a
separable Hilbert space H and n pairs of Hermitian operators ( Xi , Zi ) for i ∈ {1, . . . , n} acting on H such
that
[ Xi , X j ] = [ Xi , Zj ] = [ Zi , X j ] = [ Zi , Zj ] = 0 ,
The commutation condition (ii) indeed implies that measurements on different qubits can be performed
“independently”. For example, the expectation of a measurement of qubit 2 in the Hadamard basis after
qubit 1 has been measured in the computational basis is given by (where we write X1 = X10 − X11 for the
spectral decomposition of the observable X1 )
hψ| X10 Z2 X10 |ψi + hψ| X11 Z2 X11 |ψi = hψ| X1 Z2 X1 |ψi
= hψ| Z2 X12 |ψi
= hψ| Z2 |ψi ,
as desired. (Here, for the first equality we used that hψ| X10 ZX11 |ψi = hψ| X11 ZX10 |ψi, for the second we
used the commutation condition [ X1 , Z2 ] = 0, and for the last we used X12 = Id.) This calculation can be
done for any pair of qubits, or even any sequence of measurements of qubits, and it shows that item (ii) in
Definition 1.4 indeed captures the idea that each of the n qubits can be measured independently.
Note however that this “independence” is not necessarily quite the same as there truly being n qubits. In
particular, if our definition of a qubit only required the use of a single observable X, as a classical bit would,
then taking X1 = · · · = Xn would satisfy both (i) and (ii), since an operator always commutes with itself.
Indeed, just as we’re used to a qubit being defined through its state space S(C2 ), we’re used to n qubits being
defined through their state space S(C2 ) ⊗ · · · ⊗ S(C2 ). Where is the tensor product in Definition 1.4, isn’t
it missing? The following lemma shows that an n-fold tensor product is in fact implicit in the definition.
13
Lemma 1.5. Let (H, X1 , Z1 , . . . , Xn , Zn ) be a system of n qubits. Then there exists a Hilbert space H0 and
an isomorphism H ' (C2 )⊗n ⊗ H0 such that under the same isomorphism, for every i ∈ {1, . . . , n} and
W ∈ { X, Z }, Wi ' σW,i ⊗ IdH0 , where here σW,i denotes the Pauli W operator acting on the i-th copy of
C2 .
Proof. We show the lemma by induction on n ≥ 1. The case n = 1 is provided by Lemma 1.2. Suppose
the lemma shown for some n ≥ 1, show it for (n + 1). Let (H, X1 , Z1 , . . . , Xn+1 , Zn+1 ) be a system of
(n + 1) qubits. Since (H, X1 , Z1 , . . . , Xn , Zn ) is a system n qubits we can apply the induction hypothesis
to it. Let H0 and π 0 be the promised space and isomorphism. The key step is provided by the following
claim.
Claim 1.6. Let W be an Hermitian operator on H such that [W, Xi ] = [W, Zi ] = 0 for all i ∈ {1, . . . , n}.
Then there exists W 0 Hermitian acting on H0 such that under π 0 , W ' Id(C2 )⊗n ⊗W 0 .
The claim immediately gives us the induction step: by applying it to Xn+1 and Zn+1 we find Xn0 +1 and
Zn0 +1 on H0 such that (H0 , Xn0 +1 , Zn0 +1 ) is a qubit. Applying Lemma 1.2 to this qubit and composing the
isomorphism obtained with π 0 completes the induction step. Therefore, it only remains to prove the claim.
Proof of Claim 1.6. Clearly it suffices to prove the statement “under π”, i.e. for the case where Xi = σX,i
and Zi = σZ,i . We introduce the following notation: for a, b ∈ {0, 1}n ,
a1 an b1 bn
σX ( a) = σX,1 ⊗ · · · ⊗ σX,n and σZ (b) = σZ,1 ⊗ · · · ⊗ σZ,n .
Using that the four 1-qubit Pauli matrixes Id, σX , σZ and σX σZ form a basis for the complex vector space of
linear operators on C2 , W has a decomposition
where Wa,b are arbitrary operators on H0 (they are not necessarily Hermitian). Let’s write out the left and
right products of W with σX (c)σZ (d), for some c, d ∈ {0, 1}n :
where in the second line we used the anti-commutation relation σZ (d)σX ( a) = (−1) a·d σX ( a)σZ (d), as
well as the “additivity” relations σX ( a + c) = σX ( a)σX (c), and similarly for σZ . Similarly,
Using that the σX ( a)σZ (b) are linearly independent we can identify terms in (1.3) and (1.4); it follows that
for any a, b, c, d, (−1)b·c Wa,b = (−1) a·d Wa,b . For any ( a, b) unless a = b = 0 we can find strings c, d
such that the two terms in Wa,b are given opposite signs. Thus Wa,b = 0 whenever ( a, b) 6= (0, 0), and
W = Id ⊗W0,0 . Since W is Hermitian, W0,0 is also Hermitian, proving the claim.
14
Remark 1.7. The statement of Lemma 1.5 can be reformulated in the language of group representation
theory, and this reformulation will be useful later on. The “n qubit Weyl-Heisenberg group” is the 2 · 4n -
element group Gn that is generated by the n-qubit σX and σZ matrices; its elements are (−1)c σX ( a)σZ (b)
for a, b ∈ {0, 1}n and c ∈ {0, 1}. From any system of n qubits (H, X1 , Z1 , . . . , Xn , Zn ) it is straightforward
to specify a representation φ of Gn by setting φ((−1)c σX ( a)σZ (b)) = (−1)c ∏i Xiai ∏i Zibi . The lemma
can be adapted to show that any representation of Gn that in addition sends −1 to −1, as φ does, must be a
direct sum of copies of the representation by Pauli matrices.
Exercise 1.1. Suppose that X and Z are binary observables on H such that k{ X, Z }k ≤ ε for some ε ≥ 0,
where k · k denotes the operator norm (largest singular value). Show that there exists a qubit (H, X 0 , Z 0 )
such that max{k X − X 0 k, k Z − Z 0 k} ≤ δ(ε). State the best dependence δ that you can get.
The exercise can be extended to consider n approximate qubits, but the proof is more delicate as some
work is needed to keep the errors under control. The following is shown in [CRSV17].
Theorem 1.8. Let X1 , Z1 , . . . , Xn , Zn be binary observables on H and ε ≥ 0 such that ε/(1 − ε)2 ≤
1/(64n) and k{ Xi , Zi }k ≤ ε and k[Si , Tj ]k ≤ ε for all i 6= j ∈ {1, . . . , n} and S, T ∈ { X, Z }.8 Then
there exists binary observables X10 , Z10 , . . . , Xn0 , Zn0 on H such that { Xi0 , Zi0 } = 0, [Si0 , Tj0 ] = 0 and moreover
kS0j − S j k ≤ 4nε/(1 − ε)2 + ε for all i 6= j ∈ {1, . . . , n} and S, T ∈ { X, Z }.
The theorem shows that “n approximate qubits” are close to “n exact qubits” according to our defini-
tions. Note that there is a dependence of the error on n, but not on the dimension of H. In [CRSV17] it is
shown by an explicit example that a linear dependence on n is necessary.
15
16
Lecture 2
Testing a qubit
Recall the definition of a qubit from the first lecture: a qubit is a triple (H, X, Z ) of a Hilbert space H
and a pair of binary observables X and Z on H such that { X, Z } = 0. Unfortunately, this definition is far
from operational! The operator condition { X, Z } = 0 is not something that we can hope to test based on
experimental data alone. A simple reason for this is that in general we may only hope to observe expectation
values for observables W evaluated on a certain state |ψi. While we may be able to prepare quite a range
of states |ψi using our experimental system, there is no hope that we can prepare all possible states, which
would be required for a full “tomography” of the observable.1
Today we tweak our definition to obtain a new one that we claim is truly “operational,” and we start
exploring means of justifying this claim by showing how the definition can be “tested”.
2.1 Setup
Before we can make precise what we mean by “operational” we need to describe the framework in which we
operate. This framework is inspired by an (idealized) perspective on how “real-life” experiments are made.
An experiment can be formalized as an interactive process that involves two entities. One of the entities is
the “experimentalist”, whom we will refer to as the verifier. The other entity is the “quantum device” on
which the experiment is being performed. We will personify that device and refer to it as the prover. (We
motivate this terminology a little later.)
In an experiment the experimentalist generally has a model of how the device is expected to behave.
This model can be used to predict the input-output behavior for the device, i.e. how it will react to various
stimuli that the experimentalist might subject it to. For example, the device may be the combination of a
laser, a sheet of paper with two slits on it, and a screen. This device takes inputs in {0, 1}2 that model the
experimentalist’s choice of slits to open (0 for ’open’ and 1 for ’closed’). The device’s outputs are elements
of, say, { R, G, B}1000×1000 , i.e. a 1000 × 1000 pixel RGB image of the screen. The experimentalist’s model
makes a prediction for the device’s output pic ab on each possible input ( a, b). In addition, if the experimen-
talist follows best practices in statistics they should decide a priori on a scoring function that determines,
whenever the experiment is performed, a “success score” for the experimental outcome obtained. In our ex-
ample we could use the normalized Hamming distance 10−6 d H ( pic ab , res ab ) where for a, b ∈ {0, 1}, pic ab
is the ideal outcome and res ab the experimental outcome. The experimentalist would then repeatedly provide
1 The problem is distinct from the “exponential scaling” of the Hilbert space: here, the issue is that we simply can’t expect that
the experimentalist has the ability to probe the system’s entire Hilbert space; in particular, we cannot impose any dimension bound
a priori.
17
inputs ( a(i) , b(i) ) to the device for i = 1, . . . , chosen uniformly at random or with some smarter distribution
(e.g. she could decide to never test the case (1, 1) corresponding to both slits closed), obtain a sequence of
outputs res(1) , res(2) , . . ., and return an averaged score that quantifies agreement of the experiment with the
theory.
Having set the stage with this rather loose description we make some important remarks:
1. Our notion of interactive experiment substantially restricts the means by which the experimentalist
may interact with the device. The experimentalist is allowed to provide classical inputs and obtain
classical outputs in return. While there may be some semantics associated with the inputs and outputs
(“which slit is open”, “an RGB image”) when the experiment is performed there is no guarantee that
these semantics correspond to any real-life phenomenon: inputs and outputs are strings of bits, nothing
more. There is no a priori guarantee that the device has any number of “slits” that are being “opened”
or “closed”; maybe the mysterious device contains a student equipped with a textbook on quantum
mechanics that allows her to calculate a reasonable outcome for the experiment. We emphasize that
“in real life” the experimentalist will typically make a number of explicit and implicit assumptions
about the system that is being tested and how it is accessed; here we aim to minimize such assumptions
to the extreme.
2. The insistence on classical inputs and outputs also means that we forbid the experimentalist from
directly accessing the quantum state or measurements of the device. One of our basic goals is to
devise tests that distinguish a classical device from a quantum one, and so we cannot assume any
quantum access to it a priori. We will formalize this model of “black-box access” in more detail in
the next section.
3. Nevertheless, we will assume throughout that quantum mechanics is a correct theory, i.e. the device
can always be modeled using the framework of quantum mechanics: it has a quantum state (that may
be entangled with the environment) that it evolves unitarily and measures according to the Born rule.
What we will aim to test is e.g. that the device does not have a model in classical mechanics.
4. Assuming correctness of quantum mechanics will not suffice. Make sure that you can convince your-
self of the following statement: “for any non-trivial experiment, i.e. such that for each possible input
of the verifier there is at least one output that would be accepted, there is a classical device that is
always accepted in the experiment.” In other words, any meaningful experiment will need to place
additional assumptions on the device: maybe the “valid” outcomes are hard to compute for a clas-
sical device, or maybe they are impossible to generate without entanglement or communication, etc.
Are we contradicting our first item? It all depends on what the assumption is. We will aim for as-
sumptions that require the least “faith” possible in the adequate execution of the experiment (i.e. the
experimentalist’s skills).
5. We ended the description of the double slit experiment by suggesting that the experimentalist may re-
peat the same experiment multiple times in order to collect statistics. In real life there is no guarantee
that a device behaves identically from one experiment to the next; its behavior may naturally fluctuate
with time, or it may have memory and adapt itself, etc. The assumption that the device can be ac-
cessed repeatedly without changing its behavior is called the “i.i.d. assumption”, for “identically and
independently distributed”. We will make that assumption when it is convenient; more often than not
it can be dropped at the cost of substantial technical work that we will not always have the opportunity
to accomplish.
18
2.2 Interactive proofs
With this informal motivation for our notion of an “interactive experiment” in place we now give a more
precise framework for modeling such experiments. For this we adapt the framework of interactive proof
systems from cryptography and complexity theory. In this framework it is generally assumed that a trusted
entity called the verifier interacts with an not-necessarily-trusted entity called the prover. The verifier is
trying to verify some claim about the world (e.g. in complexity, that some input formula ϕ is satisfiable) or
about the prover itself (e.g. in cryptography, that the prover has the right identifying information). Towards
this the verifier may “interrogate” the prover in an interactive manner. At the end of the interaction the
verifier makes a decision to accept or reject. Informally, the proof system will be called “sound” if whenever
the verifier accepts, the claim is indeed true.
The formal definition of an interactive proof system makes use of the notion of “interactive Turing
machine” to model the prover and verifier. Since this formalism will not be essential for us we refer the
interested reader to [VW16, Chapter 4] for details. In complexity theory an interactive proof is always
associated to a language, that is a collection of problems, usually specified by strings x ∈ {0, 1}∗ , such that
some of the problems have an affirmative answer and some have a negative answer (e.g. the problems could
be graphs, and the ones with affirmative answer those that have a proper 3-coloring). At the beginning of
the interactive proof both prover and verifier are provided with a problem instance x, and the goal of the
verifier is to leverage the prover’s computational power to help her determine if x is a positive instance, all
the while accounting for the fact that the prover may misbehave.
For our purposes we are led to slightly broaden the notion in an informal manner, so that we can not
only associate interactive proof systems to formal languages but also to statements about the device itself,
as is sometimes done in cryptographic applications of interactive proof systems. We will thus refer to an
interactive proof system, or sometimes more simply a “test,” for a hypothesis H as the specification of a
verifier in an interactive protocol with the following properties: (In the protocol both verifier and prover
may be provided with some auxiliary input, a classical xV for the verifier and a quantum ρ P for the prover.)
1. Completeness: This property means that whenever the hypothesis H (which may depend on xV and/or
ρ P ) is satisfied there is a way for the prover to be accepted in the protocol “with high probability.” We
will sometimes use a parameter c ∈ [0, 1] to designate the probability that a “honest prover” succeeds
in the protocol.
2. Soundness: This property means that whenever the hypothesis H is not true no prover can succeed in
the protocol with probability higher than a small quantity s ∈ [0, 1] termed the “soundness parameter”.
We give a few examples. In the traditional setting of interactive proof systems the hypothesis H is that
xV = ρ P ∈ L, where L is a fixed language, xV is the verifier’s input, and the prover’s input ρ P is assumed
to equal xV . For example if L = 3COL then completeness states that whenever both V and P are provided
with the valid description of a graph as input, and that this graph is 3-colorable, there must be a way for
the prover to convince the verifier that this is so; soundness states that whenever xV designates a graph that
is not 3-colorable, irrespective of what ρ P is there is no way for the prover to convince the verifier. (An
interactive proof system that satisfies both conditions is one in which the verifier simply expects the prover
to directly provide it with a proper coloring.)
As a second example, H could be the hypothesis that “P has the BB’84 state that is specified by xV ”.
In this case we expect that e.g. xV = (v, θ ) for v, θ ∈ {0, 1} and ρ P = H θ |vi. Completeness states that if
this is indeed the case then there should be a way for P to succeed; soundness states the converse. There is
an easy quantum protocol for this hypothesis in which P is expected to provide its qubit to V, who verifies
it by performing the appropriate measurement. But is there a classical protocol?
19
Finally, a less formal but more interesting for us example is that we could consider H to be the hypothesis
that “P has a qubit.”. In this case we do not make use of the auxiliary inputs; completeness states that for
any prover that does have a qubit (i.e. P has access to observables X, Z on H such that { X, Z } = 0) then
there should be a way for it to succeed in the protocol, whereas soundness states that conversely, any prover
that succeeds in the protocol must “have a qubit.”
case using cyclicity of the trace, Tr(Π ax ρ) = Tr(Π ax |ψihψ|) = hψ|Π ax |ψi.
3 We write “at best” because the experimentalist does not get to see probabilities. Under the i.i.d. assumption it can sometimes
estimate them to within an additive error. However, in the case where A is a large alphabet it may be that all probabilities are
exponentially small. This will be the case in some of the experiments that we describe.
20
Definition 2.2 (Qubit, Take 2). A qubit is a triple (|ψi, X, Z ) such that |ψi ∈ S(H), where H is a separable
Hilbert space left implicit in the notation, and X and Z are Hermitian operators on H such that
{ X, Z }|ψi = 0 . (2.1)
Note that the definition still makes the requirement that X 2 = Z2 = Id as operators. This is because this
requirement follows from the laws of quantum mechanics themselves; informally, it just means that each of
X and Z has a spectral decomposition with two associated eigenprojections, i.e. they represent valid binary
observables.
At this point there are two important questions we should be asking: (i) Is this definition meaningful?
With the anti-commutator weakened as in (2.1), does the definition still capture our intuitive notion of a
qubit? (ii) We weakened the definition in an arbitrary-looking way by inserting a dependence on the state
vector |ψi. Can we justify this, i.e. are we now able to develop protocols that test the definition?
In the remainder of the lecture we provide partial answers to these two questions. To answer the first,
we show the following.
Lemma 2.3. Let (|ψi, X, Z ) be a qubit on H. Then there exists a Hilbert space H0 and an isometry
V : H → C2 ⊗ H0 such that
VX |ψi = (σX ⊗ Id)V |ψi and VZ |ψi = (σZ ⊗ Id)V |ψi . (2.2)
The following diagram illustrates the situation guaranteed by the lemma:
V
H C2 ⊗ H 0
X, Z σX ⊗Id, σZ ⊗Id (2.3)
V
H C2 ⊗ H 0
Note that the lemma no longer says that X is equal to σX ⊗ Id (under the isomorphism π), but only that it
has the same action on the state, up to the isometry V. In particular, it is now possible for H to have odd
dimension. This is necessary: for example, we can set
1 0 1 0 1 0 0
| ψ i = 0 , X = 1 0 0 , Z = 0 −1 0
0 0 0 1 0 0 1
and still satisfy Definition 2.2. Here, the third dimension has been added to the operators but since none
of |ψi, X |ψi or Z |ψi has support on it it is “inaccessible” to any experiment that involves only this state
and operators. However, it is good to verify that the definition is non-trivial, and in particular requires
dim(H) ≥ 2. Indeed, suppose that X |ψi and Z |ψi are colinear. Then by (2.2) it follows that (σX ⊗
Id)V |ψi and (σZ ⊗ Id)V |ψi are colinear. As we saw in the previous lecture, due to {σX , σZ } = 0 this is
impossible.
Proof. The proof is very similar to the proof of Lemma 1.2. Using Jordan’s lemma we find a decomposition
H = ⊕i Si such that for each i, Si is stable by both X and Z and moreover either
Si is 1-dimensional
ci si
or Si is 2-dimensional and in a well-chosen basis, Z = σZ and X = for some ci = cos 2θi ,
si − ci
θi ∈ [0, π/2). For the one-dimensional blocks the anti-commutator equals (2). For a two-dimensional
block we compute { X, Z }2|S = 4c2i Id. Decompose |ψi = ∑i αi |ψi i with |ψi i ∈ Si . Then we immediately
i
see that if Si is a 1-dimensional block, or a 2-dimensional block such that ci 6= 0, then αi = 0. This proves
the lemma.
21
Note that the proof of the lemma shows something slightly stronger than is captured by the statement of
the lemma: informally, that for any of the subspaces Si on which |ψi “has nonzero mass”, it must be that
{ X, Z }|Si = 0, as operators. But we can’t conclude anything about blocks where |ψi “has no mass”.
The proof that we gave easily extends to the approximate case.
Exercise 2.1. Say that (|ψi, X, Z ) is an ε-approximate qubit if k{ X, Z }|ψik ≤ ε. Show that there is an
isometry V : H → C2 ⊗ H0 such that for W ∈ { X, Z },
2
W − V † (σW ⊗ Id)V |ψi
≤ O(ε) .
√
[Hint: Use 2(1 − sin θ ) ≤ 4 cos2 θ for θ ∈ [0, π ).]
We end the section with a semi-informal definition of “self-testing” that connects the notion of interactive
experiment that we discussed earlier with the definition of qubit that we arrived at. For convenience we state
the definition for the setting of an experiment that involves a single round of interaction: a question x is
selected by the experimentalist, and an answer a is provided by the device. The “observable data” of such
an experiment is completely captured in the family of distributions { p(·| x )} x∈X over A, and so the starting
point for the definition is that data only.
Definition 2.4. We say that the family of conditional distributions { p(·| x )} x∈X self-tests a qubit if for any
state |ψi ∈ S(H) and family of POVM { Pax } a∈A for x ∈ X such that p( a| x ) = hψ| Pax |ψi for all a, x there
is an isometry V : H → C2 ⊗ H 0 and x0 , z0 ∈ X such that the measurements P x0 and P x1 have only two
possible outcomes 0, 1 and moreover
V ( P0x0 − P1x0 )|ψi = (σX ⊗ Id)V |ψi and V ( P0z0 − P1z0 )|ψi = (σZ ⊗ Id)V |ψi . (2.4)
As you can see the definition is a little uncomfortable to state; not only does the notation quickly get
pretty heavy but one also has to be quite careful to make a meaningful statement for the applications that
one has in mind.
The use of the isometry in the definition may come as a surprise, because it allows us to “artificially”
extend the space in which the operators live. This is necessary because as discussed below Definition 2.2
in general the dimension of H may not be even, whereas any space in which we can write something like
“σX ⊗ Id” must have even dimension. For the time being you can think of V as an artifact that may create
additional dimensions in which V |ψi has no “mass” at all, but are still needed to give the desired form to
the operators. As discussed below Lemma 2.3, even with the isometry the conclusion of the lemma is not
trivial since it at least implies that dim H ≥ 2.
Unfortunately, it is not hard to see that the definition is not “achievable” in the sense that without further
assumptions, no family of distributions { p(·| x )} x∈X self-tests a qubit in the sense of the definition. This is
simply because in general one cannot avoid that, say, |ψi = 1 ∈ C and Pax = p( a| x ) for all a and x, which
is a valid POVM.4 As such one should only treat this definition as “indicative” and we use it for inspiration
only. In the future we will generally establish special-purpose statements that are more precise depending
on the situation we’re in.
4 It
is also possible to get a trivial realization using projective measurements by taking |ψi to be sufficiently many EPR pairs, or
a more general entangled state, so as to instantiate the randomness required to implement the distribution.
22
2.4 A first test for a qubit
We proceed to give a first answer to our second question, “is the definition testable?” Our answer today will
not be completely satisfactory, but it’s a start. Most important is that it will allow us to practice the notions
introduced so far and put in place techniques that will be useful later on.
In order to analyze the protocol that we give in Section 2.4.2 we will need some elementary notions
about density matrices and entanglement. The reader already familiar with these notions may skip the next
section, which contains a very brief introduction; as usual we refer to [NC02] for a much more leisurely,
and comprehensive, discussion.
where the λi are non-negative reals that sum to k|ψik2 = 1 and {|ui i} and {|vi i} are orthonormal bases
of HA and HB respectively. Here in the notation we sometimes, but not always, include a subscript A or
B (or both) on a “ket” to indicate which subsystem the state lies in. The coefficients λi in (2.5) are called
Schmidt coefficients and are uniquely defined. The {|ui i} and {|vi i} are called Schmidt vectors. The
reduced state of |ψiAB on H A is described by a density matrix ρ A = ∑i λi |ui ihui |, that one can interpret
as a distribution over pure states |ui i. More generally, if ρAB is a density matrix on HA ⊗ HB we use the
notation ρA = TrB (ρAB ) to denote its reduced density on HA , and ρB = TrA (ρAB ) for HB . These reduced
densities can be computed by extending the definition given for pure states by linearity, or in any other of a
number of equivalent ways.
For us, the EPR pair is a specific bipartite state |φ+ i = √1 (|00i + |11i). It has the interesting property
2
that for any orthonormal basis |u0 i, |u1 i of C2 ,
1
|φ+ i = √ (|u0 i|u0 i + |u1 i|u1 i) . (2.6)
2
This is because more generally for a linear operator A on C2 , ( A ⊗ Id)|φ+ i = (Id ⊗ A T )|φ+ i. In particu-
lar, we see that if a measurement of the first qubit is made in the basis {|u0 ihu0 |, |u1 ihu1 |} and the outcome
b ∈ {0, 1} is obtained then the state of the second qubit reflects this fact, becoming |ub ihub |.
v, θ ∈
1. V selects two bits {0, 1} uniformly at random. She prepares a single-qubit state |vθ i = H θ |vi,
1 1
where H = √1 is the Hadamard matrix, and sends it to P.
2 1 −1
23
2. V waits for a few seconds.
3. V sends θ to P.
We claim that any prover that succeeds with probability 1 in this protocol “has a qubit”. Before showing
this, let’s discuss a few points.
• What do you mean, the prover has a qubit? Of course it has a qubit–the verifier sent it to him! Aha,
but remember the discussion surrounding our definition of a qubit! What the prover gets is the state of
a qubit. A good model for a “classical” prover would be one that quickly measures (“decoheres”) any
state it receives in the computational basis, recovering the classical information only. Certainly, such
a prover would not count as having a “qubit”, because any measurement they are able to make is in
the computational basis, and in particular commutes. And indeed, it is easy to verify that such prover
only succeeds with probability at most 3/4 in the test. This is why step 2., the few seconds’ pause, is
inserted in the protocol. As we will see from the proof, we will be able to show that the prover still
“has a qubit” at step 3, when it receives the value θ from v.
• Didn’t we say that the verifier is classical? How come they can prepare qubits? That’s a good point.
As our analysis will show it is possible to show that the same protocol remains valid if we remove the
assumption that the verifier prepares the claimed state. That is, we can assume that an arbitrary entity
prepares an arbitrary (1 + N )-qubit state and sends one qubit to V and the others to P. In that case
the only thing that we need to assume is that the verifier has the ability to measure σX and σZ . So,
using that the verifier has a qubit, they can check that the prover also has a qubit. It’s not so trivial!
• How can you check that the prover succeeds with probability 1? Of course, we can’t. Assuming
that the prover behaves in an i.i.d. fashion, repeating the protocol K ∼ (1/ε) log(1/δ) times and
observing K successes would let us conclude, with confidence 1 − δ, that the prover’s “intrinsic”
probability of succeeding is at least 1 − ε.5
Lemma 2.5. Suppose that a prover P succeeds with probability 1 in the protocol. Then P has a qubit.
To connect the statement of the lemma to Definition 2.4 we could also try to say that in this protocol, the
family of distributions { p(v0 |θ, v) = 1v0 =v }v,θ ∈{0,1} “self-tests” a qubit. As we had predicted however, the
protocol does not neatly fit the definition for multiple reasons: it is not a 1-round protocol, there is quantum
communication, and the verifier maintains private information (the value v).
Proof. Before we show anything let’s first model precisely what goes on in this protocol; this modeling
step is often the most important one in the analysis of a protocol. For the proof it is more convenient (and
also more general) to consider the “purified” variant hinted at above. First, note the following equivalent
description of the protocol:
1. The verifier prepares a two-qubit EPR pair |φ+ i = √1 (|00i + |11i). She keeps the first qubit to
2
herself and and sends the second to the prover.
5 Inother words, we’d show that any prover whose probability of succeeding is < 1 − ε only has a chance at most δ to succeed
in K repetitions.
24
2. The prover applies an arbitrary quantum map to their qubit, yielding the shared state |φ̃i = (Id ⊗W )|φ+ i,
where W is the prover’s operation. In general, the prover’s map can be any isometry6 as the prover
may append ancilla qubits if it so desires.7
3. The verifier flips a coin θ ∈ {0, 1} and measures her qubit in the standard basis (i.e. the eigenbasis
of σZ ) if θ = 0 and the Hadamard basis (the eigenbasis of σX ) if θ = 1, obtaining an outcome
v ∈ {0, 1}.
4.-5. Same.
Using the observation (2.6) (and the discussion that follows it) we see that Step 4 has the effect of projecting
the prover’s share of the joint state to W |vθ i, which is effectively the state that it would be in had we
proceeded according to the original description of the protocol. So, the two descriptions are equivalent.
This “purified” description of the protocol has one major advantage, which is that it allows us to “delay”
Alice’s choice of θ and v until step 3; as we will see this is very helpful. Yet the version that we wrote down
is still not so easy to analyze, mainly due to the fact that the isometry W may be completely arbitrary. As it
turns out it is more convenient to analyze another variant in which the prover is given more power, so that
showing this variant secure will immediately imply the same for the original one. In the new variant we
replace the first two steps by imagining that both verifier and prover are handed out a share of an arbitrary
initial state |ψiAB ∈ C2A ⊗ HB . Here the verifier gets the first subsystem, that is assumed to be of dimension
2, and the prover gets the second subsystem, whose dimension is arbitrary. This is more general because the
state of the verifier’s qubit is no longer characterized (except for its dimension, that we fix to 2). However,
we will show that even in this variant in order to succeed the prover must “have a qubit”.
Remark 2.6. It will generally be convenient to assume that any measurement that the prover makes can
be modeled by a projective measurement. Abstractly, this can be guaranteed by Naimark’s theorem. We
will not review the theorem here, but if you are not familiar with it it is a good idea to make sure that you
understand its formulation. In particular, any use of Naimark’s may require extending the Hilbert space
by adding ancilla qubits to |ψi. This operation is an isometry that one should not forget to include in the
conclusion one is making—it is another reason for including the isometry V from Definition 2.4.
Continuing our modeling effort, at step 4 of the protocol the prover has in its hands (i) the qubit it
received from the verifier, that we model as the second half of some |ψiAB ∈ C2A ⊗ HB (where the extension
to a larger space HB may have occurred as a result of some map that the prover applied during the course
of step 2 in the protocol), and (ii) the value θ ∈ {0, 1} it has received at step 3. Given this information,
it is expected to return a value v0 ∈ {0, 1}. In full generality we can model this by saying that for each
θ ∈ {0, 1} the prover has a measurement { P0θ , P1θ } that it performs on its share of |ψiAB in order to obtain
v0 . Using the remark we may further assume that this measurement is projective, and so we can associate a
binary observable Pθ = P0θ − P1θ , for θ ∈ {0, 1}, to it. While this requires to enlarge the prover’s space to
apply Naimark’s theorem, since here we already allow the space to be arbitrary there is no loss in generality
with assuming at the outset that { P0θ , P1θ } is projective.
With all this modeling in place we are ready to write a formal expression for the prover’s success prob-
6 An isometry is a linear length-preserving map into a larger space. Formally, W : C2 7 → H such that W † W = Id. For example,
W |ui = |ui|0i is an isometry, which simply appends a qubit in state |0i to its input.
7 We can use the ancilla to model a classical prover as well; here, W would simply copy the qubit to an environment register that
would become inacessible to the prover. This effectively decoheres the qubit that remains in the prover’s possession.
25
ability in the test. By definition it is
1
Pr(v = v0 ) = hψ|(|0ih0| ⊗ P00 )|ψi + hψ|(|1ih1| ⊗ P10 )|ψi
2
1
+ hψ|(|+ih+| ⊗ P01 )|ψi + hψ|(|−ih−| ⊗ P11 )|ψi .
(2.7)
2
Here the factors 21 represent the probabilities that the verifier chooses θ = 0 (measurement in the standard
basis) and θ = 1 (measurement in the Hadamard basis) respectively, and inside each bracket each of the
two terms represents the probability that the prover and verifier obtain the same measurement outcome
v = v0 = 0 for the first term and v = v0 = 1 for the second. Using the identities
1 1 1 1
|0ih0| = Id +σZ , |1ih1| = Id −σZ and |+ih+| = Id +σX , |−ih−| = Id −σX
2 2 2 2
as well as the symmetric ones
1 1 1 1
P00 = Id + P0 , P10 = Id − P0 and P01 = Id + P1 , P11 = Id − P1
2 2 2 2
together with some simple manipulations we can rewrite the expression (2.7) as
1 1
Pr(v = v0 ) = + hψ|σZ ⊗ P0 |ψi + hψ|σX ⊗ P1 |ψi .
(2.8)
2 4
This equality is the central equality in the proof, so it is worth looking at it closely. The expression quantifies
some form of “correlation” between the verifier’s observables, σZ and σX , and the prover’s, P0 and P1 . Each
of the numbers inside the brackets on the right-hand side is a real number in [−1, 1] that is the expectation
value of the product of their outcomes, when interpreted as values in ±1. For the success probability to
equal 1 the outcomes must always match. Note, however, that the verifier is making two incompatible
measurements on their share of the state. The following claim shows that in this situation the prover’s
observables must also be incompatible, i.e. anti-commute.
Claim 2.7. Let |ψi ∈ C2 ⊗ H be an arbitrary state and X, Z arbitrary observables on H such that
hψ|σX ⊗ X |ψi = hψ|σZ ⊗ Z |ψi = 1 . (2.9)
Then (Id ⊗{ X, Z })|ψi = 0.
Intuitively, if X and Z were not incompatible then, since X can be used to predict the outcome of σX
and Z that of σZ , by simultaneously measuring the compatible observables X and Z we would be able
to simultaneously predict the outcomes of a measurement in the incompatible observables σX and σZ , a
contradiction. Let’s see the proof.
Proof. Using that all operators have norm at most 1 and that k|ψik = 1 the equality (2.9) implies that
Id ⊗ X |ψi = σX ⊗ Id |ψi and Id ⊗ Z |ψi = σZ ⊗ Id |ψi .
Using these identities,
XZ |ψi = σX σZ |ψi
= −σZ σX |ψi
= − ZX |ψ̃i ,
as required.
26
Exercise 2.2. The proof can be adapted to show a bit more than we extracted from it. By using Lemma 2.3
show that under the same assumptions as in the claim there must exist an isometry V : H → C2 ⊗ H0 on
H under which (IdC2 ⊗V )|ψi = |φ+ i ⊗ |ψ0 i, where |φ+ i = √12 (|00i + |11i is an EPR pair and |ψ0 i an
arbitrary state on H0 . That is, even if we do not assume a priori that the two parties share an EPR pair, they
must do so in order to win with probability 1.
Applying Claim 2.7 to Z = P0 and X = P1 and using (2.8) to verify that (2.9) is satisfied we obtain
that (|ψi, P0 , P1 ) is a qubit according to Definition 2.2. This concludes the proof.
27
it we recall the definition of the Shannon entropy,
H ({ pi }) = − ∑ pi log pi ,
i
for any distribution { pi }. Note that here we use a variant using base 2 logarithms, which is the standard
used for the extension to density matrices, that we give a little later.
Theorem 2.8. Let R and S be observables on H. Let c = max |hψ|φi|2 where |ψi (resp. |φi) ranges over
all eigenvectors of R (resp. S). Let |ψi be an arbitrary state on H and let R and S be random variables
distributed as the outcome of a measurement of R and S on |ψi, respectively. Then
1
H ( R) + H (S) ≥ log2 . (2.10)
c
In the case when R and S are binary observables then c is precisely the squared cosine of the smallest
principal angle between an eigenspace of R and an eigenspace of S. If R and S have an eigenvector in
common then c = 1 and the right-hand side in (2.10) vanishes, as one would expect since taking |ψi to be
that eigenvector yields zero entropy on the left-hand side. If R and S anti-commute, all the principal angles
are π/4 and so c = 21 . In this case, the uncertainty principle states that among the two binary variables R
and S there is at least one bit of entropy. This is a quantitative version of an observation that we made in
the first lecture, which was that any state that is determined for one observable must be “fully random” with
respect to the other: in that case we get H ( R) = 0 and H (S) = 1 (or vice-versa). Theorem 2.8 shows that
there is always a quantitative trade-off between these two extremes.
For our purposes we need an extension of this relation to the case of quantum memory. To motivate it,
interpret Theorem 2.8 as a statement about the difficulty of a prediction task:
1. The “adversary” prepares an arbitrary pure state |ψi and sends it to the “challenger”.
2. The challenger selects a uniformly random θ ∈ {0, 1} and measures |ψi using the observable R (case
θ = 0) or S (case θ = 1), obtaining an outcome r or s respectively. It sends θ to the prover.
28
where ρB is the reduced density matrix of ρAB on H B and for a density matrix σ, H (σ) is its von Neumann
entropy
H (σ) = −Tr(σ ln σ) = − ∑ λi log λi ,
i
where here x ranges over the standard basis of HA . The first system is “classical” in the sense that a
measurement of it in the standard basis does not change ρ. Now, for an arbitrary state ρ ∈ HA ⊗ HB
suppose that we can decompose the B part into a “classical” part C and a “quantum” part Q:
ρB = ∑ pc |cihc| ⊗ ρc ∈ HC ⊗ HQ ,
c
where { pc } is an arbitrary distribution. Then ρ AB = ∑c pc |cihc| ⊗ ρ0c , with ρ0c ∈ D(HA ⊗ HQ ) such that
TrA (ρ0c ) = ρc . Then,
Here, the first line is by definition, the second is the chain rule, the third and fourth are clear, and the last is
again by definition.
Theorem 2.9. Let R and S be observables on HA and c = max |hψ|φi|2 where |ψi (resp. |φi) ranges over
all eigenvectors of R (resp. S). Let ρAB be an arbitrary density matrix on HA ⊗ HB . Let R(ρ), S(ρ) ∈
D(H A ⊗ H B ) denote the post-measurement states after a measurement of A using the observables R and S
respectively.8 Then
1
H ( A| B) R(ρ) + H ( A| B)S(ρ) ≥ log2 + H ( A| B) . (2.13)
c
If B is empty and |ψiA is a pure state then H ( A| B) = 0 and we recover the previous relation. If B
is empty and ρA is a mixed state than H ( A| B) > 0 and we obtain a strengthening of Theorem 2.8. If
ρ AB = |φ+ ihφ+ |AB is an EPR pair then we can compute H ( A| B)φ+ = −1, so the inequality does not
imply any non-trivial bound on the left-hand side, as we expect it to based on the discussion above.
8 Equivalently, this is like decohering A in the eigenbasis of R or S respectively.
29
2.5.2 A test for large quantum memory
The information-theoretic tools introduced in the previous section allow us to introduce a neat “scaling up”
of the single-qubit test from Section 2.4. Towards this we consider the following variant of the protocol
from Section 2.4.2, which was introduced in [CR20]. Important changes are highlighted in blue.
1. V selects a bit θ ∈ {0, 1} and a string v ∈ {0, 1}n uniformly at random. For i = 1, . . . , n she
successively prepares the single-qubit states |viθ i = H θ |vi i and sends them to P.
2. V waits for a few seconds.
3. V sends θ to P.
4. P returns a string v0 ∈ {0, 1}n .
5. V declares that P has succeeded if and only if v0 = v.
Note that compared to the naı̈ve repetition of the single-qubit protocol, here we elected to use the same
basis for all qubits. This brings a very minor saving in communication, and in parameters, that comes for
free from the tools that we use to analyze the protocol.
Lemma 2.10. Suppose that P succeeds with probability 1 in this protocol. Then P has quantum memory of
dimension 2n .
Proof. As in the proof of Lemma 2.5 it is convenient to consider a purified version of the protocol in which
the verifier prepares n EPR pairs and measures her n halves in the basis θ at step 3. Moreover, we can give
more power to the adversary by considering that the joint state between V and P at the end of step 2 is an
arbitrary ρ ∈ (C2 )⊗n ⊗ H where the n copies of C2 correspond to the verifier’s qubits, and the remaining
space H is in the hands of the prover. Let R (resp. S) be the observable associated with a measurement of
the verifier’s n qubits in the computational (resp. Hadamard) basis.
First we show that the fact that the prover succeeds with probability 1 in the protocol implies that nec-
essarily the left-hand side in (2.13) equals 0. This is due to the data processing inequality, which states that
the conditional entropy can only increase as a result of any quantum information processing performed on
the system that is being conditioned on. (This is intuitive: in an information-theoretic sense post-processing
can only increase uncertainty, by discarding information, and not reduce it.) Starting from e.g.
where v denotes the verifier’s outcome, Pr(v) denotes the probability that the verifier obtains the outcome v
(conditioned on having chosen to perform a measurement in the standard basis) and ρ0v ∈ D(H) the prover’s
system conditioned on the verifier having obtained v, the prover’s measurement that returns v0 yields
since v = v0 with probability 1. On the state ρ00 , H ( A| B)ρ00 = 0 since both systems are classical and
perfectly correlated. Since ρ00 is obtained by a measurement on register B in ρ0 , it follows that H ( A| B)ρ0 ≤
0.9 Of course a similar argument applies to S, showing that the left-hand side in (2.13) is non-positive (and
in fact, equal to 0).
9 This inequality suffices for our purposes, but using that A is classical it is possible to conclude that H ( A| B)ρ0 = 0.
30
Using that the maximum overlap c between an eigenvector of R and an eigenvector of S is c = 1/2n
and applying Theorem 2.9 we deduce that necessarily
1
H ( A| B)ρ ≤ − log2 = −n
c
We conclude by (2.12): the dimension of Bob’s quantum memory must be at least 2n .
An advantage of using information theory is that it is generally a very robust technique, i.e. with all the
machinery that we put in place it is not hard to extend the proof of Lemma 2.10 to cover the case where the
prover’s success probability is not necessarily 1 and may even be quite small. It is also possible to analyze
a “fault-tolerant” variant of the protocol in which the verifier accepts the outcome v0 reported by P as long
as it matches v in a fraction at least (1 − α) of positions, where α ∈ (0, 1/2] is an arbitrary constant. The
following is shown in [CR20].
Theorem 2.11 (Theorem 2.1 in [CR20]). If P succeeds with probability p in the protocol, then its Hilbert
space must have dimension d such that
log2 (d) ≥ (1 − H (α))2p − 1 n − 2H ( p) ,
This result is quite strong, as even for small constant values of α and values of p that are sufficiently
close to 1 we get a bound on the number of qubits of memory that Bob needs to keep that scales linearly with
n. Aside from the “dimension test” presented here these kinds of bounds have found numerous applications
in cryptography such as to proving security in the bounded storage model, where it is assumed that the
adversary has a limited amount of storage available (for the reader familiar with cryptography but who
hasn’t seen this before, we probably already said enough to start suggesting a protocol for some variant of
oblivious transfer...).
While techniques based on information theory have quantitative advantages, they will generally not
suffice for our purposes. In particular, note the difference between Lemma 2.5 and Lemma 2.10: while the
latter guarantees “one qubit” the former certifies “dimension 2n ”: the former is quantitatively stronger, but
qualitatively weaker as it does not give us access to information about the prover’s observables. From now
on we will mostly abandon the use of information theory, as it is too coarse grained for our purposes.
31
32
Lecture 3
In this lecture we introduce a new assumption in addition to our overarching assumption that all parties
in a protocol can be modeled using quantum mechanics; as argued in the previous lecture additional assump-
tions are necessary to develop a test for a qubit with classical verifier. In physical terms our new assumption
consists in requiring that the device that is being tested is made of two parts that are “physically isolated,” in
the sense that no communication can take place between the two parts for the duration of the protocol. For
the case where the protocol consists of a single round of interaction (a question from the verifier and an an-
swer from the prover) one can imagine enforcing this assumption by e.g. placing the provers and verifier on
a line P1 − V − P2 and ensuring that the round-trip interaction between the verifier and either prover takes
place sufficiently fast that the verifier is confident, based on relativistic considerations (information does not
travel faster than light), that no information can be exchanged between the provers between the times when
they receive their question and have to send their answer. Mathematically, the assumption is reflected by
modeling the device’s Hilbert space H as HA ⊗ HB and writing that each sub-device’s observables act on
its Hilbert space only. Following tradition we will use the symbols A and B to denote “registers” (a word
loosely used to refer to the physical substrate modeled by the mathematical Hilbert space) associated with
each device and, oftentimes personify the devices as “provers” or “players” with the lovely names of “Alice’
and “Bob” respectively.
As we will see in this lecture as well as in the last third of the course this assumption of “localization”
allows the verifier to gain much leverage over the device. Some intuition for this may be gained from
thinking about a situation where a detective (the verifier) interrogates two suspects (the provers). Clearly the
detective has more leverage over the suspects if she interrogates them in isolation and cross-examines their
answers. Be warned however that this intuition only goes so far, because it only explains why interactive
proofs with two provers may be more powerful than single-prover interactive proofs; it does not give insight
into why specifically quantum aspects of the provers may manifest themselves in this framework. The fact
that quantum mechanics allows a broader set of behavior for the provers than classical mechanics does
is evidenced in the EPR paradox [EPR35], whose authors puzzle over the “non-local” nature of quantum
mechanics. A precise framework for describing this non-locality was set in place by Bell [Bel64] who
identified simple “inequalities” that separate classical from quantum behavior in bipartite scenario. Here we
take the modern tack on Bell’s inequalities and introduce them directly through the framework of nonlocal
games.
33
3.1 Nonlocal games
A non-local game is a cooperative game of imperfect information between a referee and two players. The
referee is a trusted party that executes the game by sending a question to each player, collecting answers
from them, and deciding whether the players’ answers satisfy a winning criterion. The rules of the game
(the distribution on questions used by the referee, the possible answers, the winning criterion) are public
and known to the players, who cooperate in order to maximize their chances of winning. The only source of
uncertainty is that each player is only revealed their question, but not the other’s; this point is what makes
the difference between a single-player and a multi-player game.
Remark 3.1. To make the connection with interactive proof systems of the kind that we described in the
previous lecture, somewhat informally a multi-prover interactive proof system for a language L is specified
by a collection of non-local games { Gx } x∈{0,1}∗ , one for each possibe input x. These games should have
the property that if x ∈ L then there is a strategy for the players that succeeds with high probability (this
is the completeness property) and if x ∈ / L then no strategy will make them win with high probability
(the soundness property).1 In the notes we freely interchange between the terminology of non-local games,
referees and players and that of interactive proofs, verifier and prover depending on context.
One may rightfully wonder what is the benefit of associating games, or interactive proof systems, to com-
putational problems. One element that we can point out is that a game itself is a computational problem—is
the maximum winning probability high (larger than some c) or low (smaller than some s)? By providing
a different, “dynamic” perspective on e.g. a 3SAT formula the framework of games has historically been
instrumental in proving results in hardness of approximation for constraint satisfaction problems. In a com-
pletely different direction, they are a natural setting for cryptography where they were introduced in the
context of zero-knowledge proofs.
For the sake of concreteness let us see an example. Consider the language L that is the collection of
all strings x such that x represents a satisfiable 3SAT formula ϕ.2 For example, ϕ could be “y1 ∨ y2 ∨
y3 AND y2 ∨ y3 ∨ y4 ,” which is obviously satisfiable. Since it is in general believed to be hard to determine
satisfiability of such a formula, let’s make the provers work and design an interactive proof systems for the
hypothesis “ϕ is satisfiable”.3
Here is a first candidate, which involves a single prover:
This proof system has completeness 1 (if there is a solution, a prover that sends it will be accepted with
probability 1) and soundness 0 (if there is no solution, no prover has any chance of being accepted). Unfor-
tunately, while the verifier is more efficient than solving the formula herself (by e.g. trying out all possible
1 For a formal connection between interactive proofs and games one would also have to insist that the games be “uniformly
generated” from x, and that the verifier in each game is described by a circuit of size poly(| x |).
2 In the following we use the notation ϕ and x interchangeably: we think of x as a string of bits and ϕ as a formula, but we
—the prover— still has to do the work. The goal rather is to provide a different framework in which to think about the complexity
of the computational problem “decide if ϕ is satisfiable”.
4 In the theory of interactive proof systems it is always assumed that the prover has access to the instance that is being decided,
34
solutions) she still has to read a lot of information in order to make her decision.5 In keeping with our goal
of making verifiers more efficient, let’s see a more succinct proof system with two provers. Let ϕ consist
cj cj cj
of equations E1 , . . . , Em such that Ej has the form y j11 ∨ y j22 ∨ y j33 with c j ∈ {0, 1} and for a variable y,
y0 = y and y1 = (1 − y).
1. The verifier selects j ∈ {1, . . . , m} uniformly at random and k ∈ {1, 2, 3} uniformly at random. She
sends j to the first prover and jk to the second, where jk is the index of the k-th variable on which
clause Ej acts in some canonical ordering. (Importantly, this ordering hides k, i.e. the prover only
knows that its variable appears in some clause, but not which clause or which position the variable
appears in it.)
2. The first prover returns a triple ( a1 , a2 , a3 ) ∈ {±1}. The second prover returns a value b ∈ {±1}.
3. The verifier accepts if and only if (consistency check:) ak = b and (equation check:) ( a1 , a2 , a3 )
satisfy clause Ej .
We make the following claim regarding completeness and soundness of this proof system:
1
Claim 3.2. The two-prover proof system described above has completeness 1 and soundness at most 1 − 3m ,
where m is the number of clauses in the input formula.
Note that while our proof system brought us gains in terms of communication, the soundness has de-
1
graded quite substantially, from 0 to 1 − 3m . It is possible to obtain improved variants of this proof system
1
that have roughly similar communication complexity but much better soundness, say 100 or even less. How-
ever, this requires much more work and is essentially the content of the PCP theorem, to which we will
return in the last part of the course.
Proof. The completeness is easy to verify. For soundness, consider an arbitrary strategy for the two provers
that succeeds with some probability p. In order to analyze this strategy we first need to accomplish the
usual modeling step: how do we represent a two-prover strategy? The most “naı̈ve” way to do so is to use
a representation of each prover as a function from questions to answers and declare that the provers’ joint
strategy is the combination (direct product) of these functions: the first prover, Alice, employs a function
f A : {1, . . . , m} → {0, 1}3 and the second prover, Bob, a function f B : {1, . . . , n} → {0, 1}; their joint
strategy is simply the function f = ( f A , f B ) that goes from pairs of questions ( x, y) in the protocol to pairs
of answers ( a, b). If one gives a little more thought to the question then it is not at all obvious that this is
the right answer. Nevertheless, let’s postpone any further thinking for now and finish the proof of the claim
using this model for the provers.
Fix a strategy ( f A , f B ) of this form for the provers. We distinguish two cases. Either the strategies
“match”, meaning that for any clause Ej it holds that
f A ( j) = ( f B ( j1 ), f B ( j2 ), f B ( j3 )) , (3.1)
where y j1 , y j2 , y j3 are the three variables involved in Ej . In this case we interpret the list of values
f B (1), . . . , f B (n) as an assignment to the n variables of ϕ. Since by assumption ϕ is not satisfiable there
must exist a j such that ( f B ( j1 ), f B ( j2 ), f B ( j3 )) do not satisfy clause Ej . By (3.1), f A ( j) does not satisfy Ej
5 Itis possible to argue that for a proof system of this form it is necessary for the prover to send a total number of bits that scales
linearly with the length of an NP (i.e. non-interactive) proof for the same statement, see e.g. [GVW01].
35
either. Hence whenever the verifier sends a question of the form ( j, k ) for k ∈ { j1 , j2 , j3 } the provers fail in
the equation check.
In the second case, the strategies do not match, i.e. there is a pair ( j, k ) ∈ {1, . . . , m} × {1, 2, 3} such
that the k-th entry of ( f A ( j)) does not match f B ( jk ). In this case the provers fail in the consistency check
when the question ( j, k ) is sent.
In all cases there is at least one question on which the provers must fail one of the verifier’s checks. Since
there are 3m possible questions in total and the verifier’s distribution on them is uniform this completes the
proof of the claim.
∀( x, y) ∈ X × Y , ∀( a, b) ∈ A × B , p( a, b| x, y) = pA ( a| x ) pB (b|y) . (3.2)
Since we allowed randomness it may also be natural to allow the randomness to be shared, i.e. allow the
more general class of distributions that can be represented as
Z
∀( x, y) ∈ X × Y , ∀( a, b) ∈ A × B , p( a, b| x, y) = pA ( a| x, λ) pB (b|y, λ)dλ , (3.3)
λ
where λ ranges over any measurable set and for each λ, { pA (·| x, λ)} x∈X is a family of conditional distribu-
tions on A, and similarly for the other prover. It is not hard to see that the proof of Claim 3.2 generalizes to
this case: briefly, this is because for a strategy of the form (3.3) to succeed with probability p in the protocol
it is necessary that the product strategy obtained by fixing λ succeeds with probability p for at least some
choice of λ.
The second extreme is to allow the most general family of bipartite conditional distributions that does
not “imply communication”. A natural formalization of the latter requirement, usually referred to as the
“non-signaling assumption” on p, is that for every a, x and y, y0 ,
36
In words, the answer a given by the first prover should have a marginal distribution that is independent of
the question y given to the second prover. Of course, a symmetric condition should hold with the provers’
roles exchanged.
At first it may seem that these two extreme classes “ought to” be the same. Are there distributions that
satisfy (3.4) but are not of the form (3.3)? The answer is yes. Here is a simple example: let X = Y =
A = B = {0, 1}. For ( x, y) 6= (1, 1) let p(·, ·| x, y) be uniform over {(0, 0), (1, 1)}. For ( x, y) = (1, 1)
let p(·, ·| x, y) be uniform over {(0, 1), (1, 0)}. It is easy to see that this distribution cannot be expressed in
factorized form, or even as a convex combination of factorized forms as in (3.3). (Showing this is a good
exercise which we leave to the reader.6 ) However, the distribution clearly satisfies (3.4) since all marginals
are uniform. We will see another example in Section 3.3.1.
Having observed that there are at least two possible models for the “non-communicating provers,” which
one is it most appropriate? Conventionally we call the first model “classical” because it can be realized
physically using local computation only, together with possibly a source of shared randomness. The second
model is called “non-signaling” and is considered non-physical even though it does not strictly violate
the no-communication assumption, because we do not have a credible physical theory in which arbitrary
distributions in that model can be generated at locations that are space-time isolated (in other words, there
is no physical theory that allows us to describe an experiment which would be able to generate any kind of
correlation that is in principle allowed by special relativity; there are other constraints that relativity itself
does not provide a means to model). Interestingly, the kind of correlations that can be generated by quantum
provers lies strictly in-between the two extremes. Let’s explore those correlations next.
these four values together cannot all lie exclusively among the allowed pairs for all four possible pairs of questions.
7 A non-local game, just as an interactive proof system, can in principle involve multiple rounds of interaction. Here we always
always restrict ourselves to the single-round case, that is simpler to analyze and captures everything that we need.
8 Assume for simplicity that the probability space is countable.
37
y
A ax = ∑λ pA ( a| x, λ)|λihλ|A , and similarly for Bb . One immediately verifies that these define valid POVM
y
and that they lead to the desired correlation (3.3). Moreover, the POVM condition ∑b Bb = Id for all y
implies that the correlations (3.5) always satisfy the no-signaling condition (3.4). However, the model is
strictly more general than the classical model (3.3), as we show next by identifying a non-local game in
which the use of quantum correlations leads to a strictly higher winning probability than classical correla-
tions could. (It is also possible to show that it is not as general as the non-signalling model, as the example
of a non-signaling correlation given above cannot be realized in quantum mechanics.)
38
3.3.1 An example: the Magic Square game
The Magic Square game is the following BLS game with 6 constraints on 9 variables. The constraints are
best visualized by picturing the variables arranged in the entries of a 3 × 3 square, as follows:
y1 y2 y3 +1
y4 y5 y6 +1
y7 y8 y9 +1
+1 +1 −1
As indicated on the picture the 6 constraints are that the product of all variables in any given row should
equal +1 and that the product of all variables in any column should equal +1 except for the last column,
where it should equal −1.
This system of equations does not have a solution (make sure you can show this!), and so the associated
BLS game, as described in Definition 3.4, does not have a perfect classical strategy: it is not hard to see that
the maximum success probability that classical players can achieve is 17 18 , matching the bound of Claim 3.2.
A remarkable fact is that there is a perfect quantum strategy for this game (“perfect” means that the
strategy succeeds with probability 1 in the game). This is remarkable because, as we just saw, the underlying
system of equations does not have a solution! Yet quantum players are able to always give answers that are
accepted by the referee. For this to be possible these answers necessarily have to be generated “on the fly”,
freshly every time a question is asked: if this were not the case then the same proof as that of Claim 3.2
would apply. Quantum provers are able to win with certainty, yet there is no way to extract a satisfying
assignment from them. What feature of the system of equations makes this possible? Can quantum provers
win any BLS game with probability 1, irrespective of any truth value of the underlying system of equations?
To gain insight into this question let us describe an explicit quantum strategy for the players that succeeds
with probability 1. The key observation is that even though as we saw the system of equations associated
with the magic square does not have a solution with values in {±1}, it has an operator solution
I ⊗ σZ σZ ⊗ I σZ ⊗ σZ
σX ⊗ I I ⊗ σX σX ⊗ σX (3.6)
σX ⊗ σZ σZ ⊗ σX σY ⊗ σY
where σY = iσX σZ . Observe that in each row or column the three observables always commute; moreover,
the product of the three observables in each row or column is always + I except for the last column, where
it is − I. This is what we mean by “operator solution”.
It is not too hard to show that for any BLS, an operator solution immediately translates into a perfect
quantum strategy for it.
Lemma 3.7. Suppose given an operator solution Y1 , . . . , Yn to a BLS ( E, c) such that each Yj is a binary
observable on a finite-dimensional Hilbert space H. Then the following strategy succeeds with probability
1 in the BLS game:
39
• The players share the maximally entangled state
1
|ψiAB = √ ∑ |i iA ⊗ |i iB ∈ HA ⊗ HB , (3.7)
d i
where d is the dimension of H, each of HA and HB is a copy of H, and {|i i} an orthonormal basis
for it.10
• On question j, Alice sequentially measures the observables Yj1 , Yj2 , . . . , Yj` on her share of |ψi, where
j1 , . . . , j` are the indices of the nonzero entries of the j-th row of E. She obtains outcomes a1 , . . . , a`
that she returns as her answer.
• On question k ∈ {1 . . . , n} Bob measures the observable YkT on his share of |ψi. He obtains an
outcome b ∈ {±1} that he returns as his answer.
Proof. First we note that the strategy described in the lemma is valid: since by definition of an operator
solution the observables Yj1 , Yj2 , . . . , Yj` always commute it is possible for Alice to measure them simulta-
neously.
The following relation holds the key to the proof: for any operators A on HA and B on HB it holds that
1
hψ| A ⊗ B|ψi = Tr( AB T ) , (3.8)
d
where |ψi is as in (3.7). This relation follows easily from the relation (Id ⊗ B)|ψi = ( B T ⊗ Id)|ψi that
we saw in the previous lecture and the fact that the reduced density matrix of |ψi on either subsystem is the
totally mixed stated d−1 Id. Using this relation it is a matter of direct calculation to verify that the prover’s
answers always satisfy the verifier’s checks in the game. In more detail,
• For the consistency check, we note that the probability that the two players return consistent answers
on question ( j, k ) is
1 1 1 11
+ hψ|Yjk ⊗ YjTk |ψi = + Tr Yj2k = 1 ,
2 2 2 2d
where the first equality follows from (3.8) and the second holds since Yjk is a binary observable so
Yj2k = Id.
• For the equation check, we note that the probability that Alice’s answers satisfy the check for the j-th
equation is
1 cj 1 cj
+ hψ|Yj1 · · · Yj` ⊗ Id |ψi = + hψ|c j Id ⊗ Id |ψi = 1 ,
2 2 2 2
where the first equality holds since Yj1 · · · Yj` = c j Id by definition of an operator solution.
Remark 3.8. The reader will have noticed that in Lemma 3.7 we carefully added the assumption that the
operator solution is finite-dimensional, and indeed this seems necessary for the state |ψi to be well-defined.
It is possible to show that infinite-dimensional operator solutions to a BLS correspond to commuting-
operator strategies for the associated game, and conversely; this correspondence is established in [CLS17].
Commuting-operator strategies are a strict superset of tensor-product strategies
10 The maximally entangled state is a natural generalization of the EPR pair which can be defined on any tensor product of
(finite-dimensional) isomorphic Hilbert spaces.
40
Combining Lemma 3.7 with the operator solution to the magic square given by (3.6) we obtain a perfect
strategy for the magic square game that uses two qubits per player, and two EPR pairs shared between them.
Since we saw that the magic square does not have a perfect strategy this strategy gives us another example
of a non-signaling correlation that is not classical.
Lemma 3.9. Suppose given a BLS ( E, c) and a strategy (|ψi, A, B) for the associated game that succeeds
with probability 1. Then the BLS has a finite-dimensional operator solution.
Proof. We give the proof for the special case of the Magic Square game, as the general case is similar. We
start with the modeling step: a strategy (|ψi, A, B) for the magic square game is given by a bipartite state
|ψi ∈ HA ⊗ HB for finite-dimensional HA and HB as well as the following measurements. For the first
player (Alice), for each row or column x there is a 9-outcome projective measurement { A ax : a ∈ {±1}3 }
on HA . For the second player (Bob), for each variable (square) y there is an observable By on HB . Note
that here we assumed that the measurements made by each player are projective, which is without loss of
generality by applying Naimark’s theorem and enlarging the spaces HA and HB if necessary.
To each of Alice’s questions we can associate three observables that correspond to the three bits of her
answer. For example, for question j = 1 (first row) we can define
We can similarly proceed to define A4 , . . . , A9 from the rows and A10 , . . . , A90 from the columns. Next we
show that success with probability 1 in the consistency checks implies that
Take for example the consistency check on question (1, 2) (first row to Alice, second entry to Bob). It is
easy to show that success in that check implies that
Proof sketch. Let K = ∑t λt |ut ihvt |. Then the equality hψ| A ⊗ B|ψi = 1 is equivalent to AKB T =
K. Identifying left and right eigenspaces we see that A and B must each preserve the eigenspaces of K
associated with any given eigenvalue. Thus AKB T = K decomposes in block form ⊕λ Aλ BλT = Idλ ,
where for each block we indicated with a subscript λ the restriction of each operator to the eigenspace of K
associated with eigenvalue λ. This shows the claim.
41
Using Claim 3.10 and the implications of the form (3.10) for the consistency checks, (3.9) follows,
where the operators and the transpose should be understood to be written with respect to the Schmidt bases
of |ψi. To conclude we claim that B1T , . . . , B9T (precisely, their restriction to the support of |ψi on HB ) are
an operator solution to the Magic Square. Commutation in each row or column follows from (3.9) and the
definition of the Ay (which by definition commute by rows) and A0y (by columns). The constraints follow
from the fact that e.g. for the first row, hψ| A1 A2 A3 ⊗ Id |ψi = +1, which using Claim 3.10 implies that
A1 A2 A3 = Id and hence B1T B2T B3T = Id. (Of course we could remove the transpose signs and still have a
valid solution.)
Claim 3.11. Suppose given an operator solution Y1 , . . . , Y9 to the magic square. Then Y2 and Y4 anti-
commute.
Y2 Y4 = Y1 Y3 · Y6 Y5
= Y1 · Y9 · Y5 ,
where the second line is by the last column constraint. Next we write the product Y4 Y2 by columns:
Y4 Y2 = Y1 Y7 · Y8 Y5
= Y1 · (−Y9 ) · Y5 ,
where the second line is by the last row constraint. Combining both equations it follows that Y2 Y4 = −Y4 Y2 ,
as claimed.
The following lemma is immediate from the proof of Lemma 3.9 and Claim 3.11. We state the lemma
using the language of “self-testing” from the previous lecture.
Lemma 3.12. Suppose that two non-communicating quantum devices A and B generate correlations
y
p( a, b| x, y) = hψ| A ax ⊗ Bb |ψi
that perfectly satisfy the referee’s tests in the Magic Square game. Let SB denote the support of the reduced
density ρB of |ψi ∈ HA ⊗ HB on HB . Then the observables B1 , . . . , B9 stabilize SB , and their restriction
to that space form an operator solution to the Magic Square. In particular, the device’s joint state |ψiAB
together with observables B2 and B4 of device B associated with inputs y = 2 and y = 4 respectively form
a qubit (|ψi, B2 , B4 ).
Proof. The first part of the lemma follows from the proof of Lemma 3.9. By Claim 3.11 the observables
associated to y = 2 and y = 4 anti-commute.
42
The preceding lemma shows that two of device B’s observables, B2 and B4 , must anti-commute. As we
saw in Lemma 1.211 this means that up to an isomorphism on the device’s space these observables must
take the form B2 ' σZ ⊗ Id and B4 ' σZ ⊗ Id, which is exactly the form that they take in the solution
given in (3.6). What about the other observables? In other words, are the constraints that underlie the Magic
Square game rigid?
Lemma 3.13. Under the same assumptions as Lemma 3.12 there is a unitary U on the space HB associated
with device B such that the observables U † Bk U for k ∈ {1, . . . , 9} take the form described in (3.6). in
particular, the dimension of (the span of the support of |ψi on) HB is a multiple of 4.
Proof. The main ingredient in this proof is the qubit lemma, Lemma 1.2, together with Claim 1.6 which
allows us to argue that observables that commute with σZ and σX on a copy of C2 must act as identity on
C2 .
First note that the proof of Lemma 3.12 immediately extends to show that any two observables not in
the same row or column anti-commute. Furthermore, by definition the condition that the 9 observables
B1 , . . . , B9 form an operator solution to the Magic Square implies that all observables in the same row or
column must commute. Using this condition and the characterization of B2 and B4 given in Lemma 3.12 it
follows from Claim 1.6 that B1 ' Id ⊗ B10 and B5 ' Id ⊗ B50 , for some observable B10 and B50 on H0 that
anti-commute. Using Lemma 1.2 again it follows that there is an isometry U 0 on H0 such that as operators
on H0 , B10 ' σZ ⊗ Id and B50 ' σX ⊗ Id, with the identity acting on some new ancilla space H00 such that
H0 ' C2 ⊗ H00 . Combining U and U 0 together, we have shown that there is an isomorphism U 0 U under
which
B1 ' Id ⊗σZ ⊗ Id B2 ' σZ ⊗ Id ⊗ Id
.
B4 ' σX ⊗ Id ⊗ Id B5 ' Id ⊗σX ⊗ Id
The remaining entries of the table are immediately filled in from the row and column constraints, which
uniquely determine them.
As a last step we show that we can also characterize the entangled state used by any strategy. Inter-
estingly, this characterization comes as a consequence of the characterization of the observables, which we
obtained without talking much about the state. This is based on the following general lemma, that we will
often make use of.
Lemma 3.14. Let |ψiABE ∈ (C2 )A⊗n ⊗ (C2 )B⊗n ⊗ HE be such that for every i ∈ {1, . . . , n} it holds that
σX,i A ⊗ σX,i B |ψiABE = σZ,i A ⊗ σZ,i B |ψiABE = |ψiABE ,
where the Pauli operators act on the i-th copy of C2 in register A and B respectively. Then |ψiABE =
⊗n
|φ+ iAB ⊗ | aux i, for some state | aux i on H.
Proof. Note that σX ⊗ σX and σZ ⊗ σZ commute, hence are simultaneously diagonalizable. The proof
immediately follows from the observation that the only simultaneous eigenvalue-1 eigenstate of σX ⊗ σX
and σZ ⊗ σZ is the EPR pair |φ+ i.
Exercise 3.1. Show that the conclusion of Lemma 3.14 holds under the following weaker assumption:
|ψiABE ∈ (C2 )A⊗n ⊗ HB⊗n ⊗ HE with HB arbitrary, and for every i ∈ {1, . . . , n},
σX,i A ⊗ Xi B |ψiABE = σZ,i A ⊗ Zi B |ψiABE = |ψiABE ,
11 Here we can apply the “state-independent” version of the qubit lemma because Lemma 3.12 states that the observables them-
selves, or rather their restriction to the support of |ψi, satisfy the operator constraints.
43
with Xi and Zi arbitrary binary observables on HB (in particular, we are not assuming any a priori qubit
structure on HB ). [Hint: Remember Claim 2.7]
3.4.1 Consequences
The characterization of perfect strategies given in Lemma 3.13 together with Lemma 3.14 have some nice
consequences. First of all, they imply that the Magic Square game tests not one, but two qubits: any perfect
strategy must have a 4-qubit entangled state, two qubits per player, and Bob’s observables specify two qubits,
e.g. B2 and B4 for the first and B1 and B5 for the second. We even have access to more: for example, we
know that when Bob is asked question 9 the observable he applies is σY ⊗ σY . Although we clearly have
some distance to go, these are first steps towards testing that Bob implements a certain computation; for
now, we are able to test that he applies specific observables.
Another consequence of the characterization has to do with the problem of randomness certification. At
this point we know that, in any perfect strategy, whenever Bob is asked question 2 he measures the first qubit
of an EPR pair in the standard basis. This has the following implications:
1. The answer reported by Bob on question 2 (and, in fact, on any question) is a uniformly random
bit. In particular, no deterministic strategy can succeed in the game! We knew this already, because
deterministic strategies are classical. As such, any game for which quantum strategies can succeed
with strictly higher probability than classical strategies can serve as a “test for randomness”.
2. More importantly, the randomness that is generated by Bob at each execution of the game is “fresh”
and “private”. What we mean by this is that Bob’s random bit is (1) independent of any information
at the verifier’s side, including Bob’s question, and (2) uncorrelated to the environment. Indeed, since
Bob’s bit is the result of a measurement of half an EPR pair, the only party that can obtain correlated
information is Alice, who holds the other half of the EPR pair. By the rigidity theorem this EPR pair
must be in control of Alice: she needs it for them to succeed in the game. Therefore the verifier has
the guarantee that the bit she obtains (1) cannot have been “planted” a priori in the devices, and (2)
cannot be learned, even partially, by any third party distinct from A and B, even if the party could a
priori have kept entanglement with the devices—this is because, using the notation of Lemma 3.14,
the third party would only at best have access to the entirety of system E, which is uncorrelated with
AB.
These observations are important for cryptography, where the use of high-quality randomness that is uncor-
related from any possible eavesdropper or adversary is an essential resource. Indeed, the observations we
just made form the basis for the so-called “device-independent” analysis of quantum cryptography protocols.
Remark 3.15. We presented the fact that the Magic Square game tests two qubits, instead of one, as a
“feature”. But what if one only cares about a single qubit, is there a simple test for this? There is such a
test, but it is not an BLS game: it is the CHSH game. The proof that this game tests a qubit was recognized
early on, see e.g. [SW87] or [MYS12] for a more modern treatment. Unfortunately the game does not
have “quantum completeness 1”, in the sense that the optimal quantum strategy for it achieves a success
probability that is greater than the optimal classical, but less than 1 (precisely, it is cos2 π/8 ≈ 0.85). This
makes it less convenient to use as a building block in larger protocols, and so here we will stick with the
Magic Square game that is the simplest value-1 game which self-tests at least one qubit that we know of.
An important drawback of our analysis so far is that it is limited to the case of perfect strategies, i.e.
strategies that succeed with probability 1 in the game. In practice one may only reasonably assume, after
multiple executions of the game, that a given strategy succeeds with some probability that is close to one,
44
1 − ε for some ε ≥ 0 that can be made small but not 0. In the next section we discuss how the results can be
extended to that case.
Theorem 3.16. Suppose that a strategy (|ψi, A, B) succeeds with probability 1 − ε in the Magic Square
game, for some ε ≥ 0. Then there are isometries VD : HD → C2 ⊗ C2 ⊗ HD0 for D ∈ { A, B} such that
2 √
VA ⊗ VB |ψiAB − |φ+ i ⊗ |φ+ i ⊗ | aux i = O ε ,
and similar relations hold for the remaining seven observables on Bob’s side.
Note that the theorem only characterizes the player’s observables “up to isometry”, as opposed to “up
to isomorphism” as we were able to in the perfect case (Lemma 3.13). As discussed in the previous lecture
(Section 2.3) this is unavoidable in general.
Later we will see a general method to derive statements such as Theorem 3.16 based on the use of
approximate group representation theory. For now, we let it serve as a good illustration of the kind of
statements we aim to prove in this course. It is worth reflecting on the strength of what we have achieved:
using only classical data and a single physical assumption (our model for spatial isolation based on the use of
tensor products) we have arrived at a very simple test that can be used to fully characterize the quantum state
of a 16-dimensional system (4 qubits) as well as elementary operations performed on it. This conclusion is
much stronger than the “standard” conclusion that motivates the study of Bell inequalities in the first place:
that they require entanglement.12 There is no equivalent to this in classical theory!
12 Note that the fact that the isometries V and V are “local”, each acting only on one half of the total Hilbert space, is important
A B
because it means that they couldn’t have artificially create the entanglement present in |φ+ i ⊗ |φ+ i: that entanglement must “exist”
even independently of the application of the isometry, which only serves to “package” it in the neat form of two EPR pairs. Of
course, the state | aux i may or may not contain entanglement itself.
45
46
Lecture 4
As we discussed in the first lecture, a simple interactive “test of quantumness” under computational assump-
tions consists in asking the device to factor a large integer n; under the assumption that factoring is hard for
classical computers this test adequately distinguishes classical from quantum devices.
The main limitation of this test that is generally pointed out is that in order for a device to successfully
demonstrate its “quantumness” it needs to have the capability to implement a large, fault-tolerant quantum
computation. In contrast, the test based on spatial isolation that we saw in the previous lecture can be
executed with a pair of two-qubit devices.1
A second limitation that is relevant for us is that the test does not seem to provide a means to certify
a qubit. Modeling the prover in a “factoring test” would give us a family of POVM {Πn{ p } }, indexed by
i
integers n and whose outcomes are lists of primes { pi }. In fact, for each n there should be a single POVM
element —the one with the correct outcome— such that Πn{ p } |ψi = |ψi with |ψi the initial state of the
i
device; in somewhat informal notation that POVM element is supposed to be obtained as U † |{ pi }ih{ pi }|U
with U a circuit implementation of Shor’s algorithm. But to identify a qubit we know that we need two
observables acting on the same space as well as some indication that these observables ought to be “incom-
patible” (anti-commutation). It is not at all clear how to identify such observables here.
A key insight from this lecture is that in order to obtain a computational test for a qubit we will need to
assume that a certain problem is hard not for classical computers but also for quantum computers. This is
because our model requires us to identify two observables X and Z in the device such that the device has
the ability to perform either X or Z but not both simultaneously. In Lecture 2 this incompatibility arose
from the necessity for X and Z to yield predictions that matched those of σX and σZ . In the third lecture, it
arose from some form of information-theoretic impossibility—in a loose sense, had X and Z (recall that in
the notation from the previous lecture these were identified as B4 and B2 ) been compatible, then the Magic
Square would have had a classical solution—which it doesn’t.
In this lecture the impossibility of measuring X and Z will be based on considerations of computational
difficulty. We will show that, if the quantum device was able to measure X and Z jointly then it would
break a computational problem that is assumed to be hard even for quantum computers — we will formulate
this later as a form of “computational uncertainty principle”. Since by definition the device can measure X
1 The test does require the ability to distribute entanglement across a large distance—if one uses relativity to certify the assump-
tion of spatial isolation—and to perform fairly high-fidelity measurements on it. This is not at all easy, but it can be done today;
implementations of Shor’s algorithm that outperform the best classical factoring algorithms are not expected within the next decade.
47
and Z separately, if they commuted then it could also measure them jointly. Therefore, the computational
assumption gives rise to an information-theoretic consequence on the observables X and Z: they must form
a qubit.
It then measures the last register in the computational basis, yielding some y = f ( x0 ) = f ( x1 ) where x0
and x1 = x0 + s are the two preimages of y under f . The re-normalized post-measurement state is
1
√ | x0 i + | x1 i | y i . (4.1)
2
Measuring the first register in the Hadamard basis yields a uniformly random d ∈ {0, 1}n such that d · s = 0.
Repeating the entire procedure O(n) times yields (n − 1) linearly independent such d’s, which suffices to
recover s with high probability.
48
the classical algorithm that would take advantage of specific code for f ; indeed, showing such a separation
would be a major breakthrough in quantum algorithms.
This difficulty shouldn’t prevent us from toying with the question: Can we identify natural candidates?
For example one could take f ( x ) = Ax for A ∈ F2n×n a matrix of rank exactly (n − 1). In that case the
kernel of A is spanned by a single vector s ∈ F2n , and f is exactly 2-to-1: f ( x0 ) = f ( x1 ) if and only
if A( x0 − x1 ) = 0, i.e. x0 − x1 is either 0 or s. Unfortunately this f is not a good candidate, because
there happens to be an efficient classical algorithm that directly solves Simon’s problem for it: Gaussian
elimination.2 The example shows that at a minimum we need a function f that is 2-to-1 but such that finding
any colliding pair of inputs ( x0 , x1 ) with f ( x0 ) = f ( x1 ) is computationally difficult. In the next section we
introduce some background from cryptography that will allow us to make this requirement precise.
49
family of classical (resp. quantum) circuits. Note that the assumption that the Turing machine is polynomial
time immediately implies that the circuits it returns act on polynomially many bits (resp. qubits) and have a
polynomial number of classical (resp. quantum) gates.
In a cryptographic context we will generally allow M to take a second input 1λ for λ ∈ N called the
security parameter. While the input size n is governed by the size of the problem, the security parameter
can be chosen at will; the larger it is the more “secure” the protocol is supposed to be (for example, the
smaller the probability that the verifier makes an incorrect decision or the higher the quality of the certified
qubits).
Definition 4.1 (Claw-free function family). A family F = { f pk : {0, 1}m(λ) → {0, 1}m(λ) } pk∈{0,1}k(λ) is
claw-free against classical (resp. quantum) adversaries if the following conditions hold:
• f pk can be efficiently evaluated: there is a PPT procedure that given pk and x as inputs returns f pk ( x ).
• For every λ ∈ N and pk ∈ {0, 1}k(λ) , f pk is 2-to-1.
• For every PPT (resp. QPT) procedure A the following holds: (the procedure A is often personi-
fied as the “adversary” trying to demonstrate that the function family is not claw-free) there exists a
negligible4 function µ : N → N such that for every λ,
Pr ( x0 , x1 ) ← A(1λ , pk) : x0 6= x1 , f pk ( x0 ) = f pk ( x1 ) ≤ µ(λ) .
pk← R {0,1}k(λ)
In words, the third condition states that there is no polynomial-time algorithm that given a uniformly
chosen index pk for a function from the family is able to return two distinct inputs for the function that
constitute a claw.5
Remark 4.2. In the definition we require the function family to be parametrized by arbitrary strings pk. In
general this requirement can be relaxed; in fact there could even be a single function for every λ. In cryp-
tographic constructions the function family generally comes equipped with a PPT key generation procedure
G EN that takes 1λ as input and returns pk.
4Afunction µ : N → R is called negligible if for every polynomial p, p(λ)µ(λ) →λ→∞ 0.
5Atriple ( x0 , x1 , y) such that x0 6= x1 and f ( x0 ) = f ( x1 ) = y is called a claw. To see why, picture the arrows x0 → y and
x1 → y drawn with x0 , x1 on top of each other on the left and y on the right.
50
An example of a claw-free family of functions against PPT adversaries can be constructed as follows.
(This construction appears in [GMR85], where it is used to construct a digital signature scheme.) Let
N = pq be a product of two primes p ≡ 3 mod 8 and q ≡ 7 mod 8. This choice ensures that −1 and 2
are not squares mod N; moreover, if Q N denotes the set of quadratic residues (i.e. squares) modulo N then
f 0 ( x ) = x2 mod N and f 1 ( x ) = 4x2 mod N are both permutations of Q N . (This fact requires proof but
it is a simple exercise in arithmetic.) However, suppose given a claw ( x0 , x1 ) such that x0 , x1 ∈ Q N and
f 0 ( x0 ) = f 1 ( x1 ). Then x02 = 4x12 but x0 6= ±2x1 mod N because ±2x1 ∈/ Q N . Thus computing the GCD
of N with x0 ± 2x1 recovers a nontrivial factor.
While this family of functions is claw-free with respect to PPT adversaries, it is clearly not claw-free
against QPT adversaries, that can use Shor’s algorithm to factor efficiently. We will construct such a function
family in the next lecture; for the time being we assume its existence.
Following the initial steps of Simon’s algorithm as described in Section 4.1.1 when instantiated with any
2-to-1 function enables a quantum device to generate strings d ∈ {0, 1}m such that d · ( x0 + x1 ) = 0,
where ( x0 , x1 ) are preimages of some y ∈ F2m by f . Intuitively one might expect that this represents a
computational advantage, because d provides an equation in x0 + x1 , which is some information about both
preimages together. For example in the case where x0 + x1 = s, where s is some fixed secret independent of
y, we saw that provided the equation d can be assumed to be uniformly distributed among all valid equations
in s then running the procedure O(m) times gives sufficiently many equations to recover s.
Unfortunately, as discussed in Section 4.1.2 for the only function that we could think of that has this
property it is in fact easy to recover s, even for a classical computer. This suggests that in general the
assumption that f satisfies the structure required for Simon’s algorithm might be too strong to obtain an
explicit candidate. Moreover, recall that at the start of the lecture we pointed out that our goal is not directly
to find a task for which there is a quantum computational advantage, but instead we are trying to identify
two tasks that the quantum device can perform separately but not simultaneously—if someone, such as
a classical device, was able to execute both tasks simultaneously then it would break the computational
assumption. What could those two tasks be here?
Starting from the state (4.1) it is natural to measure in the Hadamard basis, obtaining as before an
equation d such that d · ( x0 + x1 ) = 0, but also in the computational basis, obtaining either x0 or x1 . Given
that “honest” measurements in the computational and Hadamard basis are incompatible, these are natural
candidates for our “qubit.” However, we also saw that if x0 + x1 = s for some fixed secret s then the
Hadamard measurements alone allow us to recover s. So a quantum procedure could recover s “on the side”
and then, knowing f explicitly, succeed in any reasonable “test” by using classical operations alone—this
would make it very hard for us to identify the “qubit” that the device should have used to recover s (this is
similar to the example of Shor’s algorithm given at the start of the lecture). But what if the structure of f is
a little more complicated, so that e.g. x0 + x1 = g( x0 , s) for some function g? In that case a single equation
in g( x0 , s) might not be so useful; even many such equations for varying x0 could be useless since without
knowledge of x0 itself one cannot determine what the equation is about. However, if one was able to obtain
x0 simultaneously with the equation then one would obtain a sequence of (possibly non-linear, depending
on g) constraints on s. These considerations motivate the following computational assumption:
Assumption 1 (Adaptive hardcore bit). There is a claw-free family of functions F = { f pk } such that for
51
any QPT adversary A there is a negligible function µ such that
1
−1
− Pr ( x, d) ← A(1λ , pk), { x0 , x1 } ← f pk ( f pk ( x )) : (d 6= 0m ) ∧ (d · ( x0 + x1 ) = 0) ≤ µ(λ) .
2 pk←R {0,1}k(λ)
(4.2)
In words, the assumption is that no quantum polynomial-time algorithm can simultaneously return an
element x in the domain of f and an equation d such that, letting { x0 , x1 } be the two preimages of f pk ( x )
under f pk it holds that d 6= 0m and d · ( x0 + x1 ) = 0. Note that although we required { f pk } to be claw-free,
this requirement is stronger, since any algorithm that can find a claw ( x0 , x1 ) can be used to break (4.2).
Remark 4.3. Assumption 1 is called adaptive hardcore bit for the following reason. Given a function f a
hardcore bit for f is a 1-bit function h such that given f ( x ) (but not x) it is hard to predict h( x ). Here,
the hardcore bit that underlies the assumption is the function h( x ) = d · ( x0 + x1 ) for any d 6= 0m : the
Goldreich-Levin theorem implies that if f is indeed claw-free then it is hard to predict h( x ) for a random d.
The “adaptive” qualifier refers to the fact that in (4.2) we allow the adversary A itself to select the equation
d without requiring that this equation is uniformly distributed (we will see why this is needed in the next
section); in particular A may return always the same d, and this invalidates the classic Golreich-Levin
argument. This makes the property harder to satisfy, because more power is given to the adversary. (Note
in particular that we had to explicitly require d 6= 0m , as otherwise there is an easy adversary that always
succeeds.)
(F.2) The function family F satisfies the adaptive hardcore bit assumption, Assumption 1.
(F.3) F is equipped with a trapdoor: in addition to pk, G EN (1λ ) returns a trapdoor td such that given pk,
td and any y in the range of f pk it is possible to efficiently recover the two preimages x0 and x1 of y.
(F.4) For any pk and any y in the range of f pk the two preimages of y are labelled ‘x0 ’ and ‘x1 ’ using some
canonical efficient procedure. That is, given a key pk and an x in the domain of f pk it is possible to
efficiently determine if x is the ’x0 ’ or the ’x1 ’ preimage of y = f ( x ). Let b : {0, 1}m → {0, 1} be
this labeling procedure; b may depend on pk.
Let us fix a function family F satisfying the assumptions (F.1) to (F.4). We give a protocol based on F . The
protocol describes the interaction between a classical polynomial-time verifier and a (possibly quantum)
polynomial-time prover. Here, the input to both parties is the security parameter λ; when we refer to PPT
or QPT we mean with respect to λ. The protocol is described in Figure 4.1. For future reference we refer to
it as “protocol Q.”
52
Let F be a function family and λ ∈ N a security parameter.
3. The verifier selects a uniformly random challenge c ← R {0, 1} and sends c to the prover.
4. (a) (pre-image test:) In case c = 0 the prover is expected to return an x ∈ {0, 1}m . The verifier
accepts if and only if f pk ( x ) = y.
(b) (equation test:) In case c = 1 the prover is expected to return a d ∈ {0, 1}m . The verifier uses td
to determine the two preimages ( x0 , x1 ) of y by f pk . She accepts if and only if d · ( x0 + x1 ) = 0.
Figure 4.1: Protocol Q, the computational test for a qubit. The protocol is parametrized by a function
family F satisfying assumptions (F.1) to (F.4).
Theorem 4.4. Let F satisfy the assumptions (F.1) to (F.4). Then the following hold for protocol Q.
• (Completeness:) There is a QPT prover P which succeeds with probability 1 in the protocol.
• (Soundness:) Suppose that a QPT prover P succeeds with probability 1 in the protocol. Then P has a
(near-perfect) qubit.
As we are now accustomed to, we note the slightly informal nature of the theorem and make a few
comments:
• First of all, we make explicit the computational assumption: combining Assumption 1 with the re-
quirement that the prover P is QPT effectively means that we are assuming that P does not “have the
ability” to violate (4.2). Slightly more formally, in the proof we will show that if P does not “have
a qubit” then it can be used to construct an adversary A that violates (4.2). Note also that in the
soundness case it should be assumed that P is in fact a family of { Pλ }, one for each possible choice
of λ, that can be uniformly generated from λ (i.e. there is a classical Turing machine that takes 1λ as
input and returns a description of a family of circuits that can be used to implement Pλ ).
• Second, we ought to be a little more precise as to how P’s qubit is specified. The two observables X
and Z that define it will be derived from the two measurements that P makes based on the challenges
c = 0 or c = 1. Since these measurements in general have outcomes in {0, 1}n some post-processing
will be required. Interestingly, the post-processing for the X observable will not be efficient, in the
sense that it will require knowledge of td. So, our proof will show that there exists two anti-commuting
observables on the Hilbert space of P that can be defined from P’s operations and some classical
post-processing. Since the post-processing is classical we can nevertheless claim in good faith that
the “qubit” is located on the prover’s space, as we are not injecting any external “quantumness” in it.
• Third, we make the usual comment regarding the assumption that the prover succeeds with probability
1: this assumption is, of course, unrealistic. As in other protocols that we have seen so far the
assumption can be lifted at the cost of some amount of work. We will discuss this in more detail when
we build on the present protocol to construct a more complex protocol for verifying an entire quantum
computation in the next few lectures.
53
• Finally, an explanation is in order regarding the “(near-perfect)” qualifier. This is an unavoidable
consequence of the fact that the protocol relies on a computational assumption. Indeed, consider
the following possible behavior for the prover. The prover first devotes a small amount of time to
trying their luck at breaking the underlying computational assumption (in our case, the prover could
randomly generate candidate trapdoors td0 and check if they allow it to invert the function f pk ). If the
prover succeeds then it can pass in the protocol without manipulating any quantum state, using the
fake td0 to find a claw that allows it to answer both types of challenges. If it does not succeed then
it behaves honestly in the protocol. Such a prover succeeds with probability 1, but the measurement
operators associated with its answers have a part that is “classical” and from which we have no hope
of extracting a qubit.
Proof of Theorem 4.4. The completeness part of the theorem is clear. In the first phase the prover proceeds
exactly as in Simon’s algorithm to obtain the state (4.1). In the second phase, it measures the preimage
register in the standard basis in case c = 0 and in the Hadamard basis in case c = 1, returning the n-bit
outcome obtained as its answer. This prover is always accepted with probability 1 in the protocol.
To show the soundness part of the theorem we start with the usual (and, here, crucial) modeling step.
Step 1: Modeling Since we will not need to model the prover’s actions in the first phase of the protocol
in detail we directly give a name to the state of the prover at the end of step 2; let it be |ψi ∈ HP . This
state depends on pk as well as on y; for clarity we suppress this dependence from the notation. Moreover,
in general |ψi may be a mixed state, and we represent it as a pure state for convenience only; in general one
could assume that we included a register E to denote an “environment” that holds a purification |ψiPE of a
general ρ ∈ D(HP ).
At the second stage of the protocol the prover is given a challenge c ∈ {0, 1} and tasked with responding
with an n-bit string, x or d depending on the challenge. In general, x is obtained by performing a POVM
{Π x } on the prover’s entire space, and similarly d is the outcome of a POVM { Md }.6 We make the
following observations that allow us to simplify the presentation of these POVM:
• Without loss of generality both Π and M are projective measurements. This is because we can enlarge
P and add sufficiently many ancilla qubits initialized to |0i so as to apply Naimark’s theorem.
• Without loss of generality, assume that the prover has access to an m-qubit register X initialized to
| 0m i.
• Without loss of generality, assume that Π is obtained by first applying a unitary transformation U0 on
HX ⊗ HP followed by a standard basis measurement of HX ' (C2 )⊗m . Any projective measurement
can be put in this form by letting U0 be any unitary extension of the map
√
|0i|ψi ∈ HX ⊗ HP 7→ ∑ | x i Π x |ψi ,
x
54
We now introduce observables Z and X on HX associated with the prover. For Z, we define it to be
Z = ∑ (−1)b(x) | x ih x | , (4.3)
x ∈{0,1}m
where b : {0, 1}n → {0, 1} is the function from assumption (F.4). Z is efficiently computable since b is.
For X, we define it to be
where x0 and x1 are the two preimages under f pk of the string y returned by P at step 2. (There is an
observable X for each possible string y, but we suppress this dependence from the notation for clarity.) Note
that X is not efficient, because we are not assuming that determining x0 + x1 from y is efficient in general.
However, X can be computed in a straightforward manner by applying the prover’s efficient measurement
{ Md } followed by (non-efficient) classical post-processing. (We insist on this point to clarify that our
definition is not injecting “quantumness” artificially.) Informally, X can be thought of as the observable that
determines if the equation d returned by the prover on challenge c = 1 is correct or not. In particular, later
we will use that for a prover that always succeeds to a challenge c = 1 we have X |ψi = |ψi, i.e. |ψi is a
+1 eigenstate of X.
Step 2: Establishing a qubit The goal for the remainder of the proof is to show that (|ψi, Z, X ) form a
qubit, i.e. that the two observables X and Z anticommute on |ψi. Informally, this is because if X and Z were
jointly measurable then they could be used to simultaneously obtain a preimage of y and a valid equation
d in x0 + x1 , thereby violating (F.2). We proceed with the details. The heart of the proof is the following
claim.
Claim 4.5. For any b ∈ {0, 1},
hψ| Zb XZb |ψi = negl(λ) ,
where Zb = (Id +(−1)b Z )/2, negl(λ) denotes some negligible function of λ, and the expression on the
left should be understood on average over pk ← G EN (1λ ) and the distribution of y as returned by P in the
protocol.
Proof. We do the proof for the case b = 0, the other case being similar. Suppose for contradiction that there
is a polynomial q : N → R+ such that
1
hψ| Z0 XZ0 |ψi ≥ (4.5)
q(λ)
for infinitely many values of λ. We use this assumption to construct an adversary in (4.2). The adversary
proceeds as follows. Given as input 1λ and pk the adversary first executes the first phase of the prover,
obtaining an outcome y and a state |ψi. Then, the adversary measures the m qubits in register X in the
computational basis to obtain a value x ∈ {0, 1}m . If b( x ) = 0 then the adversary applies the unitary V
and measures register X (again) in the Hadamard basis to obtain d ∈ {0, 1}n . The adversary returns the pair
( x, d). If b( x ) = 1 then the adversary chooses d ∈ {0, 1}m uniformly at random and returns d. Since the
prover P and b are both efficient, A is efficient.
Note that this adversary does something “unusual” in the sense that it sequentially applies two operators
that the prover would never have applied simultaneously in the protocol. It is to make sense of this sequential
55
application that we made the structural simplifications at the start of the proof. Let’s analyze the success
probability of A by using (4.5). There are two cases. Suppose first that the adversary obtains an x such that
b( x ) = 0. Then since P is assumed to succeed with probability 1 in case c = 0, we know that necessarily
x = x0 , and moreover prior to the measurement the support of |ψi on X contained only the two values | x0 i
and | x1 i (as otherwise there would be a chance that the prover returns an invalid preimage to the challenge
c = 0). Thus by definition of Z in (4.3) the post-measurement state is Z0 |ψi (suitably re-normalized). The
probability that A obtains b( x ) = 0 and then a correct equation is then, by definition of X in (4.3) and
X0 = 21 (Id + X ), precisely
1
hψ| Z0 X0 Z0 |ψi = hψ| Z0 |ψi + hψ| Z0 XZ0 |ψi .
2
For the second case assume that A obtains an x such that b( x ) = 1. In this case it returns a uniformly
random equation; since x0 + x1 6= 0 this has probability exactly 12 of being correct. Overall, the adversary’s
success probability is
1 1 1 1
hψ| Z1 |ψi + hψ| Z0 |ψi + hψ| Z0 XZ0 |ψi = + hψ| Z0 XZ0 |ψi ,
2 2 2 2
where the equality uses Z0 + Z1 = Id to combine the first two terms. Using (4.5), this violates (4.2).
To conclude the proof of the theorem we need the following simple calculation.
Claim 4.6. Let X, Z be any two binary observables on H. Then
1
{ X, Z }2 = XZ0 XZ0 + Z1 XZ1 X .
4
Proof. This can be verified by direct calculation. Using that X and Z are Hermitian and square to identity
we get by expanding the square
{ X, Z }2 = 2 + XZXZ + ZXZX . (4.6)
Expanding Z = Z0 − Z1 ,
ZXZ = Z0 XZ0 + Z1 XZ1 − Z0 XZ1 − Z1 XZ0 .
Moreover, using Z0 + Z1 = Id it follows that
Z0 XZ0 + Z1 XZ1 + Z0 XZ1 + Z1 XZ0 = X
Putting the two equations together, ZXZ = 2 Z0 XZ0 + Z1 XZ1 − X. Plugging back into (4.6) and using
X 2 = Id proves the claim.
Combining Claim 4.6 and Claim 4.5 we make the following calculation:
1 2
{ X, Z }|ψi = hψ| XZ0 XZ0 |ψi + hψ| Z1 XZ1 X |ψi
4
= hψ| Z0 XZ0 |ψi + hψ| Z1 XZ1 |ψi
= negl(λ) ,
where to obtain the second line we used that X |ψi = |ψi since the prover is assumed to succeed with
probability 1 in the protocol (and hence always return a correct equation). This shows that (|ψi, Z, X ) is a
near-perfect qubit, completing the proof.
56
Lecture 5
So far we have been entirely focused on the problem of certifying a “qubit”, i.e. that a certain device to
which the experimentalist, or verifier, has access to and is willing to make simple assumptions about (the
device has two spatially isolated components/the device is computationally bounded) is, at some point in its
execution, making a pair of anti-commuting measurements.
Our goal in the next three lectures is to go beyond the certification of a single qubit, to the verification
that the device implements an entire quantum computation of the verifier’s choice. In this lecture we define
this problem of delegating quantum computations to an untrusted party and give an overview of existing
approaches. Towards the end of the lecture we describe a protocol due to Fitzsimons and Morimae [MF16]
that involves quantum communication from the prover to the verifier. In subsequent lectures we combine
that protocol with the computational qubit test from the previous lecture and a few additional ideas to obtain
a purely classical protocol due to Mahadev [Mah18].
57
Given a quantum circuit C acting on n qubits and x ∈ {0, 1}m for some m ≤ n we say that “C
accepts input x with probability p” if the probability of obtaining the outcome 1 after a measurement in the
computational basis of the first qubit of the n-qubit state obtained by applying the unitary C to the input state
| x i|0n−m i is p.
Definition 5.1. We say that a promise language L = ( Lyes , Lno ) is in BQP if there exists a family of
polynomial-time generated quantum circuits {Cn }n∈N such that for all integer n and x ∈ {0, 1}n ,1
• (Completeness:) If x ∈ Lyes then Cn accepts x with probability at least 32 ;
• (Soundness:) If x ∈ Lno then Cn accepts x with probability at most 13 .
Note the requirement that the family {Cn } is polynomial-time generated. This means that there exists a
classical Turing Machine that on input 1n runs in time poly(n) and returns a description of Cn as a sequence
of gates taken from a fixed universal set—here we use (5.1), but the specific choice will not matter for us.
The definition of BQP sets arbitrary values 2/3 and 1/3 for the completeness and soundness param-
eters. Error amplification works just as for the case of BPP, by repeating the circuit sequentially. This
requires intermediate measurements, but it is not hard to show that these can be postponed till the end
of the computation by the use of ancilla qubits and CNOT gates. As a result, any choice of a, b such
that a − b > poly−1 (n) gives the same definition: for any such a, b, and for any fixed polynomial q,
BQP ( a, b) = BQP = BQP (1 − 2−q , 2−q ).
Exercise 5.1. Show that BQP is included in PP, the class of languages for which there exists a probabilistic
Turing machine that accepts YES inputs with probability > 1/2, and rejects NO inputs with probability
> 1/2. (Hint: first show inclusion in PSPACE by giving space-efficient implementations of basic linear
algebra operations. Inclusion in PP follows from similar arguments, but is a bit more delicate.)
The class PP lies outside of the polynomial hierarchy. The most commonly-held belief is that the
intersection of BQP and PH is non-trivial: it is neither BPP, nor PH itself. Recently Raz and Tal [RT19]
showed that an oracle problem introduced by Aaronson [Aar10] is in BQP but not in PH.
Recall the notion of interactive proof system that we introduced informally in Section 2.2. We end this
section by defining a family of complexity classes associated with interactive proof systems.
Definition 5.2 (Adapted from [AG17]). Given complexity classes P and Q, IP [P , Q] is the class of
(promise) languages L such that there is a polynomial-time Turing machine M that on input 1n returns
the description of classical circuits for the verifier Vn in an interactive protocol with a prover P such that
• (Completeness:) There is a family of provers { Pn }n∈N that lie in the class P such that for all x ∈ Lyes
the interaction of V| x| and P| x| on common input x accepts with probability at least 32 .
• (Soundness:) For any family of provers { Pn }n∈N that lie in the class Q, for all x ∈ Lno the interaction
of V| x| and P| x| on common input x accepts with probability at most 13 .
When the classes P and Q coincide we simply write IP [P ] for IP [P , P ]. We use the standard notation
IP = IP [ BPP, ALL ] with ALL the class of all languages (i.e. soundness is proves without any restriction
on the prover).
The definition is slightly informal, because for some classes P it may not be clear what it means for the
prover to lie in P . For us the meaning will always be clear from context, as P and Q will always be either
BPP, BQP or ALL.
1 Note that in general, Cn may act on poly(n) qubits, the first n of which are by convention destined to receive the input x and
the first of which also serves as output qubit.
58
5.1.2 Delegating quantum computations
The fact that BQP is not (believed to be) in NP implies that in general we do not expect there to exist
classically verifiable proofs for the correctness of an arbitrary quantum computation. This poses a challenge:
as we see quantum computers emerging, how will we test their predictions? This is a practical problem —
will anyone trust the “quantum cloud” — but also a philosophical one — is quantum mechanics a testable
theory? (For more on this, see [AV13].)
Not all is lost. What we do know is that BQP is included in PSPACE, the class of languages that can
be decided using polynomial space (and arbitrary time); in fact Exercise 5.1 asked you to show a stronger
statement. And even though it is not a trivial result, it is known that PSPACE = IP. So all languages
in BQP have classical interactive proofs, with an efficient classical verifier! Unfortunately there is a major
caveat to this observation. The proof that PSPACE is in IP is based on the classical SUM-CHECK protocol,
which in general requires the server to execute PSPACE-complete computations (essentially, the server has
to compute exponentially large sums in order to determine answers that will satisfy the client). (For an
exposition of the proof we refer to the book [AB09].)
So, even though a protocol exists, it is unknown if there is such a protocol in which a honest server is
only required to have the power of BQP. Today this is a major open question:
Open Question 5.3. Is BQP ⊆ IP [ BQP, ALL ]? In words, do all languages in BQP have single-server
interactive proofs in which the client has the power of BPP and for which completeness holds with a BQP
server and soundness holds against any server?
In [ACGK17] some partial impossibility results are shown for the case of blind delegation protocols. If
the inequality BQP ⊆ IP [ BQP, ALL ] does hold it is likely to require protocols with polynomially many
rounds of interaction, because constant-round protocols lie in AM and BQP is not believed to be in AM.
Such protocols are known where completeness holds for provers that require more power than BQP but not
necessarily the entire power of PSPACE; see e.g. [AG17]. If, however, one allows slightly more power to
the verifier then there are scenario in which the question is known to have a positive answer:
1. The client has access to a limited quantum computer, such as the ability to prepare single qubits in
arbitrary states and send them to the server, or receive single qubits from the server and make simple
measurements on them;
2. The client is allowed to interact with multiple quantum servers sharing entanglement.
The question as formulated above asks for verifiable delegation: given a quantum circuit (deciding some
BQP language L), is there a protocol that allows a classical client to extract the outcome of the circuit
from a BQP server, in a way that any cheating server, attempting to convince the client of the wrong
outcome, will be detected? A second desirable property of a delegation protocol is blindness: while the
client would like to learn the valid outcome of her circuit, she might not want to disclose the particular
circuit or input she is interested in to the server. This is a distinct property from verifiability; in particular,
one may ask for blindness in the “honest-but-curious” model, where verifiability is trivial. The following
definition introduces these properties slightly more formally.
Definition 5.4 (Delegated computation). In the task of delegated computation, a client (sometimes called
the verifier) has an input ( x, C), where x is a classical string and C the classical description of a quantum
circuit. The client has a multiple-round interaction with a quantum server (sometimes also called server).
At the end of the interaction, Alice either returns a classical output y, or she aborts. A protocol for delegated
computation is called:
59
• Correct if whenever both the client and the server follow the protocol, with high probability Alice
accepts (she does not abort) and y = C( x ). (This property is sometimes called completeness.)
• Verifiable if for any server deviating from the protocol, the client either aborts or returns y = C( x ).
(This property is analogous to what we have been calling soundness.)
• Blind if for any server deviating from the protocol, at the end of the protocol the server has no infor-
mation at all about the client’s input ( x, C).
The definition remains rather informal. For example, how should we formalize the “information” that
the server has at the end of the computation? This can be rather delicate, especially once one starts taking
into account a small chance ε of deviation from the perfect properties. A precise definition satisfying all the
desired properties (universal composability in particular) would take us too far. Such a definition was given
using the framework of abstract cryptography in [DFPR14].
The informal definition will be sufficient for our purposes. Note that in spite of being rather similar
neither of the properties of verifiability or blindness is known to directly implies the other. In practice
verifiability often follows from blindness by arguing, using “traps”, that if a protocol is already blind then
the server’s trustworthiness can be tested by making it run “dummy” computations for which Alice already
knows the output, without the server being able to distinguish whether it is asked to do a real or dummy
computation. We will see an example of this technique later on.
Open Question 5.5. Is there a general transformation from any protocol satisfying blindness, to a protocol
satisfying both verifiability and blindness? See [Mor18] for how to achieve this by making use of post-hoc
verification (cf. Section 5.2), and [KMW17] for another approach.
Remark 5.6. The problem of delegating computation is interesting even for classical computation. In this
case the client herself could directly execute the classical circuit C . But it makes sense to be even more
demanding, and seek protocols where the client is super-efficient: the best we could hope for is a client that
runs in time linear in the input length, and independent of the size of the circuit. In addition, we would like
the overhead for the server to be as small as possible, so that the honest behavior requires a server effort
of the same order as the size of the circuit, |C|. This kind of interactive proofs are called doubly efficient
interactive proofs [GKR08]. The paper [RRR16] shows how to achieve such proofs with client runtime
that is linear in the input length, polynomial in the space required by C , and polylogarithmic in |C|. If one
is willing to make computational assumptions (essentially, subexponential LWE) then even more efficient
delegation is possible [KRR14], with client runtime that is linear in the input size and poly-logarithmic in
|C|.
These results usually do not put emphasis on the requirement of blindness: they focus on verifiabil-
ity alone. One reason for this is that blindness is “trivially solved” by employing homomorphic encryp-
tion [Gen09]. This, however, requires computational assumptions, and induces significant computational
overhead.
60
5.2 The Fitzsimons-Morimae protocol
We describe the receive-and-measure protocol from [MF16], as it will form the basis for the Mahadev
protocol.
[Link]
Figure 5.1: Two different ways to create a tableau from a quantum circuit. The state |ψtableau i is the tensor
product of the state of the circuit at each time step. The state |ψhist i is their superposition, indexed by a
clock register that goes from |0i to | T i.
For quantum circuits the idea of a tableau of the computation is less straightforward. The most direct
analogue is to consider the juxtaposition of the quantum state of a T-gate circuit at each step of the com-
putation, i.e. the tensor product |ψ0 i ⊗ · · · ⊗ |ψT i of the states |ψi i obtained by executing the circuit from
scratch and stopping after i gates have been applied. While this is a well-defined n( T + 1)-qubit quantum
state (see Figure 5.1) the property of being a valid “quantum tableau” cannot be enforced using local con-
straints! The reason is subtle, and has to do with the possible presence of entanglement at intermediate steps
of the computation. Indeed, there are quantum states that are very different, in the sense that they are per-
fectly distinguishable by some global observable, yet cannot be distinguished at all by any local observable,
that would act on at most, say, half the qubits. An example is given by the two n-qubit “cat” (named after
the homonymous animal) states
1
|ψ± i = √ |0 · · · 0i ± |1 · · · 1i .
2
The two states |ψ+ i and |ψ− i are easily seen to be orthogonal, so that they can be perfectly distinguished
by a measurement. But it is an exercise to verify that for any observable that acts on at most (n − 1) of the
n qubits, both states give exactly the same expectation value. (Informally, this is because any measurement
on a strict subset of the qubits of the state necessarily destroys the coherence; the only relevant information,
the ± sign, is encoded “globally” and cannot be accessed locally.) Note that this is a uniquely quantum
phenomenon: if two classical strings of bits have each of their bits equal, one pair at a time, then the strings
are “globally” identical. Not so for quantum states.
So naı̈ve tableaus will not do. In the late 1990s Alexei Kitaev introduced a very powerful idea that
provides a solution. Kitaev’s idea is to replace the juxtaposition of snapshot states by their superposition
61
(see Figure 5.1). A special ancilla system, called the “clock”, is introduced to index different elements of
the superposition. Thus, instead of defining a tableau as |ψ0 i · · · |ψT i, Kitaev considers the state
T
1
|ψhist i = √ ∑
T + 1 t =0
|ti|ψt i . (5.2)
Note that this takes less qubits to store, but this is not the important point. Kitaev showed that, assuming
the clock register is encoded in unary, it is possible to check the correct propagation of every step of the
circuit directly on this superposition by only applying local observables: there is a set of observables Hin
that checks that |ψ0 i has the right format; a set of observables H prop that checks propagation of the circuit,
and an observable Hout that checks that the output qubit of the circuit is in the right state. (In addition,
there is a term Hclock that checks that the clock register is well-formed, i.e. contains the representation of
an integer in unary. This can be done locally by penalizing configurations of the form “· · · 10 · · · ”.) The
key point that makes this possible is that, while equality of quantum states cannot be decided locally when
the states are juxtaposed, it becomes possible when they are given in superposition. As an exercise, we can
verify that a measurement of the first qubit of the state
1
|ψSWAP i = √ |0i|ψ0 i + |1i|ψ1 i
2
in the Hadamard basis {|+i, |−i} returns the first outcome with probability exactly 12 (1 + |hψ0 |ψ1 i|2 ).
With more work, replacing the use of gadgets in the classical Cook-Levin reduction by techniques from
perturbation theory, it is possible to write the resulting observables as a linear combination of local terms
that all take a particularly simple form. The result is the following theorem from [CM16].
Theorem 5.7. For any integer n ≥ 1 there are n0 = poly(n), a = a(n) and δ ≥ 1/ poly(n) such
that the following holds. Given a T-gate quantum circuit C = (( G1 , i1 , j1 ), . . . , ( GT , i T , jT )) acting on n
qubits, such that T = poly(n), and an input x for the circuit, there exist efficiently computable real weights
{ Jij , i, j ∈ {1, . . . , n0 }} such that | Jij | ≤ 1 for all i, j and moreover if
Jij
HC = − ∑
σX,i σX,j + σZ,i σZ,j , (5.3)
i,j
2
where σX,i and σZ,j denote single-qubit Pauli X and Z operators acting on the i-th and j-th qubit respectively,
then:
• (Completeness) If the circuit C accepts its input x with probability at least 2/3, then the smallest
eigenvalue of HC is at most a;
• (Soundness) If the circuit C accepts its input x with probability at most 1/3, then the smallest eigen-
value of HC is at least a + δ.
Remark 5.8. It is possible to modify Theorem 5.7 so that the completeness and soundness statements specify
that “if there exists a state |φi such that C accepts on input ( x, |φi) with probability at least 2/3...” and “if
there does not exist a state |φi such that C accepts on input ( x, |φi) with probability greater than 1/3...”
respectively. Thus, Theorem 5.7 can be adapted to show that the problem of estimating the minimal energy
of a Hamiltonian of the form (5.3) is a QMA-complete problem.
Theorem 5.7 provides us with a roadmap for the verification of quantum circuits: it is sufficient to
verify the existence of a quantum state that yields certain statistics, when some of its qubits are measured in
62
the computational (σZ observable) or Hadamard (σX observable) basis. The reason this can be considered
progress is that we no longer need to check the time evolution of a quantum state under a quantum cicuit; it
is sufficient to collect measurement statistics and estimate the “energy” hψ| H |ψi. In particular, the theorem
readily leads to a verification protocol in a model where the prover has a full quantum computer, and the
verifier only has a limited quantum device — namely, a one-qubit memory, together with the ability to
measure the qubit using either the σX or σZ observables.
Let C be a quantum circuit provided as input, and HC the n0 -qubit Hamiltonian obtained from C as in (5.3).
1. The verifier initializes a counter γ to 0. She executes the following interaction with the prover inde-
C n0 2
pendently N = ( ) ln(1/ε)
δ2 2
times, where C is a large enough universal constant:
We note that in the protocol, the verifier measures the qubits in a randomly chosen basis, and then selects
a single pair (i, j) such that Jij 6= 0 uniformly at random to update her counter. One could imagine small
optimizations where e.g. a maximum matching of such pairs is measured at each step. Such optimizations
only bring marginal improvements in efficiency of the protocol; moreover they complicate the extension to
a classical verifier that we will see later. For this reason, we prefer to keep the simplest expression possible
for the protocol.
Theorem 5.9. Let C be a quantum circuit and HC the Hamiltonian associated to it as in (5.3). Let x be an
input to the circuit C and ε > 0 a parameter for the protocol. Then the following hold:
• (Completeness:) If C accepts x with probability at least 2/3, then there is a QPT prover that is
accepted with probability at least 1 − ε
63
• (Soundness:) If C accepts x with probability at most 1/3, then any prover is accepted with probability
at most ε.
Note that in the theorem, the soundness statement does not place any computational assumption on the
prover.
Proof. The key calculation that underlies the proof is the following.
Claim 5.10. Let ρ be the density matrix that represents the mixture over the N n0 -qubit states sent by the
prover in the protocol (in general these states may be entangled). Then the expectation of γ/N is exactly
hγi 1 Jij 1
∑
j j
Tr σXi σX + σZi σZ ρ = n0 Tr Hρ .
E = − n0
(5.4)
N (2) i6= j
2 (2)
Moreover, for N chosen as in the protocol for a large enough choice of the constant C it holds that
γ n0 δ
Pr − Tr Hρ > ≤ ε. (5.5)
N 2 2
Proof. For t ∈ {1, . . . , n} let Gt denote the product of the two outcomes bW,i and bW,j obtained by the
verifier at step (c) of the protocol, where W, i and j are as sampled at step (d). Then the random variables
Gt ∈ {−1, 1} are i.i.d. such that for each t, E [ Gt ] = Tr(σWi σ j ρ ), with W, i and j are the values sampled
W
in step t. Since γ = − ∑t Jij Gt , averaging over those choices gives (5.4). Using | Jij | ≤ 1, by Hoeffding’s
inequality for any s > 0
2s2
Pr γ − E [γ] > s ≤ e− 4N .
0 2
By choosing N sufficiently large with respect to (n2 ) δ−2 ln(1/ε) we get (5.5).
Based on Claim 5.10 the proof of Theorem 5.9 follows rather directly. For the completeness, we take ρ =
|ψihψ| such that hψ| H |ψi ≤ a, whose existence is guaranteed by the completeness case of Theorem 5.7.
As noted above, this ρ can be prepared efficiently by a QPT prover. Using (5.5) it follows that this prover
is accepted with probability at least 1 − ε. For the soundness, ρ is arbitrary. Using the soundness case of
Theorem 5.7 it must be that Tr( Hρ) ≥ a + δ, so that the conclusion follows again from (5.5).
Even though the verifier’s “quantumness” in this protocol is limited — she only needs to hold one qubit
at a time — this capability is crucial for the analysis, as it is used to guarantee the “existence” of the state
that is being measured: it allows us to meaningfully talk about “the state ρ whose first qubit is the first qubit
received by the verifier; whose second qubit is the second qubit received by the verifier; etc.”. These qubits
are distinct, because the verifier has seen and then discarded them (it would be a different matter if they
were returned to the prover). In particular, the fact that a one-qubit computer can be trivially simulated on a
classical piece of paper is immaterial to the argument.
With a classical verifier things become substantially more delicate. How can we verify the existence of
an n-qubit state with certain properties, while having only access to classical data about the state, data that,
for all we know a priori, could have been generated by a simple — classical — laptop? To achieve this we
need to find a way for the verifier to establish that the prover holds an n-qubit state, without ever having the
ability to directly probe even a single qubit of that state. In the previous lecture we saw a means to achieve
this for a single qubit based on the computational hardness of certain functions called “claw-free”. In the
next lecture we extend that method to introduce a protocol by which the prover can certify the existence
64
of any single-qubit state that is a low-energy eigenstate of a single-qubit Hamiltonian. In the following
lecture we combine this extension with the Fizsimons-Morimae protocol to obtain a protocol for delegating
quantum computations with a classical client.
65
66
Lecture 6
In the previous lecture we introduced the circuit-to-Hamiltonian construction, that given a quantum cir-
cuit C and an input x to it returns a Hamiltonian HC of the form (5.3) such that the completeness and
soundness properties stated in Theorem 5.7 hold. This construction allowed us to reduce the problem of del-
egating a quantum computation to the problem of deciding if a certain publicly known, explicitly specified
exponential-size Hermitian matrix HC has an eigenvalue below a certain threshold a, or all its eigenvalues are
above b + δ for a δ that is at least inverse polynomial in the number of qubits n on which HC acts.1 We then
introduced the Fitzsimons-Morimae protocol (Figure 5.2) that is a protocol with one-way communication
for verifying this fact.
Our goal in the next two lectures is to combine the Fitzsimons-Morimae protocol with the computational
test for a qubit from lecture 4, Section 4.3 to obtain a classical protocol with similar guarantees to the
Fitzsimons-Morimae protocol. For this we will develop a test that allows one to verify that a prover “has” a
quantum state |ψi with certain properties (e.g. it satisfies hψ| H |ψi ≤ a + δ/2, i.e. certifies that the outcome
of the computation is ‘1’. Note that even though in principle it is sufficient for the verifier to be convinced
that such a |ψi exists to make the right decision, we will see from the proofs that we can go a little further
and give a precise meaning to the notion that the prover ‘has’ |ψi. This, however, will not be as strong as
the claim that the prover ‘has n qubits in state |ψi’ in the sense that we gave to the phrase ‘has n qubits’, i.e.
we will not quite exhibit 2n Pauli operators Xi , Zi that satisfy all the required relations.
Remark 6.1. In passing to the Hamiltonian model of computation we relaxed our main goal, from obtaining
a value b ∈ {0, 1} that is distributed as a measurement of the output qubit of the quantum circuit C in the
standard basis to obtaining a value that is 1 whenever this measurement returns 1 with probability larger than
2 1
3 , and 0 whenever it is less than 3 . In particular, we make no requirement for circuits that are “undecided”,
e.g. return a random bit as output. This is typical to applications in complexity where it is assumed that
circuits of interest make a clear-cut decision, 0 or 1; this is the setting discussed in Section 5.1. By tweaking
the definition of HC it is in fact possible to guarantee that any state |ψi such that hψ| HC |ψi ≤ a + δ/2 is
such that a measurement of the first qubit of |ψi in the standard basis yields an outcome whose distribution is
1
within total variation distance, say, 100 from a measurement of the output qubit of C . Using this observation
the protocol given at the end of this lecture can be adapted to return outcomes that are distributed close to
the circuit output distribution, even in cases where the output is not assumed to be biased one way or the
other. For simplicity we leave this extension as an exercise to the reader.
1 In the previous lecture this number of qubits was called n0 , with n the number of qubits of the circuit C . For the next two
lectures, C disappears and so we re-use n to measure the size of HC .
67
6.1 A test for a specific single-qubit Hamiltonian
We start with an “easy” case: we show how the computational test for a qubit from lecture 4, protocol Q, can
be cast as a verification protocol for the claim that the Hamiltonian H = −σZ has a “low” eigenvalue, equal
to −1. We go a little further by showing how such an eigenstate can be “extracted” from any successful
prover in the protocol.
1
Id ⊗ IdA ⊗ IdQ + X ⊗ σX ⊗ IdQ + Z ⊗ σZ ⊗ IdQ + XZ ⊗ σX σZ ⊗ IdQ | ϕi|φ+ iAQ ,
∀| ϕi ∈ H , V | ϕi =
2
(6.1)
where the systems in the range of V are re-ordered so that the first factor C2 is associated with the second
qubit of |φ+ iAQ in (6.1), and H0 consists of the state of the first qubit of |φ+ i, i.e. register A, as well as the
part of the state in H. Then V is an isometry and for all W ∈ { X, Z },
Proof. The proof is by direct calculation. First we verify that V is indeed an isometry. This is simply because
the four states {(σX ( a)σZ (b) ⊗ Id)|φ+ i, a, b ∈ {0, 1}} are orthonormal2 and X and Z are observables, so
2 For a, b ∈ {0, 1} we use the notation σX ( a) for σXa and similarly σZ (b) for σZb . The motivation for this notation will be seen
later when we consider n-qubit Pauli operators.
68
that for normalized | ϕi each of the four terms on the right-hand side of (6.1) has norm exactly 1. Note that
this does not require any other condition on X, Z than that they are observables (in fact, unitarity suffices).
In particular, they do not need to anti-commute. Next we verify (6.2). Take W = X. Then
1
X ⊗ Id ⊗ Id + Id ⊗σX ⊗ Id − XZ ⊗ σZ ⊗ Id − Z ⊗ σX σZ ⊗ Id |ψi|φ+ i
VX |ψi =
2
1
= X ⊗ Id ⊗ Id + Id ⊗σX ⊗ Id − XZ ⊗ σZ ⊗ Id − Z ⊗ σX σZ ⊗ Id |ψi(σX ⊗ σX )|φ+ i
2
1
= X ⊗ σX ⊗ σX + Id ⊗ Id ⊗σX + XZ ⊗ σX σZ ⊗ σX + Z ⊗ σZ ⊗ σX |ψi|φ+ i
2
= (σX ⊗ Id)V |ψi ,
where for the first line we used that X and Z anti-commute on |ψi, for the second that σX ⊗ σX |φ+ i = |φ+ i,
for the third that σX and σZ anti-commute, and for the last we re-ordered terms.
69
of a space for a qubit, and a state for that qubit, associated with any prover in protocol Q, the computational
test for a qubit described in Figure 4.1. This definition does not guarantee that the prover “has a qubit,”
because it does not say anything about how the prover’s observables operate on it. However, it still allows us
to define a candidate for a single-qubit state on which σX and σZ measurements can in principle be made.
The next claim evaluates how outcomes of these measurements when performed on the extracted qubit are
a distributed as a function of the observables X and Z on the prover’s state |ψi.
Claim 6.4. Let |ψi ∈ H and X, Z observables on H be arbitrary. Let V be defined as in (6.1). Then the
following hold:
V
H C2 ⊗ H0
Z σZ ⊗Id
(6.5)
E b∈{0,1} (−1)b Z b XZ b σX ⊗Id
V
H C2 ⊗ H0
We emphasize that this diagram is purely illustrative and should be understood exactly in the sense of (6.3)
and (6.4); i.e. it does not imply a relation on the operators but only on the expectation values on the state
|ψi. Informally, when considering expectation values only the isometry has the effect of applying a Z-twirl
to the Hadamard basis observable X.
1
hψ|V † σW ⊗ Id V |ψi = ∑ hψ| P† Q|ψi · hφ+ |σP† σQ ⊗ σW |ψi
4 P,Q∈{ I,X,Z,XZ }
1
=
4 ∑ hψ| P† Q|ψi ,
P,Q: σP† σQ =σW
where for the second line we used that hφ+ |σW ⊗ σW 0 |φ+ i = δW,W 0 with δ the Kronecker symbol. In case
W = Z the pairs P, Q that appear in the last summation above are ( X, I ), ( I, X ), ( XZ, X ) and ( X, XZ ).
Using X 2 = Id we obtain (6.3). In case W = X then the summation is over ( Z, I ), ( I, Z ), ( XZ, Z ) and
( Z, XZ ) and has a minus sign for the last two terms due to σX σZ = −σZ σX . Thus we get (6.4) as well.
Observe that if X and Z anti-commute then Claim 6.4 gives us the result that we expect: in this case
(|ψi, Z, X ) is a qubit so Proposition 6.2 applies and the isometry “intertwines” measurements X and Z on
|ψi with σX and σZ respectively on the first factor of V |ψi. At the other extreme, if X and Z commute
then (6.4) indicates that a measurement in the Hadamard basis of the extracted qubit returns an unbiased
70
random bit. This is expected of a “classical” state, which always leads to uniformly random results in the
Hadamard basis. The lemma in some sense interpolates between these results. Importantly, it allows us to
associate a qubit with the state of an arbitrary prover in the protocol, that is such that the distribution of mea-
surements on the extracted qubit can be related to quantities that involve the prover’s state and observables
in the protocol. For convenience we make this into a definition.
Definition 6.5 (Extracted qubit). Let P be a prover in protocol Q. Let |ψi be the state of P after having sent
y in the first round of interaction. Let V be defined as in (6.1). Then we call the reduced density of V |ψi on
the first factor C2 , associated with register Q, the extracted qubit and denote it by ρQ .
Lemma 6.6. Let P be a prover that succeeds with probability 1 in the pre-image test of protocol Q and such
that the string d returned in the equation test is d = 0m with probability that is negligibly small in λ. (No
other assumption is made on the equation test.) Let ρ be the extracted qubit, as defined in Definition 6.5.
Then the following hold:
• (Z-measurement:) The outcome of measuring ρ in the computational basis is identically distributed
to the bit (−1)b(x) computed from the prover’s answer x in case c = 0.
• (X-measurement:) Under assumption (F.2), the outcome of measuring ρ in the Hadamard basis is
computationally indistinguishable from the bit (−1)d·(x0 + x1 ) where d is obtained from the prover in
case c = 1.
Remark 6.7 (Computational distinguishability). The statement of the lemma refers to two distributions being
computationally indistinguishable. Informally, this means that no computationally efficient procedure can
distinguish a sample taken from one distribution from a sample taken from the other. Formally, families of
distributions D = { Dλ } and D 0 = { Dλ0 } on universes {Xλ } are said to be computationally indistinguish-
able if for any PPT (or QPT for computational indistinguishability against quantum adversaries) procedure
A there is a negligible function µ such that for every λ,
A(1λ , x 0 ) = 1
Pr A(1λ , x ) = 1 − Pr ≤ µ(λ) .
x ← Dλ x 0 ← Dλ0
Here, when we refer to computational indistinguishability we will always mean against QPT adversaries.
Note that for distributions on a family of universes {Xλ } such that |Xλ | grows at most polynomially with λ
the notion of computational indistinguishability is equivalent to statistical indistinguishability, i.e. the total
variation distance between Dλ and Dλ0 goes to 0 as fast as some negligible function. (Showing this formally
is a good exercise to practice with the definitions.)
Proof. The first item follows immediately from (6.3) in Claim 6.4 and the definition of Z in (4.3), which
guarantees that the bit (−1)b(x) obtained from the prover in case c = 0 has expectation precisely hψ| Z |ψi.
To show the second item we assume for contradiction that the two distributions are computationally
distinguishable. Since the distributions are over a single bit, as recalled in Remark 6.7 this is equivalent to
statistical distinguishability: there must exist a polynomial q(λ) such that for infinitely many values of λ,
1
hψ| X |ψi + hψ| ZXZ |ψi > , (6.6)
q(λ)
where recall that the expression on the left should be understood on average over the generation of pk by
the verifier and the message y sent by the prover in the first round of interaction. We derive a contradiction
with (F.2) by constructing an adversary in (4.2). Given λ and pk as input, A prepares the state |ψi. A
71
then measures register X in the standard basis to obtain an outcome x. Using the assumption that the prover
succeeds with probability 1 in the pre-image test, f pk ( x ) = y and the (unnormalized) post-measurement
state is exactly Zb(x) |ψi, where as usual Zb = (Id +(−1)b Z )/2. Finally, the adversary applies the prover’s
unitary U and measures in the Hadamard basis to obtain a string d. It returns the pair ( x, d). The expected
value of (−1)d·(x0 + x1 ) under this procedure is
1
hψ| Z0 XZ0 |ψi + hψ| Z1 XZ1 |ψi = hψ| X |ψi + hψ| ZXZ |ψi ,
2
which can be seen by expanding Zb = (Id +(−1)b Z )/2 for b ∈ {0, 1} and canceling cross-terms. Us-
ing (6.6), A violates (4.2).3
assumes that this is the case when the equation is measured directly on |ψi, here A measures after |ψi has already been measured
using the observable Z. To show that the assumption that d 6= 0m with probability negligibly close to 1 still holds one needs to use
the “collapsing” property of f pk , that we will introduce in the next lecture.
72
2. Upon receipt of the function index pk, coherently evaluate f pk on the input in registers BX, writing
the output in register Y to obtain the state
α β
|ψ(1) iBXY =
2m −1 ∑ |0iB | x iX | f (0x )iY +
2m −1 ∑ |1iB | x iX | f (1x )iY .
x ∈{0,1}m−1 x ∈{0,1}m−1
3. Measure the last register to obtain a y. Let (0, x0 ) and (1, x1 ) be the two preimages of y under f pk .
Then the re-normalized post-measurement state is
4. Upon receipt of challenge c, perform as the honest prover in protocol Q: if c = 0 measure registers
BX in the standard basis and return the outcome x = (b, xb ); if c = 1 measure in the Hadamard basis
and return the outcome d.
This prover always returns a valid preimage in the case of a challenge c = 0, so it is accepted with probability
1. Observe that the operator Z associated to this prover is equal to a σZ on register B. Regarding the operator
X, a simple calculation reveals that the action of X restricted to the span of |0, x0 iBX and |1, x1 iBX consists
in exchanging these two basis states. Using the explicit form of the isometry V given in (6.1) one can verify
that
1
V | ψ (2) i = √ | 0 i B | x 0 i X | 0 i A + | 1 i B | x 1 i X | 1 i A ⊗ α | 0 i Q + β | 1 i Q ⊗ | y i Y ,
2
where AQ are the two registers introduced to hold the EPR pair |φ+ iAQ used in the definition of V. Register
Q contains the extracted qubit.
Let F be a 2-to-1 trapdoor claw-free function family and λ ∈ N a security parameter. Let ε, δ > 0 be
accuracy parameters. Let γ = 0 and N = δC2 ln(1/ε) for some large constant C. The verifier and prover
repeat the following interaction N times.
3. The verifier selects a uniformly random challenge c ← R {0, 1} and sends c to the prover.
4. (a) (Computational basis, c = 0:) In case c = 0 the prover is expected to return an x ∈ {0, 1}m .
If f pk ( x ) 6= y then the verifier immediately aborts. The verifier sets a ← (−1)b(x) and γ ←
γ − JZ a.
(b) (Hadamard basis, c = 1:) In case c = 1 the prover is expected to return a d ∈ {0, 1}m . The
verifier uses td to determine the two preimages ( x0 , x1 ) of y by f pk . She sets b ← (−1)d·(x0 + x1 )
and γ ← γ − JX b.
1
If the verifier has not aborted at any of the steps c = 0, she returns the real number o = N γ.
73
The following proposition summarizes what we have achieved so far, a verification protocol for single-
qubit Hamiltonians and a completely classical verifier. (Of course a simpler protocol would be to have
the verifier classically do the computation themselves! The point is that this protocol is not too hard to
extend to n qubits, as we will see in the next lecture.) The protocol, which combines protocol Q with the
Fitzsimons-Morimae verification protocol, is summarized in Figure 6.1.
Proposition 6.9. Let H = − J2X σX − J2Z σZ be a single-qubit Hamiltonian and δ, ε > 0 accuracy parameters.
Then the verification protocol from Figure 6.1 has the following properties:
1. (Completeness:) For any single-qubit state | ϕi, there is a QPT prover that is accepted with probability
1 in the protocol and such that the value o returned by the verifier at the end of the protocol satisfies
E [ o ] = h ϕ | H | ϕ i.
2. (Soundness:) For any QPT prover that is accepted with probability 1 in the protocol, there is a single-
qubit state ρ such that the value o returned by the verifier at the end of the protocol satisfies E [o ] =
Tr( Hρ).
Moreover, with the value of N specified in the protocol in both cases it holds that Pr(|o − Tr( Hρ)| > δ) ≤ ε.
Remark 6.10. The assumption that the prover succeeds with probability negligibly close to 1 in the protocol
can be relaxed to a constant sufficiently close to 1, where the distance to 1 will affect the distance | E [o ] −
Tr( Hρ)|. First we observe that a success probability negligibly close to 1 is sufficient; this can be verified
by going through the argument again, and nothing needs to be changed. Second, it is possible to show that
any prover with success probability 1 − κ for some κ ≥ 0 can be transformed to a prover with success
probability negligibly close to 1, affecting the distribution of o proportionately to κ. Intuitively, the new
prover will test if the value y that the old prover would have returned will lead to success on challenge
c = 0, in case that the test is actually executed by the verifier. This can be done efficiently by the prover
by evaluating the pre-image condition on register X. If this test fails then the new prover simply re-executes
the old prover from scratch, until it is certain to achieve success. With probability negligibly close to 1
this iterative procedure will stop in a polynomial number of steps, and using the √ “pretty-good lemma” it is
possible to show that the prover’s distribution of outcomes is affected by some O( κ ) in statistical distance.
We omit the details.
Proof. The completeness statement follows from Lemma 6.8. For soundness we use Lemma 6.6. This
shows that the expectation of the bit a in step 4.(a) satisfies E [ a] = Tr(σZ ρ) where ρ is the extracted qubit.
Similarly, the bit b in step 4.(b) satisfies E [b] = Tr(σZ ρ). Since by definition
JZ JX
E [o ] = − E [ a] − E [b]
2 2
the proposition follows.
74
Lecture 7
Moving beyond the case of a single qubit, our goal in this lecture is to generalize the results from Section 6.2
to a procedure for extracting n qubits from a prover, together with a statement that allows us to relate
measurements in the standard or Hadamard basis of the extracted qubits to measurements performed by the
prover in the protocol. Once this has been put in place we will not be far from a delegation protocol along
the lines of the Fitzsimons-Morimae protocol from Section 5.2, but, crucially, with classical verifier and
communication.
7.1 Setup
To set the stage we first give a straightforward generalization of the single-qubit verification protocol from
Figure 6.1 to the case of n qubits. Recall from Section 5.2.2 that for our purposes it suffices to consider
Hamiltonians that take the form (5.3). This form allows us to restrict our attention to a collection of mea-
surement outcomes on an n-qubit state such that all qubits are measured in the same basis, computational
or Hadamard. In particular we do not need to consider “mixed” measurements, with some qubits measured
in the standard basis and other qubits in the Hadamard basis, because (5.3) does not have mixed terms such
as σX,i σZ,j . (See Remark 7.1 regarding extensions to the mixed case.) It is then natural to request that the
honest prover behaves exactly as in the single-qubit verification protocol, except that each action should
be repeated independently for each of the n qubits: in the first phase the verifier sends the information
for n functions f pk1 , . . . , f pkn , the prover executes the encoding procedure from the proof of Lemma 6.8
independently for each of the n qubits of its claimed low-energy eigenstate | ϕi of HC and reports the n
images y1 , . . . , yn obtained; in the second phase the verifier sends a single-bit challenge c ∈ {0, 1} and the
prover measures all its qubits in the computational or Hadamard basis and returns the outcomes x1 , . . . , xn
or d1 , . . . , dn respectively. Note that the only part that is not repeated is the challenge, which is identical
for each of the n concurrent repetitions. The reason that we can restrict ourselves to such challenges is due
to the form of HC from (5.3) and, as we will see, greatly simplifies the analysis. The complete protocol is
given in Figure 7.1.
Before proceeding to the analysis of the protocol we examine the question, “Where are the qubits?”
For the single-qubit verification protocol our initial intuition came from the qubit computational test from
lecture 4, for which we were able to argue that the prover indeed has a qubit (|ψi, Z, X ). For the verification
protocol seen in the last lecture we saw that in order to allow verification of other states than the |+i state
75
Let F be a 2-to-1 trapdoor claw-free function family and λ ∈ N a security parameter. Let ε, δ > 0 be
2
accuracy parameters. Let γ = 0 and N = δC2 (n2 ) ln(1/ε). The verifier and prover repeat the following
interaction N times.
2. For ` = 1, . . . , n the verifier generates ( pk ` , td` ) ← G EN (1λ ). It sends ( pk1 , . . . , pk n ) to the prover.
4. The verifier selects a uniformly random challenge c ← R {0, 1} and sends c to the prover.
(b) (Hadamard basis, c = 1:) In case c = 1 the prover is expected to return d1 , . . . , dn ∈ {0, 1}m .
The verifier uses tdi and td j to determine the preimages ( xi,0 , xi,1 ) of yi by f pki and ( x j,0 , x j,1 )
of y j by f pk j respectively. She sets
1 n
If the verifier has not aborted at any of the steps c = 0, she returns the real number o = N ( 2 ) γ.
Jij
Figure 7.1: Verification protocol Vn for an n-qubit Hamiltonian HC = − ∑i,j 2 ( σX,i σX,j + σZ,i σZ,j ).
76
we had to remove some of the tests done by the verifier (specifically, the equation check) and that due to
this we were no longer able to guarantee a qubit in the sense of Definition 2.2. Nevertheless we were able
to get around this by defining an abstract extracted qubit that did not directly correspond to the prover’s
observables but was still such that measurement outcomes on the extracted qubit could be shown to have a
distribution that is negligibly close to outcomes obtained from the prover in the actual protocol (Lemma 6.6).
For the case of demonstrating n qubits a priori one would have to show that the prover has a state |ψi
and two families of observables { X ( a) : a ∈ {0, 1}n } and { Z (b) : b ∈ {0, 1}n } that satisfy the Pauli
commutation and anti-commutation relations when they act on |ψi. Indeed, a straightforward generalization
of Lemma 2.3 then guarantees the existence of a suitable isometry with the space of n actual qubits. Showing
this is challenging; luckily, for our purposes it is also not necessary.1 Indeed, just as in the single-qubit case
it is worth emphasizing that in the context of verification we do not need to guarantee that the prover has a
certain quantum state, nor that it is able to perform certain measurements on it. The only real requirement is
that a state | ϕi exists such that h ϕ| HC | ϕi ≤ a. Thus, as we did in the analysis of the single-qubit verification
protocol we will first introduce a abstract extracted n qubit defined from the prover’s state and actions in
the protocol but that also include additional ingredients that make it at first unclear how they relate to the
prover itself. The definition of the extracted qubits is given in Section 7.2. Once this has been defined
we will perform the second, crucial step, which is to relate the distribution of measurement outcomes on
the extracted qubits to quantities that are directly observable in the protocol. This is done in Section 7.3.
Finally in Section 7.4 we put everything together and show the completeness and soundness properties of
the verification protocol given in Figure 7.1. In addition in Section 7.5 we will sketch a construction of a
function family based on the Learning With Errors (LWE) problem that (approximately) satisfies all required
assumptions and can thus be used to instantiate the protocol.
1. A state |ψi, that may depend on pk1 , . . . , pk n and y1 , . . . , yn , such that |ψi ∈ HX1 ⊗ · · · HXn ⊗ HP
with each space HXi isomorphic to (C2 )⊗m . The state |ψi represents the state of the prover and the
message registers at the end of step 3 in the protocol.
2. For the case c = 0, the prover directly measures all the X registers in the standard basis to obtain
x1 , . . . , xn that it returns to the verifier. For a string a ∈ {0, 1}n we let
where the functions bi are not necessarily all equal since they may depend on pk i . This is analogous
to (4.3).
1 In the last three lectures of the course we will see how in the context of spatial assumptions it is known how to test n qubits in
this sense; for computational assumptions we do not yet know how to do it.
77
3. For the case c = 1, the prover applies an arbitrary unitary U followed by a measurement of the qubits
in X in the Hadamard basis to obtain d1 , . . . , dn . For a string b ∈ {0, 1}n we let
Remark 7.1. Note that the fact that the protocol only has two different challenges, c = 0 and c = 1, allows
us to have a simple description for all Z ( a) and all X (b) observables that involves only one “adversarial”
unitary U. If we had to design a protocol that allows more general Hamiltonians with mixed terms of the
form σX,i σZ,j we would need to consider more challenges, and this would require a more complex analysis.
This is done in [Mah18].
where each EPR pair |φ+ i has one qubit in register Q and the other in register A and the σX and σZ
operators act on register A. Then V is an isometry.
The proof of the claim is immediate and only uses that the family of states
is orthonormal. Similarly to Definition 6.5 we can now define the n extracted qubits.
Definition 7.3 (Extracted qubits). Let P be a prover in the verification protocol Vn described in Figure 7.1.
Let |ψi be the state of P after having sent y1 , . . . , yn at step 3 of the t-th iteration, for some t ∈ {1, . . . , N }.
Let V be defined in (7.3). Then we call the reduced density of V |ψi on register Q the extracted qubits
(implicitly, at iteration t) and denote them by ρQ1 ···Qn .
∀b ∈ {0, 1}n ,
Tr σZ (b)ρ = hψ| Z (b)|ψi , (7.4)
1
∀ a ∈ {0, 1}n , Tr σX ( a)ρ = n ∑ (−1) a·b hψ| Z (b) X ( a) Z (b)|ψi .
(7.5)
2 b
78
The claim can be illustrated using the following generalization of (6.5)
V
H C2 ⊗ H0
Z (b) σZ (b)⊗Id
(7.6)
E b∈{0,1} (−1)b·a Z (b) X ( a) Z (b) σX ( a)⊗Id
V
H C2 ⊗ H0
Proof. Eq. (7.4) is immediate using that X ( a) are observables and hφ+ |⊗n σX ( a0 )σZ (b0 ) ⊗ σZ (b)|φ+ i⊗n is
zero unless a0 = 0 and b = b0 . Eq. (7.5) is shown similarly by direct calculation, using X ( a0 ) X ( a00 ) =
X ( a0 + a00 ) and σZ (b)σX ( a)σZ (b) = (−1) a·b σX ( a).
The next lemma is the key lemma. It argues that for computationally bounded provers, the quantity on
the right-hand side of (7.5) is close to the simpler quantity hψ| X ( a)|ψi, that in particular can be inferred in
the protocol from the prover’s outcomes yi and di (for those i such that ai = 1). Before we can state the
lemma we need to introduce one last assumption on the function family F . Intuitively, this assumption is a
natural quantum analogue of the classical property of collision resistance, but is stronger than it.
(F.5) Consider the following abstract game between an arbitrary “adversary” (think prover) and a trusted
(quantum) “challenger” (think verifier). First, the adversary is provided a label pk (generated at ran-
dom by the challenger) and required to prepare an arbitrary state of the form |φi = ∑ x α x | x i, where
x ranges over the domain of f pk . (In general the adversary may keep an additional register entan-
gled with this state. For ease of notation we do not consider such entanglement in this description.)
The adversary hands the state |φi over to the challenger, who evaluates f pk in superposition on |φi
and measures the image register, obtaining a y in the range of f pk and the (suitably re-normalized)
post-measurement state |φ0 i = ∑ x: f pk (x)=y α x | x i. The challenger then returns to the adversary the
string c together with either the state |φ0 i or the probabilistic mixture ∑ x: f (x)=c |α x |2 | x ih x | obtained
by measuring the same state |φ0 i in the computational basis (and throwing away the outcome). The
adversary wins if it correctly guesses which is the case. Assumption (F.5) on the function family F
states that for any QPT adversary A there is a negligible function µ such that for any λ, A succeeds
in this game with probability that deviates from 21 by at most µ(λ).
Remark 7.5. Assumption (F.5) is referred to as the “collapsing” property for the function family F . This
property was introduced by Unruh as a strengthening of the classical property of collision resistance required
for his work on the security of commitment protocols that are computationally binding against quantum
adversaries [Unr16]. The reason that this assumption implies collision resistance is that, if the function were
not collision resistant, the adversary could identify a colliding pair ( x0 , x1 ) and submit |φi = √1 (| x0 i +
2
| x1 i) to the challenger. It could then measure the challenger’s response in a basis containing the two states
√1 (| x0 i ± | x1 i) and guess that, in case the “−” outcome is obtained, the challenger must have measured;
2
in the other case, the adversary guesses at random.
Note that assumption (F.2) also trivially implies collision resistance, since the ability to identify a claw
allows one to generate arbitrary equations in it. It is possible to show that both (F.2) and (F.5) are strictly
stronger than collision resistance. It is likely that the two assumptions are incomparable, but I have not tried
to show this explicitly.
We can now state and prove the key lemma.
79
Lemma 7.6. Let P be a prover that succeeds with probability 1 in protocol Vn . Let ρ be the n extracted
qubits, as defined in Definition 7.3 (for any iteration). Then the following hold for any i 6= j ∈ {1, . . . , n}:
• (Z-measurement:) The outcome of measuring qubits i and j of ρ in the computational basis is identi-
cally distributed to the bits b( xi ) and b( x j ) obtained from the prover in case c = 0.
• (X-measurement:) Under assumptions (F.2) and (F.5) the outcome of measuring qubits i and j of ρ
in the Hadamard basis is computationally indistinguishable from the pair of bits di · ( xi,0 + xi,1 ) and
d j · ( x j,0 + x j,1 ) where di and d j are obtained from the prover in case c = 1.
As already noted in the previous lecture, for distributions on two bits the notions of computational and
statistical indistinguishability are essentially equivalent. The lemma generalizes to the joint distribution of
any number of bits, and in this case it is only the weaker computational indistiguishability that is obtained.
For simplicity we restrict ourselves to proving the lemma for the setting of two bits only.
Proof. For the case of a measurement in the computational basis the lemma follows directly from (7.4) in
Claim 7.4 and the definition of the extracted qubits. For the case of a measurement in the Hadamard basis
we proceed in two steps.
In the first step we show that for any b ∈ {0, 1}n the states |ψi and Z (b)|ψi are computationally
indistinguishable. We show this by performing a reduction to an adversary that breaks assumption (F.5). Fix
any i ∈ {1, . . . n} and suppose for contradiction that there exists an efficient observable R such that
1
hψ| R|ψi − hψ| Z (ei ) RZ (ei )|ψi > ,
q(λ)
for some polynomial q and where the left-hand side should be understood on expectation over the creation
of a state |ψi according to the first three steps of protocol Vn . Let i be a position in which bi 6= 0. Our
goal is to reach a contradiction with (F.5). Towards this we construct an adversary A to the collapsing game
that underlies assumption (F.5). Upon input pk, A creates the state |ψi and returns to the challenger only
the m-qubit register Xi . Note that the first part of the challenger’s actions in the game does not change |ψi,
since the prover has already collapsed it to a pair of preimages. The two cases correspond to the challenger
returning either the mixed state ∑b∈{0,1} Zb,i |ψihψ| Zb,i or |ψihψ|, where Zb,i = (Id +(−1)b Z (ei ))/2. The
adversary A measures R and returns the outcome. The advantage of A in distinguishing the two cases is
1
hψ| R|ψi − ∑hψ| Zb,i RZb,i |ψi = hψ| R|ψi − hψ| Z (ei ) RZ (ei )|ψi ,
b
2
where the equality follows by definition of Zb,i . Since by (F.5) this advantage should be negligible, we
deduce that for every i ∈ {1, . . . , n} and every efficient observable R it must be that
Since for any b the observable Z (b) RZ (b) itself is efficient, applying (7.7) n times (with different choices
of R) we deduce that for any b and efficient R,
80
We now extend the preceding reasoning to show that for any a of the form a = ai ei + a j e j with ei , e j the
canonical basis vectors and ai , a j ∈ {0, 1},
1
2n ∑ (−1)a·b hψ|Z(b)X (a)Z(b)|ψi
b
1
4 b ,b ∑
− (−1) ai bi +a j bj hψ| Z (bi ei + b j e j ) X ( a) Z (bi ei + b j e j )|ψi ≤ µ(λ) , (7.8)
i ∈{0,1}
j
for some negligible function ν. Supposing this were not the case, by the triangle inequality and an averaging
argument there must exist a b such that
1
hψ| Z (b) X ( a) Z (b)|ψi − hψ| Z (bi ei + b j e j ) X ( a) Z (bi ei + b j e j )|ψi > ,
q(λ)
for some polynomial q. This leads to a contradiction with (F.5) using the same reasoning as before, because
from the point of view of the statement of (F.5) for qubits not in positions i and j, the observable X ( a) is
efficient, as its computation only requires trapdoors tdi and td j .
To obtain the second part of the claim it remains to handle the Z (ei ) and Z (e j ) operators. For the
positions i and j the associated trapdoor information is used in the computation of X ( a), so the preceding
reasoning cannot be applied. Instead, we proceed similarly to the proof of Lemma 6.6, by reduction to the
adaptive hardcore bit property, assumption (F.2). Note that if ai = 0 or a j = 0 then our task is exactly the
task handled in Lemma 6.6. So assume ai = a j = 1. We perform a reduction to Lemma 6.6 via a simple
hybrid argument. Suppose for the sake of contradiction that
1 1
hψ| X ( a)|ψi − ∑
4 b ,b ∈{0,1}
(−1) ai bi +a j bj hψ| Z (bi ei + b j e j ) X ( a) Z (bi ei + b j e j )|ψi >
q(λ)
.
i j
or
1 1
hψ| Z (bi ei ) X ( a) Z (bi ei )|ψi − ∑
2 b ∈{0,1}
(−1) a j bj hψ| Z (bi ei + e j b j ) X ( a) Z (bi ei + e j b j )|ψi >
q(λ)
.
j
The first case is ruled out directly by Lemma 6.6. The second case is ruled out by the same lemma, simply
considering a prover that creates the state Z (b j )|ψi instead of |ψi at the 3rd step (i.e. the step where |ψi is
defined).
81
1. (Completeness:) For any n-qubit state | ϕi, there is a QPT prover that is accepted with probability 1
in the protocol and such that the value o returned by the verifier at the end of the protocol satisfies
E [ o ] = h ϕ | H | ϕ i.
2. (Soundness:) For any QPT prover that is accepted with probability 1 in the protocol, there is an n-
qubit state ρ such that the value o returned by the verifier at the end of the protocol satisfies Pr(|o −
Tr( Hρ)| > δ) ≤ ε.
Remark 7.8. The protocol in Figure 7.1, as the one in Figure 6.1, involves N repetitions of an elementary
4-message procedure. It is possible to parallelize the protocol to a single repetition in which the prover is
asked to perform measurements on all N qubits of a ground state of HC . This however requires more work,
because in the parallelized protocol the verifier needs to request “mixed” measurements from the prover; see
Remark 7.1.
Remark 7.9. We pause to insist on how amazing Theorem 7.7 is. Due to Kitaev’s circuit-to-Hamiltonian
construction (Section 5.2.1) it is known that, under the widely believed assumption that QMA 6= QCMA
(where QCMA is the class of languages that admit classical proofs verifiable by QPT verifiers), there exist
families of Hamilitonians of the form HC such that any sufficiently low-energy eigenstate of HC cannot have
a simple classical description; in particular, there is no small quantum circuit to prepare such eigenstates,
they must have high entanglement, etc. Yet Theorem 7.7 states that through an efficient classical interaction
with a device that has the ability to prepare such states it is possible to efficiently verify their existence. There
are two ways in which one might aim to strengthen that statement. First, in the spirit of “proofs of knowl-
edge” we might aim to show that the prover has such a state, and not only that it exists. Showing this requires
a formalization of the notion of the prover “having” a certain quantum state, but it can be done without any
modification to the protocol itself; see [VZ20]. Second, in the spirit of our “test for a qubit” we might aim
to show that the prover has n qubits. This we do not know how to show in the computational setting: it is an
open question. (See the full notes at [Link] vidick/teaching/fsmp/[Link] for how to
achieve this broader goal under a different assumption, that of spatial assumption between two provers.)
Remark 7.10. The assumption that the prover succeeds with probability 1 that is made in the soundness
statement is not difficult to relax; see Remark 6.10.
Proof. The completeness statement is entirely analogous to the same statement for Proposition 6.9. In
slightly more detail, at each of the N iterations the honest prover prepares a fresh copy of the state | ϕi and
then applies the procedure described in the proof of Lemma 6.8 independently to each of the n qubits of
| ϕi, using the key pk i for the i-th qubit and obtaining an outcome yi . For each qubit the post-measurement
state is in an m-qubit register Xi that the prover measures in the standard basis in case of challenge c = 0,
and Hadamard basis in case c = 1. It can then be verified by direct calculation that in case c = 0 for any
pair i 6= j the parity (−1)b(xi )+b(x j ) is distributed as a measurement of σZ (ei + e j ) on | ϕi, and similarly
in case c = 1 for any pair i 6= j the parity (−1)di ·(xi,0 + xi,1 )+d j ·(x j,0 + x j,1 ) is distributed as a measurement of
σX (ei + e j ) on | ϕi.
For soundness we use Lemma 7.6. The lemma shows that for any iteration t = 1, . . . , N in the protocol
we can define a state ρt such that averaging over the verifier’s choice of qubits i and j it holds that, whenever
c = 0 then
E Jij (−1)b(xi ) (−1)b(x j ) = Jij Tr σZ,i σZ,j ρt .
E Jij (−1)di ·(xi,0 + xi,1 ) (−1)d j ·(x j,0 + x j,1 ) ≈ Jij Tr σX,i σX,j ρt ,
82
where the approximation is up to some negligible quantity in λ. Averaging these two quantities we see that
on average over all the rounds,
N
1 1 1
E [o ] ≈
N ∑∑ − Jij Tr σZ,i σZ,j ρt − Jij Tr σX,i σX,j ρt
2 2
t =1 i 6 = j
N
1
∑ Tr
= HC ρt
N t =1
= Tr HC ρ ,
where we defined ρ = N1 ∑t ρt . The more quantitative statement given in the soundness part of the theorem
follows directly by using a martingale concentration argument, provided the constant C in the definition of
N is chosen large enough.
83
error distribution χ over Zq .3 Given χ, write χm for the distribution over Zm
q that is obtained by sampling
each entry of a vector independently according to χ. The decisional LWE assumption is the following.
(Decisional LWE, informal) Let A be a uniformly random matrix in Zqm×n , s a uniformly ran-
dom vector in {0, 1}n , e a random vector in Zm m
q drawn from χ , and r a uniformly random
vector in Zq . Then no classical or quantum probabilistic polynomial-time procedure can dis-
m
tinguish ( A, As + e) from ( A, r ).
Note that the distribution of ( A, As + e) and the distribution of ( A, r ) are in general very far from each
other: provided m is sufficiently larger than n a random vector r will not lie in the column span of A, nor
even be close to it. What the (decisional) LWE assumption asserts is that, even though in principle these
distributions are far from each other, it is computationally difficult, given a sample from the one or the other,
to tell which is the case. Note that without the error vector e the task would be easy: given ( A, y), solve for
As = y and check whether the solution has coefficients in {0, 1}. The LWE assumption is that the inclusion
of e makes the task substantially more arduous. In particular, it is well-known that Gaussian elimination is
very sensitive to errors, which rules out the most natural approach.
The definition we gave is informal because we have not specified how the parameters n, m and q should
be chosen as a function of the security parameter λ, and we have not specified the distribution χ. In general
one can make the decisional LWE assumption for any choice of these parameters—but for some choices
the assumption will be invalidated by existing algorithms. We comment on come choices of parameters
that are made in cryptography. The integer n should generally be thought of as commensurate with the
security parameter λ, i.e. n = Θ(λ). The modulus q should be at least polynomial in n, but can be as
large as exponential; this will be the case in our construction. The error distribution χ can be chosen in
multiple ways. A common choice is to set χ a discretized centered Gaussian distribution with variance
αq, for some small parameter α (typically chosen as an inverse polynomial function of n); this is generally
denoted DZq ,αq . For more details on LWE and its applications, we refer to the survey [P+ 16].
7.5.2 Construction
To specify the function family F we first describe how public and private parameters for the function are
chosen. Let λ be the security parameter (i.e. the number 2λ is thought of as an estimate of the time required
to break assumptions such as (F.2)).
First, integers n, m and a modulus q are chosen such that n = Ω(λ), q ≥ 2 is a prime, and m =
Ω(n log q). Then, a matrix A ∈ Zm q
×n is sampled at random, together with a “trapdoor” in the form of a
matrix R ∈ Z`× q
m , where n ≤ ` ≤ m is a parameter. The sampling procedure has the property that the
distribution of A is statistically close to uniform, and R is such that G = RA ∈ Zq`×n is a “nice” matrix, in
the sense that given b = Gs + e, for any s ∈ Znq and e small enough, it is computationally easy to recover
s.4 That such a sampling procedure would exist and be efficiently implementable is non-trivial, and relies
on the underlying lattice structure given by the columns of A; see [MP12]. Finally, a uniformly random
s ∈ {0, 1} , and a random e ∈ Zq distributed according to DZq ,αq with α of order 1/( mn log q),5
n m
p
3 The use of the parameters n, m and q is local to this section. In particular, the m that specifies the domain and range of the
84
are sampled. The public information is pk = ( A, z = As + e). The trapdoor information is the pair
td = ( R, s). Note that pk is not uniformly distributed, but pairs ( pk, td) can be sampled in randomized
polynomial time in λ.
Next we discuss how the function f = f pk can be evaluated, given the public parameters pk = ( A, z).
We define two functions f 0 , f 1 that should be understood as f (0k·) and f (1k·) respectively. Each function
goes from Z2wn to Z2wm for w = dlog qe. For b ∈ {0, 1} the function f b takes as input an x ∈ Znq (that
can be seen as an element of Z2wn through its binary representation) and returns Ax + e0 + bz, which is an
element of Zm q ⊆ Z2 . Here, e is a vector sampled at random from a distribution DZq ,α0 q such that α
wm 0 0
is “much larger” than α. The inclusion of e0 makes f a “randomized” function, which is the main way in
which the construction differs from the requirements expressed in Section 4.3. A formal way around this
is to think of f b as the function that returns not Ax + e0 + bz, but the distribution of Ax + e0 + bz, when
e0 ∼ DZq ,α0 q and all other variables are fixed. In practice, the evaluation of f on a quantum computer (as
required of the honest prover in the verification protocol) involves preparing a weighted superposition over
all error vectors, and computing the function in superposition.
We would, of course, rather do away with this complication. Why is the error vector necessary? It is
there to satisfy the important requirement that the functions f 0 and f 1 are injective with overlapping ranges,
so that f itself is 2-to-1. Injectivity follows from the existence of the trapdoor for A and an appropriate
setting of the standard deviation of the error distribution, which guarantee that (given the trapdoor) x can
be recovered from Ax + e0 + bz (with high probability over the choice of e0 ). To make the function ranges
overlap, we need the distribution of Ax + e0 to be statistically close to the distribution of Ax 0 + e0 + z =
A( x 0 + s) + (e0 + e). The first distribution considers an arbitrary vector in the column span of A, shifted
by e; the second considers the same, except that the shift is by (e0 + e). For the two distributions to (almost)
match, we need the distribution of e0 to (almost) match the distribution of e + e0 . This is possible as long
as the standard deviation σ0 = α0 q is substantially larger than the standard deviation σ = αq; provided this
holds it is an exercise to compute the statistical distance between the two Gaussian and verify that it can be
made very close to 1.
With this important caveat in place, we have specified the function f and verified property (F.1). Prop-
erty (F.3) follows from the existence of the secret information td = ( R, s). Given a b ∈ {0, 1} and an
element y = Ax + e0 + bz = A( x + bs) + (e0 + be) in the range of f b it is possible to use the trapdoor
matrix R to recover x + bs and subtract bs to deduce the preimage x of z under f b . Property (F.4) holds triv-
ially from the construction. Note that the function f has domain and range that are different. In particular,
here the domain is larger than the range, and in case q is not a power of 2 f is only defined on a subset of its
natural domain Z2wn . These points are not very important and can be ignored at the level of our discussion.
Showing the hardcore bit property (F.2) and the collapsing condition (F.5) require more work, and we
refer to [BCM+ 18] for a detailed exposition.6 Similar “hardcore bit” properties to (F.2) have been shown
for many LWE-based cryptographic schemes (see e.g. [AGV09]). Usually the property states that “for
any vector d ∈ Znq \{0}, the value d · s ∈ Zq is indistinguishable from uniform, even given a sample
( A, As + e)”. Our property (F.2) is subtly stronger, in that the adversary may choose the vector d itself,
possibly as a function of the sample ( A, As + e). An additional difficulty stems from the specific equation
that the adversary is asked to return. In the definition of Assumption (F.2) this is a d such that d · ( x0 + x1 ) =
0, where x0 , x1 are the binary representation of the two preimages in Znq of the prover’s first message string
y ∈ Zm q . (The use of the binary representation comes from the requirements on the honest prover, that
is asked to perform a measurement in the Hadamard basis, yielding a binary string of outcomes.) So here
6 The collapsing condition is not shown in [BCM+ 18]. It is implicitly shown in [Mah18], where it can be seen to follow from
property 2 in Definition 4.4 of an extended trapdoor claw-free family. (The connection is made explicit in [GV19].)
85
x0 = (0, r0 ) and x1 = (1, r1 ) such that r0 , r1 are binary representations for two elements x00 , x10 ∈ Znq
such that x10 = x00 − s over Zq . Since the binary representation is not linear the equation obtained is not
directly a linear equation in the secret s. Completing the argument showing that a procedure that returns the
information asked for in Assumption (F.2), i.e. the pair ( x = (b, rb ), d), can be turned into a procedure that
breaks the decisional LWE assumption, requires a little more work; this is where we need to assume that the
secret vector s is a binary vector.
86
Lecture 8
In lecture 5 we considered the class IP [P ] of languages that can be decided by a BPP verifier interacting
with a prover in class P . We showed how to construct verification protocols for all of BQP in this model:
informally, the result of the previous three lectures is that BQP ∈ IP [ BQP ] under the Learning with Errors
assumption.1 What if we do not wish to make computational assumptions? A first motivation for this is that
we might simply not wish to rely on relatively untested assumptions — after all, isn’t it likely that a few
decades of algorithmic research (and even less for quantum algorithms) have barely scratched the surface
of the possible ways of approaching a problem such as LWE or even e.g. factoring? A second motivation is
that we could aim for more: firstly, in terms of complexity — almost by definition the class IP [ BQP ] lies in
BQP (and giving any more power to the prover risks breaking the computational assumption); what if we
are interested in languages outside BQP?2 Secondly, in terms of structural characterizations — in particular,
remember how we stopped short of showing that the prover in the Mahadev protocol “has n qubits”: can we
achieve such a characterization in a different model?
In the next three lectures we switch gears and replace the use of computational assumptions by an as-
sumption of spatial isolation. In this new model the verifier has the ability to interact with two (or more)
provers that are restricted to acting locally on their respective quantum systems. This is the model that we
already encountered in Section ??. As we will see this physical (and, once properly formalized, mathemat-
ical) limitation on prover strategies will allow us to go further along the two motivating directions outlined
in the preceding paragraph.
In this lecture we first introduce the model from a complexity-theoretic standpoint, discuss the recent
characterization MIP ∗ = RE, and examine some consequences. In the following two lectures we introduce
techniques that build towards a proof of the equality MIP ∗ = RE by developing efficient tests for increasing
numbers of qubits and increasingly complex computations.
87
languages.
Definition 8.1. The class MIP ∗ is the class of promise languages L = ( Lyes , Lno ) such that there is a
classical polynomial-time Turing machine M that on input 1n returns the description of classical circuits for
the verifier Vn in an interactive protocol with two quantum provers A and B such that:
• (Completeness:) There is a family of quantum provers { An , Bn }n∈N such that for all x ∈ Lyes the
interaction of V| x| and A| x| , B| x| on common input x accepts with probability at least 32 .
• (Soundness:) For any family of quantum provers { An , Bn }n∈N , for all x ∈ Lno the interaction of V| x|
and A| x| , B| x| on common input x accepts with probability at most 31 .
Some comments on the definition are in order. Following tradition we called the provers A and B rather
than P1 and P2 ; A stands for “Alice” and B for “Bob”, a personification that is inspired from cryptogra-
phy.4 In general one may allow interaction with more than two provers; however the two-prover setting is
sufficiently interesting for our purposes. (Furthermore, it can be shown that in purely complexity-theoretic
terms there is no gain to considering more than 2 provers.) The number of rounds of interaction is left
implicit in the definition; since Vn is polynomial-size there can be at most polynomially many rounds of
interaction. Soon we will restrict ourselves to single-round protocols, which consist of a message from the
verifier to each prover followed by an answer from each prover; again both for our purposes and in terms of
complexity-theoretic expressive power this is without loss of generality.
Note that we did not (and will not) restrict the computational power of the provers — in fact, we did not
even precisely specify what collection of strategies they may employ. For the time being we stay with the
informal prescription that the provers may employ any quantum strategy that can be implemented locally, in
finite dimension, and without communication — typically, local operations augmented with measurements
on a shared entangled state that may have been agreed on prior to the protocol execution. We will see later
how to formalize this more precisely.
The goal in complexity theory is to relate different classes of languages . This is especially interest-
ing when the classes are defined in very different terms, as relations between them can provide insights
into different models of computation. A pertinent example is the famous equality IP = PSPACE due
to [LFKN92, Sha92]. Among the two classes, PSPACE is the simplest to define: this is the class of all
languages that can be decided using a polynomial amount of space, and arbitrary time. A complete prob-
lem for PSPACE is the quantified Boolean formula (QBF) problem, which is to decide if a formula of the
form ∃ x1 ∀ x2 ∃ x3 · · · ( x1 ∧ x2 ∧ ¬ x3 ) ∨ (· · · ) is satisfiable. Clearly this can be done in polynomial space
by trying out all possibilities; it is also possible to show that any problem that is solvable in PSPACE can
be reduced to this one, and so we say that QBF is complete for PSPACE. The class IP is defined very
differently: it is the class of languages L such that membership x ∈ Lyes can be decided efficiently by
a randomized polynomial-time verifier interacting with a single infinitely powerful prover (so this is the
single-prover analogue of MIP ∗ ). While it is not too hard to show that IP ⊆ PSPACE, the converse inclu-
sion is not easy at all — to see why, try coming up with a verification protocol for the QBF problem, and
keep in mind that the prover is not to be trusted!
Our goal is to characterize the complexity of MIP ∗ in terms of other complexity classes, with the hope
of gaining insights about computation, entanglement, and verification of quantum devices. Before we do
this let’s first review what is known about the classical analogue of MIP ∗ , in which the provers are restricted
4 Indeed the model of multi-prover interactive proof systems is first introduced by a team of cryptographers [BOGKW19] moti-
vated by the development of zero-knowledge proof systems.
88
to classical strategies. This restriction affects both the completeness and soundness requirements in Def-
inition 8.1, and so generally any stipulation of the set of allowed strategies for the provers will lead to a
different complexity class.
2. The verifier selects a pair of vertices (i, j) uniformly at random in {0, 1}n × {0, 1}n . She sends i to
Alice and j to Bob.
4. The verifier accepts if and only if any of the following conditions hold: C (i, j) = 0 (there is no edge);
i = j and a = b (same color for identical vertices); C (i, j) = 1 and a 6= b (different colors for
5 As usual, we consider that circuits are represented in some given, fixed manner, e.g. as a list of gates and bits that they act on.
89
neighboring vertices).6
It is clear that this protocol has completeness 1: whenever Gx is 3-colorable there is a winning strategy for
the provers. Moreover, a moment’s thought will reveal that if Gx is not 3-colorable then there is no perfect
winning strategy; hence the maximum probability of success in this case is at most 1 − 2−Ω(n) (because
any strategy must fail on at least one question). While this is a separation between the two cases, it is not
sufficient to establish soundness, which requires that the maximum probability of success for an x ∈ Lno be
at most 13 .
What the proof of the inclusion NEXP ⊆ MIP shows is that there is in fact a much better verifier,
somewhat more involved than the one that we described here, which is such that whenever the graph is
not 3-colorable then the maximum success probability is at most 31 . Achieving such a protocol essentially
entails finding an efficient method that, informally, maps any graph to another graph of polynomially related
size such that graphs that are 3-colorable are mapped to graphs that remain 3-colorable, but graphs that are
not 3-colorable are mapped to graphs that are very far from 3-colorable. Achieving this can be done using
advanced tools from the theory of error-correcting codes; we will not be able to say more in this lecture and
refer the interested reader to e.g. [AB09].7
other case is an automatic “free ride” for the provers; we gloss over this point here.
7 Technically such a reduction is not obviously necessary, because the definition of MIP allows more complicated protocols
than the 3-coloring game described here. Nevertheless, using appropriate manipulations it is possible to show that any proof of
NEXP ⊆ MIP does imply such a reduction.
90
use of the fact that they can do even better with entanglement, and indeed this fact is a new nuisance that
we have to deal with in order to establish the soundness property. But what if we start from a more complex
problem, that does not necessarily lie in NEXP, and attempt to design a protocol such that completeness
requires the use of entanglement?
To see how far one might hope to go in this direction we ought to think about upper bounds on MIP ∗ .
Recall from the previous section that for MIP we simply enumerated over all possible strategies. In the
quantum setting it is not so direct: since we do not place a priori bounds on the complexity of the provers, it
is unclear what dimension one should choose in order to find an optimal strategy. If one was able to show an
upper bound on the dimension that is sufficient to approach the optimal success probability (as a function of
the size of the protocol) then one would automatically get a corresponding upper bound on the complexity
of MIP ∗ . However, no such bound is known! The only upper bound on MIP ∗ is the following folklore
result:
Proof. Recall that a language L = ( Lyes , Lno ) is recursively enumerable if there exists a Turing machine
such that on input x, if x ∈ Lyes then the Turing machine eventually halts and accepts, whereas if x ∈ Lno
then the Turing machine may either halt and reject, or it may never halt.
Consider the Turing machine M that on input x specifying a verifier V| x| searches in increasing di-
mension and with increasing accuracy for a good strategy in the associated protocol. Since we have not
introduced a precise formalism for strategies in MIP ∗ protocols — we will do so for two-prover one-round
protocols in Section 8.2.1 — we cannot make this too precise. At present it is sufficient to think intuitively
that each prover is specified by a dimension of the Hilbert space on which they act, and for each possible
question they may receive, in any round, a POVM on their space that is used to determine an answer; these
POVM act on an initial quantum state that lies in the tensor product of the prover’s Hilbert spaces. (Any
unitary actions the provers may take can be incorporated in the POVMs.) For any given dimension d and
accuracy ε the space of strategies in dimension at most d can be discretized to a finite set such that the
optimum success probability over elements of that set will be within an additive ε of the optimum over all
strategies in dimension at most d.
If x ∈ Lyes by definition there must exist a finite dimension d and a strategy in dimension d that succeeds
with probability at least (say) 32 − 100
1
; eventually, taking into account discretization errors M will identify
a strategy that succeeds with probability at least 32 − 100 2
and halt with acceptance, having successfully
ruled out the case that x ∈ Lno . However, in case x ∈ Lno the Turing machine will never find a strategy
with success larger than 31 + 1001 1
(where the 100 accounts for possible discretization errors and can be made
arbitrarily small), but it will not be able to rule out the existence of such a strategy either; indeed, for all it
knows such a strategy may exist in “just one more dimension”.
For a long time it was unclear where the complexity of MIP ∗ lies, between the two “trivial” extremes
of IP and RE. In 2012 Ito and the author showed that NEXP ⊆ MIP ∗ by adapting the proof of NEXP ⊆
MIP by Babai et al. In the past few years better lower bounds were obtained. Quite astonishingly, in
2018 Natarajan and Wright [NW19] showed that NEEXP ⊆ MIP ∗ . One reason that this is “astonishing”
is because NEEXP is a strictly (unconditionally) larger class that NEXP, and so their result established
unconditionally that the presence of entanglement increases the verifier’s ability to verify languages, even
though the latter’s complexity has not changed at all (it remains classical polynomial-time)! Building on
this result in 2020 Ji et al. [JNV+ 20a] obtained the following characterization.
91
A complete problem for the class RE is the halting problem: given the description of a Turing machine
M as input, does M eventually halt? What Theorem 8.3 shows is that this problem, even though it is not
decidable, can be efficiently verified by asking questions to two provers sharing entanglement. In purely
complexity-theoretic terms this is an extremely surprising result in and for itself; note that RE contains any
bounded time or space complexity class — and much more. The following two lectures will be devoted to
a sketch of the main arguments that go in the proof of the theorem; these arguments involve the design of
tests for multiple qubits as well as delegation protocols and so we will be on familiar terrain. Aside from the
complexity theory it turns out that the characterization MIP ∗ = RE has some interesting consequences in
the foundations of quantum mechanics as well as in the theory of operator algebras which we discuss next.
8.2 Consequences
Theorem 8.3 is related to a problem in the foundations of quantum non-locality called Tsirelson’s problem,
itself connected to a problem in the theory of von Neumann’s algebra usually referred to as Connes’ Embed-
ding Problem (CEP). Even though they have no bearing on the remainder of the course, for motivation in
this section we explain those connections. We start by (re-)introducing the language of nonlocal games that
we already encountered in lecture ?? and which we will generally use to talk about multiprover interactive
proof systems.
Informally this quantity is the average, over the referee’s choice of questions and the player’s probabilistic
strategy, that the players provide valid answers to the referee. If one fixes a collection of possible strategies
92
S then one can define an associated value ω ( G; S) for the game, which is the supremum success probability
achievable using strategies S ∈ S :
ω ( G; S) = sup ω ( G; S) .
S∈S
For example, if S is the set of classical local strategies, i.e. all those families of distributions that take the
form (3.3), then ω ( G; S) is called the classical value of the game and is usually denoted ω ( G ). If S is
the set of (tensor) quantum strategies, i.e. all those families of distributions that take the form (3.5), then
ω ( G; S) is called the entangled value of the game and is usually denoted ω ∗ ( G ). Explicitly,
where the supremum is taken over all quantum states |ψi ∈ HA ⊗ HB for finite-dimensional HA and HB
y
and collections of POVMs { A ax } and { Bb } on HA and HB respectively, one POVM for each question x or
y to Alice or Bob respectively. Using the language of games the question of characterizing the complexity
of the class MIP ∗ (2, 1) boils down to determining the complexity of approximating the optimum of the
optimization problem (8.1). This is because for a language L ∈ MIP ∗ (2, 1) the problem of determining if
some input x ∈ Lyes reduces to evaluating the value ω ∗ ( Gx ), where Gx is the game associated with x and
the verifier in a protocol for L, with good enough approximation to differentiate between the cases where
x ∈ Lyes (ω ∗ ( Gx ) ≥ 32 ) and x ∈ Lno (ω ∗ ( Gx ) ≤ 31 ).8
v1 ≤ v2 ≤ · · · ≤ v k ≤ · · · ≤ ω ∗ ( G )
by enumerating strategies in increasing dimension and with increasing level of accuracy. Using the def-
inition (8.1) of the entangled value it is clear that vk →k→∞ ω ∗ ( G ). To make algorithm A into an ac-
tual approximation algorithm we need to have a sense of when to stop, e.g. when can we guarantee that
|vk − ω ∗ ( G )| ≤ 100
1 9
? A natural approach is to construct a companion algorithm B that constructs a
decreasing sequence of upper bounds
w1 ≥ w2 ≥ · · · ≥ w k ≥ · · · ≥ ω ∗ ( G ) .
Given algorithms A and B consider a third algorithm C that given a game G as input runs both algorithms in
1
an interleaved fashion, computing v1 , w1 , v2 , w2 , etc., halts whenever |vk − wk | ≤ 100 and returns “YES”
if and only if 2 (vk + wk ) > 2 . Now suppose that both (vk ) and (wk ) converge to ω ∗ ( G ). Then C
1 1
8 The correspondence is not entirely exact because complexity is measured as a function of the input size; for MIP ∗ protocols
the input is directly x, whereas for games G we think of the input as an explicit description of the underlying distribution π and
predicate R. In particular it is possible that the description length of Gx is exponential in the description length of V| x| , since the
latter only specifies π and V implicitly through a circuit that computes them.
9 The bound 1 is arbitrary; we want it to be small enough to guarantee that the algorithm can eventually distinguish ω ∗ ( G ) ≥ 2
100 3
from ω ∗ ( G ) ≤ 13 , so any bound < 16 would do.
93
always terminates. Moreover, if ω ∗ ( G ) ≥ 23 then wk ≥ 23 for all k and so the value returned is at least
1 2 1 2 2 1 1 ∗ 1 1 1 1 1 1 1 1
2 (( 3 − 100 ) + 3 ) = 3 − 50 > 2 , whereas if ω ( G ) ≤ 3 it is at most 2 ( 3 + ( 3 + 100 )) = 3 + 50 < 2 .
Thus C correctly distinguishes between the two cases.
So how do we determine such a sequence of upper bounds (wk )? A general approach to finding an
upper bound on the optimum of some optimization problem is to consider relaxations of the problem, i.e.
optimization problems whose optimum is easier to find and is guaranteed to be at least as large as the original
optimum. For example, consider the following relaxation
y
where the supremum on the second line is over all families of vectors |u ax i, |vb i ∈ HA ⊗ HB such that for
y
every x, the {|u ax i} a are orthogonal and ∑ a k|u ax ik2 = 1; similarly for the |vb i. The inequality (8.2) is
y y
verified by setting |u ax i = A ax ⊗ Id |ψi and |vb i = Id ⊗ Bb |ψi. So (8.2) is a relaxation of (8.1). What did
we gain in the process? Crucially, since the objective function in (8.2) only depends on the inner products
between the vectors, without loss of generality we can restrict the vectors to lie in a Hilbert space H such
that dim(H) ≤ min(|X ||A|, |Y ||B|); this is true even if the original HA and HB were much larger. This
means that by exhaustive search we can find arbitrarily good approximations to the optimum (8.2), without
having to go beyond a certain fixed dimension that is determined by the size of the game. In fact, (8.2)
is an optimization problem that falls in the class of semidefinite programs (informally, linear optimization
problems over affine sections of the positive semidefinite cone) and can be solved in time polynomial in its
size (as opposed to exponential for exhaustive search).
So the optimum (8.2) can be determined efficiently. How useful is it, i.e. how good is the inequality
(8.1) ≤ (8.2)? Unfortunately, in general there can be an arbitrarily large (multiplicative) gap between the
two [JP11], and in particular it can be that ω ∗ ( G ) ≤ 13 but (8.2)≥ 23 .10 The relaxation we have devised
is thus too coarse for us to obtain a good algorithm right away. But maybe we can do better? What we
y
did so far consists in adding a vector variable to represent A ax ⊗ Id |ψi and Id ⊗ Bb |ψi. Each of these can
y
be thought of as a degree-1 monomial in the matrix variables { A ax , Bb }, evaluated on |ψi. Considering
vectors obtained from higher-degree monomials would allow us to impose more constraints, as for example
we could require that
y y
hψ| A ax ⊗ Id · A ax ⊗ Bb |ψi = hψ| Id ⊗ Id · A ax ⊗ Bb |ψi ,
due to { A ax } a being projective. It is not hard to think of other such constraints. For any integer k ≥ 1 let’s
define
wk = sup ∑ π ( x, y) ∑ R( a, b| x, y)Γ xa,yb ,
(k)
(8.3)
Γ(k) ≥0 x,y a,b
where the supremum is taken over all positive semidefinite matrices Γ(k) of dimension (|X ||A|+|Y k
||B|
)×
|X ||A|+|Y ||B|
( k ). Here we think of the entries of Γ as being labeled by sequences (z1 , c1 ), . . . , (zk , ck )
( k )
where zi ∈ X ∪ Y and ci ∈ A ∪ B , and Γ(k) is the Gram matrix of the associated vectors
94
where Ccz = Azc ⊗ Id if z ∈ X and c ∈ A, Ccz = Id ⊗ Bcz if z ∈ Y and c ∈ B , and Ccz = 0 otherwise. In
y
addition, we add any linear constraint on the entries of Γ that follows from the facts that { A ax } and { Bb } are
projective measurements for all x, y, and that they act on different tensor factors and hence commute.
With this definition we can verify that w1 = (8.2); this follows since any positive semidefinite matrix Γ
has a factorization as a matrix of inner produces. Moreover, w1 ≥ w2 ≥ · · · ≥ wk ≥ ω ∗ ( G ) since each
successive level in the “hierarchy” consists in adding additional variables and constraints. Finally, using
standard algorithms for semidefinite programs the optimization problem at the k-th level can be solved in
time polynomial in its size, i.e. time (|X ||A| + |Y ||B|)O(k) . Let’s call Algorithm B the algorithm that on
input k returns wk .11
where the supremum is taken over all states |ψi ∈ H where H is a (possibly infinite-dimensional) separable
y
Hilbert space and families of projective measurements { A ax } and { Bb } on H such that for all x, y, a, b, A ax
y
and Bb commute. Since A ⊗ Id and Id ⊗ B always commute it always holds that ω ∗ ( G ) ≤ ω com ( G ). The
hierarchy of values (wk ) is introduced in [NPA08], where they show the following convergence result.
Proof. First note that by definition ω com ( G ) ≤ limk→∞ wk , since none of the constraints imposed on the
y
definition (8.3) of wk makes use of the tensor product structure other than to say that A ax ⊗ Id and Id ⊗ Bb
commute.
The remainder of the proof shows the reverse inequality. For any k ≥ 1 fix a feasible solution Γ(k) to the
optimization problem (8.3). The entries of Γ(k) are indexed by pairs of monomials m in non-commutative
y
variables { A ax , Bb } of degree at most k. Crucially, the constraints on the optimization problem require
(k) (k)
that (i) Γ(k) ≥ 0, and (ii) this matrix satisfies Γm1 ,m2 = Γn1 ,n2 whenever both entries are well-defined and
y
m1 m2∗ = n1 n2∗ as monomials in { A ax , Bb }, because by definition any such constraint is imposed on the
optimization problem.
(k)
For any monomial m and integer k at least as large as the degree of m let τk (m) = Γm,1 . Extend τk to
a linear form on all non-commutative polynomials by setting τk (m) = 0 if m has degree larger than k and
extending by linearity. Since |τk | ≤ 1 for each k (this can be verified because the diagonal entries of Γ(k)
are all constrained to equal 1, so using (i) all entries of Γ(k) must have modulus at most 1) by the Banach-
Aleoglu theorem the sequence (τk )k≥1 admits a pointwise convergent subsequence (τki )k1 ≤k2 ≤··· ; let τ be
the pointwise limit. Now crucially we observe that τ is a positive linear form. Indeed, for any polynomial
11 Technically we need to allow B to return an approximation to wk . Since well-behaved semidefinite programs such as (8.3)
can be solved in time polynomial in their size and in the logarithm of the desired accuracy we could e.g. require that B returns an
additive approximation of wk that is within error at most 2−k ; this will suffice for our purposes.
95
p = ∑m αm m where m ranges over monomials we have
τ ( p∗ p) = lim τki ( p∗ p)
i
= lim
i
∑0 α∗m αm0 τk (m∗ m0 )
i
m,m
= lim α† Γ(ki ) α
i
≥0,
where for the first line we used linearity of τki , for the second line we used the definition of τki (the equality
holds for all i such that k i ≥ deg( p)), for the third line we let α = (αm ) and used property (ii), and for the
last we used property (i).
At this point we may conclude in a single abstract step by invoking the GNS construction from C ∗ -
algebra theory: for any positive linear functional τ on a C ∗ -algebra A there is a ∗-representation π of A on
a Hilbert space H and a unit vector |ξ i ∈ H such that
∀a ∈ A , τ ( a) = hξ |π ( a)|ξ i . (8.5)
y
For us A is the algebra of non-commutative polynomials in { A ax , Bb } with complex coefficients satisfying
y y
the POVM and commutation conditions, and so the image à ax = π ( A ax ), B̃b = π ( Bb ), together with the
state |ξ i, immediately gives us a commuting strategy for G with value limk wk :
= ∑ π ( x, y) ∑ R( a, b| x, y)hξ | Ã ax B̃b |ξ i ,
y
x,y a,b
where the first line is by definition of wki , the second line by the linear constraints (ii), the third by definition
of τki , the fourth by definition of τ, the fitfth by (8.5), the sixth because π is a representation and the last by
y
definition of à ax and B̃b .
It is also possible to finish the construction more concretely by defining an infinite-dimensional matrix
Γ = limi Γ(ki ) , where for the limit to make sense we embed each Γ(ki ) as the top left corner of an infinite-
dimensional matrix by padding with zeroes. Since all finite minors of Γ are positive semidefinite, it is
positive semidefinite and therefore admits a factorization Γm,m0 = hm|m0 i for some {|mi} in a Hilbert
space H. We can then define à ax as the projection on the span of all |mi such that m = A ax m0 for some m0 ,
i.e. the first variable of monomial m is A ax . Using the relations satisfied by the inner products between the
vectors |mi (i.e. condition (ii) above) it is possible to verify that the à ax together with analogously defined
96
y
B̃b and |ψi = |1i satisfy the required conditions for a commuting strategy, and that the associated value is
once again limk wk .
The two values ω ∗ ( G ) and ω com ( G ) were introduced by Tsirelson in a series of papers laying the
foundations for the mathematical study of non-locality [Tsi93]. Rather than using the language of games
(which at the time was not much in use yet), Tsirelson directly studied the underlying correlation sets
defined as
y
C ∗ (n, k ) = hψ, A ax ⊗ Bb ψi a,b,x,y : HA , HB Hilbert spaces, ψ ∈ HA ⊗ HB , kψk = 1,
y
∀( x, y) ∈ {1, . . . , n}2 , { A ax } a∈{1,...,k} , { Bb }b∈{1,...,k} POVM on HA , HB resp. , (8.6)
y
C com (n, k ) = hψ, A ax Bb ψi
a,b,x,y
: H Hilbert space, ψ ∈ H, kψk = 1,
y
∀( x, y) ∈ {1, . . . , n}2 , { A ax } a∈{1,...,k} , { Bb }b∈{1,...,k} PVOM on H
y
s.t. [ A ax , Bb ] = 0 ∀( a, b) ∈ {1, . . . , k }2 .12 (8.7)
By taking direct sums of POVMs and scaled vectors it is not hard to see that both sets are convex subsets
2 2
of [0, 1]n k . Note that in the definition of C ∗ (n, k ) we did not restrict the dimension of HA and HB to be
finite. This is to match Tsirelson’s presentation; for our purposes the distinction is not important as it is not
hard to see that allowing infinite-dimensional strategies in the definition of the entangled value ω ∗ ( G ) does
not change the supremum.1314 However, in case the Hilbert spaces in both definitions are taken to be finite-
dimensional then the two sets can be shown to coincide. (This fact essentially follows from von Neumann’s
Double Commutant Theorem, though it can also be shown directly; we skip the proof.) In his paper Tsirelson
states as “fact” the claim that C ∗ (n, k ) = C com (n, k ) for arbitrary separable Hilbert spaces and all n, k ≥ 1.
Having realized that a proof of the claim seemed elusive (with the inclusion C ∗ (n, k ) ⊆ C com (n, k ) that we
already observed being the only obvious one), in a subsequent note15 Tsirelson reformulates the “fact” as
an open problem and, realizing that the answer may be negative, formulates as an “even more important”
problem the question of whether the closure C ∗ (n, k ) = C com (n, k ). (Here the overline designates closure
2 2
in the usual topology for Rn k . It is not hard to verify that C com is closed.) Two and a half decades after its
introduction Tsirelson’s first problem was solved by Slofstra [Slo19], who used techniques from the theory
of nonlocal games to show the existence of finite n, k such that C ∗ (n, k ) 6= C com (n, k). Until the proof of
Theorem 8.3, an apparently purely complexity-theoretic result, Tsirelson’s “even more important problem”
remained open. However, we can now observe the following corollary to Theorem 8.3.
Corollary 8.6. There exists finite n, k ≥ 1 such that C ∗ (n, k ) ( C com (n, k ).
Proof. Suppose for contradiction that C ∗ (n, k) = C com (n, k ) for all n, k ≥ 1. As an immediate conse-
quence, for any game G it holds that ω ∗ ( G ) = ω com ( G ). Therefore, algorithm C described in Section 8.2.2
always converges in finite time to a correct answer. This contradicts Theorem 8.3, which implies that the
problem “Given a game G, is ω ∗ ( G ) ≥ 32 or ω ∗ ( G ) ≤ 31 ?” is undecidable.
13 To show this, observe that any state |ψi ∈ HA ⊗ HB , even in infinite dimensions, always has a Schmidt decomposition |ψi =
∑i λi |ui i|ui i such that ∑i λ2i = 1. |ψi can be arbitrarily well approximated in finite dimension by truncating the coefficients;
using that the restriction of a POVM to a subspace is a POVM we find arbitrarily good approximations to the game value in finite
dimension.
14 It does change the definition of the set however: as shown in [CS18] some elements of C ∗ ( n, k ) cannot be represented in finite
dimensions.
15 “Bell inequalities and operator algebras”, available at [Link]
[Link].
97
Note how indirect the proof of Lemma 8.6 is! In particular, while it asserts the existence of n, k there is
no obvious way to determine what these integers are, or even upper bounds on them, from the proof. In fact
it is possible to tweak the argument to get an explicit construction; we refer to [JNV+ 20a] for more.
where the supremum ranges over all pairs of representations π A : C ∗ (F2 ) → B(HA ) and π B : C ∗ (F2 ) →
B(HB ), whereas
k x kmax = sup kπ ( x )k
π
where here π : C ∗ (F2 ) ⊗ C ∗ (F2 ) → B(H) is any representation that is such that π ( a ⊗ b) = π A ( a)π B (b)
where π A , π B : C ∗ (F2 ) → B(H) are representations with commuting range. Clearly, k x kmin ≤ k x kmax
always, and these two norms can be seen to be the smallest and largest “reasonable” norms that one may put
on the tensor product of two C ∗ -algebras.
With this reformulation it may not be surprising that Kirchberg’s QWEP is directly related to Tsirelson’s
problem, and indeed building on work of Fritz [Fri12] and Junge et al. [JNP+ 11] Ozawa [Oza13a] showed
that Tsirelson’s “even more important” problem is equivalent to CEP. This brings us to a second corollary
of Theorem 8.3.
15 The brief discussion in this section is adapted from [Vid19].
16 Concretely, a C ∗ algebra can always be represented as a sub-algebra of the algebra of bounded linear operators on a Hilbert
space that is closed under taking adjoints, and closed under the norm topology. A von Neumann algebra is further restricted to be
closed under the weak operator topology.
98
Corollary 8.7. CEP has a negative answer, i.e. there exists a von Neumann algebra that is not hyperfinite.
For more background on the relation between Tsirelson’s problem and Kirchberg’s conjecture, presented
in an accessible way, I recommend [Fri12]. For additional results and the connection to CEP, presented in a
less accessible way, I recommend [Oza13b].
99
100
Lecture 9
then ω ∗ (Vn (z)) ≥ 32 , and if no such a exists then ω ∗ (Vn (z)) ≤ 31 . Now suppose that we’re able to achieve
a somewhat stronger reduction, where for the starting point we replace the condition (9.1) by
2
On average over x ∼ U N , Pr ∃ a : M accepts (z, x, a) in time ≤ exp(n) ≥ , (9.2)
x 3
where N = 2n and for every n, U N is the uniform distribution on {0, 1} N . (Suppose also that a symmetric
condition holds for soundness.) This would be a form of delegation for (exponential-time) AM (“Arthur-
Merlin”) protocols, where an AM protocol is one in which the verifier can send a uniformly random string
as question to the prover before receiving the proof. Note that the step we just made is highly non-trivial
because of the introduction of a distribution on x; delegating randomized computations like this is hard
because there is no easy means to verify that the computation is being performed with the “right choice” of
the random string x—indeed, we need to make sure to detect cases where it might be that there exists ( x, a)
1 This inclusion is shown in [IV12] for 5 provers. The 2-prover version follows from the work in [JNV+ 20b].
2 This formulation is a bit unusual due to the use of the letter n to represent the input, which is usually called x; this is for later
convenience. Here n is written in binary. Note that the time bound implies that without loss of generality |y| ≤ exp(n).
3 An example would be to take M the Turing machine that parses n as an implicitly represented graph n = (1n0 , C ) and expects
0
y to be an explicit coloring for the 2n vertices of the graph; see Section 8.1.1.
101
such that M accepts (n, x, a), but it is still very unlikely to be the case when x is chosen at random. As we
will see later the use of quantum provers and entanglement will be useful to achieve this.
Let’s do one last leap of faith and suppose that we have an even stronger reduction, that applies directly
to exponential-size multiprover interactive proofs. Precisely, we’d replace the condition (9.2) by
2
On avg over ( x, y) ∼ U N × U N , Pr ∃( a, b) : M accepts (z, x, y, a, b) in time ≤ exp(n) ≥ ,
( x,y) 3
(9.3)
where in addition we’d require that ( a, b) are generated locally by quantum provers sharing entanglement,
such that the provers are given x and y respectively; formally, given ( x, y) the pair ( a, b) should be dis-
y y
tributed as hψ| A ax ⊗ Bb |ψi for some state |ψi (independent of ( x, y)) and POVM { A ax } and { Bb }. Once
again we’d also require a symmetric condition with probabilities ≤ 13 for soundness.
Let’s call the resulting reduction a “compression” procedure: it takes as input an exponential-time veri-
fier V and returns a polynomial-time verifier V C OMPR that has the same completeness and soundness prop-
erties: if there is a good strategy for Vn there is also one for VC OMPR n and vice-versa. Then I claim that by
iterating this compression procedure we could obtain progressively stronger inclusions, from EXP ⊆ MIP ∗
to EEXP ⊆ MIP ∗ to .... any time complexity that is a finite tower of exponentials.4 Recall that for well-
chosen M, the problem of given an integer n, does M halt in at most 2n steps is EXP-complete. Now
suppose that e.g. we have a family of verifiers {Vn }, implicitly depending on M, such that ω ∗ (Vn ) ≥ 23 if
M halts in ≤ 2n steps, and ω ∗ (Vn ) ≤ 13 otherwise; such a family follows from EXP ⊆ MIP ∗ (2, 1). Now
define {VnC OMPR } = C OMPR ({V2n }). Then by definition ω ∗ (VnC OMPR ) ≥ 32 if ω ∗ (V2n ) ≥ 23 if M halts in
n
≤ 22 steps, and similarly ω ∗ (VnC OMPR ) ≤ 13 otherwise. Thus EEXP ⊆ MIP ∗ . Iterating this procedure
and stretching things a little bit, this would give us the inclusion TIME( T (n)) ⊆ MIP ∗ for any computable
function T. And then taking the “limit”, we’d get RE ⊆ MIP ∗ ...?
Obviously there’s a lot of moving pieces in this description. The goal in this lecture is to make them
sufficiently precise as to be believable, and eventually arrive at a core “nugget” that encapsulates the key step
that needs to be proven—which we’ll do in the next lecture. For now we focus on, first, setting things up so
that the above sketch can be made more precise, and second, discussing in more detail the “compression”
procedure, which is the key part where the use of quantum provers is essential.
102
M and x simulates the execution of M on input x.
Lemma 9.2. The language L HALT is undecidable.
Proof. Suppose for contradiction that there exists a Turing Machine A such that given as input M, A halts
with “YES” in case M halts on the empty tape, and A halts with “NO” otherwise. Now consider the
following Turing Machine B. When run on an empty tape, B first executes A on B. If A halts with “YES”
then B enters an infinite loop. If A halts with “NO” then B halts with “YES”. Does B halt? We have reached
a contradiction, therefore A does not exist.
Note that in the proof of Lemma 9.2 we designed a Turing Machine B that at some point performs an
instruction that depends on its own “source code” B. That this is allowed is a consequence of Kleene’s
recursion theorem, which is basically a generalization of the standard diagonalization argument. We will
use this possibility again later.
9.1.3 Compression
We make more precise what we need of the magical “compression procedure” discussed in Section 9.1.1.
First we introduce a restricted class of verifiers.
Definition 9.3. A normal form verifier is a Turing Machine V that on input n returns the description of a
Turing Machine Rn (the “referee,” or “decision procedure”) that on input ( x, y, a, b) ∈ {0, 1}4n returns a
value d ∈ {0, 1}. To Rn we associate a two-player one-round game Gn whose question and answer sets are
X = Y = A = B = {0, 1}n and such that the question distribution π is uniform on {0, 1}n × {0, 1}n and
the referee predicate is given by Rn .
We let TIMEV (n) be the worst-case running time of Rn over all inputs ( x, y, a, b). If TIMEV (n) ≤
(λn)λ for some integer λ ≥ 1 and all n ≥ 1 then we say that V is λ-bounded.
Note that in the definition we fixed the question distribution used for the game Gn to the uniform dis-
tribution. At this stage this is mostly for convenience. Later we will realize that this is too restrictive, and
so one should bear in mind that the definition can be generalized to allow various classes of distributions,
where the key point is that the distribution should be fixed and independent of V.
We need one last definition.
Definition 9.4. For a two-player one-round game G and a probability p ∈ [0, 1] let E ( G, p) denote the
y
smallest integer d ≥ 1 such that there exists a strategy (|ψi, { A ax }, { Bb }) for the players in G that has
success probability at least p and such that |ψi ∈ Cd ⊗ Cd . If no such strategy exists, then E ( G, p) = ∞.
For example, for the Magic Square game (Section 3.3.1) it is possible to show that E ( G, 1) = 4 (two
qubits per player), and in fact there is a c < 1 such that E ( G, p) = 4 for all p ∈ [c, 1]. For a game that has
a perfect classical strategy we have E ( G, p) = 1 for all p ∈ [0, 1].
Let’s make the following specification for a compression procedure.
Claim 9.5. There is a polynomial-time computable mapping C OMPR that takes as input a Turing machine
description V and an integer λ written in unary and returns a Turing machine description V C OMPR =
C OMPR (V, λ) such that the following conditions hold:
(a) V C OMPR is always a normal form verifier such that TIMEV COMPR (n) ≤ p C OMPR (λ + n), for some
universal polynomial p C OMPR independent of V.
(b) If V is a normal form λ-bounded verifier then for every n ≥ 1 letting N = 2n the following hold:
103
(b.i) If ω ∗ ( R N ) = 1 then ω ∗ ( RnC OMPR ) = 1.
([Link]) E ( GnC OMPR , 12 ) ≥ max E ( GN , 12 ), N .
The key point about Claim 9.5 is that the running time of RnC OMPR can be much smaller than that of R N ,
yet it preserves essential properties of it, stated in (b.i) and ([Link]).
We make a few comments on the requirements stated in the claim. First of all, even though eventually
we only need to create a computable mapping F from Turing Machines to games, it will be important that
here C OMPR is required to run in polynomial time. Second, it will also be essential that for any input
(V, λ) to C OMPR the output V C OMPR is the description of a time-bounded verifier. Note that this is not
hard to enforce in practice by hard-coding some kind of time-out mechanism in the definition of V C OMPR .
Finally, observe that condition ([Link]) states something a little stronger (strictly speaking, incomparable) than
the “soundness preservation” condition we considered in Section 9.1.1. Indeed the fact that we are able to
make a statement about entanglement will play an important role in the final argument. (On the other hand,
that the conditions apply to N = 2n as opposed to e.g. N = n + 1 is not important; since it is what comes
out of the proof we keep it here—what matters is that VnC OMPR reproduces properties of VN for some N > n
while having complexity comparable to Vn , not VN .) Finally, note that due to condition (b) running C OMPR
on a trivial input that always accepts already yields an interesting family of games: due to (b.i) we will have
ω ∗ (VnC OMPR ) = 1 for all n, and due to ([Link]) achieving any value larger than 21 will necessarily require a
quantum state of local dimension at least N = 2n .
These observations show that designing a procedure C OMPR that fulfills all conditions will likely not be
an easy task. Nevertheless, let’s put that task aside for the time being and see how the desired reduction can
be completed assuming the validity of Claim 9.5.
1. Rn simulates M on the empty tape for n steps. If M halts then Rn accepts (i.e. it returns the value ‘1’,
irrespective of its inputs ( x, y, a, b). Otherwise, if M has not halted in n steps then Rn proceeds to the
next item.
Note that in giving this high-level description of a Turing Machine V, that on input 1n returns the description
Rn , we have referred to the description V itself. That this is possible, i.e. V is a well-defined Turing Machine,
is a consequence of Kleene’s recursion theorem—this is similar to the self-referential call we made for the
definition of algorithm B in the proof of Lemma 9.2.
The following three claims establish the key properties of this construction.
Claim 9.6. For any Turing Machine M there is an integer λ ≥ 1 which is computable from | M| and such
that V is λ-bounded.
104
Proof. By definition V on input 1n returns a decision procedure Rn that takes four inputs of length n each,
so it is a normal form verifier. It remains to estimate its running time. First we estimate |V |. Clearly, the
actions to be performed in each of the three steps can be described using poly(| M|, λ) bits. Note that the
description C OMPR does not depend on anything, so its size is a constant.
Next we estimate the running time of Rn . The first step, the simulation of M for n steps, takes time
p1 (n, M ) for some universal polynomial p1 . The second step, the computation of V C OMPR , takes time
p2 (V, λ), for some universal polynomial p2 that bounds the running time of C OMPR. The last step, the
evaluation of RnC OMPR ( x, y, a, b), takes time p C OMPR (λ + n) by property (a) in Claim 9.5.
Overall the running time is poly(n, M, λ) for some universal polynomial. This can be bounded above
by the expression (λn)λ for all n ≥ 1 provided λ is large enough compared to M.
For the remaining two claims we fix λ to the value promised in Claim 9.6 and let { Rn } and { Gn } be the
family of decision procedures and games respectively implied by the verifier V specified from M and λ.
Claim 9.7. Suppose that M halts on an empty input tape. Then ω ∗ ( Rn ) = 1 for all n.
Proof. Let T be the number of steps taken by M to halt. Then for all n ≥ T the decision procedure Rn
always accepts its inputs at step 1. Therefore ω ∗ ( Rn ) = 1 for all n ≥ T. Now we show by (strong)
downwards induction from m = T to 1 that ω ∗ ( Rm ) = 1. We showed the induction hypothesis for m = T
already. Suppose it true up to some value m > 1. Then since M does not halt in (m − 1) steps, the decision
procedure Rm−1 proceeds to step 2. and executes ( R C OMPR )m−1 . Since 2m−1 > m − 1, it follows from the
induction hypothesis that ω ∗ ( R2m−1 ) = 1. Using property (b.i) in Claim 9.5 we have that ω ∗ ( Rm−1 ) = 1,
as desired.
Proof. We show that E ( Gn , 12 ) = ∞ for all n ≥ 1. This shows that no finite strategy can achieve a success
probability larger than 12 , and taking the limit that ω ∗ ( Rn ) ≤ 12 , as desired. Since M does not halt, for any
n, Rn proceeds to step 2. and returns the desision of R CNOMPR where N = 2n . By property ([Link]) in Claim 9.5
it follows that for all n ≥ 1,
1 n 1 o
E ( Gn , ) ≥ max E GN , ,N .
2 2
By straightforward induction, E ( Gn , 12 ) ≥ T for any integer T, so it must be ∞.
105
Remark 9.9. It is worth pausing to appreciate the significance of this reduction. Beyond the stated inclusion
of complexity classes, it makes quite a striking statement about the complexity that may lurk behind simple,
finite, observable phenomena in quantum mechanics. What the existence of F states is that for any problem
that can be encoded in the halting of a Turing machine there is a game, that moreover is easily computable
from the Turing machine, that “witnesses” this fact. Consider for example the Riemann Hypothesis (RH).
There is a simple Turing Machine M that halts if and only if RH is provable in ZFC (Zermelo-Fraenkel set
theory with the axiom of choice included). Indeed M simply enumerates over all possible proofs in ZFC
and checks if they are (i) valid proofs and (ii) prove RH. Moreover, the Turing machine M is large, but
not absurdly so; probably a few millions of characters are more than enough. This means that we can, in
principle but also in practice, write a simple computer program that will return the rules for a moderately-
sized nonlocal game G = GRH such that ω ∗ ( G ) = 1 if and only if RH is provable in ZFC. Isn’t this
amazing?
Remark 9.10. A natural question is what is the commuting value ωcom of the games G = GM,λ . Naturally
this value is always at least ω ∗ ( M), and moreover for some infinite family of M it must be the case that
ωcom ( G ) = 1 even if M does not halt (and hence ω ∗ ( G ) ≤ 21 ), as otherwise using algorithm C from the
previous lecture we would be able to solve the Halting problem. We do not know if ωcom ( G ) = 1 for all
games G in the range of the reduction F .
Claim 9.11. There is a family of games { Gn }n≥1 such that for each n ≥ 1, the game Gn tests n qubits.
We gave a quite succinct statement for the claim; let’s unpack it a little bit. First, by “the game Gn
tests n qubits” we mean the following: there is a constant c < 1, independent of n, such that for any
n and any two players that succeed in the game Gn with probability at least c, each player must “have
n qubits”. Recalling our definition of n qubits what we mean by this is that to each strategy we should
be able to associate 2n observables ( Xi , Zi )i=1,...,n such that whenever the strategy succeeds with high
enough probability the ( Xi , Zi ) are “close” to satisfying the appropriate commutation and anti-commutation
relations, where closeness is measured in the right state-dependent norm. As it turns out, for the construction
that we give next time a stronger condition will hold, giving us the following somewhat more formal variant
of Claim 9.11.
Claim 9.12. There is a family of games { Gn }n≥1 with the following properties. For each n ≥ 1, in the game
Gn there are questions of the form ( X, a) and ( Z, b) where X, Z are labels and a, b ∈ {0, 1}n such that
the answer expected from a player upon such a question is a single bit. In addition there are two questions
X and Z such that the expected answer on such a question is n bits long. Furthermore, for each n ≥ 1
106
y
and ε > 0, for any strategy (|ψi, { A ax }, { Bb }) that succeeds with probability tat least 1 − ε in the game
there is an isometry VA : HA → (C2 )⊗n ⊗ HA0 such that, if X ( a), Z (b) and { A X Z
a } a , { Ab }b are Alice’s
observables and POVM on the aforementioned questions then
n
2
max E a (VA X ( a) − (σX ( a) ⊗ IdA0 )VA ) ⊗ IdB |ψi ,
o
2
E b (VA Z (b) − (σZ (b) ⊗ IdA0 )VA ) ⊗ IdB |ψi ≤ O(εd ) ,
where the expectation is taken over uniformly random a, b ∈ {0, 1}n , and letting {σaX } a and {σbZ } denote
POVMs representing an n-qubit measurement in the Hadamard and computational basis respectively,
n
max ∑ (VA A X X 2
a − ( σa ⊗ IdA0 )VA ) ⊗ IdB | ψ i ,
a
o
∑
2
(VA AbZ − (σbZ ⊗ IdA0 )VA ) ⊗ IdB |ψi ≤ O(εd ) ,
b
for some universal constant d > 0. A similar statement holds for Bob’s observables. Finally, there is a state
| aux i ∈ H0A ⊗ H0B such that
2
VA ⊗ VB |ψi − |φ+ i⊗n | aux i ≤ O(εd ) ,
3. Return VN ( X, Y, A, B).
Here, the first and last steps are executed by VN and take time polynomial in N, hence exponential in n.
The second step is executed by the provers and can take an arbitrary amount of time. The main idea for
designing VnC OMPR is to “delegate” these steps to the provers and limit the verifier’s computation to some
form of “verification” that the provers are performing the right computation:
1. Generate a pair of questions ( x, y) ∈ {0, 1}n × {0, 1}n uniformly at random.
107
(a) Locally generate X ∈ {0, 1} N and Y ∈ {0, 1} N respectively;
(b) Execute original prover’s strategy to obtain answers ( A, B);
(c) Return “proofs” a and b respectively that (i) X and Y have been selected uniformly at random;
(ii) A and B can be obtained locally; (iii) VN ( X, Y, A, B) = 1.
3. Given ( x, y, a, b), check that ( a, b) are a valid proof of (i), (ii) and (iii).
As it turns out the most delicate step in implementing this scheme is the verification of (i). Indeed this is
where we will use the fact that the provers can be forced to share entanglement in an essential way. The
verification of (ii) would be automatic if we asked each prover to report A and B respectively; because we
only ask them for shorter “proofs” a and b this requires more care, but it is not a real problem. Finally, while
the verification of (iii) requires quite some work at its heart it is not substantially different from the efficient
verification of an exponential-time computation; here again the part that is a bit delicate is that the inputs
X, Y, A, B to the computation are not known explicitly to the verifier but only through the “proofs” of items
(i) and (ii).
Focusing on (i) now, observe that the game GN from Claim 9.12 provides us with the means to “force”
the provers to generate uniformly random X and Y: we simply send them, say, question Z in the game, and
request that they use the outcome obtained as their X and Y respectively.
There is one good thing about this, and many bad things. The good thing is that based on Claim 9.12
we know that if the provers succeed in the game GN , a condition which we can imagine checking separately
(meaning that with some probability the verifier VnC OMPR executes GN and accepts if and only if accepts),
then when one prover is sent the label Z and the other the label X they obtain outcomes a, b which are
statistically close to uniformly distributed and independent from each other; both facts are a consequence
of the fact that computational and Hadamard basis measurements on two halves of the same EPR pair yield
independent uniformly distributed outcomes.
As for the bad things, we point out a few of them:
• While we can request the provers to perform computational basis measurements and thereby obtain
uniformly random X, Y, it is unclear how we can require that these are precisely the inputs that they
use for the evaluation of VN , unless they report X, Y to us—which is not possible since these strings
are too long;
• Furthermore, X, Y are not uniformly random but only close to being so—we need to make sure that
this possible error cannot be maliciously used by the provers to too large an extent;
• The game GN as we described it involves N-bit long questions; however, the verifier VnC OMPR is only
allowed n-bit long questions;
• We have not examined the running time of VnC OMPR : this should be bounded by some polynomial in n
and λ, and independent of the running time of VN .
These difficulties are substantial difficulties. They can all be overcome by introducing a more involved
variant of Claim 9.12 that is based on the use of what are called “low-degree tests’ in complexity theory.
Informally, this consists in combining the presentation of V C OMPR that we gave with ideas from the theory
of error-correcting codes so as to (a) reduce the complexity of the referee in the game, and (b) ensure that
the little information that the players provide about X, Y is sufficient to “lock” them into using X, Y, or to
the least strings that are sufficiently close to them, in the other steps (i.e. the proofs of items (ii) and (iii)).
We will not be able to dive into these difficulties here, and instead allocate the last lecture to a proof of
Claim 9.12.
108
Remark 9.13. For the entire lecture we assumed that we could work with verifiers that use a uniform dis-
tribution on their questions. In fact, this is provably not sufficient, and once must necessarily use more
complex question distributions. For this reason the fact that Claim 9.12 allows us to certify measurements
in either computational or Hadamard basis for the provers is crucial: in this way we are able not only to
request that they generate uniform independent ( X, Y ), by sending them different bases, but also uniform
equal ( X, Y ), by sending them the same basis. By introducing further variations on this theme it is possible
to “command” the provers to generate ( X, Y ) according to quite a broad class of distributions.
109
110
Lecture 10
Recall from the last lecture that we reduced the proof of MIP ∗ = RE to showing a form of “n-qubit test”,
stated as Claim 9.12 and reformulated as a theorem here:
Theorem 10.1. There is a family of games { Gn }n≥1 with the following properties. For each n ≥ 1, in
the game Gn there are questions of the form ( X, a) and ( Z, b) where X, Z are labels and a, b ∈ {0, 1}n
such that the answer expected from a player upon such a question is a single bit. In addition there are two
questions X and Z such that the expected answer on such a question is n bits long. Furthermore, for each
y
n ≥ 1 and ε > 0, for any strategy (|ψi, { A ax }, { Bb }) that succeeds with probability tat least 1 − ε in the
game Gn there is an isometry VA : HA → (C2 )⊗n ⊗ HA0 such that, if X ( a), Z (b) and { A X Z
a } a , { Ab }b are
Alice’s observables and POVM on the aforementioned questions then
n
2
max E a (VA X ( a) − (σX ( a) ⊗ IdA0 )VA ) ⊗ IdB |ψi ,
o
2
E b (VA Z (b) − (σZ (b) ⊗ IdA0 )VA ) ⊗ IdB |ψi ≤ O(εd ) , (10.1)
where the expectation is taken over uniformly random a, b ∈ {0, 1}n , and letting {σaX } a and {σbZ } denote
POVMs representing an n-qubit measurement in the Hadamard and computational basis respectively,
n
max ∑ (VA A X X 2
a − ( σa ⊗ IdA0 )VA ) ⊗ IdB | ψ i ,
a
o
∑
2
(VA AbZ − (σbZ ⊗ IdA0 )VA ) ⊗ IdB |ψi ≤ O(εd ) , (10.2)
b
for some universal constant d > 0. A similar statement holds for Bob’s observables. Finally, there is a state
| aux i ∈ H0A ⊗ H0B such that
2
VA ⊗ VB |ψi − |φ+ i⊗n | aux i ≤ O(εd ) , (10.3)
Remark 10.2. The games Gn in Theorem 10.1, as well as all games considered in this lecture, are sym-
metric: X = Y and A = B , the distribution on questions π is invariant under permutation of the
two questions, π ( x, y) = π (y, x ) for all ( x, y), and the verification predicate is symmetric as well, i.e.
y
Rn ( a, b, x, y) = Rn (b, a, y, x ) for all ( x, y, a, b). Define a strategy (|ψi, { A ax }, { Bb }) to be symmetric if
111
HA = HB , |ψi is invariant under exchange of the two subsystems, and A ax = Bax for all x, a. It is not hard
y
to verify that whenever a game G is symmetric then for any strategy (|ψi, { A ax }, { Bb }) that succeeds with
some probability 1 − ε in the game there is a symmetric strategy (|ψ̃i, { Ã ax }) that succeeds with the same
probability, such that moreover “rigidity” statements such as the conclusion of Theorem 10.1 can be “lifted”
from the symmetric strategy back to the original strategy. (The symmetrized strategy uses a state
1
|ψ̃i = |ψiAB ⊗ √ |0iA0 |1iB0 + |1iA0 |0iB0 ∈ HA ⊗ HB ⊗ C2A0 ⊗ C2B0 ,
2
and each player uses its additional qubit to decide whether to compute its answer a to question x using the
“Alice” POVM { A ax } or the “Bob” POVM { Bax }; formally, for all x, a, Ã ax = A ax ⊗ |0ih0| + Bax ⊗ |1ih1|.)
Due to this observation in the lecture we limit ourselves to the analysis of symmetric strategies.
There is one important aspect in which the theorem falls short of what we needed in the previous lecture:
its verification procedure is too complex. In the theorem, n qubits are being tested using —as we will see—
questions of length O(n). In order for the test to be of use in the design of the compression procedure
(Claim 9.5) we need the test verifier to run in time n, so in particular questions cannot be of length O(n).
Achieving such a test is a challenge beyond what we can expose in a single lecture, and so we will focus
on the less efficient version provided by Theorem 10.1. The more efficient version combines the kind of
techniques introduced in this lecture with techniques similar to the use of polynomial error-correcting codes
in the proof of the PCP theorem. For details we refer to [JNV+ 20b] and [JNV+ 20a, Appendix A].
Our strategy for the proof of Theorem 10.1 is to derive it from two ingredients. Firstly, in Section 10.1
we introduce a general theory of approximate group representations and note that the consequences of
Theorem 10.1 follow provided that the players’ strategy is, in some sense, an approximate representation of
the n-qubit Pauli group (a finite group which we will define). Secondly, in Section 10.2 we design a game,
or “test”, that enforces that any successful strategy for the players in the game specifies an approximate
representation of the n-qubit Pauli group, so that the results from the first part can be applied to it to conclude
the theorem.
where we use B∗ to denote the conjugate-transpose. Note that the matrix trace inner product is recovered
for σ = Id. If σ is the totally mixed state, then we obtain a dimension-normalized variant of the trace inner
product. We will also write k Akσ = h A, Ai1/2 σ .
Given an arbitrary finite group G (not necessarily abelian), a group representation of G is a map f :
G → Ud (C), the group of d × d unitary matrices, such that f is a homomorphism: for any x, y ∈ G,
f ( x −1 y) = f ( x )∗ f (y), where we used ∗ to denote the conjugate transpose (which, for unitary matrices,
corresponds to taking the inverse). The following definition introduces a notion of approximate group
representation.
112
Definition 10.3. Given a finite group G, an integer d ≥ 1, ε ≥ 0, and a d-dimensional positive semidefinite
matrix σ with trace 1, an (ε, σ)-representation of G is a function f : G → Ud (C), the unitary group of d × d
matrices, such that
E x,y∈G < f ( x )∗ f (y), f ( x −1 y) σ ≥ 1 − ε ,
(10.4)
where the expectation is taken under the uniform distribution over G.
Note that the condition (10.4) is equivalent to
2
E x,y∈G f ( x −1 y) − f ( x )∗ f (y) σ
≤ 2ε . (10.5)
Taking ε = 0 and σ any invertible positive definite matrix, we see that the case ε = 0 corresponds to an
exact representation of G.
Example 10.4. Consider the Weyl-Heisenberg group P , which is the group generated by the Pauli σX and
σZ matrices. It is not hard to verify that this group has 8 elements, which can be decomposed as (−1)c σXa σZb
for a, b, c ∈ {0, 1}. A qubit ( X, Z ) according to our first definition (Definition 1.1) can be used to specify a
(0, σ) representation of P for any σ as follows:
f (−1)c σXa σZb = (−1)c X a Z b ,
(10.6)
for all a, b, c ∈ {0, 1}. It is immediate to verify that for all ( x, y) ∈ P we have f ( x )∗ f (y) = f ( x −1 y) and
so (10.4) holds with ε = 0 for any σ.
The example makes explicit the connection between our notion of qubit with group representation the-
ory. In this lecture we will leverage the connection to make use of powerful theorems from representation
theory towards the analysis of an n-qubit test. As a warm-up, the following simple and recommended
exercise asks you to generalize the example to the case of a single ε-approximate qubit.
Exercise 10.1. Let (|ψi, X, Z ) be a qubit such that |ψi ∈ H. Define f : P 7→ U (H) as in (10.6). Show that
f is an (0, σ )-representation of P for σ = |ψihψ|. Now √ suppose that (|ψi, X, Z ) is only an ε-approximate
qubit in the sense of Exercise 2.1. Show that f is an (O( ε), σ)-representation of P .
Remark 10.5. The condition (10.4) in Definition 10.3 is very closely related to Gowers’ U 2 norm
4
k f kU 2 = E xy−1 = zw−1 f ( x ) f (y)∗ , f (z) f (w)∗ σ .
While a large Gowers norm implies closeness to an affine function, we are interested in testing homomor-
phisms, and the condition (10.4) will arise naturally from our calculations in the next section.
113
Theorem 10.6 (Gowers-Hatami). Let G be a finite group, ε ≥ 0, and f : G → Ud (C) an (ε, σ)-
0
representation of G. Then there exists a d0 ≥ d, an isometry V : Cd → Cd , and a representation
g : G → Ud0 (C) such that
2
E x∈G f ( x ) − V ∗ g( x )V σ ≤ 2 ε.
Gowers and Hatami limit themselves to the case of σ = d−1 Id , which corresponds to the dimension-
normalized Frobenius norm. In this scenario they in addition obtain a tight control of the dimension d0 , and
show that one can always take d0 = (1 + O(ε))d in the theorem. We will see a much shorter proof than
theirs (the proof is implicit in their argument) that does not seem to allow to recover this estimate. The
extension to general σ, however, will be necessary for our purposes.
Note that Theorem 10.6 does not in general hold with d0 = d. The reason is that it is possible for G to
have an approximate representation in some dimension d, but no exact representation of the same dimension:
to obtain an example of this, take any group G that has all non-trivial irreducible representations of large
enough dimension, and create an approximate representation in e.g. dimension one less by “cutting off”
one row and column from an exact representation. For sufficiently “smooth” σ (no disproportionately large
singular values) the dimension normalization induced by the norm k · kσ will make this barely noticeable, but
it will be impossible to “round” the approximate representation obtained to an exact one without modifying
the dimension.
Example 10.7. Continuing with Example 10.4 we consider the example of G = P . In Example 10.4 we
observed that a qubit (|ψi, X, Z ) can be used to specify a (0, σ) representation f of P such that moreover
f (−1) = − Id. We now check that the converse holds: for any (0, σ)-representation of P for invertible
σ, if X = f (σX ) and Z = f (σZ ) then using (10.5), taking x = y = σX and x = y = σZ it follows that
X 2 = Z2 = f (1) = Id, and taking x = σX and y = σZ we get that XZ = f (σX σZ ) while
ZX = f (σZ σX ) = f (−σX σZ ) = f (−1) f (σX σZ ) ,
where the second equality uses that the Pauli anti-commute and the last equality again uses (10.5). Thus
if f (−1) = − Id then { X, Z } = 0, so the (0, σ)-representation f specifies a qubit and in particular
Lemma 2.3 on the structure of a qubit applies. As a result, we have shown that there exists a single repre-
sentation of P such that f (−1) = − Id, and that it is given by the Pauli matrices in dimension 2. 2
Exercise 10.2. Using Exercise 10.1 and Example 10.7, show that Theorem 10.6 for the case where G = P
implies Exercise 2.1.
Exercise 10.3. Show Theorem 10.6 for the case where G = P . [Hint: Adapt the proof “by calculation” of
Proposition 6.2 to take into account ε-approximations.]
The main ingredient for the proof of Theorem 10.6 is an appropriate notion of Fourier transform over
non-abelian groups. Given an irreducible representation ρ : G → Udρ (C), define
2 The conditionf (−1) = − Id is necessary, as there are four 1-dimensional representations of P : all combinations f (σX ) = ±1
and f (σZ ) = ±1. We have found the right number of irreps: 1 · 22 + 4 · 1 = 8 = |P |.
114
for any x ∈ G. Note that plugging in x = e (the identity element in G) yields ∑ρ d2ρ = | G |.
Proof of Theorem 10.6. Our first step is to define an isometry V : Cd → Cd ⊗ (⊕ρ Cdρ ⊗ Cdρ ) by
dρ
V : u ∈ C 7→ d
d1/2 ∑ fˆ(ρ)(u ⊗ ei ) ⊗ ei ,
M
ρ
ρ i =1
where the direct sum ranges over all irreducible representations ρ of G and {ei } is the canonical basis.3
Note what V does: it “embeds” any vector u ∈ Cd into a direct sum, over irreducible representations ρ, of a
d-dimensional vector of dρ × dρ matrices. Each (matrix) entry of this vector can be thought of as the Fourier
coefficient of the corresponding entry of the vector f ( x )u associated with ρ. The fact that V is an isometry
follows from the appropriate extension of Parseval’s formula:
where for the second line we used the definition (10.7) of fˆ(ρ) and for the third we used (10.8) and the fact
that f takes values in the unitary group.
Next define M
g( x ) = Id ⊗ Idρ ⊗ ρ( x ) ,
ρ
a direct sum over all irreducible representations of G (hence itself a representation). Lets’ first compute the
“pull-back” of g by V: following a similar calculation as above, for any x ∈ G,
This relates correlation of f with V ∗ gV to the quality of f as an approximate representation and proves the
theorem.
3 Observe that this expression directly generalizes (6.1).
115
10.1.3 Application: rigidity for the Magic Square game
Recall the Magic Square game from Section 3.3.1. In Lemma 3.12 we analyzed perfect strategies in this
game and showed that any perfect strategy must “have a qubit”. Remembering the proof, we had seen that
Bob’s observables in a perfect strategy must form an operator solution to the underlying system of equations,
and that any such operator solution must contain two anti-commuting observables. Using Theorem 10.6 we
can extend our earlier result to the case of approximate strategies with very little extra work. (This was first
shown in [WBMS16] using a more direct proof.)
Theorem 10.8. Let ε > 0, and suppose that a strategy for the players in the Magic Square game, using
a bipartite state |ψi ∈ Cd ⊗ Cd and observables
√ B1 , . . . , B9 for Bob succeeds with probability 1 − ε, for
some ε ≥ 0. Then (|ψi, B2 , B4 ) is an O( ε)-approximate qubit. Moreover, there are local isometries
0
VA , VB : Cd → C2 ⊗ Cd such that
√
VA ⊗ VB |ψi − |φ+ i ⊗ |ψ0 i = O( ε) , (10.9)
and
√
(VA ⊗ VB )(Id ⊗ B2 )|ψi − (σZ ⊗ Id)|φ+ i ⊗ |ψ0 i = O ε , (10.10)
Note that this is a slightly weaker variant of Theorem 3.16 that we stated without proof, because it only
characterizes a single qubit of the strategy, instead of two for the case of Theorem 3.16. This will suffice for
our purposes.
Proof. For the first step of the proof we follow the proof of Claim 3.11, except that all equalities must be
made approximate equalities. Assume without loss of generality that Alice’s strategy is specified by six
4-outcomes projective measurements { Aia1 ,a2 ,a3 }, where a1 , a2 , a3 ∈ {±1} range over the four possible
assignments that satisfy the constraint associated with the i-th row (i ∈ {1, 2, 3}) or (i − 3)-th column
(i ∈ {4, 5, 6}). (We can assume that Alice always returns a valid assignment because she knows that she
will lose if not, so we do not even need to include a symbol for such evidently wrong answers in the game.)
For any i ∈ {1, . . . , 9}, in addition to Bob’s observable Bi associated with question i we define two
observables from Alice’s strategy, obtained by recording her answer associated to entry i when she is asked
the unique row containing i — call this observable Ci — or the unique column containing i — call this
observable Ci0 . Formally, C1 = ∑ a1 ,a2 ,a3 ∈{±1} a1 A1a1 ,a2 ,a3 , and similar relations can be used to define each
Ci and Ci0 . Due to the parity constraints enforced on Alice’s answers it is always the case that C1 C2 C3 =
+ Id, . . . , C3 C6 C9 = − Id.
By definition, success of the strategy in the game implies 18 equations of the form
for all i ∈ {1, . . . , 9}. Indeed, each such equation represents the probability that the players return valid
answers, conditioned on each of the 18 possible pairs of questions in the game. These relations allow us to
116
mimic the proof of Claim 3.11, as follows:
B2 B4 |ψi ≈ C4 ⊗ B2 |ψi
= C5 C6 ⊗ B2 |ψi
≈ C5 C6 C2 ⊗ Id |ψi
= C5 C6 C3 C1 ⊗ Id |ψi
≈ C5 C6 C3 ⊗ B1 |ψi
≈ C5 C6 ⊗ B1 B3 |ψi
≈ C5 C60 ⊗ B1 B3 |ψi
≈ C5 C60 C30 ⊗ B1 |ψi
= C5 C90 ⊗ B1 |ψi ,
where here we use the notation |ui ≈ |vi to mean k|ui − |vik2 = O(ε). Here, each of the approximations
is obtained by bounding the squared norm of the difference using the Cauchy-Schwarz inequality and the
required relation; for example, for the first approximation we write
2 2
(Id ⊗ B2 B4 − C4 ⊗ B2 )|ψi = (Id ⊗ B2 )(Id ⊗ B4 − C4 ⊗ Id)|ψi
2
= (Id ⊗ B4 − C4 ⊗ Id)|ψi
= 2 − 2hψ| B4 ⊗ C4 |ψi
≤ 36ε ,
where the derivation uses that B2 , B4 and C4 are Hermitian and square to identity.
√ Using a similar chain of
approximations starting from B4 B2 |ψi, it follows that (|ψi, B2 , B4 ) is an O( ε)-approximate qubit.
As already observed in Exercise 10.1, it follows that B2 and B4 induce an approximate representation of
P by setting
f (± Id) = ± Id, f (±σZ ) = ± B2 , f (±σX ) = ± B4 , f (±σX σZ ) = ± B4 B2 .
Note that this is a legal definition, since B2 , B4 , and B2 B4 are all unitary. Moreover, using only the ap-
proximate anti-commutation and the fact that B2 and B4 are observables it is immediate to verify that the
conditions of Theorem 10.6 are satisfied, i.e. f is an (O(ε), ρB )-representation of P , where ρB denotes the
reduced density of |ψi on HB .
Applying the theorem, there must exist an exact representation g of P to which f is close. However, as
we saw in Example 10.7 the representation theory of P is not complicated. It has four 1-dimensional irre-
ducible representations, but all of them map − Id to 1, so they cannot be close to f . Since any representation
is a direct sum of irreducible representations, and all irreducible representations of P are far from f , g must
be a direct sum of multiple copies of the unique irreducible 2-dimensional representation of P , which is
precisely given by the Pauli matrices, together with possibly a small (relative to the total dimension) number
of 1-dimensional relations. Ignoring the presence of such representations for simplicity,4 g(σZ ) = σZ ⊗ Id
and g(σX ) = σX ⊗ Id, which gives (10.10). √
To conclude (10.9) we observe that the relations (10.11) imply that also (ρA , C2 , C4 ) is an O( ε)-
approximate qubit. This allows us to define an approximate representation of P on HA , and apply Theo-
rem 10.6 again to obtain on isometry VA which maps (ρA , C2 , C4 ) close to an exact qubit. Letting
|ψ0 i = VA ⊗ VB |ψi ∈ (C2 ⊗ HA0 ) ⊗ (C2 ⊗ HB0 )
4 To account for them we would select the “corner” of the range of the isometry V that includes only copies of the 2-dimensional
irrep; this is a simple technicality.
117
we see from (10.11) and (10.10) that
hψ| σX ⊗ σX ⊗ IdA0 B0 +σZ ⊗ σZ ⊗ IdA0 B0 |ψi ≥ 1 − O(ε) .
To conclude note that 12 (σX ⊗ σX + σZ ⊗ σZ ) is an observable with a single eigenvalue 1, with associated
eigenvector |φ+ i, and all other eigenvalues equal to 0 or −1.
linearity
2 2
E a,a0 X ( a) X ( a0 ) − X ( a + a0 ) σ
≤ε, E b,b0 Z (b) Z (b0 ) − Z (b + b0 ) σ
≤ε, (10.13)
and anti-commutation
2
E a,b X ( a) Z (b) − (−1) a·b X ( a) Z (b) σ
≤ ε. (10.14)
0
Then there exists a d0 ≥ d, an isometry V : Cd → Cd , and a representation g : Pn → Ud0 (C) such that
g(− I ) = − Id0 and
2
E a,b X ( a) Z (b) − V ∗ g(σX ( a)σZ (b))V σ = O(ε) .
118
Note that the conditions (10.13) and (10.14) in the corollary are very similar to the conditions required of
an approximate representation of the group Pn ; in fact it is easy to convince oneself that their exact analogue
suffices to imply all the group relations. The reason for choosing those specific relations is that they can
be checked using games; see the next subsection for this. Condition (10.12) is necessary to derive the
conditions for the application of the Gowers-Hatami theorem from (10.13) and (10.14), and is also testable;
see the proof. The conclusion of the corollary implies the conclusion of Theorem 10.1 simply by using the
aforementioned fact on non-trivial representations of Pn (see details at the end of Section 10.2.3).
Remark 10.10. Corollary 10.9 can be seen as an extension of the Blum-Luby-Rubinfeld linearity test [BLR93].
The latter makes a similar statement, but for the commutative group {±σX ( a)| a ∈ {0, 1}n }.
Proof. To apply the Gowers-Hatami theorem we need to construct an (ε, σ )-representation f of the group
Pn . Using that any element of Pn has a unique representative of the form ±σX ( a)σZ (b) for a, b ∈ {0, 1}n ,
we define f (±σX ( a)σZ (b)) = ± X ( a) Z (b). Next we need to verify that f is an approximate representation.
Let x, y ∈ Pn be such that x = σX ( a x )σZ (bx ) and y = σX ( ay )σZ (by ) for n-bit strings ( a x , bx ) and ( ay , by )
respectively. Up to phase, we can exploit successive cancellations to decompose ( f ( x ) f (y)∗ − f ( xy−1 )) ⊗
I as
(It is worth staring at this sequence of equations for a little bit. In particular, note the “player-switching” that
takes place in the 2nd, 4th and 6th lines; this is used as a means to “commute” the appropriate unitaries, and
is the reason for including (10.12) among the assumptions of the corollary.) Evaluating each term on the
state |ψi, taking the squared Euclidean norm, and then the expectation over uniformly random a x , ay , bx , by ,
the inequality k AB|ψik ≤ k Akk B|ψik and the assumptions of the theorem let us bound the overlap of
each term in the resulting summation by O(ε). Using k( A ⊗ I )|ψik = k Akσ by definition and the triangle
inequality we have obtained the bound
2
E x,y f ( x ) f (y)∗ − f ( xy−1 ) σ
= O ( ε ).
We are now in a position to apply the Gowers-Hatami theorem, which gives an isometry V and exact
representation g such that
1 2
E a,b X ( a) Z (b) − V ∗ g(σX ( a)σZ (b)) − g(−σX ( a)σZ (b)) V
= O ( ε ). (10.15)
2 σ
Using that g is a representation, g(−σX ( a)σZ (b)) = g(− I ) g(σX ( a)σZ (b)). It follows from (10.15) that
k g(− I ) + I k2σ = O(ε), so we may restrict the range of V to the subspace where g(− I ) = − I without
introducing much additional error.
119
10.2.2 Testing the Weyl-Heisenberg group relations
Corollary 10.9 makes three assumptions about the observables X ( a) and Z (b): that they satisfy approximate
consistency (10.12), linearity (10.13), and anti-commutation (10.14). To complete our test, we need to show
how these relations can be “certified” in a two-player game. There are multiple ways this can be done; we
give one. We start by introducing two stand-alone “tests” that we later combine to define the game Gn .
Linearity test:
(a) The referee selects W ∈ { X, Z } and a, a0 ∈ {0, 1}n uniformly at random. She sends
(W, a, a0 ) to one player and (W, a), (W, a0 ), or (W, a + a0 ) to the other.5
(b) The first player replies with two bits, and the second with a single bit. The referee accepts
if and only if the player’s answers are consistent.
As always in this section, the test treats both players symmetrically. As a result (see Remark 10.2
we can assume that the players’ strategy is symmetric, and is specified by a permutation-invariant state
|ψi ∈ Cd ⊗ Cd and a measurement for each question: an observable W ( a) associated to questions of the
form (W, a), and a four-outcome measurement {Wa,a0 } associated with questions of the form (W, a, a0 ).
The linearity test described above is almost identical to the BLR linearity test, except for the use of the
basis label W ∈ { X, Z }. The following lemma states conditions that a strategy must satisfy in order to
succeed with high probability in the test.
Lemma 10.11. Suppose that a family of observables {W ( a)} for W ∈ { X, Z } and a ∈ {0, 1}n , generates
outcomes that succeed in the linearity test with probability 1 − ε, when applied on a symmetric bipartite
state |ψi ∈ Cd ⊗ Cd with reduced density matrix σ. Then the following hold: approximate consistency
E a h ψ | X ( a ) ⊗ X ( a ) | ψ i = 1 − O ( ε ), E b h ψ | Z ( b ) ⊗ Z ( b ) | ψ i ≥ 1 − O ( ε ),
and linearity
2 2
E a,a0 X ( a) X ( a0 ) − X ( a + a0 ) σ
= O ( ε ), E b,b0 Z (b) Z (b0 ) − Z (b + b0 ) σ
= O ( ε ).
Exercise 10.4. Prove the lemma. (In the case of classical strategies, the conditions are an immediate refor-
mulation of the test. The proof for quantum strategies is not much harder.)
Anti-commutation test:
(a) The referee selects a, b ∈ {0, 1}n uniformly at random under the condition that a · b = 1.
She plays the Magic Square game with both players, with the following modifications: if
the question to the second player is 2 or 4 she sends ( X, a) or ( Z, b) instead; in all other
cases he sends the original label of the question in the Magic Square game together with
both strings a and b.
(b) Each player provides answers as in the Magic Square game. The referee accepts if and
only if the player’s answers would have been accepted in the game.
120
Lemma 10.12. Suppose a strategy for the players succeeds in the anti-commutation test with probability
at least 1 − ε, when performed on a symmetric bipartite state |ψi ∈ Cd ⊗ Cd with reduced density matrix
σ. Then the observables X ( a) and Z (b) applied by the player upon receipt of questions ( X, a) and ( Z, b)
respectively satisfy
2 √
E a,b: a·b=1 X ( a) Z (b) − (−1) a·b Z (b) X ( a) σ = O ε . (10.16)
Proof sketch of Theorem 10.1. For any integer n ≥ 1 let Gn be the n-qubit Pauli braiding test. Suppose that
a family of observables W ( a), for W ∈ { X, Z } and a ∈ {0, 1}n , together with projective measurements
{ AXa } a∈{0,1}n and { Ab }b∈{0,1}n and a state | ψ i ∈ C ⊗ C specify a symmetric strategy that succeeds in
Z d d
for some non-trivial representation g of Pn . Using what we know of non-trivial representations, (10.1)
follows. To obtain (10.2) we use success in part (c) of the test, which using σaX = E b (−1) a·b σX (b) and
similarly for σbZ immediately translates into the desired relation.
Finally, using the consistency relations (10.12) that follow from part (a) of the test together with the
above we get
√
E a,b hψ|(V ⊗ V )∗ σX ( a)σZ (b) ⊗ σX ( a)σZ (b) (V ⊗ V )|ψi = 1 − O( ε).
Using similar reasoning as the end of the proof of Theorem 10.8, (10.3) follows.
121
122
Bibliography
[Aar10] Scott Aaronson. Bqp and the polynomial hierarchy. In Proceedings of the forty-second ACM
symposium on Theory of computing, pages 141–150. ACM, 2010.
[AB09] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge
University Press, 2009.
[ACGK17] Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, and Elham Kashefi. On the
implausibility of classical client blind quantum computing. arXiv preprint arXiv:1704.08482,
2017.
[AG17] Dorit Aharonov and Ayal Green. A quantum inspired proof of P\#p ⊆ IP. arXiv preprint
arXiv:1710.09078, 2017.
[AGV09] Adi Akavia, Shafi Goldwasser, and Vinod Vaikuntanathan. Simultaneous hardcore bits and
cryptography against memory attacks. In Theory of Cryptography Conference, pages 474–
495. Springer, 2009.
[AV12] Dorit Aharonov and Umesh Vazirani. Is quantum mechanics falsifiable? A computational
perspective on the foundations of quantum mechanics. arXiv preprint arXiv:1206.3686,
2012.
[AV13] Dorit Aharonov and Umesh Vazirani. Is quantum mechanics falsifiable? A computational
perspective on the foundations of quantum mechanics. Computability: Turing, Gödel,
Church, and Beyond. MIT Press, 2013.
[BC20] Oren Becker and Michael Chapman. Stability of approximate group actions: uniform and
probabilistic. arXiv preprint arXiv:2005.06652, 2020.
[BCM+ 18] Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, and Thomas Vidick. A
cryptographic test of quantumness and certifiable randomness from a single quantum device.
In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages
320–331. IEEE, 2018.
[Bel64] John S Bell. On the einstein podolsky rosen paradox. Physics Physique Fizika, 1(3):195,
1964.
[BLR93] Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications
to numerical problems. Journal of computer and system sciences, 47(3):549–595, 1993.
123
[BOGKW19] Michael Ben-Or, Shafi Goldwasser, Joe Kilian, and Avi Wigderson. Multi-prover interac-
tive proofs: How to remove intractability assumptions. In Providing Sound Foundations for
Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, pages 373–410. 2019.
[Bre06] Frédéric Brechenmacher. Histoire du théorème de Jordan de la décomposition matricielle
(1870-1930). Formes de représentation et méthodes de décomposition. PhD thesis, 2006.
[BV14] Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from
(standard) lwe. SIAM Journal on Computing, 43(2):831–871, 2014.
[Cap15] Valerio Capraro. Connes’ Embedding Conjecture, pages 73–107. Springer International
Publishing, Cham, 2015.
[CCKW19] Alexandru Cojocaru, Léo Colisson, Elham Kashefi, and Petros Wallden. Qfactory:
classically-instructed remote secret qubits preparation. In International Conference on the
Theory and Application of Cryptology and Information Security, pages 615–645. Springer,
2019.
[CLS17] Richard Cleve, Li Liu, and William Slofstra. Perfect commuting-operator strategies for linear
system games. Journal of Mathematical Physics, 58(1):012202, 2017.
[CM14] Richard Cleve and Rajat Mittal. Characterization of binary constraint system games. In Inter-
national Colloquium on Automata, Languages, and Programming, pages 320–331. Springer,
2014.
[CM16] Toby Cubitt and Ashley Montanaro. Complexity classification of local hamiltonian problems.
SIAM Journal on Computing, 45(2):268–316, 2016.
[Con76] Alain Connes. Classification of injective factors cases II1 , II∞ , IIIλ , λ 6= 1. Annals of
Mathematics, pages 73–115, 1976.
[CR20] Rui Chao and Ben W Reichardt. Quantum dimension test using the uncertainty principle.
arXiv preprint arXiv:2002.12432, 2020.
[CRSV17] Rui Chao, Ben W Reichardt, Chris Sutherland, and Thomas Vidick. Overlapping qubits.
arXiv preprint arXiv:1701.01062, 2017.
[CRSV18] Rui Chao, Ben W Reichardt, Chris Sutherland, and Thomas Vidick. Test for a large amount
of entanglement, using few measurements. Quantum, 2:92, 2018.
[CS17] Andrea Coladangelo and Jalex Stark. Robust self-testing for linear constraint system games.
arXiv preprint arXiv:1709.09267, 2017.
[CS18] Andrea Coladangelo and Jalex Stark. Unconditional separation of finite and infinite-
dimensional quantum correlations. arXiv preprint arXiv:1804.05116, 2018.
[DFPR14] Vedran Dunjko, Joseph F Fitzsimons, Christopher Portmann, and Renato Renner. Compos-
able security of delegated quantum computation. In International Conference on the Theory
and Application of Cryptology and Information Security, pages 406–425. Springer, 2014.
[EPR35] Albert Einstein, Boris Podolsky, and Nathan Rosen. Can quantum-mechanical description of
physical reality be considered complete? Physical review, 47(10):777, 1935.
124
[Fri12] Tobias Fritz. Tsirelson’s problem and Kirchberg’s conjecture. Reviews in Mathematical
Physics, 24(05):1250012, 2012.
[Gen09] Craig Gentry. Fully homomorphic encryption using ideal lattices. In STOC, volume 9, pages
169–178, 2009.
[GH17] William Timothy Gowers and Omid Hatami. Inverse and stability theorems for approximate
representations of finite groups. Sbornik: Mathematics, 208(12):1784, 2017.
[GKK19] Alexandru Gheorghiu, Theodoros Kapourniotis, and Elham Kashefi. Verification of quantum
computation: An overview of existing approaches. Theory of computing systems, 63(4):715–
808, 2019.
[GKR08] Shafi Goldwasser, Yael Tauman Kalai, and Guy N Rothblum. Delegating computation: inter-
active proofs for muggles. In Proceedings of the fortieth annual ACM symposium on Theory
of computing, pages 113–122. ACM, 2008.
[GKW17] Rishab Goyal, Venkata Koppula, and Brent Waters. Lockable obfuscation. In Foundations of
Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on, pages 612–621. IEEE,
2017.
[GKW18] Rishab Goyal, Venkata Koppula, and Brent Waters. Collusion resistant traitor tracing from
learning with errors. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory
of Computing, pages 660–670. ACM, 2018.
[GMR85] Shafi Goldwasser, Silvio Micali, and Ronald Rivest. A “paradoxical” solution to the signature
problem. In Advances in Cryptology, pages 467–467. Springer, 1985.
[GV19] Alexandru Gheorghiu and Thomas Vidick. Computationally-secure and composable remote
state preparation. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Sci-
ence (FOCS), pages 1024–1033. IEEE, 2019.
[GVW01] Oded Goldreich, Salil Vadhan, and Avi Wigderson. On interactive proofs with a laconic
prover. In International Colloquium on Automata, Languages, and Programming, pages
334–345. Springer, 2001.
[GVW15] Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. Attribute-based encryption for
circuits. Journal of the ACM (JACM), 62(6):45, 2015.
[Ito10] Tsuyoshi Ito. Polynomial-space approximation of no-signaling provers. In International
Colloquium on Automata, Languages, and Programming, pages 140–151. Springer, 2010.
[IV12] Tsuyoshi Ito and Thomas Vidick. A multi-prover interactive proof for nexp sound against
entangled provers. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer
Science, pages 243–252. IEEE, 2012.
[Ji13] Zhengfeng Ji. Binary constraint system games and locally commutative reductions. arXiv
preprint arXiv:1310.3794, 2013.
[JNP+ 11] Marius Junge, Miguel Navascues, Carlos Palazuelos, David Perez-Garcia, Volkher B Scholz,
and Reinhard F Werner. Connes’ embedding problem and Tsirelson’s problem. Journal of
Mathematical Physics, 52(1):012102, 2011.
125
[JNV+ 20a] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP∗ = RE.
arXiv preprint arXiv:2001.04383, 2020.
[JNV+ 20b] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. Quantum
soundness of the classical low individual degree test. arXiv preprint arXiv:2009.12982, 2020.
[JP11] Marius Junge and Carlos Palazuelos. Large violation of bell inequalities with low entangle-
ment. Communications in Mathematical Physics, 306(3):695, 2011.
[Kir93] Eberhard Kirchberg. On non-semisplit extensions, tensor products and exactness of group
C ∗ -algebras. Inventiones mathematicae, 112(1):449–489, 1993.
[KKMV09] Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, and Thomas Vidick. Using entangle-
ment in quantum multi-prover interactive proofs. Computational Complexity, 18(2):273–307,
2009.
[KMW17] Elham Kashefi, Luka Music, and Petros Wallden. The quantum cut-and-choose technique
and quantum two-party computation. arXiv preprint arXiv:1703.03754, 2017.
[KRR14] Yael Tauman Kalai, Ran Raz, and Ron D Rothblum. How to delegate computations: the
power of no-signaling proofs. In Proceedings of the forty-sixth annual ACM symposium on
Theory of computing, pages 485–494. ACM, 2014.
[LFKN92] Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for
interactive proof systems. Journal of the ACM (JACM), 39(4):859–868, 1992.
[Mah18] Urmila Mahadev. Classical verification of quantum computations. In 2018 IEEE 59th Annual
Symposium on Foundations of Computer Science (FOCS), pages 259–267. IEEE, 2018.
[Mer90] N David Mermin. Simple unified form for the major no-hidden-variables theorems. Physical
review letters, 65(27):3373, 1990.
[Mer93] N David Mermin. Hidden variables and the two theorems of john bell. Reviews of Modern
Physics, 65(3):803, 1993.
[MF16] Tomoyuki Morimae and Joseph F Fitzsimons. Post hoc verification with a single prover.
arXiv preprint arXiv:1603.06046, 2016.
[Mor18] Tomoyuki Morimae. Blind quantum computing can always be made verifiable. arXiv preprint
arXiv:1803.06624, 2018.
[MP12] Daniele Micciancio and Chris Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller.
In Annual International Conference on the Theory and Applications of Cryptographic Tech-
niques, pages 700–718. Springer, 2012.
[MYS12] Matthew McKague, Tzyh Haur Yang, and Valerio Scarani. Robust self-testing of the singlet.
Journal of Physics A: Mathematical and Theoretical, 45(45):455304, 2012.
[NC02] Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.
126
[NPA08] Miguel Navascués, Stefano Pironio, and Antonio Acı́n. A convergent hierarchy of semidef-
inite programs characterizing the set of quantum correlations. New Journal of Physics,
10(7):073013, 2008.
[NW19] Anand Natarajan and John Wright. Neexp is contained in mip. In 2019 IEEE 60th Annual
Symposium on Foundations of Computer Science (FOCS), pages 510–518. IEEE, 2019.
[Oza13a] Narutaka Ozawa. About the Connes embedding conjecture. Japanese Journal of Mathemat-
ics, 8(1):147–183, 2013.
[Oza13b] Narutaka Ozawa. About the connes embedding conjecture. Japanese Journal of Mathemat-
ics, 8(1):147–183, 2013.
[P+ 16] Chris Peikert et al. A decade of lattice cryptography. Foundations and Trends R in Theoreti-
cal Computer Science, 10(4):283–424, 2016.
[Reg09] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Jour-
nal of the ACM (JACM), 56(6):34, 2009.
[RRR16] Omer Reingold, Guy N Rothblum, and Ron D Rothblum. Constant-round interactive proofs
for delegating computation. In Proceedings of the forty-eighth annual ACM symposium on
Theory of Computing, pages 49–62. ACM, 2016.
[RT19] Ran Raz and Avishay Tal. Oracle separation of BQP and PH. In Proceedings of the 51st
Annual ACM SIGACT Symposium on Theory of Computing, pages 13–23, 2019.
[RUV13] Ben W Reichardt, Falk Unger, and Umesh Vazirani. Classical command of quantum systems.
Nature, 496(7446):456–460, 2013.
[Sha92] Adi Shamir. IP= PSPACE. Journal of the ACM (JACM), 39(4):869–877, 1992.
[Slo19] William Slofstra. The set of quantum correlations is not closed. In Forum of Mathematics,
Pi, volume 7. Cambridge University Press, 2019.
[SW87] Stephen J Summers and Reinhard Werner. Maximal violation of bell’s inequalities is generic
in quantum field theory. Communications in Mathematical Physics, 110(2):247–259, 1987.
[Tsi93] Boris S Tsirelson. Some results and problems on quantum Bell-type inequalities. Hadronic
Journal Supplement, 8(4):329–345, 1993.
[Vid19] Thomas Vidick. From operator algebras to complexity theory and back. Notices of the
American Mathematical Society, 66(10), 2019.
[Vid20] Thomas Vidick. Verifying quantum computations at scale: A cryptographic leash on quantum
devices. Bulletin of the American Mathematical Society, 57(1):39–76, 2020.
127
[VW16] Thomas Vidick and John Watrous. Quantum proofs. Foundations and Trends R in Theoreti-
cal Computer Science, 11(1-2):1–215, 2016.
[VZ20] Thomas Vidick and Tina Zhang. Classical proofs of quantum knowledge. arXiv preprint
arXiv:2005.01691, 2020.
[WBMS16] Xingyao Wu, Jean-Daniel Bancal, Matthew McKague, and Valerio Scarani. Device-
independent parallel self-testing of two singlets. Physical Review A, 93(6):062121, 2016.
[WZ17] Daniel Wichs and Giorgos Zirdelis. Obfuscating compute-and-compare programs under
LWE. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS),
pages 600–611. IEEE, 2017.
[Yue16] Henry Yuen. A parallel repetition theorem for all entangled games. In 43rd International
Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss Dagstuhl-
Leibniz-Zentrum fuer Informatik, 2016.
128