Bounding sets of sequential quantum correlations and
device-independent randomness certification
Joseph Bowles
1
, Flavio Baccari
1,2
, and Alexia Salavrakos
1
1
ICFO-Institut de Ciencies Fotoniques, The Barcelona Institute of Science and Technology, 08860 Castelldefels (Barcelona),
Spain
2
Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-Straße 1, 85748 Garching, Germany
An important problem in quantum information theory is that of bounding sets of
correlations that arise from making local measurements on entangled states of arbitrary
dimension. Currently, the best-known method to tackle this problem is the NPA hier-
archy; an infinite sequence of semidefinite programs that provides increasingly tighter
outer approximations to the desired set of correlations. In this work we consider a
more general scenario in which one performs sequences of local measurements on an
entangled state of arbitrary dimension. We show that a simple adaptation of the origi-
nal NPA hierarchy provides an analogous hierarchy for this scenario, with comparable
resource requirements and convergence properties. We then use the method to tackle
some problems in device-independent quantum information. First, we show how one
can robustly certify over 2.3 bits of device-independent local randomness from a two-
quibt state using a sequence of measurements, going beyond the theoretical maximum
of two bits that can be achieved with non-sequential measurements. Finally, we show
tight upper bounds to two previously defined tasks in sequential Bell test scenarios.
1 Introduction
The correlations between outcomes of local measurements made on entangled quantum systems
are known to exhibit a rich structure. Firstly, they are generally stronger than correlations at-
tainable via classical resources, a phenomenon known as Bell nonlocality [1, 2]. Secondly, sets of
quantum correlations are known to contain both smooth and flat boundaries [3, 4], and there exist
correlations whose realisation requires infinite-dimensional entangled states [5], even in scenarios
involving small and finite alphabet sizes.
All of this makes the problem of characterising, and optimising over, the set of quantum cor-
relations a highly non-trivial and potentially undecidable problem. At the same time, being able
to perform an optimisation over the entire set of quantum correlations is crucial for many areas of
quantum information theory, principally in the field of device-independent quantum information,
where quantum systems are treated as black-boxes and one makes no assumption on the physical
dimension of the underlying state. A major breakthrough in this direction came with the discovery
of the NPA-hierarchy [6, 7], which provides a characterisation of the set of quantum correlations via
a sequence of increasing tighter outer approximations, each expressed in terms of a semi-definite
program (SDP). Consequently, the NPA hierarchy has become a vital tool for the study of device-
independent protocols in the standard scenario in which they are usually considered, commonly
referred to as a Bell test. There, a bipartite state is shared between two parties, each of which
makes a number of local measurements in order to generate the data that is used in the protocol.
In recent years a number of works have also considered sequential Bell test scenarios, in which
the parties make a sequence of local measurements that obey a time-ordered causal structure
[8, 9, 10, 11, 12] (see figure 1). Such scenarios have been shown to be relevant for Bell non-
locality via for example the phenomenon of hidden nonlocality [10, 11, 12]. As a result, sequential
measurement scenarios are known to provide an advantage in device-independent randomness
Accepted in Quantum 2010-10-02, click title to verify. Published under CC-BY 4.0. 1
arXiv:1911.11056v4 [quant-ph] 9 Oct 2020
Figure 1: A sequential Bell scenario in which both parties perform a sequence of two measurements on their
halves of a bipartite quantum state. In this work we develop methods to characterise the sets of probability
distributions that can arise in such scenarios involving arbitrary numbers of parties in each sequence.
certification [13] and, we expect, in many other device-independent protocols. Further to this,
sequential measurement scenarios also play a role in demonstrations of contextuality [14] and
Leggett-Garg type tests of nonclassicality [15].
It is thus very desirable to develop methods to characterise the correlations arising in sequential
Bell test scenarios. In this work we show that such a characterisation is possible by augmenting
the original NPA hierarcy with a finite number of additional linear constraints. This provides a
sequence of outer approximations to the corresponding set of correlations that can each be defined
via a suitable SDP, with analogous resource requirements and convergence properties of the NPA
hierarchy. We then apply our hierarchy to several problems in quantum information. First, we
investigate device-independent randomness certification. We show how to use the hierarchy to
robustly certify over 2.3 bits of local randomness from a two-qubit state via a simple sequential
measurement strategy, thus going beyond the theoretical maximum of two bits that is achievable
in non-sequential Bell scenarios. We then show that the previously studied strategies for the simul-
taneous violation of two CHSH inequalities [9] and the violation of the sequential Bell inequality
defined in [8] are both optimal for strategies of any dimension, up to numerical precision.
We note that the recent work [16] also describes a sequence of SDP relaxations for generic
quantum-causal networks that can be applied to the sequential structures we consider; see the
discussion for further information.
2 Preliminaries
2.1 Quantum correlations
In a standard Bell scenario, two spatially-separated players perform measurements on their local
share of a bipartite state, chosen according to some random inputs x, y = 1, . . . , m, and then
collect the corresponding outputs a, b = 1, . . . , d. The resulting correlations P (a, b|x, y) are called
quantum, P (a, b|x, y) Q, if they can be written tr[ρ A
x
a
B
y
b
] for some bipartite quantum state
ρ and local measurement operators A
x
a
and B
y
b
. Here one can take ρ pure and the measurements
projective without loss of generality, since any measurement on a mixed state can be realised as a
projective measurement on a purification of the state [17]. Thus,
P (a, b|x, y) Q P (a, b|x, y) = hψ|A
x
a
B
y
b
|ψi (1)
with
A
x
a
A
x
a
0
= A
x
a
δ
a,a
0
x, a, a
0
, B
y
b
B
y
b
0
= B
y
b
δ
b,b
0
y, b, b
0
. (2)
Since the state and measurements appearing in (1) are potentially infinite dimensional, the
problem of deciding membership in, or optimising over the set Q is highly non-trivial. Currently,
the only general purpose technique to tackle such a problem is the NPA hierarchy [6, 7], which we
will recap shortly.
2.2 Sequential quantum correlations
In this work we consider sequential measurement scenarios, where a quantum system is subjected
local measurements that obey a time-ordered structure (see Fig. 1). Consider first a single quantum
Accepted in Quantum 2010-10-02, click title to verify. Published under CC-BY 4.0. 2
system |ψi, of potentially uncountable infinite dimension, that undergoes a sequence of n measure-
ments with inputs x
i
and outcomes a
i
. The first measurement outcome and its corresponding
post-measurement state are described by sets of Kraus operators {K
x
1
a
1
1
}. For finite dimensional
systems the (sub-normalised) post-measurement state obtained after obtaining outcome a
1
takes
the form
ρ
a
1
|x
1
=
X
µ
1
K
x
1
a
1
1
|ψihψ|K
x
1
a
1
1
, (3)
with P (a
1
|x
1
) = tr ρ
a
1
|x
1
,
P
a
1
1
K
a
1
1
K
a
1
1
= , and where the sum over µ
1
is needed since we
may have multiple Kraus operators associated to a single measurement outcome. Generally, for
infinite dimensional systems one replaces the sum with an integral:
ρ
a
1
|x
1
=
Z
µ
1
dµ
1
K
x
1
a
1
1
|ψihψ|K
x
1
a
1
1
, (4)
where again P (a
1
|x
1
) = tr ρ
a
1
|x
1
and
P
a
1
R
dµ
1
K
a
1
1
K
a
1
1
= . Continuing this process for the
entire sequence with inputs x = (x
1
, ··· , x
n
) and outputs a = (a
1
, ··· , a
n
), one finds
P (a|x) = hψ|A
x
a
|ψi, A
x
a
=
Z
···
Z
dµ
1
···dµ
n
K
x
1
a
1
1
K
x
2
a
2
2
···K
x
n
a
n
n
K
x
n
a
n
n
···K
x
2
a
2
2
K
x
1
a
1
1
,
X
a
i
Z
dµ
i
K
x
i
a
i
i
K
x
i
a
i
i
=
A
x
i
. (5)
To ease notation we have left the time-step dependence of the Kraus operators implicit. That
is, {K
x
1
a
1
1
} and {K
x
2
a
2
2
} are in general different sets of operators, which is understood from the
input/output indices. We define the set of sequential quantum correlations Q
SEQ
as those that
arise from performing sequential measurements locally on a bipartite quantum state |ψi, i.e.
P (a, b|x, y) Q
SEQ
P (a, b|x, y) = hψ|A
x
a
B
y
b
|ψi,
where the measurement operators A
x
a
and B
y
b
have the sequential structure (5). Can we define a
hierarchy, analogous to the NPA hierarchy for Q, to characterise the set Q
SEQ
? In this work we
show how this can be achieved in an efficient manner, via a simple adaptation of the original NPA
hierarchy.
2.3 The NPA hierarchy
Before explaining our method, we review the NPA hierachy [6, 7]. The NPA hierarchy provides a
sequence of tests, each of which checks membership in a set Q
i
Q such that Q
1
Q
2
··· Q.
To see how the NPA hierarchy works, consider some state and projective measurements |ψi, A
x
a
, B
y
b
with corresponding correlations P (a, b|x, y) = hψ|A
x
a
B
y
b
|ψi (where A
x
a
should be understood as
A
x
a
B
and B
y
b
as
A
B
y
b
). Define sets S
k
, consisting of the identity operator and all products
of the operators A
x
a
and B
y
b
up to degree k;
S
1
= { }
a,x
{A
x
a
}
b,y
{B
y
b
}, S
k+1
= S
k
i,j
{S
(i)
k
S
(j)
1
} (6)
where S
(i)
k
is the i
th
element of S
k
. Next, define the moment matrix of order k, Γ
k
, with elements
Γ
(i,j)
k
Γ
(i,j)
k
= hψ|(S
(i)
k
)
S
(j)
k
|ψi, (7)
By construction, the matrix Γ
k
has the following properties:
i. Γ
k
satisfies a number of linear constraints stemming from the orthogonality properties (2),
the normalisation of the measurement operators, and from the commutation of Alice’s and
Bob’s operators. For example hψ|A
x
a
A
x
a
0
|ψi = 0 for a 6= a
0
and hψ|[A
x
a
, B
y
b
]|ψi = 0. We can
write these constraints as tr[Γ
k
G
i
] = 0 for some suitable fixed matrices G
i
.
Accepted in Quantum 2010-10-02, click title to verify. Published under CC-BY 4.0. 3
ii. Γ
k
contains some elements that correspond to observable probabilities. For example hψ|A
x
a
B
y
b
|ψi =
P (a, b|x, y). We write these constraints as tr[Γ
k
F
j
] = P
j
, where F
j
are fixed matrices and P
j
denotes the corresponding observed probability. Similarly, taking S
(0)
k
= we have Γ
(0,0)
k
= 1
since tr |ψihψ| = 1.
iii. Γ
k
= Γ
k
and Γ
k
is positive semi-definite (see [6] for a simple proof).
Imagine that we are given some other correlation P(a, b, |x, y) for which we want to test mem-
bership in Q. If P Q, there exists a state and measurements leading to P and a corresponding
matrix Γ
k
satisfying the above conditions. We thus have a necessary condition for P Q:
NPA hierarchy (level k):
Find Γ
k
such that Γ
k
< 0, Γ
k
= Γ
k
, Γ
(0,0)
k
= 1, (8)
tr[Γ
k
G
i
] = 0 i,
tr[Γ
k
F
i
] = P
i
i.
We denote the set of correlations with a positive solution to the above problem at level k as Q
k
.
Since the test is a necessary condition for P Q we have Q
k
Q. As the test contains only
linear and positive-semidefinite constraints, it can be cast as a SDP feasibility problem and solved
efficiently (in the size of the matrix Γ
k
) by a suitable solver. We thus have a sequence of SDPs,
each of which provides a relaxation to the problem of deciding membership in Q. Since Γ
k
is a
principle sub-matrix of Γ
k+1
, one has Γ
k+1
< 0 = Γ
k
< 0 and so Q
k+1
Q
k
. Furthermore, one
can perform optimization of linear combinations of the probabilities P
j
over Q
k
by removing the
final constraint in (8) and defining a linear combination of the elements tr[Γ
k
F
j
] as an objective
function of the SDP. One can then obtain certified upper and lower bounds to the problem via
duality theorems of convex optimisation. In practice, relevant problems can be tackled in this way
at low levels of the hierarchy that are tractable on a desktop computer.
In principle, one can use other sets than S
k
to generate the moment matrix (7), with each
choice giving a different relaxation to Q. Often, and in the examples we present later, we will use
a level that is mid-way between level 1 and level 2, often called level 1+AB. This level is defined
by the set
S
1+AB
= S
1
a,x,b,y
{A
x
a
B
y
b
}. (9)
This set defines the lowest level in the hierarchy of [18], and defines the so-called set of ‘almost
quantum’ correlations [19]. As we will see, this set is often sufficient to get non-trival and even
tight bounds to relevant optimisation problems.
3 NPA hierarchy for sequential correlations
First, let us state our main technical result regarding the characterisation of sequential quantum
correlations.
Fact 1. A given set of correlations P (a, b|x, y) belongs to Q
SEQ
if and only if it can be realised
as P (a, b|x, y) = hψ|A
x
a
B
y
b
|ψi, with the measurement operators being projective and satisfying
one-way ‘no-signalling’ and orthogonality conditions. That is
A
x
a
A
x
a
0
= δ
a,a
0
A
x
a
x, a, a
0
(10)
X
a
k+1
,··· ,a
n
A
x
a
A
x
0
a
= 0 a
1
, . . . , a
k
, (11)
x, x
0
s.t x
i
= x
0
i
(i k)
1 k n 1
A
x
a
A
x
0
a
0
= 0 x, x
0
, a, a
0
s.t x
i
= x
0
i
, (i k), (12)
(a
1
, . . . , a
k
) 6= (a
0
1
, . . . , a
0
k
).
1 k n
and similarly for B
y
b
.
Accepted in Quantum 2010-10-02, click title to verify. Published under CC-BY 4.0. 4
Note that the projective condition (10) is in fact implied by the more general condition (12)
and so one can equivalently take only (11) and (12) in the above.
Proof. We first prove that any correlations in Q
SEQ
can be realised using measurement operators
satisfying (10), (11) and (12). This can be proven by considering Stinespring dilations of the
sequential measurements; see appendix A. For example, for a sequence of two measurements (see
figure 2), one finds that Alice’s full measurement operator can be written
A
x
a
= U
x
1
1
U
x
2
2
( Π
a
1
Π
a
2
)U
x
2
2
U
x
1
1
, (13)
which describes a projective measurement and thus satisfies (10). Here, U
x
1
1
acts trivially (with
the identity) on the third Hilbert space in the product, and U
x
2
2
acts trivially on the second Hilbert
space, as shown graphically in figure 2.
The constraint (11) is true for any set of measurement operators that are realised sequentially,
as can be seen from (5). This is because it reflects the fact that the measurement operators that
define the first k measurements (obtained by marginalising A
x
a
over the last n k outcomes) must
be independent of the last n k inputs, since these occur later in the sequence. The Stinespring
dilation of the measurement operators described previously retains the sequential structure of the
measurement, and so this constraint holds for the projective measurement operators as well. For
example, by summing over a
2
in (13), one finds an operator that is independent of x
2
.
Finally, given the Stinespring dilations of the sequential measurements, property (12) follows
from the orthogonality conditions of the Π
a
j
’s. Consider again the sequence of two measurements
in (13). One has for x
1
= x
0
1
and a
1
6= a
0
1
(omitting the tensor products and the identity operator)
A
x
a
A
x
0
a
0
= U
x
1
1
U
x
2
2
Π
a
1
Π
a
2
U
x
2
2
U
x
0
2
2
Π
a
0
1
Π
a
0
2
U
x
0
2
2
U
x
1
1
(14)
= U
x
1
1
U
x
2
2
Π
a
2
U
x
2
2
U
x
0
2
2
Π
a
1
Π
a
0
1
Π
a
0
2
U
x
0
2
2
U
x
1
1
= 0,
where we have used [U
x
2
2
, Π
a
1
] = 0. Generalising this for a general sequence we find (12)
We now show the opposite direction, i.e. that any measurement operators satisfying (10), (11)
and (12) admit a sequential realisation. In fact, to show this we need only conditions (10), (11).
Consider a projective measurement with two input labels x
1
, x
2
and two output labels a
1
, a
2
defined
by the measurement operators A
x
1
x
2
a
1
a
2
, and assume that the measurement operators satisfy (11). The
measurement can be realised sequentially as follows. The first device performs a measurement with
Kraus operators K
x
1
a
1
=
P
a
2
A
x
1
x
2
a
1
a
2
. These operators are projective and independent of x
2
due to
(11). The value x
1
is then sent to the second device (using a classical channel) and the second
device measures K
x
2
a
2
=
P
a
1
A
x
1
x
2
a
1
a
2
. The measurement operator describing the full sequence is
therefore
K
x
1
a
1
K
x
2
a
2
K
x
2
a
2
K
x
1
a
1
= K
x
1
a
1
K
x
2
a
2
K
x
1
a
1
=
X
a
0
2
A
x
1
x
2
a
1
a
0
2
X
a
0
1
A
x
1
x
2
a
0
1
a
2
X
a
00
2
A
x
1
x
2
a
1
a
00
2
= A
x
1
x
2
a
1
a
2
(15)
as required. In the first equality we have used the fact that the Kraus operators are Hermitian
and projective by construction. The final equality follows from A
x
1
x
2
a
1
a
2
being projective. In the
above we made use of a communication channel that we have not explicitly modelled but can be
realised sequentially ; see appendix B for a proof where this channel is explicit. The general result
for sequences of any length can be achieved in the same fashion by applying the same technique
inductively on the sequence.
Having established Fact 1 we may define a hierarchy of relaxations to Q
SEQ
as follows. Define
moment matrices Γ
k
as in (7) using the projective measurement operators A
x
a
and B
y
b
(i.e. satisfying
(10)), leading to analogous constraints to (8). At this point, the relaxation is equivalent to the
standard NPA hierarchy, treating the sequences of measurements as single measurements. The
constraints (10), (11) and (12) are linear constraints on the measurement operators and thus imply
additional linear constraints on Γ
k
. One can therefore add these extra constraints in the form of
Accepted in Quantum 2010-10-02, click title to verify. Published under CC-BY 4.0. 5
Figure 2: Top: the dilation of a sequence of two measurements. Each measurement in the sequence can be
realised by appending an ancila state, performing a joint unitary operation and making a projective measure-
ment on the ancilla space. Bottom: absorbing the ancilla states in the initial state and moving all projective
measurements to the end, the scheme is equivalent to a unitary operation followed by a projective measurement.
The measurement operators A
x
a
can thus be taken projective WLOG.
extra fixed matrices G
SEQ
i
to (8). This leads us to the following hierarchy for sequential quantum
correlations
Sequential hierarchy (level k):
Find Γ
k
such that Γ
k
< 0, Γ
k
= Γ
k
, Γ
(0,0)
k
= 1, (16)
tr[Γ
k
G
i
] = 0 i,
tr[Γ
k
G
SEQ
i
] = 0 i,
tr[Γ
k
F
i
] = P
i
i.
We call Q
k
SEQ
the set defined at level k of this hierarchy. As with the NPA hierachy, the sets
Q
k
SEQ
can be optimised over via SDP solvers with a comparable resource overhead. Note that
due to the normalisation of measurement operators and (11), some of the measurement operators
can be written as linear combinations of others. In practice, this means that such operators can
be excluded from the sets S
k
(thus increasing efficiency by decreasing the size of Γ
k
) since their
addition will result in linear dependencies between the rows and columns of Γ
k
, which do not affect
the constraint Γ
k
< 0. This process will also introduce further constraints on the now smaller Γ
k
.
For example, if A
x
a
and A
x
0
a
0
are two measurement operators that have been removed from S
k
through this process, then by expressing them as linear combinations of the remaining elements
in S
k
, the constraint (12) gives a polynomial operator identity that implies further constraints on
the moment matrix.
3.1 Convergence of the hierarchy
Since the conditions (11) characterise precisely the set of sequential measurement operators and
are linear constraints, one can use the same methods as in [7] to prove convergence of the hierarchy.
In fact, one can extract a quantum state and measurement operators from the moment matrix Γ
corresponding to the asymptotic level of the hierarchy. It is then straightforward to see that the
added linear constraints G
SEQ
i
enforce that the extracted measurement operators satisfy property
(11), hence having a sequential realisation. Technically speaking, the convergence is proven to
a set
˜
Q
SEQ
Q
SEQ
. Here,
˜
Q
SEQ
is the set of sequential quantum correlations where the tensor
product structure is replaced by the weaker constraint that Alice and Bob’s measurement operators
commute, i.e.
p(a, b|x, y)
˜
Q
SEQ
p(a, b|x, y) = hψ|A
x
a
B
y
b
|ψi.
where one has [A
x
a
, B
y
b
] = 0 for all a, x, b, y and the measurement operators have the sequential
structure (5). This commuting operator formalism is used in algebraic quantum field theory [20],
and it is known that there exist scenarios for which Q
SEQ
˜
Q
SEQ
[21].
Accepted in Quantum 2010-10-02, click title to verify. Published under CC-BY 4.0. 6
3.2 Relaxations of local correlations
The hierarchy can also be used to define semidefinite programming relaxations to the set of ‘time
ordered local correlations’ defined in [8]. Such correlations are those that can be obtained by a
local hidden variable model that must respect the sequential causal structure of the scenario. The
idea essentially the same as that presented in [22]; as we show in appendix C, any hidden variable
model can be seen as a special case of a quantum strategy, where all measurement operators of
the same party commute. For the sequential scenario, one therefore just has to add the additional
linear constraints to Γ
k
implied by the relations [A
x
a
, A
x
0
a
0
] = 0 and [B
y
b
, B
y
0
b
0
] = 0.
4 Applications
In the rest of this article we use our methods to tackle a number of open questions in quantum in-
formation theory. Code to implement our method in python can be found in the GitLab repository
https://gitlab.com/josephbowles/sequentialnpa.
4.1 Robust device-independent certification of more that 2 bits of local randomness
One of the most important applications of the NPA hierarchy is bounding the amount of random-
ness one can certify from an observed probability distribution in the device-independent setting
[23, 24, 25, 26, 27, 28, 29, 30]. A common figure of merit that is used is the local guessing prob-
ability, defined as the maximum probability with which an adversary—usually called Eve—could
guess the value of one of the local outputs for a fixed local input. More precisely, consider the
set of tripartite probability distributions p
ABE
(a, b, e|x, y) for Alice, Bob and Eve (where Eve has
no input and the same output alphabet as Bob) that have a realisation in quantum theory, i.e.
p
ABE
(a, b, e|x, y) = hψ|A
x
a
B
y
b
E
e
|ψi p
ABE
Q for some state and measurements. Define
p
AB
(a, b|x, y) and p
BE
(b, e|y) to be the corresponding marginal distributions of p
ABE
(a, b, e|x, y).
The local guessing probability for Bob’s input y = y
given an observed probability distribution
P
obs
(a, b|x, y) is the best probability that Eve could guess b given y = y
while simultaneously
reproducing P
obs
when marginalising over her output. That is,
G(y
) = max
p
ABE∈Q
|b|
X
e=1
p
BE
(e, e|y
) such that p
AB
(a, b|x, y) =
X
e
p
ABE
(a, b, e|x, y) (17)
= P
obs
(a, b|x, y)
where |b| is the size of Bob’s output alphabet. To define the local guessing probability in the
sequential scenario one imposes that the distribution p
ABE
be realised by a sequential quantum
strategy. That is, the local guessing probability for Bob’s input y
given an observed distribution
P
obs
(a, b|x, y) becomes
G(y
) = max
p
ABE
X
e
p
BE
(e, e|y
) such that p
AB
(a, b|x, y) =
X
e
p
ABE
(a, b, e|x, y) (18)
= P
obs
(a, b|x, y),
where the alphabet of e is the same as b and where p
ABE
has a sequential realisation, i.e.
p
ABE
(a, b, e|x, y) = hψ|A
x
a
B
y
b
E
e
|ψi, (19)
where the measurement operators A
x
a
and B
y
b
have the structure (5). In appendix D we show how
upper bounds to (18) can be obtained efficiently using our hierarchy.
In the standard Bell scenario, the local guessing probability (17) is always lower bounded
by 1/d
2
, where d is the local Hilbert space dimension of the state used to obtain the observed
correlations. This follows from the fact that extremal measurements acting on a Hilbert space of
dimension d have at most d
2
outcomes [30, 31]. Hence, the amount of randomness, expressed as the
min entropy log
2
(G) is always lower than 2 log
2
(d) bits. However, if one imposes the sequential
structure on the local measurement one can no longer bound the number of outcomes of extremal
Accepted in Quantum 2010-10-02, click title to verify. Published under CC-BY 4.0. 7
measurements. In [13] Curchod et. al. use this to construct a protocol to obtain arbitrarily small
local guessing probabilities from any two-qubit entangled pure state using a single Alice and a
sequence of Bobs.
The construction in [13] has two disadvantages however. Firstly, the number of measurements
that Alice makes grows quickly with the amount of certified randomness. For example, to certify
more that two bits of local randomness one needs at least 14 measurements for Alice. Secondly,
although the authors prove that the protocol is noise resistant in principle, precise upper bounds
on the guessing probability could not be proven for any nonzero level of noise, and the method
can therefore not be used in practice. In the following we show that one can use our hierarchy
to certify more than two bits of local randomness in a simple sequential scenario using only two
measurements for Alice. Moreover, we use our hierarchy to calculate upper bounds to the guessing
probabilities in the presence of noise, thus making the scheme experimentally relevant.
To generate the observed correlations P
obs
we consider a scenario involving one Alice and a
sequence of two Bobs (that we call Bob
1
and Bob
2
), where Alice and Bob
1
share the two-qubit
isotropic state with noise parameter η:
ρ(η) = (1 η)|φ
+
ihφ
+
| + η /4 (20)
with |φ
+
i = [|00i + |11i]/
2. Alice performs one of two measurements given by the observables
cos µ σ
z
± sin µ σ
x
, where tan µ = sin 2 and is a free parameter. Bob
1
performs one of two
measurements. For y
1
= 0 he performs a projective measurement of σ
z
with Kraus operators |0ih0|
and |1ih1|. For y
1
= 1 he performs the two outcome measurement defined by the Kraus operators
K
+
= cos |+ih+| + sin |−ih−|, K
= cos |−ih−| + sin |+ih+|. (21)
The parameter controls the strength of the measurement: for = 0, the measurement is a
projective measurement in the x direction; for = π/4 the measurement is non-interacting. Bob
2
performs one of three measurements. For y
2
= 0, 1 he performs a projective measurement of σ
z
or
σ
x
. For y
2
= 2 he performs the symmetric 3-outcome POVM given by the measurement operators
M
b
2
=
2
3
+ v
b
2
·~σ
2
b
2
= 0, 1, 2, (22)
where v
b
2
= (sin(
2π
3
b
2
), 0, cos(
2π
3
b
2
)). The inspiration for these measurements is the following. For
y
1
= 1, the post measurement state shared between Alice and Bob
2
will be one of two partially
entangled states, depending on the value of b
1
. The correlations obtained by performing the
measurements for x, y
2
= 0, 1 on these states are known to self-test both of the corresponding
state and measurements [32]. We expect (although we have not proven) that this implies that the
state shared between Alice and Bob
1
is |φ
+
i and the measurement for Bob
1
(21), which essentially
implies that one must have p(b
2
|y
2
= 2) =
1
3
, leading to more than two bits of randomness.
In figure 3 we present upper bounds to G(y
= (1, 2)) obtained in this way as a function of
η, with = 7π/32 and calculated using level 1 + AB of the hierarchy. For low noise, one can
surpass two bits of randomness. Moreover, for close to 4% noise (well within experimental reach)
our strategy outperforms the non-sequential strategy where one performs the measurement that
maximally violate the CHSH Bell inequality on the same state. We leave a more detailed analysis
of noise including detector inefficiencies to future work.
4.2 Monogamy of nonlocality in sequential measurement scenarios
Consider a scenario involving one Alice and two Bobs, where each party has two inputs and two
outputs, with inputs and outputs labelled by 0,1. The value of the CHSH Bell functional between
Alice and Bob
1
is
CHSH
AB1
=
X
x,y
1
X
a,b
1
(1)
a+b
1
+x·y
1
P
AB1
(a, b
1
|x, y
1
) (23)
where P
AB1
is the marginal distribution between Alice and Bob
1
. We may define the average CHSH
Bell functional between Alice and Bob
2
as
CHSH
AB2
=
1
2
X
b
1
,y
1
X
x,y
2
X
a,b
2
(1)
a+b
2
+x·y
2
P (a, b
1
, b
2
|x, y
1
, y
2
),
Accepted in Quantum 2010-10-02, click title to verify. Published under CC-BY 4.0. 8
0 0.02 0.04 0.06 0.08 0.10 0.12 0.14
0
0.5
1
1.5
2
2.5
noise parameter η
min entropy (bits)
seq. strategy (level Q
1+AB
SEQ
)
CHSH strategy (NPA level 4)
Figure 3: Blue: lower bound to the local randomness as a function of the noise parameter η for our sequential
measurement strategy, obtained at level 1+AB of our sequential hierarchy. Red: corresponding local randomness
obtainable with the same state in a non-sequential scenario using measurements that lead to the maximal
violation of the CHSH Bell inequality, obtained at level 4 of the NPA hierarchy.
i.e. the CHSH Bell functional between Alice and Bob
2
, averaged over b
1
and a uniform choice of y
1
.
The values of CHSH
AB1
and CHSH
AB2
are subject to monogamy due to both the monogamy of
correlations and the sequential measurement constraints. Silva et. al. investigate this in [9], finding
that for two-qubit systems, the optimal trade-off satisfies
CHSH
AB2
2
1 +
r
1
(CHSH
AB1
)
2
8
!
, (24)
which can be saturated with an appropriate choice of measurements. We use the sequential NPA
hierarchy to investigate this trade-off for systems of general dimension. We numerically maximise
the value of CHSH
AB2
conditioned on values of CHSH
AB1
at level 1+AB of the hierarchy (see
figure 4). We find that the values obtained match those of (24) up to the precision of the SDP
solver. Thus, we conjecture that the strategies presented in [9] are optimal for any dimension.
This is somewhat surprising since one may expect to gain an advantage from higher dimensional
systems. For example, it would allow Bob
1
to communicate perfectly the value of y
1
and b
1
to
Bob
2
, which in principle could increase the value of CHSH
A,B2
.
4.3 Tight bounds on sequential Bell inequalities
In [8] Gallego et. al. present a Bell inequality (see equation 51 therein) that defines a facet of the
set of correlations that admit a sequential time-ordered local model. The scenario involves one
Alice and two Bobs, with each party performing one of two dichotomic measurements. The Bell
inequality is constructed as follows. Define the correlators
hA
x
B
2
y
1
y
2
i = P (a · b
2
= +1|x, y
1
, y
2
) P (a · b
2
= 1|x, y
1
, y
2
)
hA
x
B
1
y
1
B
2
y
1
y
2
i = P (a · b
1
· b
2
= +1|x, y
1
, y
2
) P (a · b
1
· b
2
= 1|x, y
1
, y
2
). (25)
The inequality is given by
I = hA
0
(B B
0
) A
1
(B + B
0
)i 2 (26)
where
B =
1
2
[(1 + B
1
0
)B
2
01
(1 B
1
0
)B
2
00
]
B
0
=
1
2
[(1 B
1
1
)B
2
11
+ (1 + B
1
1
)B
2
10
] (27)
Accepted in Quantum 2010-10-02, click title to verify. Published under CC-BY 4.0. 9
0 0.5 1 1.5 2 2.5
1.5
2
2.5
CHSH
A,B1
CHSH
A,B2
optimal (qubits)
SEQ hierarchy level 1+AB
NPA hierarchy level 2
Figure 4: Upper bounds on the maximum value of CHSH
A,B2
as a function of the value of CHSH
A,B1
. The
values obtained at level 1+AB of the sequential hierarchy match the optimal values for qubit strategies found
in [9]. To show the effect of our new constraints, we plot the same bounds obtained via the standard NPA
hierarchy at level 2, treating the two Bobs as a single party.
and the bound 2 holds for sequential time-ordered local correlations.
The authors show that it is possible to violate the inequality up to a value of 2
2 using a
sequential quantum strategy, providing a lower bound to the maximum violation using a sequential
quantum strategy. Using our hierarchy at level 1+AB, we are able to certify a corresponding upper
bound that agrees with the value 2
2 up to the precision of the SDP solver. We therefore expect
that the strategy given in [8] is optimal for this inequality.
5 Discussion
We have presented a general method to bound sets of correlations arising from performing sequen-
tial measurements on entangled quantum states. Our techniques can be seen as part of a collection
of works that extend the original applicability of the NPA hierarchy to scenarios of restricted
dimension [33, 34] and entanglement [18], classicality [22], and modified causality [16? ].
We note that the techniques described in [16] can in principle deal with the sequential causal
structures considered in this work. More specifically, one could use their method to treat ‘quantum
exogenous’ variables by explicitly using the unitaries in (13) as operators in the generating set S
k
and defining a resulting relaxation. This method is significantly less efficient however since one
needs to go to high levels (with large moment matrices) of the corresponding relaxation, and
no convergence properties are proven. Given these points, it would thus be interesting to study
whether our method could be extended to other causal scenarios, or be used to improve the
efficiency of the method in [16]. For example, can our method be applied to give a convergent
hierarchy for a generic causal structure involving latent quantum variables?
The NPA hierarchy is often used as a numerical method to bound fidelities in self-testing proto-
cols [35]. One avenue of research would therefore be to investigate whether sequential measurement
scenarios can improve self-testing fidelity bounds, by adapting the current method to our hierarchy,
or to investigate the self-testing of quantum channels, to which sequential measurement scenarios
are naturally related. Finally, it would also be interesting to use our method to investigate to what
extent sequential measurements can improve other device-independent protocols. For example,
can our advantages in local guessing probability be translated to practical improvements to rates
in randomness extraction or quantum key distribution protocols?
Accepted in Quantum 2010-10-02, click title to verify. Published under CC-BY 4.0. 10
Acknowledgements
We thank Erik Woodhead for pointing out equation (12) and Flavien Hirsch for inspiring pre-
liminary discussions. We also thank Daniel Cavalcanti, Florian Curchod, Dr. Bibounde, Antonio
Acin, Remigiusz Augusiak, Marco Tulio Quintino and Peter Wittek for discussions throughout the
project.
All authors acknowledge funding from the Spanish MINECO (QIBEQI FIS2016-80773-P, Severo
Ochoa SEV-2015-0522, a Severo Ochoa PhD fellowship), Fundacio Cellex, Generalitat de Catalunya
(SGR 1381 and CERCA Programme). JB acknowldges funding from the AXA Chair in Quan-
tum Information Science, Juan de la Cierva-formación and the EU Quantum Flagship project
QRANGE. FB acknowledges the support from the Deutsche Forschungsgemeinschaft (DFG, Ger-
man Research Foundation) - Project number 414325145 in the framework of the Austrian Science
Fund (FWF): SFB F71.
References
[1] J. S. Bell. On the Einstein-Podolsky-Rosen paradox. Physics, 1:195, 1964.
[2] N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner. Bell nonlocality. Rev. Mod.
Phys., 86:839–840, 2014. DOI: 10.1103/RevModPhys.86.839.
[3] Koon Tong Goh, J ędrzej Kaniewski, Elie Wolfe, Tamás Vértesi, Xingyao Wu, Yu Cai, Yeong-
Cherng Liang, and Valerio Scarani. Geometry of the set of quantum correlations. Phys. Rev.
A, 97:022104, Feb 2018. DOI: 10.1103/PhysRevA.97.022104.
[4] Mafalda L. Almeida, Jean-Daniel Bancal, Nicolas Brunner, Antonio Acín, Nicolas Gisin, and
Stefano Pironio. Guess your neighbor’s input: A multipartite nonlocal game with no quantum
advantage. Phys. Rev. Lett., 104:230404, Jun 2010. DOI: 10.1103/PhysRevLett.104.230404.
[5] William Slofstra. The set of quantum correlations is not closed, 2017. URL https://arxiv.
org/abs/1703.08618. arXiv:1703.08618v2.
[6] M. Navascués, S. Pironio, and A. Acín. Bounding the set of quantum correlations. Phys. Rev.
Lett., 98:010401, 2007. DOI: 10.1103/PhysRevLett.98.010401.
[7] M. Navascués, S. Pironio, and A. Acín. A convergent hierarchy of semidefinite programs
characterizing the set of quantum correlations. New Journal of Physics, 10(7):073013, 2008.
DOI: 10.1088/1367-2630/10/7/073013.
[8] Rodrigo Gallego, Lars Erik Würflinger, Rafael Chaves, Antonio Acín, and Miguel Navascués.
Nonlocality in sequential correlation scenarios. New Journal of Physics, 16(3):033037, mar
2014. DOI: 10.1088/1367-2630/16/3/033037.
[9] Ralph Silva, Nicolas Gisin, Yelena Guryanova, and Sandu Popescu. Multiple observers can
share the nonlocality of half of an entangled pair by using optimal weak measurements. Phys.
Rev. Lett., 114:250401, Jun 2015. DOI: 10.1103/PhysRevLett.114.250401.
[10] Flavien Hirsch, Marco Túlio Quintino, Joseph Bowles, and Nicolas Brunner. Genuine hid-
den quantum nonlocality. Phys. Rev. Lett., 111:160402, Oct 2013. DOI: 10.1103/Phys-
RevLett.111.160402.
[11] Sandu Popescu. Bell’s inequalities and density matrices: Revealing “hidden” nonlocality. Phys.
Rev. Lett., 74:2619–2622, Apr 1995. DOI: 10.1103/PhysRevLett.74.2619.
[12] N. Gisin. Hidden quantum nonlocality revealed by local filters. Physics Letters A, 210(3):151
156, 1996. ISSN 0375-9601. DOI: https://doi.org/10.1016/S0375-9601(96)80001-6.
[13] F. J. Curchod, M. Johansson, R. Augusiak, M. J. Hoban, P. Wittek, and A. Acín. Unbounded
randomness certification using sequences of measurements. Phys. Rev. A, 95:020102, Feb 2017.
DOI: 10.1103/PhysRevA.95.020102.
[14] Matthew F Pusey. Anomalous weak values are proofs of contextuality. Physical review letters,
113(20):200401, 2014. DOI: 10.1103/PhysRevLett.113.200401.
[15] Costantino Budroni, Tobias Moroder, Matthias Kleinmann, and Otfried Gühne. Bound-
ing temporal quantum correlations. Physical review letters, 111(2):020403, 2013. DOI:
10.1103/PhysRevLett.111.020403.
[16] Elie Wolfe, Alejandro Pozas-Kerstjens, Matan Grinberg, Denis Rosset, Antonio Acín, and
Miguel Navascues. Quantum inflation: A general approach to quantum causal compatibility.
arXiv preprint arXiv:1909.10519, 2019. URL https://arxiv.org/abs/1909.10519.
Accepted in Quantum 2010-10-02, click title to verify. Published under CC-BY 4.0. 11
[17] W. Stinespring. Positive functions on C
-algebras. Proceedings of t he American Mathematical
Society, 6(2):211–211, Jan 1955. DOI: 10.1090/s0002-9939-1955-0069403-4.
[18] Tobias Moroder, Jean-Daniel Bancal, Yeong-Cherng Liang, Martin Hofmann, and Otfried
Gühne. Device-independent entanglement quantification and related applications. Phys. Rev.
Lett., 111:030501, Jul 2013. DOI: 10.1103/PhysRevLett.111.030501.
[19] Miguel Navascués, Yelena Guryanova, Matty J Hoban, and Antonio Acín. Almost quantum
correlations. Nature communications, 6(1):1–7, 2015. DOI: 10.1038/ncomms7288.
[20] Rudolf Haag and Daniel Kastler. An algebraic approach to quantum field theory. Journal of
Mathematical Physics, 5(7):848–861, 1964. DOI: 10.1063/1.1704187.
[21] William Slofstra. Tsirelson’s problem and an embedding theorem for groups arising from non-
local games. Journal of the American Mathematical Society 33, 2020. DOI: 10.1090/jams/929.
[22] F. Baccari, D. Cavalcanti, P. Wittek, and A. Acín. Efficient device-independent entanglement
detection for multipartite systems. Phys. Rev. X, 7:021042, Jun 2017. DOI: 10.1103/Phys-
RevX.7.021042.
[23] Roger Colbeck. Quantum and relativistic protocols for secure multi-party computation. arXiv
preprint arXiv:0911.3814, 2009. URL https://arxiv.org/abs/0911.3814.
[24] Roger Colbeck and Adrian Kent. Private randomness expansion with untrusted devices. Jour-
nal of Physics A: Mathematical and Theoretical, 44(9):095305, 2011. DOI: 10.1088/1751-
8113/44/9/095305.
[25] Renato Renner. Security of quantum key distribution. International Journal of Quantum
Information, 6(01):1–127, 2008. DOI: 10.1142/S0219749908003256.
[26] Olmo Nieto-Silleras, Stefano Pironio, and Jonathan Silman. Using complete measurement
statistics for optimal device-independent randomness evaluation. New Journal of Physics, 16
(1):013035, 2014. DOI: 10.1088/1367-2630/16/1/013035.
[27] Olmo Nieto-Silleras, Cédric Bamps, Jonathan Silman, and Stefano Pironio. Device-
independent randomness generation from several bell estimators. New journal of physics,
20(2):023049, 2018. DOI: 10.1088/1367-2630/aaaa06.
[28] Stefano Pironio, Antonio Acín, Serge Massar, A Boyer de La Giroday, Dzmitry N Matsukevich,
Peter Maunz, Steven Olmschenk, David Hayes, Le Luo, T Andrew Manning, et al. Random
numbers certified by bell’s theorem. Nature, 464(7291):1021, 2010. DOI: 10.1038/nature09008.
[29] Jean-Daniel Bancal, Lana Sheridan, and Valerio Scarani. More randomness from the same
data. New Journal of Physics, 16(3):033011, 2014. DOI: 10.1088/1367-2630/16/3/033011.
[30] Antonio Acín, Stefano Pironio, Tamás Vértesi, and Peter Wittek. Optimal randomness certi-
fication from one entangled bit. Physical Review A, 93(4):040102, 2016. DOI: 10.1103/Phys-
RevA.93.040102.
[31] Giacomo Mauro D’Ariano, Paoloplacido Lo Presti, and Paolo Perinotti. Classical randomness
in quantum measurements. Journal of Physics A: Mathematical and General, 38(26):5979,
2005. DOI: 10.1088/0305-4470/38/26/010.
[32] Cédric Bamps and Stefano Pironio. Sum-of-squares decompositions for a family of clauser-
horne-shimony-holt-like inequalities and their application to self-testing. Physical Review A,
91(5):052111, 2015. DOI: 10.1103/PhysRevA.91.052111.
[33] Miguel Navascués and Tamás Vértesi. Bounding the set of finite dimensional quantum corre-
lations. Phys. Rev. Lett., 115:020501, Jul 2015. DOI: 10.1103/PhysRevLett.115.020501.
[34] Miguel Navascués, Gonzalo de la Torre, and Tamás Vértesi. Characterization of quantum
correlations with local dimension constraints and its device-independent applications. Phys.
Rev. X, 4:011011, Jan 2014. DOI: 10.1103/PhysRevX.4.011011.
[35] Ivan Šupić and Joseph Bowles. Self-testing of quantum systems: a review. Quantum, 4:337,
September 2020. ISSN 2521-327X. DOI: 10.22331/q-2020-09-30-337.
A Stinespring dilation of sequential measurement
Consider for simplicity a sequence of two measurements with inputs x
1
, x
2
and outputs a
1
, a
2
on a single quantum system |ψi that is described by Kraus operators K
x
j
a
j
,i
j
. The sequence of
Accepted in Quantum 2010-10-02, click title to verify. Published under CC-BY 4.0. 12
measurement can be realised as follows. Introduce ancilla spaces A
0
1
and A
00
1
and the ancilla state
|0i = |0i
A
0
1
|0i
A
00
1
. Define an operator U
x
1
1
via its action on the state |ψi|0i as
U
x
1
1
|ψi|0i =
X
a
1
Z
µ
1
dµ
1
(K
x
1
a
1
1
|ψi)|a
1
i|µ
1
i. (28)
One has hφ|h0|h0|U
x
1
1
U
x
1
1
|ψi|0i|0i = hφ|ψi for all |ψi, |φi. It follows that U
x
1
1
can be extended to
a unitary operator acting on |ψi|0i. Measure the A
0
1
space in the |a
1
i basis, obtaining outcome a
1
.
Conditioning on outcome a
1
and tracing out the A
0
1
and A
00
1
spaces, one finds (4). We have thus
reproduced the first measurement in the sequence. Introducing a fresh ancilla and repeating this
for the second measurement in the sequence we find
A
x
a
= U
x
1
1
U
x
2
2
( Π
a
1
Π
a
2
)U
x
2
2
U
x
1
1
, (29)
where the Π
a
i
’s are projectors onto the corresponding spaces. The full measurement A
x
a
is thus
projective. We may repeat this process for a sequence of arbitrary length, and hence A
x
a
can be
taken to be projective without loss of generality.
B Detailed proof of fact 1
Here we give a proof of the reverse direction of fact 1, where we explicitly model the communication
channel in the Kraus operators. Enlarge the system via an ancilla state so that the full state is
|ψi |0i. This space will be used as a communication channel in the following. The first device
performs a measurement with Kraus operators K
x
1
a
1
=
P
a
2
A
x
1
x
2
a
1
a
2
V
x
1
, where V
x
1
is a unitary
operator that maps |0i to |x
1
i (for example, if x
1
= 0, 1 then V
x
1
= σ
x
1
x
). These operators
are independent of x
2
due to (11). The second device measures (projective) Kraus operators
K
x
2
a
2
=
P
x
1
,a
1
A
x
1
x
2
a
1
a
2
|x
1
ihx
1
|. The measurement operator describing the full sequence is therefore
K
x
1
a
1
K
x
2
a
2
K
x
2
a
2
K
x
1
a
1
=(
X
a
0
2
A
x
1
x
2
a
1
a
0
2
V
x
1
)(
X
x
0
1
,a
0
1
A
x
0
1
x
2
a
0
1
a
2
|x
0
1
ihx
0
1
|)(
X
a
00
2
A
x
1
x
2
a
1
a
00
2
V
x
1
)
=
X
x
0
1
(
X
a
0
2
A
x
1
x
2
a
1
a
0
2
X
a
0
1
A
x
0
1
x
2
a
0
1
a
2
X
a
00
2
A
x
1
x
2
a
1
a
00
2
) V
x
1
|x
0
1
ihx
0
1
|V
x
1
(30)
The resulting correlations are
hψ| h0|
X
x
0
1
(
X
a
0
2
A
x
1
x
2
a
1
a
0
2
X
a
0
1
A
x
0
1
x
2
a
0
1
a
2
X
a
00
2
A
x
1
x
2
a
1
a
00
2
) V
x
1
|x
0
1
ihx
0
1
|V
x
1
|ψi |0i
=hψ|(
X
a
0
2
A
x
1
x
2
a
1
a
0
2
X
a
0
1
A
x
1
x
2
a
0
1
a
2
X
a
00
2
A
x
1
x
2
a
1
a
00
2
)|ψi = hψ|A
x
1
x
2
a
1
a
2
|ψi (31)
as desired.
C Hierarchy for time ordered local correlations
Here we show how to modify the our hierarchy for sequential quantum correlations introduced in
the main text in order to approximate the set of time ordered local correlations. Following [8], we
say that the correlations from a Bell scenario are time ordered local if they can be described by
the following model
P (a, b|x, y) =
Z
λ
dλρ(λ)p(a|x, λ)p(b|y, λ) , (32)
Accepted in Quantum 2010-10-02, click title to verify. Published under CC-BY 4.0. 13
where the distribution p(a|x, λ) satisfies the following sequential no-signaling constraint for all
values of λ
X
a
k+1
,··· ,a
n
p(a|x, λ) p(a|x
0
, λ) = 0 a
1
, . . . , a
k
(33)
x, x
0
s.t x
i
= x
0
i
,
(i k),
and similarly for p(b|y, λ). Correlations in the above form are the only ones that can be achieve
with classical means in a sequential Bell scenario.
It is well know that, by using the constraints in (33), the model (32) can be reduced to a sum
over deterministic strategies, namely
P (a, b|x, y) =
X
λ
p(λ)D
SEQ
(a|x, λ)D
SEQ
(b|y, λ) , (34)
where the deterministic probability distributions split into a product
D
SEQ
(a|x, λ) =
n
Y
k=1
D(a
k
|x
1
, . . . , x
k
, λ) (35)
and where the expression D(a
k
|x
1
, . . . , x
k
, λ) corresponds to outputting deterministically a
k
=
λ(x
1
, . . . , x
k
) depending on the strategy given by λ(.) and on all the inputs of previous boxes in
the sequence (and similarly for Bob’s strategy).
Determining whether a given distribution admits a decomposition in such a form is an instance
of linear programming. Indeed, it implies checking if the distribution can be written as a con-
vex combination of a finite amount of extremal points, represented by all the possible choices of
deterministic strategies D
SEQ
(a|x, λ), D
SEQ
(b|y, λ). This linear program quickly becomes compu-
tationally intractable, since the number of extremal points increases exponentially with the number
of inputs. Moreover, for each additional box in the sequence, the scaling is even worse than the
equivalent multipartite locality scenario, because the possible strategies for each box depend on
the inputs of all the previous boxes.
That is why we are interested in relaxing the linear program with an SDP, in a similar spirit
as in [22]. In particular, the objective is to have a way of determining whether a distribution is
sequentially local that, despite being a relaxation, works in many relevant cases and has a better
scaling with the number of inputs/boxes. In the following we show how to do this by adapting our
sequential hierarchy. The first step is to find a particular realisation of sequentially local correlations
in terms of a quantum measurement on a quantum state; namely we look for realisation of the
kind
p(a, b|x, y) = tr(ρ
AB
A
x
a
B
y
b
) . (36)
Now, it can be easily checked that correlations of the kind (34) can be reproduced by the
following choice of state
ρ
AB
=
X
λ
p(λ)|λihλ|
2
(37)
and measurements for Alice and Bob’s side respectively
A
x
a
=
X
λ
D
SEQ
(a|x, λ) |λihλ|,
B
y
b
=
X
λ
D
SEQ
(b|y, λ) |λihλ|.
(38)
It is also easy to verify that measurements in the above form satisfy the constraints (10) and
(11). In particular, the second property follows directly from the fact that the deterministic strate-
gies D
SEQ
(a|x, λ) and D
SEQ
(b|y, λ) satisfy the no-signalling condition (33). Moreover, since all
measurement operators are diagonal in the |λi basis it follows that [A
x
a
, A
x
0
a
0
] = 0 and [B
y
b
, B
y
0
b
0
] = 0.
Accepted in Quantum 2010-10-02, click title to verify. Published under CC-BY 4.0. 14
In other words, the set of time ordered local correlations can be obtained by means of locally
commuting quantum sequential measurements. These commutativity conditions imply additional
linear constraints on the moment matrix elements, expressed by some fixed matrices G
LOC
i
. We
can thus define the following hierarchy
Hierarchy for sequential local correlations (level k)
Find Γ
k
such that Γ
k
< 0, Γ
k
= Γ
k
, Γ
(0,0)
k
= 1, (39)
tr[Γ
k
G
i
] = 0 i,
tr[Γ
k
G
SEQ
i
] = 0 i,
tr[Γ
k
G
LOC
i
] = 0 i,
tr[Γ
k
F
i
] = P
i
i.
We call L
k
SEQ
the set defined at level k of this hierarchy. By construction, each L
k
SEQ
defines an
outer approximation of the set of time ordered local correlations. The computational advantage
gained by replacing a linear programming characterisation of the exact set with an SDP relaxation
is clear: at each fixed level k, the number of variables involved in the moment matrix Γ
k
scales
polynomially with the number of input choices for x
1
, . . . , x
n
and y
1
, . . . , y
n
, contrarily to the
exponential scaling of the linear programming. This may allow one to probe scenarios which would
otherwise be practically impossible using linear programming methods.
D Using the hierarchy to upper bound guessing probabilities
We first review how the standard NPA hierarchy can be used to provide upper bounds to the
guessing probability (17) (see also [26, 27, 29]). Define the subnormalised distributions (both
normalised to p
E
(e))
˜p
e
AB
(a, b|x, y) = p
ABE
(a, b, e|x, y) = p
E
(e)p
AB
(a, b|x, y, e),
˜p
e
B
(b|y) = p
BE
(b, e|y) = p
E
(e)p
B
(b|y, e) =
X
a
˜p
e
AB
(a, b|x, y).
Define Q
p
to be the set of quantum correlations, subnormalised to p, that is, P (a, b|x, y) Q
p
if
P (a, b|x, y) = p P
0
(a, b|x, y) for some P
0
Q. Thus ˜p
e
AB
Q
p(e)
and with this notation (17) reads
G(y
) = max
˜p
e
AB
|b|
X
e=1
˜p
e
B
(e|y
),
X
e
˜p
e
AB
(a, b|x, y) = P
obs
(a, b|x, y) (40)
˜p
e
AB
(a, b|x, y) Q
p(e)
e.
Define the set Q
p(e)
k
in the same way as Q
k
but changing the normalisation condition Γ
(0,0)
k
= 1
to Γ
(0,0)
k
= p(e) in (8). Thus Q
p(e)
k
Q
p(e)
. The problem (40) can therefore be upper bounded by
relaxing the condition ˜p
e
AB
(a, b|x, y) Q
p(e)
to ˜p
e
AB
(a, b|x, y) Q
p(e)
k
. Practically, this means that
one has to consider a set of |b| subnormalised moment matrices in the optimisation.
An analogous procedure can be followed in the sequential scenario by defining the set Q
p
SEQ
,
the set of subnormalised sequential correlations, and corresponding relaxations Q
p
SEQ,k
. Following
the same logic as above, one arrives at the guessing probability
G(y
) = max
˜p
e
AB
X
e
˜p
e
B
(e|y
),
X
e
˜p
e
AB
(a, b|x, y) = P
obs
(a, b|x, y) (41)
˜p
e
AB
(a, b|x, y) Q
p(e)
e.
One then relaxes the condition ˜p
e
AB
(a, b|x, y) Q
p
SEQ
to ˜p
e
AB
(a, b|x, y) Q
p
SEQ,k
, thus needing as
many moment matrices as the total alphabet size of b
Accepted in Quantum 2010-10-02, click title to verify. Published under CC-BY 4.0. 15