Test for a large amount of entanglement,
using few measurements
Rui Chao
1
, Ben W. Reichardt
1
, Chris Sutherland
1
, and Thomas Vidick
2
1
University of Southern California
2
California Institute of Technology
Bell-inequality violations establish that two systems share some quantum entangle-
ment. We give a simple test to certify that two systems share an asymptotically large
amount of entanglement, n EPR states. The test is efficient: unlike earlier tests that
play many games, in sequence or in parallel, our test requires only one or two CHSH
games. One system is directed to play a CHSH game on a random specified qubit i,
and the other is told to play games on qubits {i, j}, without knowing which index is i.
The test is robust: a success probability within δ of optimal guarantees distance
O
(
n
5/2
δ
)
from n EPR states. However, the test does not tolerate constant δ; it breaks
down for δ
=
˜
(1
/
n
)
. We give an adversarial strategy that succeeds within δ of the
optimum probability using only
˜
O(δ
2
) EPR states.
1 Introduction
Entanglement separates quantum from classical physics, and is a key source for the power of
quantum-mechanical devices. A natural experimental challenge, to advance our quantum engineer-
ing skills and possibly test quantum physics itself, is to generate highly entangled states. However,
for studying the foundations of physics and for cryptographic applications, it is important to take
a conservative, adversarial perspective. A convincing test for entanglement must avoid modeling
assumptions—such as that experimental operation X, perhaps shining a laser, implements a unitary
X on a particular qubit—or even the assumption that the system is quantum-mechanical at all. A
system may appear to be entangled under simple tests, and yet its behavior might still have an
underlying classical explanation.
Recently, “loophole-free” Bell-inequality violations have been demonstrated [H
+
15, H
+
16, S
+
15,
G
+
15]. These experiments establish that there exists some entanglement between two experimental
systems, ruling out classical local-hidden-variable models, in a very adversarial setting. Following
the rules of the CHSH game [CHSH69], they ask random questions to the two systems—electrons
separated by over a kilometer in [H
+
15]—and security is based on the space-like separation of the
measurements giving the answers. This separation prevents any collusion, even with signals moving
at the speed of light. The results are up to high statistical confidence, because unentangled systems
could get lucky and pass the tests by chance.
Beyond showing some entanglement, how can one certify that two systems are highly entangled?
Accepted in Quantum 2018-08-17, click title to verify 1
arXiv:1610.00771v2 [quant-ph] 30 Aug 2018
We address this natural question. We develop a test for n EPR states worth of entanglement,
1
2
n
(|00i + |11i)
n
. We will explain this test below, but first let us give some more context.
A Bell-inequality violation certifies that there is some entanglement; a nearly optimal violation
can certify that the entanglement is of the specific form of an EPR state [MMMO06, MYS12,
RUV13]. Wu et al. [WBMS16] have shown that two CHSH games, played in parallel, can be
used to test for n
= 2
EPR states. One might reasonably suppose that if playing one or two
CHSH games can show some entanglement, then playing many CHSH games should suffice to show
lots of entanglement. It is not so simple. Different games need not be independent from each
other, and complicated dependencies could conceivably allow low-dimensional systems to act like
higher-dimensional ones [CRSV17].
The first test for asymptotically many EPR states was given in [RUV13]. The motivation for
this test was to develop a scheme for delegated quantum computation, allowing one to securely run
a quantum circuit across several untrusted devices. The test tolerates polynomially small deviations
from the ideal behavior, and in principle can be run with polynomial overhead, but it is severely
impractical. The ideal systems need to share much more entanglement, N
=
n
O(1)
n EPR states,
than is being certified. The test is based on playing N CHSH games sequentially. This is highly
constraining: the answer to one game must be given before the question for the next game, and
yet the whole sequence of questions and answers must be space-like separated from one system to
the other. Finally, the test tolerates only an inverse-polynomial error rate in the systems.
McKague [McK16] gave a much-improved test for n EPR states. His test uses only n EPR states;
none are lost in the analysis. They are all measured, and the measurements must still be space-like
separated from one system to the other, but they can be performed in parallel. The final distance
from
1
2
n
(
|00i
+
|11i
)
n
, in Euclidean norm, is O
(
n δ
1/8
)
, where δ is an upper bound on the error
for each of
˜
O
(
n
)
test settings. Thus to achieve error , one should set δ
8
/n
4
, so each EPR
state and one-qubit measurement should have error δ/n
8
/n
5
. Then
˜
O
(
n ·
1
2
) =
˜
O
(
n
9
/
16
)
experiments suffice to establish, say, 99% statistical confidence.
Our test is simpler. Let i and j be uniformly random distinct indices between
1
and n.
Conceptually, the key component of the test amounts to giving the first system {i, j} and the
second system i, or vice versa; ask each system to play CHSH games on the specified qubits. (See
Section 3 for a complete description of the protocol, which involves a couple other sub-tests.) Thus
most of the EPR states are not destructively measured, so they can be used later.
We show that passing our test with probability within δ of the optimal value implies that the
systems are O
(
n
5/2
δ
)
close to n EPR states. Therefore to achieve a final error of , the error on
individual EPR states and one-qubit measurements can be δ
2
/n
5
. To achieve a given statistical
confidence, O
(1
2
) =
O
(
n
10
/
4
)
experiments suffice.
1
This is obviously quite inefficient; the main
novelty and advantage of our protocol is its simple form.
The intuition behind our test is as follows. Call the two systems Alice and Bob. If they truly
share n EPR states, then it is easy for them to pass the test. In general, Alice and Bob can do
anything at all. For example, they might try to devise some scheme that uses only n
1
EPR
states. The reason that n EPR states are required is that when Bob is asked {i, j} he has to select
two qubits, one of which will be tested for entanglement with Alice—and he does not know which
one. Monogamy of entanglement prevents both qubits from simultaneously forming EPR states
1
Avoiding a Markov inequality in the proof can improve this to O(n
9
/
4
).
2
with Alice’s qubit. Therefore (skipping over some arguments), Alice and Bob must share two EPR
states. Chaining together pairwise statements like this establishes that they share n EPR states.
Note that this test requires very little processing to test a high-dimensional quantum state, as
the number of possible operations to be performed scales quadratically with the number of qubits
tested. This contrasts with the exponential number of possibilities required for parallel self-tests.
Possibly a further value is that the test is largely nondestructive; only two of the n EPR states are
measured in the test, leaving n 2 verified EPR states for other uses.
The practical usefulness of the test, however, depends on its tolerance to imperfections. We
characterize a test as “robust” if the guaranteed distance to the target state scales polynomially
with the sub-optimality incurred by, say, instrumental imperfection. Precisely, we say that a test
has “robustness f
(
n, δ
)
if a success probability that is δ-close to optimal guarantees a distance
f
(
n, δ
)
to the target state. For example, the test from [RUV13] is robust, and our test is robust
as well: the dependence on errors grows only polynomially in n, not exponentially. This is not to
say that the test can readily be implemented experimentally. Might a stronger analysis show, for
example, that if Alice and Bob pass the test with
99%
probability, then they must share a state
with
99%
fidelity to
1
2
n
(
|00i
+
|11i
)
n
? No. We give an explicit construction by which Alice
and Bob can use logarithmically many EPR states, O
1
δ
2
log n
, to pass the test with probability
within δ of the optimal value. This implies that the analysis breaks down for δ
= Ω(
p
(log n)/n
)
.
The test does not tolerate constant error rates. (A similar limitation will likely hold for other tests
that consider only two qubits at a time [CRSV17].)
Our strategy for exhibiting n qubits is based on a technique first used in [KKM
+
11]. We intro-
duce two main ideas. The first consists in combining
2
n
(
n
1)
pairwise approximate commutation
relations
[
P
i
, Q
j
]
|ψi
0
, for P, Q {X, Z} and i 6
=
j, with the exact commutation that always
exists between an operator on Alice’s Hilbert space H
A
and an operator on Bob’s space H
B
. We
crucially use the fact that, as a consequence of the CHSH test, an operator P
i
or Q
j
can be “pulled”
from H
A
to H
B
, at which point it commutes with any operator on H
A
. This operation allows us to
control the error blow-up that would become unmanageable if we only had access to a single space H.
The second idea is to enforce the desired approximate commutation
[
P
i
, Q
j
]
|ψi
0
through the use
of an intermediate set of operators, P
{i,j}
i
and Q
{i,j}
j
, that are obtained by adding an additional test
in which the CHSH test is executed on a pair {i, j} of (purported) qubits. The use of a “dummy
question” was first introduced in [IKM09] for the purposes of inducing approximate commutation,
and we show that it can be effectively leveraged in our context as well.
Although our main result is based on the CHSH test and the use of EPR states, we show in
Appendix A that the result can be generalized to separate qubits via any two-qubit state entangled
across H
A
H
B
. It is an open question whether similar results can be attained based on higher-
dimensional partially entangled states.
Recently, several other entanglement tests have been given. Coudron and Natarajan [CN16] and
Coladangelo [Col17] study parallel repetition of the Magic Square game [Mer90, Per90], achieving
robustness of O
(
n
2
δ
)
and O
(
n
3/2
δ
)
, respectively. The optimal success probability for this game
is
1
, which allows for a more efficient analysis in comparison to the CHSH game. They also
require fewer experiments to achieve certain statistical confidence. Natarajan and Vidick [NV17]
leverage a quantum version of the linearity test by Blum et al. [BLR93], and obtain robustness
that is independent of n. Their test is rather complex and requires the verifier to choose among
exponentially many possible questions. This was recently improved [NV18] to a test that achieves
simultaneously poly
(
n
)
questions and constant robustness (O
(
δ
)
). Subsequently to our work,
3
Ostrev and Vidick [OV16] apply our Theorem 2.1 to analyze a simpler XOR game than ours,
resulting in similar number of possible questions, but slightly weaker robustness guarantees. It
is an open question to determine the best trade-offs in terms of robustness, number of questions,
and number of EPR pairs tested. Robust protocols certifying a large amount of entanglement,
without explicitly certifying that the state must be (close to) maximally entangled, are provided
in [CS17, AY17, AB17].
1.1 Notation
Denote the EPR state by |EPRi
=
1
2
(
|00i
+
|11i
)
. Let
[
n
] =
{
1
, . . . , n}. The Pauli matrices are
I
=
1 0
0 1
, σ
x
=
0 1
1 0
, σ
y
=
0 i
i 0
and σ
z
=
1 0
0 1
. On higher-dimensional spaces, we will denote
the identity operator by 1.
We consider Hilbert spaces H
A
, H
A
0
, H
B
, H
B
0
, etc., which for clarity are labeled by the register
A, A
0
, B or B
0
that contains the quantum state whose state space they represent. Each such space
is assumed to be finite dimensional. We will use the letter D as a variable which ranges over a
subset of {A, A
0
, B, B
0
, . . .} that will be clear from context.
2 State-dependent separation of n EPR states
In this section we prove a separation theorem for qubits that satisfy certain state-dependent
commutation relations. In Section 3 we provide a simple protocol that can establish the state-
dependent assumptions in an experimental setting.
Theorem 2.1.
Let
|ψi H
A
H
B
, with
k|ψik
= 1. Assume that for
j
[
n
] we are given reflections
(X
j
)
A
, (Z
j
)
A
L(H
A
) and (X
j
)
B
, (Z
j
)
B
L(H
B
)
that for D either A or B, all i 6= j, and P, Q either X or Z, satisfy {(X
j
)
D
, (Z
j
)
D
} = 0 and
[P
i
, Q
j
]
D
|ψi
(P
j
)
A
(P
j
)
B
|ψi |ψi
.
Let
|ψ
0
i = |ψi |EPRi
n
A
0
|EPRi
n
B
0
H
A
(C
2
)
2n
A
0
H
B
(C
2
)
2n
B
0
.
Then for
D {A, B}
, there exist reflections
X
0
1
, Z
0
1
, . . . , X
0
n
, Z
0
n
on
H
D
(
C
2
)
2n
D
0
, with
{X
0
j
, Z
0
j
}
= 0,
[P
0
i
, Q
0
j
] = 0 for i 6= j, and
P
0
j
P
j
1
D
0
|ψ
0
i
= O(n), and furthermore satisfying
2
(P
0
j
)
AA
0
(P
0
j
)
BB
0
|ψ
0
i |ψ
0
i
= O(n) . (1)
In words, the assumption of the theorem is that Alice and Bob have n overlapping qubits,
with Pauli operators on different qubits nearly commuting on |ψi, and such that |ψi is nearly
stabilized by
(
X
j
X
j
)
AB
and
(
Z
j
Z
j
)
AB
for each j. Note that these assumptions are satisfied
by |ψi = |EPRi
n
AB
and X
j
= σ
x
j
, Z
j
= σ
z
j
, with = 0.
2
For notational sanity, we suppress some subscripts
D
or
D
0
. Of course operators
P
0
j
acting on
AA
0
and
BB
0
are
in general different.
4
The conclusion of the theorem is that, up to local isometries (that introduce the ancillary states
|EPRi
n
A
0
and |EPRi
n
B
0
), there exist n non-overlapping qubits for each of Alice and Bob, with
associated Pauli operators
(
P
0
j
)
DD
0
, that on the extended state |ψ
0
i are nearly the same as the
original qubits’ Pauli operators, and such that |ψ
0
i is nearly stabilized by
(
X
0
j
X
0
j
)
AA
0
BB
0
and
(
Z
0
j
Z
0
j
)
AA
0
BB
0
. By [CRSV17, Theorem 2.3], there are local changes of basis under which these
new qubits are in tensor product. Since |EPRi is the unique pure state stabilized by both σ
x
σ
x
and σ
z
σ
z
, it follows that |ψ
0
i is close to n EPR states between Alice and Bob, plus an extra
ancillary state, with X
0
j
, Z
0
j
the standard Pauli operators on one half of the jth EPR state. We
state this as a corollary to Theorem 2.1:
Corollary 2.2.
Under the assumptions of Theorem 2.1, there are unitaries
U
D
:
H
D
(
C
2
)
2n
D
0
(C
2
)
n
D
ˆ
H
D
, for D {A, B}, and a state |extrai
ˆ
H
A
ˆ
H
B
such that
U
A
U
B
|ψ
0
i |EPRi
n
AB
|extrai
= O(n
3/2
)
k(UX
j
U
σ
x
j
1
ˆ
H
)
D
|EPRi
n
AB
|extraik = O(n
3/2
)
k(UZ
j
U
σ
z
j
1
ˆ
H
)
D
|EPRi
n
AB
|extraik = O(n
3/2
) .
Proof.
Theorem 2.3 in [
CRSV17
] gives an isomorphism from
H
0
D
to (
C
2
)
n
D
ˆ
H
D
under which the
(
X
0
j
)
D
and (
Z
0
j
)
D
promised by Theorem 2.1 are simply
σ
x
j
1
ˆ
H
D
and
σ
z
j
1
ˆ
H
D
, respectively. The
first claim below then shows that Eq. (1) implies that under this isometry
|ψ
0
i
must be close to an
EPR state on the jth qubits, for every j [n].
Claim 2.3.
There exists a universal constant
c
such that: if
|φi C
2
C
2
H
is a state with
kσ
x
1
σ
x
2
|φi |φik, kσ
z
1
σ
z
2
|φi |φik δ, then for some state |φ
0
i H,
|φi |EPRi |φ
0
i
c δ .
Proof.
Expand
|φi
=
P
a,b∈{0,1}
|a, bi|φ
a,b
i
. Then
kσ
z
1
σ
z
2
|φi |φik
2
= 4(
k|φ
01
ik
2
+
k|φ
10
ik
2
) and
kσ
x
1
σ
x
2
|φi |φik
2
=
P
a,b
k|φ
ab
i |φ
¯a
¯
b
ik
2
. The conclusion follows, for |φ
0
i = |φ
00
i/k|φ
00
ik.
The next claim completes the proof by showing that if
|ψ
0
i
is
δ
-close to an EPR state on each of
n registers, then it is O(
)-close to n EPR states.
Claim 2.4.
If
|ψi
(
C
d
)
n
H
and
|φ
1
i, . . . , |φ
n
i
(
C
d
)
(n1)
H
are states such that for all
j [n], k|ψi |1i
j
|φ
j
i
j
k δ, then there exists a state |ϕi H such that
|ψi |1i
n
|ϕi
2 .
Proof.
Expand
|ψi
=
P
x[d]
n
|xi|α
x
i
. For each
j
, the state
|φ
j
i
that minimizes
k|ψi |1i
j
|φ
j
i
j
k
is given by |
ˆ
φ
j
i/k
ˆ
φ
j
k, where |
ˆ
φ
j
i =
P
x:x
j
=1
|x
j
i|α
x
i. Then
δ
2
|ψi |1i
j
1
k
ˆ
φ
j
k
|
ˆ
φ
j
i
j
2
=
|1i
j
1
1
k
ˆ
φ
j
k
|
ˆ
φ
j
i +
|ψi |1i
j
|
ˆ
φ
j
i
2
=
1 k
ˆ
φ
j
k
2
+
X
x:x
j
6=1
k|α
x
ik
2
= 2 2k|
ˆ
φ
j
ik .
5
Thus for each
j
, we have
P
x:x
j
6=1
kα
x
k
2
δ
2
. Under the constraint
P
x
kα
x
k
2
= 1 and by a union
bound, we have kα
1
n
k
2
1
2
. Provided that
2
< 1, kα
1
n
k > 0.
Letting |ϕi = |α
1
n
i/kα
1
n
k, we get
|ψi |1i
n
|ϕi
2
= 2 2kα
1
n
k
2 2
p
1
2
2
2
.
This gives the bound
k|ψi |1i
n
|ϕik
2
provided
δ <
1
/
n
. If
δ
1
/
n
, it is still easy to
choose a state |ϕi so k|ψi |1i
n
|ϕik
2
2.
Corollary 2.2 follows.
Proof of Theorem 2.1.
The idea for the proof is as follows. There are
n
overlapping qubits on Alice’s
side, and another n overlapping qubits on Bob’s side. The assumptions of the theorem imply that
for each
j
, the joint state of Alice and Bob’s qubits
j
is close to an EPR state. For the analysis,
we sequentially swap in fresh qubits in order to force a tensor-product structure. Since there is
an underlying state,
|ψi
, we need to specify a state for the fresh qubits. The natural choice is the
maximally mixed state,
1
2
I
, because locally this looks the same as half of an EPR state, and thus
Alice and Bob’s local operators cannot tell that we have changed the state from underneath them.
On Alice’s side, therefore, the local isometry adds
n
1 EPR states (entirely on Alice’s side, not
crossing between Alice and Bob). Half of each EPR state is unused, and we swap in the other half,
which looks maximally mixed.
We proceed with the details. For each
j
, let (
S
j
)
AA
0
be the operator on
H
A
(
C
2
)
2n
A
0
that
swaps Alice’s jth qubit, defined by (X
j
)
A
, (Z
j
)
A
, with half of the jth appended EPR state:
(S
j
)
AA
0
=
1
2
1 1 + X
j
σ
x
2j1
+ Z
j
σ
z
2j1
+ i(X
j
Z
j
) σ
y
2j1
AA
0
.
For P either X or Z, define (P
0
j
)
AA
0
by
P
0
j
= (S
1
···S
j1
) (P
j
1) (S
j1
···S
1
) .
Then for P, Q {X, Z} and i < j,
k[P
0
i
, Q
0
j
]k = k[S
i
(P
i
1)S
i
, S
i+1
···S
j1
(Q
j
1)S
j1
···S
i+1
]k = 0 ,
since
S
i
(
P
i
1
)
S
i
is a Pauli on the (2
i
1)th added qubit, on which the other term has no dependence.
Let
(S
0
j
)
BA
0
=
1
2
1 1 + X
j
σ
x
2j
+ Z
j
σ
z
2j
+ i(X
j
Z
j
) σ
y
2j
BA
0
be the operator that swaps Bob’s
j
th qubit with the other half of Alice’s
j
th appended EPR state.
Then we compute
(P
0
j
)
AA
0
|ψ
0
i = (S
1
···S
j1
P
j
S
j1
···S
1
)
AA
0
|ψ
0
i
(S
1
···S
j1
P
j
S
j1
)
AA
0
(S
0
1
···S
0
j2
)
BA
0
|ψ
0
i (Lemma 2.5)
(S
1
···S
j2
P
j
)
AA
0
(S
0
1
···S
0
j2
)
BA
0
|ψ
0
i (Lemma 2.6)
···
(P
j
)
A
|ψ
0
i ,
6
Figure 1: Two ways of swapping halves of EPR states, that both lead to the same result.
where each approximation holds up to order
in Euclidean norm. The first approximation, pulling
S
j2
···S
1
over to Bob’s side, is by Lemma 2.5 below. The next line, commuting
S
j1
past
P
j
on
|ψ
0
i
, is by Lemma 2.6. The argument continues by pulling one
S
0
i
at a time back to Alice’s side,
where it can be commuted past P
j
. Overall, the error is k(P
0
j
)
AA
0
|ψ
0
i (P
j
)
A
|ψ
0
ik = O(n).
The same argument can be repeated for swap operators (
S
j
)
BB
0
defined on Bob’s side. Thus
k(P
0
j
)
BB
0
|ψ
0
i (P
j
)
B
|ψ
0
ik = O(n), and so in particular
(P
0
j
)
AA
0
(P
0
j
)
BB
0
|ψ
0
i |ψ
0
i
(P
0
j
P
0
j
)
AA
0
BB
0
|ψ
0
i (P
j
P
j
)
AB
|ψ
0
i
+
(P
j
P
j
)
AB
|ψ
0
i |ψ
0
i
= O(n) ,
as claimed.
Lemmas 2.5 and 2.6 are simple calculations based on the triangle inequality.
Lemma 2.5.
(S
i
)
AA
0
|ψ
0
i (S
0
i
)
BA
0
|ψ
0
i
= O().
Proof.
If we had (
X
i
)
A
(
X
i
)
B
|ψi
=
|ψi
= (
Z
i
)
A
(
Z
i
)
B
|ψi
, then we would have (
S
i
)
AA
0
|ψ
0
i
=
(
S
0
i
)
BA
0
|ψ
0
i
exactly, since the EPR state is uniquely stabilized by both
σ
x
σ
x
and
σ
z
σ
z
. See
Figure 1. Thus
(S
i
)
AA
0
|ψ
0
i (S
0
i
)
BA
0
|ψ
0
i
|ψ
0
i |ψ
00
i
+
|ψ
00
i (S
i
)
AA
0
(S
0
i
)
BA
0
|ψ
0
i
2
c
,
where
|ψ
00
i
restricted on Alice’s and Bob’s
i
th qubits is an EPR state and
c
is the constant from
Claim 2.3.
Lemma 2.6. For i 6= j,
[S
i
, P
j
1]
AA
0
|ψ
0
i
= O().
Proof.
Use the definition of
S
i
in terms of
X
i
and
Z
i
, which by assumption nearly commute with
P
j
on |ψi.
3 A protocol for testing n qubits
It remains to explain how the mathematical assumptions of Theorem 2.1 can be established in
an experiment. The assumption that
(
P
j
)
A
(
P
j
)
B
|ψi |ψi is straightforward to establish by
testing for an EPR state using the CHSH game; see Section 3.1 below. The EPR state |EPRi
=
1
2
(|00i + |11i) is an eigenvalue-one eigenvector of both σ
x
σ
x
and σ
z
σ
z
.
The assumption that
[
P
i
, Q
j
]
D
|ψi
0
for any i 6
=
j seems more difficult to establish, because
it involves
(
P
i
)
D
acting on
(
Q
j
)
D
|ψi, not just on |ψi directly. The main idea to obtain constraints
on quantities such as
(
P
i
Q
j
)
D
|ψi is to use both players, and design a test where the second player
performs a measurement that relates to both P
i
and Q
j
. In Section 3.2 we present a simple protocol
for which the soundness analysis uses this argument.
7
Player 1
Verier
Player 2
a
x
y
b
xy
?
=(1)
ab
Figure 2: The CHSH game. The messages a, b are in {0, 1}, and x, y {1, 1}.
3.1 The CHSH game
In Section 3.2 below we give a protocol that can experimentally establish the assumptions of
Theorem 2.1. This protocol is built on the Clauser-Horne-Shimony-Holt (CHSH) game [CHSH69].
Before presenting our protocol, let us review the CHSH game.
The CHSH game involves a verifier and two players. The verifier chooses uniformly random
bits a, b {
0
,
1
}. As shown in Figure 2, she sends a to the first player, and b to the second player.
The players share a quantum state but cannot communicate. Each player applies a two-outcome
measurement, depending on her input. They return their respective outcomes, x and y in {
1
,
1
},
to the verifier. The players win if xy = (1)
ab
.
A general strategy for the CHSH game consists of Hilbert spaces H
1
, H
2
, a state |ψi H
1
H
2
,
and reflections
(
R
0
)
D
,
(
R
1
)
D
L
(
H
D
)
for D {
1
,
2
}. On receiving c {
0
,
1
}, each player measures
R
c
and returns the outcome. Using this strategy, the players win with probability
1
2
+
1
8
hψ|
R
0
R
0
+ R
0
R
1
+ R
1
R
0
R
1
R
1
|ψi .
The maximum probability of winning is cos
2
π
8
0
.
85
. A strategy achieving this probability
uses |ψi
=
|EPRi C
2
C
2
, and the reflections
(
R
0
)
1
=
σ
z
,
(
R
1
)
1
=
σ
x
for player
1
, and
(R
0
)
2
= H =
1
2
1 1
1 1
, (R
1
)
2
= σ
x
Hσ
x
for player 2.
In fact, up to local changes of basis and choice of an ancillary state, this is the only optimal
strategy [MYS12, RUV12]. We will use:
Lemma 3.1
([
RUV12
, Lemma 4.2])
.
Consider a strategy for the CHSH game that wins with
probability at least
cos
2
π
8
γ
for some
γ >
0. Assume that for
D {
1
,
2
}
, the reflections (
R
c
)
D
each have both ±1 eigenspaces of the same dimension. Then the following properties hold:
For each
D {
1
,
2
}
, there is an isomorphism between player
D
’s Hilbert space and
C
2
ˆ
H
D
,
under which (
R
0
)
D
=
σ
z
1
and
(R
1
σ
x
1)
D
|ψi
=
O
(
γ
). The isomorphism depends
only on (R
0
)
D
and (R
1
)
D
.
There exists a unit vector |
ˆ
ψi
ˆ
H
1
ˆ
H
2
such that for G = exp(i
π
8
σ
y
),
|ψi (I (HG)|EPRi)|
ˆ
ψi
= O(
γ) .
Thus the CHSH game provides a test to establish that both players measure a single qubit in
a shared EPR state. Our protocol for testing n qubits uses many embedded CHSH games.
8
3.2 A protocol for testing n qubits
In this section, we describe and analyze a simple protocol, between a verifier and two players,
Alice and Bob, that can experimentally establish the assumptions of Theorem 2.1. Recall, these
assumptions are that Alice and Bob each have n overlapping qubits, such that the joint two-qubit
state of their jth qubits is close to an EPR state, for every j, and with Pauli operators on different
qubits nearly commuting on |ψi. Intuitively, approximate EPR states are easily established using
the CHSH game. The last commutation assumption is harder to establish.
For example, one possible protocol might have the verifier choose a random index j
[
n
]
, send
j to both players, and ask them to play a CHSH game on the jth of n shared EPR states. Honest
players, who indeed shared |EPRi
n
, could pass this protocol. However, dishonest players could
also pass this protocol by ignoring j and using always the same EPR state to play all CHSH games.
In this case, each player’s n qubits would all be the same qubit, so the protocol is inadequate.
Our protocol overcomes this flaw. It is as follows:
Protocol for testing n qubits
A verifier interacts with two players, Alice and Bob. With equal probabilities
1
/
3
, the verifier
runs one of the following sub-protocols:
1. Choose i
[
n
]
and a {
0
,
1
} uniformly at random. Send
(
i, a
)
to each player. Alice and Bob
reply, respectively, with x, y {1, 1}. Accept if and only if x = y.
2. Choose i, j
[
n
]
, i 6
=
j, and bits a, b, c {
0
,
1
} uniformly at random. Send Alice
(
i, a
)
, and
send Bob
(
i, b
)
,
(
j, c
)
if i < j, or
(
j, c
)
,
(
i, b
)
if j < i. Alice returns x
1
}. Bob returns
y and y
0
in
1
}, ordered to correspond respectively to
(
i, b
)
and
(
j, c
)
. Accept if and only if
xy = (1)
ab
.
3. The same as sub-protocol 2, but with the roles of Alice and Bob exchanged.
Observe that embedded within this protocol are
4
n
(
n
1)
CHSH games. In sub-protocol
2
,
for example, for every i 6
=
j and c {
0
,
1
}, Alice and Bob are playing a CHSH game. In general,
Alice’s strategy for the CHSH game can depend on i, while Bob’s strategy can depend on i, j and c.
The key ingredient in the protocol is the “dummy” question j used in parts
2
and
3
. Given
the indices {i, j}, Bob does not know which index was given to Alice. Intuitively, this forces Bob
to measure two independent qubits for his responses y and y
0
. In our analysis below, it allows
us to establish the state-dependent commutation relationship between Alice’s ith and jth qubits:
max
P,Q∈{X,Z}
k[P
i
, Q
j
]
A
|ψik
0
. The dummy question is related to the technique of oracularization
in complexity theory. To our knowledge, this was first used in the context of two-player quantum
games in [IKM09].
Note that Alice cannot distinguish between the first and second sub-protocols, and Bob cannot
distinguish between the first and third sub-protocols. The role of the first sub-protocol is to establish
consistency between Alice and Bob’s ith qubits, without dependence on (j, c).
3
Let us now analyze the completeness and soundness of this protocol.
3
The first sub-protocol could also be replaced with standard CHSH games.
9
3.2.1 Completeness
Honest players Alice and Bob, sharing n EPR states, |EPRi
n
, play as follows:
If given a single tuple
(
i, a
)
, the player measures her share of the ith EPR state with σ
z
if
a = 0, or with σ
x
if a = 1. She returns the measured eigenvalue.
If given two tuples
(
i, b
)
and
(
j, c
)
, the player measures her share of the ith EPR state with
H
=
1
2
1 1
1 1
if b
= 0
, or with σ
x
Hσ
x
if b
= 1
. She returns the measured eigenvalue. To
determine y
0
, she uses the same rules to measure the jth EPR state depending on c.
These strategies correspond to using the indicated qubits i and j to play CHSH games following
the optimal strategy from Section 3.1, where the player given a single tuple takes the role of CHSH
game player 1 and the player given two tuples takes the role of CHSH game player 2.
When Alice and Bob follow this honest strategy, they pass sub-protocol
1
with probability
1
,
and they pass sub-protocols
2
and
3
with probability cos
2
π
8
, the optimal success probability for a
CHSH game. Overall the verifier accepts with probability
ω
opt
:=
1
3
(1 + 2 cos
2
π
8
) 0.90 . (2)
3.2.2 Soundness
In general, a strategy for Alice and Bob consists of:
Finite-dimensional Hilbert spaces H
A
, H
B
, and a shared state |ψi H
A
H
B
.
Reflections
(
Z
i
)
D
,
(
X
i
)
D
L
(
H
D
)
, for D {A, B}. On question
(
i,
0)
, player D measures
(
Z
i
)
D
and returns the measured eigenvalue ±
1
; on question
(
i,
1)
, she returns the result of
measuring (X
i
)
D
. Note that (Z
i
)
D
and (X
i
)
D
need not anti-commute.
For each D {A, B}, for every i < j and b, c {
0
,
1
}, a complete set of orthogonal projections
{
(i,b),(j,c)
x,y
)
D
:
x, y
1
}}. On receiving question
(
i, b
)
,
(
j, c
)
, player D measures |ψi with
the projections and returns the results x, y.
Naimark’s theorem ensures the assumption of projective measurements is without loss of generality.
We state the results of the soundness analysis as a theorem:
Theorem 3.2.
Consider a strategy that is accepted with probability at least
ω
opt
δ
, with
δ >
0.
Then there exist spaces
H
0
A
,
H
0
B
extending
H
A
, H
B
respectively, and extensions of the (
Z
i
)
D
to
H
0
D
by a direct sum with other reflections, and reflections (
¯
X
i
)
D
such that
{
(
Z
i
)
D
,
(
¯
X
i
)
D
}
= 0,
k(X
i
¯
X
i
)
D
|ψik = O(n
δ), and
max
i,j[n], i6=j
P,Q∈{
¯
X,Z}
[P
i
, Q
j
]
D
|ψi
= O(n
δ)
max
i[n],P ∈{
¯
X,Z}
(P
i
)
A
(P
i
)
B
|ψi |ψi
= O(n
δ) .
In particular, the conclusions of this theorem are exactly the assumptions required to apply
Theorem 2.1 and Corollary 2.2, with
=
O
(
n
δ
)
. Thus, combining Theorem 3.2 and Corollary 2.2,
directly leads to the robustness guarantee O(n
5/2
δ) claimed in the introduction.
10
Proof. For each D {A, B}, for i < j, define reflections (R
jc
ib
)
D
by
R
jc
ib
=
X
x∈{±1}
x ·
Π
(i,b),(j,c)
x,1
+ Π
(i,b),(j,c)
x,1
.
Thus
R
jc
ib
is the reflection measured to determine the response to (
i, b
), marginalized over the
response to (j, c). Similarly, for i > j, define R
jc
ib
=
P
x,y∈{±1}
y Π
(j,c),(i,b)
x,y
. Then for i 6= j,
R
jc
ib
, R
ib
jc
= 0 . (3)
Since the optimal probability of winning a CHSH game is
cos
2
π
8
, the maximum probability that
the verifier can accept in sub-protocols 2 and 3 is also
cos
2
π
8
. In particular, by a Markov inequality,
this implies that the probability that Alice and Bob win in sub-protocol 1, conditioned on the
verifier having chosen i [n], is at least 1 3. Hence, by a straightforward calculation,
max
n
(X
i
)
A
(X
i
)
B
|ψi |ψi
,
(Z
i
)
A
(Z
i
)
B
|ψi |ψi
o
2
3 . (4)
Again by a Markov inequality, for each of the 4
n
(
n
1) CHSH games embedded in sub-protocols 2
and 3, the success probability is at least
cos
2
π
8
6
n
(
n
1)
δ
. Therefore Lemma 3.1 applies to each
game. (The condition on each observable’s two eigenspaces having the same dimension is easily
satisfied by at most doubling the dimension of the Hilbert space.)
Consider the game in sub-protocol 2 specified by
i 6
=
j
and
c {
0
,
1
}
. The CHSH game
measurement operators are (
R
0
)
1
= (
Z
i
)
A
, (
R
1
)
1
= (
X
i
)
A
and (
R
b
)
2
= (
R
jc
ib
)
B
for
b
= 0
,
1. From
Lemma 3.1 we obtain that there exists a reflection (
¯
X
i
)
A
, depending only on
i
(not
j
or
c
), such
that
{Z
i
,
¯
X
i
}
= 0 and
k(X
i
¯
X
i
)
D
|ψik
=
O
(
n
δ
). In particular, from Eq. (4) this implies that
(
¯
X
i
)
A
(
¯
X
i
)
B
|ψi |ψi
= O(n
δ).
Recall that in the ideal CHSH game strategy from Section 3.1, (
R
b
)
2
=
1
2
(
σ
z
+ (
1)
b
σ
x
). Also
|EPRi
is fixed by
1
2
(
σ
z
+ (
1)
b
σ
x
)
2
. From Lemma 3.1, the actual measurement operators have
an action on
|ψi
that is close to that of these ideal operators, and
|ψi |EPRi |
ˆ
ψi
. Combining
these bounds using triangle inequalities gives
1
2
(Z
i
+ (1)
b
¯
X
i
)
A
(R
jc
ib
)
B
|ψi |ψi
= O(n
δ) . (5)
We will use the bounds in Eq. (5) to show that [
P
i
, Q
j
]
A
|ψi
0 for
P, Q {
¯
X, Z}
and
i 6
=
j
.
For i 6= j, we compute that for b, c {0, 1},
1
2
(Z
i
+ (1)
b
¯
X
i
)
A
1
2
(Z
j
+ (1)
c
¯
X
j
)
A
|ψi
1
2
(Z
i
+ (1)
b
¯
X
i
)
A
(R
ib
jc
)
B
|ψi
(R
ib
jc
R
jc
ib
)
B
|ψi
= (R
jc
ib
R
ib
jc
)
B
|ψi
1
2
(Z
j
+ (1)
c
¯
X
j
)
A
(R
jc
ib
)
B
|ψi
1
2
(Z
j
+ (1)
c
¯
X
j
)
A
1
2
(Z
i
+ (1)
b
¯
X
i
)
A
|ψi ,
where each approximation is up to error
O
(
n
δ
) in Euclidean distance, by Eq. (5), and the middle
equality is by Eq. (3). Thus we have
Z
i
+ (1)
b
¯
X
i
, Z
j
+ (1)
c
¯
X
j
A
|ψi
=
O
(
n
δ
). Taking sums
and differences of these bounds, it follows that
max
k[Z
i
, Z
j
]
A
|ψik, k[Z
i
,
¯
X
j
]
A
|ψik, k[
¯
X
i
, Z
j
]
A
|ψik, k[
¯
X
i
,
¯
X
j
]
A
|ψik
= O(n
δ) .
The bound max
P,Q∈{
¯
X,Z}
k[P
i
, Q
j
]
B
|ψik = O(n
δ) follows by symmetry.
11
3.3 An attack: lower bound on robustness of the protocol
The soundness analysis from Theorem 3.2, Theorem 2.1 and Corollary 2.2 implies that any strategy
with success probability ω
opt
1
/n
O(1)
in our protocol must have local dimension at least
2
n
for
each player. The following construction shows that the same conclusion cannot be extended to
strategies having success probability below ω
opt
c
p
(log n)/n, for some constant c.
Lemma 3.3.
For any
>
0 there exists a strategy for the players that is accepted with probability
at least
ω
opt
in the protocol for testing
n
qubits, but such that the players’ Hilbert spaces
H
A
and
H
B
have dimension only 2
O(log n/
2
)
.
Proof sketch.
We sketch the argument, which is based on a dimension-reduction construction
from [
CRSV17
, Theorem 3.1]. The theorem states that there exist
n
pairs of anti-commuting
reflections (
X
i
, Z
i
) in a space of dimension
d
= 2
O(log n/
2
)
, satisfying
k[P
i
, Q
j
]k c
for
i 6
=
j
and
P, Q either X or Z, where c > 0 is a constant that we can choose.
Assume that Alice and Bob share a
d
-dimensional maximally entangled state and play the
protocol in Section 3.2 as follows:
1.
When asked to play a CHSH game on qubit
i
[
n
], a player follows the ideal CHSH game
strategy using the observables
Z
i
, X
i
. Thus the players pass the first sub-protocol with
probability one.
2.
When asked to play CHSH games on qubits
i, j
, with
i < j
, a player sequentially measures
using
H
i
= (
X
i
+
Z
i
)
/
2
or
X
i
HX
i
, and then similarly for
j
. Say for example that in
sub-protocol 2 Bob is given the indices
i < j
. If Alice is given index
i
, then the players win
the CHSH game with the optimal probability,
cos
2
π
8
. If Alice is given index
j
, then Bob’s
first measurement using the observables associated with qubit
i
can slightly perturb the state
on qubits
j
. However, provided
c
is chosen small enough, the commutation bounds imply
that the distribution of outcomes is
-close in statistical distance from the case in which Bob
measures qubit
j
first. Thus the players succeed with probability at least
cos
2
π
8
in the
second and third sub-protocols.
Acknowledgements
R.C., B.R. and C.S. supported by NSF grant CCF-1254119 and ARO grant W911NF-12-1-0541.
T.V. supported by NSF CAREER grant CCF-1553477, AFOSR YIP award number FA9550-16-1-
0495, and the IQIM, an NSF Physics Frontiers Center (NFS Grant PHY-1125565) with support of
the Gordon and Betty Moore Foundation (GBMF-12500028).
A Separation of n qubits from any entangled state
Based on the results of [YN13, BP15] it is possible to extend the results from Section 2 to
separating n partially overlapping qubits based on the use of an arbitrary two-qubit entangled
state |ψ
θ
i
=
cos θ|00i
+
sin θ|11i, for θ
(0
, π/
2)
. The arguments are very similar, replacing the
CHSH game by a game based on a Bell inequality introduced in [YN13, BP15]. In the following two
sections we sketch the arguments for extending Theorems 2.1 and 3.2, respectively, to this scenario.
12
A.1 Separating n qubits
The following is an analogue of Theorem 2.1.
Theorem A.1.
Let
|ψi H
A
H
B
, with
k|ψik
= 1. Assume that for
j
[
n
] we are given reflections
(X
j
)
A
, (Z
j
)
A
L(H
A
) and (X
j
)
B
, (Z
j
)
B
L(H
B
)
such that the following conditions hold:
{(X
j
)
D
, (Z
j
)
D
} = 0 D {A, B}, j [n] (6)
(Z
j
)
A
(Z
j
)
B
|ψi |ψi
j [n] (7)
sin θ (X
j
)
D
(1 + (Z
j
)
D
0
)|ψi
cos θ (1 (Z
j
)
D
) (X
j
)
D
0
|ψi
D 6= D
0
{A, B}, j [n] (8)
[P
i
, Q
j
]
D
|ψi
D {A, B}, P, Q {X, Z}, i 6= j [n] (9)
Let
|ψ
0
i = |ψi |ψ
θ
i
n
A
0
|ψ
θ
i
n
B
0
|00i
n
A
00
B
00
H
A
(C
2
)
2n
A
0
(C
2
)
n
A
00
H
B
(C
2
)
2n
B
0
(C
2
)
n
B
00
.
Then there exist reflections
X
0
1
, Z
0
1
, . . . , X
0
n
, Z
0
n
on
H
D
(
C
2
)
2n
D
0
, with
{X
0
j
, Z
0
j
}
= 0 and for
P, Q {X, Z}, [P
0
i
, Q
0
j
] = 0 for i 6= j,
P
0
j
P
j
1
D
0
|ψ
0
i
= O(n), and
(P
0
j
)
AA
0
(P
0
j
)
BB
0
|ψ
0
i |ψ
0
i
= O(n) .
Note that conditions (7) and (8) replace the conditions used to certify EPR states in Theorem 2.1.
The following analog of Claim 2.3 justifies these conditions by showing that they characterize the
state |ψ
θ
i:
Claim A.2
([
YN13
,
BP15
])
.
For any 0
< θ <
1 there exists a constant
c
θ
such that if
|φi
C
2
C
2
H is a state satisfying
max
kσ
z
1
σ
z
2
|φi |φik, ksin θ σ
x
1
(I + σ
z
2
)|φi cos θ σ
x
2
(I σ
z
2
)|φik
δ ,
then there exists a state |φ
0
i H such that
|φi |ψ
θ
i |φ
0
i
c
θ
δ .
Based on the claim we can obtain the following corollary to Theorem A.1.
Corollary A.3.
Under the assumptions of Theorem A.1, there are unitaries
U
D
:
H
D
(
C
2
)
2n
D
0
(C
2
)
n
D
00
(C
2
)
n
D
ˆ
H
D
, for D {A, B}, and a state |extrai
ˆ
H
A
ˆ
H
B
such that
U
A
U
B
|ψ
0
i |ψ
θ
i
n
AB
|extrai
= O(n
3/2
)
k(UX
j
U
σ
x
j
1
ˆ
H
)
D
|ψ
θ
i
n
AB
|extraik = O(n
3/2
)
k(UZ
j
U
σ
z
j
1
ˆ
H
)
D
|ψ
θ
i
n
AB
|extraik = O(n
3/2
) .
13
Proof sketch of Theorem A.1.
The proof follows closely the proof of Theorem 2.1. The main result
needed is the existence of appropriate SWAP operators
S
j
satisfying the properties of Lemmas 2.5
and 2.6.
For j [n] let
(U
j
)
AA
00
j
= (H
j
)
A
00
j
(CTL
A
00
j
-(Z
j
)
A
)(H
j
)
A
00
j
(CTL
A
00
j
-(X
j
)
A
) , (10)
where (
H
j
)
A
00
is a Hadamard on the ancilla qubit and
CTL
A
00
-(Z
j
)
A
(resp.
CTL
A
00
-(X
j
)
A
) is (
Z
j
)
A
(resp. (
X
j
)
A
), controlled on the qubit in
A
00
. Define
U
BB
00
similarly. As shown in [
YN13
,
BP15
],
it follows from (7) and (8) that for
D {A, B}
and
P {X, Z}
, if (
P
0
j
)
DD
00
j
= (
U
j
)
DD
00
j
(
1
D
(P
j
)
D
00
j
)(U
j
)
DD
00
j
then
(U
j
)
AA
00
j
(U
j
)
BB
00
j
|ψ
0
i |ψ
θ
i
A
00
j
B
00
j
|junki
AB
|ψ
θ
i
n
A
0
|ψ
θ
i
n
B
0
= O() (11)
for some state |junki
AB
, and
((P
j
)
D
(P
0
j
)
DD
00
)|ψ
0
i
= O() .
We now define S
j
as
S
j
= (U
j
)
AA
00
SWAP
A
00
A
0
(U
j
)
AA
00
,
and similarly define
S
0
j
, using (
U
j
)
BB
00
and swapping
B
00
with
A
0
. The following lemma establishes
the analog of Lemmas 2.5 and 2.6.
Lemma A.4. For i [n],
k(S
i
S
0
i
)|ψ
0
ik = O() . (12)
For i, j [n], i 6= j, and P {X, Z},
[S
i
, (P
0
j
)
AA
00
1
A
0
]|ψ
0
i
= O() . (13)
Proof.
For (12), we use (11). For (13), it suffices to check that for
i 6
=
j
the unitaries (
U
i
)
AA
00
and (
U
j
)
AA
00
approximately commute. This follows from the definition (10) and the approximate
commutation conditions (9).
Once Lemma A.4 has been established, the proof of the theorem follows exactly the same steps
as the proof of Theorem 2.1.
A.2 The testing protocol
In order to experimentally verify that the conditions of Theorem A.1 are satisfied, a very similar
protocol to the one described in Section 3.2 can be used, except the CHSH tests should be replaced
by the appropriate self-test for the state |ψ
θ
i. Such a test is developed in [YN13, BP15], based on
a Bell inequality with two inputs and two outputs per site.
Theorem A.5
([
YN13
,
BP15
])
.
For 0
< α <
2 let
B
α
=
αA
0
+
A
0
(
B
0
+
B
1
) +
A
1
(
B
0
B
1
), and
let
θ
be such that
tan θ
=
p
(4 α
2
)/(2α
2
)
. Then the optimal violation of
B
α
is
b
α
=
8 + 2α
2
,
and this violation can be achieved using state |ψ
θ
i.
Furthermore, suppose arbitrary observables
A
0
, A
1
and
B
0
, B
1
on
H
A
and
H
B
respectively lead
to a violation of
b
α
when applied to a state
|ψi
AB
. Assume that
A
0
, A
1
and
B
0
, B
1
each have both
14
±
1 eigenspaces of the same dimension. Then there exists observables
P
A
and
P
B
, for
P {X, Z}
,
such that
(Z
A
1
B
1
A
Z
B
)|ψi
= O(
1/2
) (14)
sin θ (X
A
(1
B
+ Z
B
)|ψi cos θ (1
A
Z
A
) X
B
|ψi
= O(
1/2
) , (15)
where the
O
(
·
) notation hides factors depending on
cos
1
θ
and
sin
1
θ
. Moreover, we can take
X
A
= A
0
and Z
A
= A
1
.
Based on the Bell inequality B
α
it is possible to design a simple game between players “Alice”
and “Bob” such that the player’s maximum success probability in the game is directly related to
the expectation value in B
α
that is induced by their strategy.
We can then use exactly the same protocol as described in Section 3.2, with the CHSH game
replaced by the game based on B
α
. The proof that the appropriate relations, as required in
Theorem A.1, are satisfied by any strategy that is accepted in the protocol with probability close
to the optimum then follows closely the proof of Theorem 3.2 and we only sketch the argument.
Observables
(
P
i
)
D
are obtained directly from Theorem A.5. Conditions (7) and (8) then
follow from Theorem A.5. The commutation conditions (9) are proven exactly as in the proof
of Theorem 3.2.
The anti-commutation relations require a little more work. From observables X
D
, Z
D
define
ˆ
Z
A
= Z
A
,
ˆ
Z
B
= Z
B
, and
ˆ
X
A
=
cos θ
2 sin θ
X
A
(1
A
Z
A
)
sin θ
2 cos θ
X
A
(1
A
Z
A
),
ˆ
X
B
=
cos θ
2 sin θ
X
B
(1
B
Z
B
)
sin θ
2 cos θ
X
B
(1
B
Z
B
) .
It follows from (14) and (15) that for T {X, Z},
ˆ
T is an operator of norm O
(
tan θ
+
tan
1
θ
)
such
that
max
n
(T
A
1
B
1
A
ˆ
T
B
)|ψi
,
(1
A
T
B
ˆ
T
A
1
B
)|ψi
o
= O
(sin
1
θ + cos
1
θ)
. (16)
Using this it is then easy to verify from the same equations that approximate anti-commutation
relations
max
n
{X
A
, Z
A
} 1
B
|ψi
,
1
A
{X
B
, Z
B
}|ψi
o
= O
(sin
1
θ + cos
1
θ)
(17)
hold, as desired. It is then not hard to turn such pairwise approximate anti-commutation into exact
anti-commutation; see, e.g., [OV16, Lemma 7].
References
[AB17] Rotem Arnon-Friedman and Jean-Daniel Bancal. Device-independent certification of
one-shot distillable entanglement. 2017, arXiv:1712.09369 [quant-ph].
[AY17] Rotem Arnon-Friedman and Henry Yuen. Noise-tolerant testing of high entanglement
of formation. In Proc. 45th ICALP, pages 11:1–11:12, 2018, arXiv:1712.09368
[quant-ph].
[BLR93] Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with
applications to numerical problems. J. Comput. Syst., 47(3):549–595, 1993.
15
[BP15] C´edric Bamps and Stefano Pironio. Sum-of-squares decompositions for a family
of Clauser-Horne-Shimony-Holt-like inequalities and their application to self-testing.
Phys. Rev. A, 91(5):052111, 2015, arXiv:1504.06960 [quant-ph].
[CHSH69] John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt. Proposed
experiment to test local hidden-variable theories. Phys. Rev. Lett., 23:880–884, 1969.
[CN16] Matthew Coudron and Anand Natarajan. The parallel-repeated magic square game is
rigid. 2016, arXiv:1609.06306 [quant-ph].
[Col17] Andrea W. Coladangelo. Parallel self-testing of (tilted) EPR pairs via copies of (tilted)
CHSH and the magic square game. Quantum Inf. Comput., 17(9&10):831–865, 2017,
arXiv:1609.03687 [quant-ph].
[CRSV17] Rui Chao, Ben W. Reichardt, Chris Sutherland, and Thomas Vidick. Overlapping
qubits. In Proc. 8th Innovations in Theoretical Computer Science Conference (ITCS),
volume 67, pages 48:1–48:21, 2017, arXiv:1701.01062 [quant-ph].
[CS17] Andrea Coladangelo and Jalex Stark. Robust self-testing for linear constraint system
games. 2017, arXiv:1709.09267 [quant-ph].
[G
+
15] Marissa Giustina et al. Significant-loophole-free test of Bell’s theorem with entangled
photons. Phys. Rev. Lett., 115:250401, 2015, arXiv:1511.03190 [quant-ph].
[H
+
15] B. Hensen et al. Loophole-free Bell inequality violation using electron spins separated
by 1.3 kilometres. Nature, 526:682–686, 2015, arXiv:1508.05949 [quant-ph].
[H
+
16] B. Hensen et al. Loophole-free Bell test using electron spins in diamond: second exper-
iment and additional analysis. Scientific Reports, 6:30289, 2016, arXiv:1603.05705
[quant-ph].
[IKM09] Tsuyoshi Ito, Hirotada Kobayashi, and Keiji Matsumoto. Oracularization and two-
prover one-round interactive proofs against nonlocal strategies. In Proc. 24th IEEE
Conf. on Computational Complexity (CCC), pages 217–228. IEEE Computer Society,
2009, arXiv:0810.0693 [quant-ph].
[KKM
+
11] Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, and Thomas
Vidick. Entangled games are hard to approximate. J. ACM, 40(3):848–877, 2011,
arXiv:0704.2903 [quant-ph]. Earlier version in FOCS’08.
[McK16] Matthew McKague. Self-testing in parallel. New J. Phys., 18:045013, 2016,
arXiv:1511.04194 [quant-ph].
[Mer90] N. David Mermin. Simple unified form for the major no-hidden-variables theorems.
Phys. Rev. Lett., 65:3373, 1990.
[MMMO06] Fed´eric Magniez, Dominic Mayers, Michele Mosca, and Harold Ollivier. Self-testing of
quantum circuits. In Proc. 33rd ICALP, pages 72–83, 2006, arXiv:quant-ph/0512111.
[MYS12] Matthew McKague, Tzyh Haur Yang, and Valerio Scarani. Robust self-testing of the
singlet. J. Phys. A: Math. Theor., 45:455304, 2012, arXiv:1203.2976 [quant-ph].
[NV17] Anand Natarajan and Thomas Vidick. A quantum linearity test for robustly verifying
entanglement. In Proc. 49th ACM STOC, pages 1003–1015, 2017, arXiv:1610.03574
[quant-ph].
16
[NV18] Anand Natarajan and Thomas Vidick. Low-degree testing for quantum states, and a
quantum entangled games PCP for QMA. 2018, arXiv:1801.03821 [quant-ph].
[OV16] Dimiter Ostrev and Thomas Vidick. Entanglement of approximate quantum strategies
in XOR games. 2016, arXiv:1609.01652 [quant-ph].
[Per90] Asher Peres. Incompatible results of quantum measurements. Phys. Lett. A, 151(3-
4):107–108, 1990.
[RUV12] Ben W. Reichardt, Falk Unger, and Umesh Vazirani. A classical leash for a
quantum system: Command of quantum systems via rigidity of CHSH games. 2012,
arXiv:1209.0448 [quant-ph].
[RUV13] Ben W. Reichardt, Falk Unger, and Umesh Vazirani. Classical command of quantum
systems. Nature, 496:456–460, 2013.
[S
+
15] Lynden K. Shalm et al. Strong loophole-free test of local realism. Phys. Rev. Lett.,
115:250402, 2015, arXiv:1511.03189 [quant-ph].
[WBMS16] Xingyao Wu, Jean-Daniel Bancal, Matthew McKague, and Valerio Scarani. Device-
independent parallel self-testing of two singlets. Phys. Rev. A, 93:062121, 2016,
arXiv:1512.02074 [quant-ph].
[YN13] Tzyh Haur Yang and Miguel Navascu´es. Robust self-testing of unknown quantum
systems into any entangled two-qubit states. Phys. Rev. A, 87(5):050102, 2013,
arXiv:1210.4409 [quant-ph].
17