Semi-device-independent certification of indefinite causal
order
Jessica Bavaresco
1
, Mateus Araújo
2
, Časlav Brukner
1,3
, and Marco Túlio Quintino
4
1
Institute for Quantum Optics and Quantum Information (IQOQI), Austrian Academy of Sciences, Boltzmanngasse 3, A-1090
Vienna, Austria
2
Institute for Theoretical Physics, University of Cologne, Zülpicher Strasse 77, 50937 Cologne, Germany
3
Vienna Center for Quantum Science and Technology (VCQ), Faculty of Physics,
University of Vienna, Boltzmanngasse 5, A-1090 Vienna, Austria
4
Department of Physics, Graduate School of Science, The University of Tokyo, Hongo 7-3-1, Bunkyo-ku, Tokyo 113-0033,
Japan
When transforming pairs of independent
quantum operations according to the fun-
damental rules of quantum theory, an in-
triguing phenomenon emerges: some such
higher-order operations may act on the in-
put operations in an indefinite causal or-
der. Recently, the formalism of process
matrices has been developed to investig-
ate these noncausal properties of higher-
order operations. This formalism pre-
dicts, in principle, statistics that ensure
indefinite causal order even in a device-
independent scenario, where the involved
operations are not characterised. Nev-
ertheless, all physical implementations of
process matrices proposed so far require
full characterisation of the involved oper-
ations in order to certify such phenom-
ena. Here we consider a semi-device-
independent scenario, which does not re-
quire all operations to be characterised.
We introduce a framework for certifying
noncausal properties of process matrices
in this intermediate regime and use it to
analyse the quantum switch, a well-known
higher-order operation, to show that, al-
though it can only lead to causal statistics
in a device-independent scenario, it can ex-
hibit noncausal properties in semi-device-
independent scenarios. This proves that
the quantum switch generates stronger
noncausal correlations than it was previ-
ously known.
Jessica Bavaresco: jessica.bavaresco@oeaw.ac.at
Marco Túlio Quintino: quintino@eve.phys.s.u-tokyo.ac.jp
A common quantum information task consists
in certifying that some uncharacterised source is
preparing a system with some features. By mak-
ing the assumption that the measurement devices
are completely characterised, that is, that they
are known exactly, it is possible to infer proper-
ties of the system. In this device-dependent scen-
ario, fidelity of a quantum state with respect to a
target state can be estimated, entanglement wit-
nesses can be evaluated [1], and even complete
characterisation of the source via state tomo-
graphy is possible [2].
Remarkably, it is possible to certify properties
of systems even without fully characterizing the
measurement devices [3, 4]. In such a device-
independent scenario it is only assumed that the
measurements are done by separated parties and
compose under a tensor product, which is justi-
fied by implementing them with a space-like sep-
aration. Under these circumstances, Bell scen-
arios can be used to certify properties like en-
tanglement of quantum states [4], incompatib-
ility of quantum measurements [5], or to per-
form device-independent state estimation via self-
testing [6, 7].
Since the assumptions are weaker, demonstra-
tions of device-independent certification are usu-
ally experimentally challenging. For instance, al-
though experimental device-independent certific-
ation of entanglement has been reported [8, 9, 10,
11], its experimental difficulty has so far preven-
ted its use in practical applications such as device-
independent quantum key distribution [12] and
randomness certification [13].
An interesting middle ground is the semi-
device-independent scenario, where assumptions
Accepted in Quantum 2019-07-07, click title to verify. Published under CC-BY 4.0. 1
arXiv:1903.10526v3 [quant-ph] 9 Aug 2019
are made about some parties but not others.
Semi-device-independent schemes have been de-
veloped and extensively studied for the certific-
ation of entanglement [14] and measurement in-
compatibility [15, 16], known as EPR-steering,
and applied to quantum key distribution proto-
cols where some but not all parties can be trusted
[17].
A close analogy can be developed with regard
to the certification of indefinite causal order, as
encoded in a process matrix [18]. A process mat-
rix is a higher-order operation [19, 20, 21] i.e.
a transformation of quantum operations that
acts on independent sets of operations. Funda-
mental laws of quantum theory predict the exist-
ence of process matrices that act on these opera-
tions in a such a way that a well-defined causal
order cannot be established among them. Pro-
cess matrices with indefinite causal order were
proven to be a powerful resource, outperforming
causally ordered ones in tasks such as quantum
channel discrimination [22], communication com-
plexity [23, 24], quantum computation [25], and
inverting unknown unitary operations [26].
To certify that a process matrix in fact does
not act in a causally ordered way, there are two
standard methods available in the literature. The
first is to evaluate a causal witness [27, 28]. Ana-
logous to the evaluation of an entanglement wit-
ness, this method relies on detailed knowledge of
the quantum operations being implemented, and
as such it allows for a device-dependent certifica-
tion. All experimental certifications of indefinite
causal order to date either measure a causal wit-
ness [29, 30] or rely on similar device-dependent
assumptions [31, 32, 33]. The second method is
the violation of a causal inequality, phenomenon
which is also predicted by quantum mechanics
[18, 34]. Analogous to the violation of a Bell in-
equality, this method does not rely on detailed
knowledge of the quantum operations implemen-
ted by the parties, but rather only that they com-
pose under a tensor product. As such, it allows
for a device-independent certification. When a
causal inequality is violated, it is verified that
least one of the principles used to derived it is
not respected. Moreover, this claim holds true in-
dependently of the physical theory that supports
the experiment that led to the violation. Hence,
although we focus on quantum theory, indefinite
causal order could in principle be certified even
without relying on the laws of quantum mechan-
ics. Although it would be highly desirable to per-
form such device-independent certification of in-
definite causal order, no physical implementation
of process matrices that would violate a causal
inequality is currently known.
In this work, we introduce a semi-device-
independent framework for certifying noncausal
properties of process matrices that allows for an
experimental certification of indefinite causal or-
der that relies on fewer assumptions than previ-
ous ones. In our semi-device-independent scen-
ario, the operations of some parties are fully char-
acterized while no assumptions are made about
the others.
We begin by considering the bipartite case,
for which we construct a general framework
for certifying indefinite causal order in a semi-
device-independent scenario, while contextualiz-
ing previously developed device-dependent and -
independent ones. We then extend our framework
to a tripartite case in which the third party is al-
ways in the future of the other two, and provide
an extensive machinery that may be generalized
to other multipartite scenarios. We apply our
methods to the notorious quantum switch [22, 35],
a process matrix that, despite having an indefin-
ite causal order, only leads to causal correlations
in a device-independent scenario. We show that
the noncausal properties of the quantum switch
can be certified in a semi-device-independent way,
proving that it generates stronger noncausal cor-
relations than it was previously known.
1 Preliminaries
In our certification scheme, we will deal with
statistical data in the form of behaviours.
A general bipartite behaviour {p
(
ab|xy
)
} is a set
of joint probability distributions, that is, a set in
which each element p
(
ab|xy
)
is a real non-negative
number such that
P
a,b
p
(
ab|xy
) = 1
for all x, y,
where a {
1
, . . . , O
A
} and b {
1
. . . , O
B
} are
labels for outcomes and x {
1
, . . . , I
A
} and y
{
1
, . . . , I
B
} are labels for inputs, for parties Alice
and Bob, respectively.
The most general operation allowed by
quantum theory is modelled by a quantum instru-
ment, which is a set of completely-positive (CP)
maps that sum to a completely-positive trace-
preserving (CPTP) map [36].
Accepted in Quantum 2019-07-07, click title to verify. Published under CC-BY 4.0. 2
The Choi-Jamiołkowski (CJ) isomorphism [37,
38, 39] allows us to represent every linear map
1
M
:
L
(
H
I
)
L
(
H
O
)
by a linear operator M
L
(
H
I
H
O
)
acting on the joint input and output
Hilbert spaces. In this representation, a set of
instruments is a set of operators {I
a|x
}, I
a|x
L(H
I
H
O
), that satisfies
I
a|x
0, a, x (1)
Tr
O
X
a
I
a|x
= 1
I
, x, (2)
where x {
1
, . . . , I} labels the instrument in the
set and a {
1
, . . . , O} its outcomes, and 1
I
is
the identity operator on H
I
.
Now let us consider the most general set of
behaviours which respects quantum theory. For
that we follow the steps of ref. [18] to analyse
behaviours that can be extracted by pairs of
independent quantum instruments. Let {A
a|x
},
A
a|x
L
(
H
A
I
H
A
O
)
and {B
b|y
}, B
b|y
L
(
H
B
I
H
B
O
)
be the Choi operators of Alice’s
and Bob’s local instruments. We then seek a
function which assigns probabilities to a pair of
instrument elements A
a|x
and B
b|y
. In order
to preserve the structure of quantum mechan-
ics, we assume that this function is linear in
both arguments. It follows from the Riesz rep-
resentation lemma [40] that this general linear
function necessarily has the form of p
(
ab|xy
) =
Tr
h
(A
A
I
A
O
a|x
B
B
I
B
O
b|y
) W
i
for some linear oper-
ator W L
(
H
A
I
H
A
O
H
B
I
H
B
O
)
. In or-
der to be consistent with extended quantum scen-
arios, we also consider the case where Alice and
Bob may share a (potentially entangled) auxili-
ary quantum state ρ L
(
H
A
I
0
H
B
I
0
)
, and have
instruments {A
0
a|x
}, A
0
a|x
L
(
H
A
I
0
A
I
A
O
)
, {B
0
b|y
},
B
0
b|y
L
(
H
B
I
0
B
I
B
O
)
which acts on the space of
the operator W and the auxiliary state ρ. A pro-
cess matrix is then defined as the most general
linear operator W such that
p(ab|xy) =
Tr
h
(A
0A
I
0
A
I
A
O
a|x
B
0B
I
0
B
I
B
O
b|y
)(W
A
I
A
O
B
I
B
O
ρ
A
I
0
B
I
0
)
i
(3)
represents
2
elements of valid probability distribu-
tions for every state ρ and sets of instruments
{A
0
a|x
} and {B
0
b|y
}.
1
In this paper we only consider finite dimensional com-
plex linear spaces. That is, all linear spaces are isomorphic
to C
d
for some natural number d.
2
In eq. (3), as well as in some other equations, we add
superscripts on the operators to indicate the Hilbert spaces
in which they act, for sake of clarity.
It was shown in ref. [27] that a linear operator
W is a process matrix if and only if it respects
W 0 (4)
Tr W = d
A
O
d
B
O
(5)
A
I
A
O
W =
A
I
A
O
B
O
W (6)
B
I
B
O
W =
A
O
B
I
B
O
W (7)
W =
A
O
W +
B
O
W
A
O
B
O
W, (8)
where
X
W
:
=
Tr
X
W
1
X
d
X
is the trace-and-replace
operation and d
X
= dim(H
X
).
We then define process behaviours {p
Q
(
ab|xy
)
}
as behaviours which can be obtained by process
matrices according to
p
Q
(ab|xy) = Tr
h
(A
A
I
A
O
a|x
B
B
I
B
O
b|y
) W
A
I
A
O
B
I
B
O
i
,
(9)
for all a, b, x, y.
Now we begin to discuss the causal properties
of behaviours and process matrices.
A behaviour is considered causally ordered
when it can be established that one party acted
before the other because the marginal probability
distributions of one party do not depend on the
inputs of the other. Formally, we have that a be-
haviour {p
AB
(
ab|xy
)
} is causally ordered from
Alice to Bob if it satisfies
X
b
p
AB
(ab|xy) =
X
b
p
AB
(ab|xy
0
), (10)
for all a, x, y, y
0
, and equivalently from Bob to
Alice.
Behaviours that are within the convex hull of
causally ordered behaviours are also considered
causal, as they can be interpreted as a classical
mixture of causally ordered behaviours. Hence,
a causal behaviour {p
causal
(
ab|xy
)
} is a behaviour
that can be expressed as a convex combination of
causally ordered behaviours, i.e.,
p
causal
(ab|xy)
:
= qp
AB
(ab|xy) + (1 q)p
BA
(ab|xy),
(11)
for all a, b, x, y, where
0
q
1
is a real number.
Behaviours that do not satisfy eq. (11) are called
noncausal behaviours.
Following the same reasoning as the one in the
definition of a general process matrix, in order
to associate causal properties to process matrices
we now define causally ordered process matrices
as the most general operator that takes pairs of
local instruments to causally ordered behaviours,
that is,
p
AB
(ab|xy) = Tr
h
(A
a|x
B
b|y
) W
AB
i
, (12)
Accepted in Quantum 2019-07-07, click title to verify. Published under CC-BY 4.0. 3
for all a, b, x, y. This definition is equivalent to
the one in refs. [20, 18], which states that a bi-
partite process matrix W
AB
L
(
H
A
I
H
A
O
H
B
I
H
B
O
)
is causally ordered from Alice to Bob
if it satisfies
W
AB
=
B
O
W
AB
, (13)
and equivalently from Bob to Alice.
In line with the definition of a causal beha-
viour, a causally separable process matrix W
sep
L
(
H
A
I
H
A
O
H
B
I
H
B
O
)
is a process matrix
that can be expressed as a convex combination of
causally ordered process matrices, i.e.,
W
sep
:
= qW
AB
+ (1 q)W
BA
, (14)
where
0
q
1
is a real number. Process
matrices that do not satisfy eq. (14) are called
causally nonseparable process matrices.
2 Certification
Let us consider the following task: we are
given a behaviour that describes the statistics of a
quantum experiment. We analyse this behaviour
in the process matrix formalism, that is, we as-
sume that there exists a process matrix W and
sets of local instruments that give rise to this be-
haviour according to the rules of quantum theory.
Without any information about W i.e., without
direct assumptions about the process matrix the
goal is to verify whether it is causally nonsepar-
able. Additionally, information about the instru-
ments which were performed may or may not be
given.
The assumptions about the instruments
can be split in three: device-dependent, -
independent, and semi-device-independent. A
device-dependent certification scenario is one in
which the operations of all parties are fully char-
acterised, i.e., the whole matrix description of
the elements of all applied instruments is known.
A device-independent certification scenario is the
opposite, no knowledge or assumption is made re-
garding the operations performed by any parties,
not even the dimension of the linear spaces
used to describe them. Finally, a semi-device-
independent certification scenario is one in which
at least one party is device-dependent, which is
often called trusted, and at least one is device-
independent, often called untrusted.
In the following we formalise our notions of cer-
tification for bipartite process matrices. We refer
to appendix E and to section 3 for a discussion of
more general scenarios.
Definition 1
(Device-dependent certification)
.
Given a process behaviour
{p
Q
(
ab|xy
)
}
, that arises
from known instruments
{A
a|x
}
and
{B
b|y
}
and
an unknown bipartite process matrix, one certifies
that this process matrix is causally nonseparable
in a device-dependent way if
p
Q
(ab|A
a|x
, B
b|y
) 6= Tr
h
(A
a|x
B
b|y
)W
sep
i
,
(15)
for all
a, b, x, y
, and for all causally separable
process matrices W
sep
.
Definition 2
(Device-independent certification)
.
Given a process behaviour
{p
Q
(
ab|xy
)
}
, that arises
from unknown instruments and an unknown bi-
partite process matrix, one certifies that this pro-
cess matrix is causally nonseparable in a device-
independent way if
p
Q
(ab|xy) 6= Tr
h
(A
a|x
B
b|y
)W
sep
i
(16)
for all
a, b, x, y
, and for all causally separable
process matrices
W
sep
and all general instruments
{A
a|x
} and {B
b|y
}.
Definition 3
(Semi-device-independent certific-
ation)
.
Given a process behaviour
{p
Q
(
ab|xy
)
}
,
that arises from unknown instruments on Alice’s
side, known instruments
{B
b|y
}
on Bob’s side,
and an unknown bipartite process matrix, one
certifies that this process matrix is causally non-
separable in a semi-device-independent way if
p
Q
(ab|x , B
b|y
) 6= Tr
h
(A
a|x
B
b|y
)W
sep
i
(17)
for all
a, b, x, y
, and for all causally separable
process matrices
W
sep
and all general instruments
{A
a|x
}.
On eqs. (15), (16), and (17) one can identify
the quantities that are given the behaviour and
the trusted instruments that belong to the device-
dependent parties and the variables in the certi-
fication problem the unknown instruments that
belong to the device-independent parties and any
causally separable process matrix. If one can
guarantee that, for any sets of instruments for the
device-independent parties and any causally sep-
arable process matrix, the given behaviour can-
not be described by the left-hand side of eqs. (15),
Accepted in Quantum 2019-07-07, click title to verify. Published under CC-BY 4.0. 4
Device-dependent
Given quantities Variables
{p
Q
(ab|xy)} W
{A
a|x
}, {B
b|y
}
Device-independent
Given quantities Variables
{p
Q
(ab|xy)} d
A
I
, d
A
O
, d
B
I
, d
B
O
{A
a|x
}, {B
b|y
}
W
Semi-device-independent
Given quantities Variables
{p
Q
(ab|xy)} d
A
I
, d
A
O
{B
b|y
} {A
a|x
}
W
Table 1: Comparison between the given (known) quant-
ities and the variables (unknown quantities) in each scen-
ario with different levels of assumptions about the op-
erations of each party involved in the task of certifying
noncausal properties of a process matrix.
(16), or (17), then the fact that the process matrix
that generated this behaviour is causally nonsep-
arable is certified. A summary of the given quant-
ities and variables in each certification scenario is
provided by table 1.
Before proceeding we remark an analogy with
the entanglement certification problem in which
behaviours are assumed to arise from quantum
measurements performed on a quantum state.
In the entanglement certification case, device-
dependent scenarios are related to entangle-
ment witnesses [1], device-independent scenarios
to Bell nonlocality [4], and the semi-device-
independent ones to EPR-steering [14].
Device-dependent
We start be analysing the device-dependent
scenario and definition 1. This scenario has been
thoroughly studied before using the concept of
causal witnesses [27], analogous to entanglement
witnesses [1], and now we formulate it under our
certification paradigm.
In this scenario, the behaviour and sets of in-
struments of both parties are given and we aim to
check whether the given process behaviour is con-
sistent with performing these exact instruments
on a causally separable process matrix. This
problem can be solved by semidefinite program-
ming (SDP) with the following formulation:
given {p
Q
(ab|xy)}, {A
a|x
}, {B
b|y
}
find W
subject to p
Q
(ab|xy) = Tr
(A
a|x
B
b|y
)W
a, b, x, y
W SEP,
(18)
where SEP denotes the set of causally separable
matrices (i.e. W is constrained to eq. (14)) which
can be characterized by SDP.
If the problem is infeasible, that is, if there does
not exist a process matrix W that satisfies the
constraints of eq. (18), then the process matrix
that generated {p
Q
(
ab|xy
)
} is certainly causally
nonseparable. Consequently, there exists a causal
witness that can certify it, without the need of
performing full tomography of the process mat-
rix [27]. On the contrary, if the problem is feas-
ible, then the solution provides a causally separ-
able process matrix that could have generated the
given behaviour.
We now show that all causally nonseparable
process matrices can be certified to be so in a
device-dependent way.
Theorem 1.
All noncasual process matrices can
be certified in a device-dependent way for some
choice of instruments.
The proof of the above theorem follows from
the fact that one can always consider a scenario
where Alice and Bob have access to tomograph-
ically complete instruments, which allows for the
complete characterization of the process matrix
[41, 42].
Device-independent
A device-independent approach for the process
matrix formalism has been previously studied in
terms of causal inequalities [34], analogous to Bell
inequalities [4], and now we formulate it under
our certification paradigm, exploring definition 2.
Accepted in Quantum 2019-07-07, click title to verify. Published under CC-BY 4.0. 5
In a device-independent scenario, besides as-
suming that the given behaviour is a process be-
haviour following eq. (9), no extra assumptions
are made. It is then necessary to check whether
the given behaviour is consistent with probability
distributions that come from any tensor product
of pair of sets of instruments, with fixed number
of inputs and outputs, performed on any causally
separable process matrix of any dimension.
Before characterizing the problem of whether
a certain behaviour can be obtained by a caus-
ally separable process matrix, we ask the more
fundamental question of whether any behaviour
can be obtained by a general process matrix on
which instruments are performed locally. That is,
whether all general (valid) behaviours are process
behaviours.
By definition, every process matrix leads to
valid general behaviours. However, it is shown
in ref. [43] that in the scenario where all parties
have dichotomic inputs and outputs, the determ-
inistic two-way signalling behaviour defined by
p
2WS
(
ab|xy
) :=
δ
a,y
δ
b,x
, where δ
i,j
= 1
if i
=
j
and δ
i,j
= 0
otherwise, cannot be obtained ex-
actly by any process matrix. Here we show that
one cannot obtain this two-way signalling beha-
viour even approximately for finite-dimensional
process matrices. The proof can be found in ap-
pendix A.
Theorem 2.
All process behaviours are valid be-
haviours, however, not all valid behaviours are
process behaviours.
In particular, in the scenario where all parties
have dichotomic inputs and outputs, any beha-
viour {p(ab|xy)} such that
1
4
X
a,b,x,y
δ
a,y
δ
b,x
p(ab|xy) > 1
1
d + 1
is not a process behaviour for process matrices
with total dimension d
A
I
d
A
O
d
B
I
d
B
O
= d.
Here we can make a parallel with Bell non-
locality, where the Popescu-Rohrlich behaviour
is known to respect the non-signalling conditions
which arise naturally in Bell scenarios but cannot
be obtained by performing local measurements on
entangled states [44, 45, 46].
As for causal behaviours, the analogous ques-
tion is also pertinent. Can all causal behaviours
be obtained by pair of sets of instruments and
causally separable process matrices? We answer
this question positively, which allows us to re-
late the properties of a behaviour directly to the
properties of the process matrices that could have
given rise to it.
Lemma 1.
A general behaviour is causal if and
only if it is a process behaviour that can be ob-
tained by a causally separable process matrix.
The proof is made by explicitly constructing
the instruments and causally separable process
matrix that can recover any causal behaviour. It
can be found in appendix B.
This result allows us to identify which causally
nonseparable process matrices can be certified in
a device-independent way:
Theorem 3.
A process matrix can be certified to
be causally nonseparable in a device-independent
way if and only if it can generate a noncausal
behaviour for some choice of instruments for Alice
and Bob.
Proof.
If a process matrix is causally separable
then its behaviours will be causal. If a behaviour
is causal, even though it could in principle have
been generated by a causally nonseparable process
matrix, according to lemma 1 it can always be
reproduced by a causally separable process matrix.
Hence, no causal properties of the process matrix
can be inferred.
From the formulation of the device-
independent certification problem in definition 2,
it is not clear whether one could obtain a simple
characterisation to solve it. In particular, be-
cause there are no constraints on the dimension
of the linear spaces and there is a product of
variables (that represent the unknown instru-
ments and process matrix). Interestingly, we
can explore the above theorem to present simple
necessary and sufficient conditions for a general
behaviour to allow for device-independent certi-
fication of indefinite causal order. This follows
from the fact that a behaviour can be checked
to be noncausal by linear programming [34].
More explicitly, the certification problem can be
formulated as follows:
Accepted in Quantum 2019-07-07, click title to verify. Published under CC-BY 4.0. 6
given {p
Q
(ab|xy)}
find q
1
(λ), q
2
(λ)
s.t. p
Q
(ab|xy) =
X
λ
h
q
1
(λ)D
AB
λ
(ab|xy)+
+ q
2
(λ)D
BA
λ
(ab|xy)
i
, a, b, x, y
q
1
(λ) 0, q
2
(λ) 0, λ,
(19)
where {D
AB
λ
(
ab|xy
)
} and {D
BA
λ
(
ab|xy
)
} are
the finite set of deterministic causal distributions
described in ref. [34].
If the problem is infeasible, then the process
matrix that was used to generate the process be-
haviour {p
Q
(
ab|xy
)
} is certainly causally nonsep-
arable and there exists a causal inequality that
can witness it [34]. If the problem is feasible, then
one can use the results presented in appendix B to
explicitly find a causally separable process matrix
W
sep
and sets of instruments {A
a|x
} and {B
b|y
}
such that p
Q
(ab|xy) = Tr
h
(A
a|x
B
b|y
)W
sep
i
.
Differently from the device-dependent scenario,
it is known that some causally nonseparable pro-
cess matrices cannot be certified in a device-
independent way [27, 47, 48]. In particular,
there exist causally nonseparable bipartite pro-
cess matrices that, for any choice of instruments
of Alice and Bob, will always lead to causal beha-
viours. This result was first presented in ref. [48]
and we rephrase it here:
Proposition 1
(Device-dependent certifiable,
device-independent noncertifiable process matrix)
.
There exist causally nonseparable process matrices
that, for any sets of instruments, always give rise
to causal behaviours. That is, a causally nonsep-
arable process matrix that cannot be certified in a
device-independent way.
In particular, let
W L
(
H
A
I
A
O
B
I
B
O
) be a pro-
cess matrix and
W
T
B
be the partial transposition
of
W
with respect to some basis in
L
(
H
B
I
B
O
) for
Bob. If
W
T
B
is causally separable, the behaviour
generated by
p
Q
(
ab|xy
) =
Tr
h
(A
a|x
B
b|y
) W
i
is
causal for every sets of instruments
{A
a|x
}
and
{B
b|y
}.
We would like to remark that this phenomenon
can be seen as a consequence of the choice of
definition of causally separable process matrices.
Recalling section 1, a causally ordered process
matrix is defined as the most general operator
W
AB
that takes any pairs of sets of instru-
ments to causally ordered behaviours according
to p
AB
(
ab|xy
) =
Tr
[(
A
a|x
B
b|y
)
W
AB
]
. On
the other hand, the definition of a causally sep-
arable process matrix W
sep
as a convex combin-
ation of process matrices with definite causal or-
ders, instead of focusing on the behaviours, has
an arguably more physical motivation of a clas-
sical mixture of causal orders. If the definition
were to, alternatively, focus on the behaviours,
then a natural choice would be to define a ‘caus-
ally separable’ process matrix
˜
W
sep
as the most
general operator that takes any pairs of sets of
instruments to causal behaviours according to
p
causal
(
ab|xy
) =
Tr
[(
A
a|x
B
b|y
)
˜
W
sep
]
. With
this alternative, inequivalent definition, ‘caus-
ally nonseparable’ process matrices would always
lead to noncausal behaviours, for some choice
of instruments, by definition. We observe the
phenomenon of causally nonseparable process
matrices leading exclusively to causal behaviours,
presented in proposition 1, when we take the phys-
ically motivated definition, and it exposes an in-
trinsic difference between these two kinds of reas-
oning. In the next sections, we show how this
phenomenon manifests itself in the semi-device-
independent scenario.
Semi-device-independent
In this final scenario, which has not been ex-
plored for process matrices before, we have the
information of the behaviour and the instruments
of one party, in this case, Bob. According to defin-
ition 3, one needs to check whether the given be-
haviour can be reproduced by performing these
exact given instruments for Bob, and any set of
instruments for Alice with fixed number of inputs
and outputs, on any causally separable process
matrix that has a fixed dimension on Bob’s side.
Since both the process matrix and Alice’s instru-
ments are variables in eq. (17), it is not clear
whether this problem can be solved by SDP.
Our approach contrasts a previous one which
exploits communication complexity tasks to cer-
tify indefinite causal order in process matrices as-
suming an upper bound for communication capa-
city between parties and the dimension of their
local systems [23, 24].
However, consider the following expression for
Accepted in Quantum 2019-07-07, click title to verify. Published under CC-BY 4.0. 7
a process behaviour,
p(ab|xy) = Tr
h
(A
a|x
B
b|y
)W
i
(20)
= Tr
h
B
b|y
Tr
A
(A
a|x
1
B
W )
i
(21)
= Tr
B
b|y
w
Q
a|x
, a, b, x, y, (22)
which motivates us to define w
Q
a|x
.
Definition 4
(Process assemblage)
.
A process
assemblage
{w
Q
a|x
}
is a set of operators
w
Q
a|x
L
(
H
B
I
H
B
O
) for which there exist a process
matrix
W
A
I
A
O
B
I
B
O
and a set of instruments
{A
A
I
A
O
a|x
} such that
w
Q
a|x
= Tr
A
I
A
O
h
(A
A
I
A
O
a|x
1
B
I
B
O
)W
A
I
A
O
B
I
B
O
i
,
(23)
for all a, x.
By defining the process assemblage, we gather
all the variables in the certification problem in
one object and can start to relate properties of
this object to properties of the process matrix.
We remark that the process assemblage gener-
alizes the notion of assemblage in EPR-steering
[14, 49], which is recovered when both Alice’s and
Bob’s output spaces have d
A
O
=
d
B
O
= 1
. Con-
sequently, {A
a|x
} becomes a set of POVMs, W
becomes a bipartite quantum state, and the pro-
cess assemblage recovers the steering assemblage
σ
a|x
= Tr
A
(A
a|x
1
B
ρ
AB
) [49].
Let us first examine the equation below more
closely:
p(ab|xy) = Tr
B
b|y
w
a|x
. (24)
In the same way that a process matrix was
defined as the most general operator that takes
sets of local instruments to a behaviour, we can
define a general assemblage to be the most gen-
eral object that takes a set of instruments to a
valid behaviour and respects linearity. In the ap-
pendix C, we prove that this definition is equival-
ent to:
Definition 5
(General assemblage)
.
A general
assemblage
{w
a|x
}
is a set of operators
w
a|x
L(H
B
I
H
B
O
) that satisfies
w
a|x
0 a, x (25)
Tr
X
a
w
a|x
= d
B
O
x (26)
X
a
w
a|x
=
B
O
X
a
w
a|x
x. (27)
By defining the general assemblage as the most
general set of operators that takes a set of instru-
ments to a behaviour and respects linearity, we
are no longer considering its relation with a pro-
cess matrix or requiring that it is a process as-
semblage.
If one compares the set of all general as-
semblages to the set of all process assemblages,
it is clear that the set of general assemblages con-
tains the set of process assemblages, since one
can see from eq. (21) that all process assemblages
lead to valid behaviours. But the former set is in
principle larger, an outer approximation with a
simpler characterisation. We show that, indeed,
the set of general assemblages is larger than the
set of process assemblages, because just like gen-
eral behaviours, not all general assemblages can
be realised by process matrices.
Theorem 4.
All process assemblages are valid
assemblages, however, not all valid assemblages
are process assemblages.
In particular, in the scenario where Alice has
dichotomic inputs and outputs, the general as-
semblage
{w
a|x
}
given by
w
a|x
=
|xihx||aiha|
is
not a process assemblage.
The proof presented in appendix A is based on
the fact that this assemblage can lead to a de-
terministic two-way signalling behaviour, which
we know not to be attainable by process matrices
from theorem 2.
Although the process assemblage can be re-
garded as a generalisation of the steering as-
semblage that arises in EPR-steering scenarios,
here we point out an important difference
between semi-device-independent certification of
indefinite causal order and entanglement. A fun-
damental result on EPR-steering theory is that
all steering assemblages admit a quantum realisa-
tion by performing POVMs on a quantum state
[50, 51, 52]. On the other hand, theorem 4 shows
that some process assemblages do not admit a
quantum realisation by performing a set of instru-
ments on a process matrix.
The next step is to assign causal properties to
assemblages. A natural approach is to define that
an assemblage {w
Q, AB
a|x
} is causally ordered from
Alice to Bob if it is a process assemblage that can
be obtained from a process matrix that is causally
ordered from Alice to Bob, namely,
w
Q, AB
a|x
= Tr
A
[(A
a|x
1
B
) W
AB
] a, x, (28)
Accepted in Quantum 2019-07-07, click title to verify. Published under CC-BY 4.0. 8
for some set of instruments {A
a|x
} and some caus-
ally ordered process matrix W
AB
, and equival-
ently from Bob to Alice.
Since the above definition depends on an un-
known set of instruments {A
a|x
}, it is not easy to
check whether a given general assemblage {w
a|x
}
is causally ordered. We therefore derive a simpler
characterisation of causally ordered assemblages
that is equivalent to the one above.
Analogously to how we defined a general as-
semblage, we characterise the most general set
of operators {w
AB
a|x
} that give rise to a caus-
ally ordered behaviour {p
AB
(
ab|xy
)
} according
to the equation
p
AB
(ab|xy) = Tr(B
b|y
w
AB
a|x
), (29)
for any set of instruments {B
b|y
} for Bob. We
then prove its equivalence to the definition below
in appendix C.
Definition 6
(Causally ordered assemblages)
.
An assemblage
{w
AB
a|x
}
is causally ordered from
Alice to Bob if it satisfies
w
AB
a|x
=
B
O
w
AB
a|x
a, x, (30)
while an assemblage
{w
BA
a|x
}
is causally ordered
from Bob to Alice if it satisfies
X
a
w
BA
a|x
=
X
a
w
BA
a|x
0
x, x
0
. (31)
In appendix B, we show that all causally
ordered assemblages {w
AB
a|x
} and {w
BA
a|x
} can
be realized by some set of instruments {A
a|x
} and
some causally ordered process matrix W
AB
and
W
BA
, respectively. That is, we show that all
{w
AB
a|x
} satisfy eq. (28), and analogously for the
causal order B A.
We now contrast the statement made in the
previous paragraph with general assemblages. As
stated before, the technique of defining the gen-
eral assemblage as the most general set of linear
operators that takes instruments to general be-
haviours results in an object that cannot always
be described by process matrices. On the other
hand, in the case of causally ordered assemblages,
this technique yielded an object that can always
be described by (causal) process matrices. The
main point to be taken here is that to character-
ize the most general set of linear operators that
takes instruments to some kind of behaviour is a
mathematical artifice to find an outer approxim-
ation to the set of assemblages that are described
by process matrices. The goal is to find an ap-
proximation of this set with a potentially sim-
pler characterization. This approximation may
be tight, as in the case of causal assemblages, or
may not be tight, as in the case of general as-
semblages. We explore this further in appendix E
for assemblages in tripartite scenarios.
We now define a causal assemblage by taking
the elements of the convex hull of causally ordered
assemblages.
Definition 7
(Causal assemblage)
.
An as-
semblage
{w
causal
a|x
}
is causal if it can be expressed
as a convex combination of causally ordered as-
semblages, i.e.,
w
causal
a|x
:
= qw
AB
a|x
+ (1 q)w
BA
a|x
, (32)
for all
a, x
, where 0
q
1 is a real number. An
assemblage that does not satisfy eq. (32) is called
a noncausal assemblage.
We can now express our result in terms of the
following lemma, proved in appendix B.
Lemma 2.
A general assemblage is causal if and
only if it is a process assemblage that can be ob-
tained from a causally separable process matrix.
This result allows us to identify which causally
nonseparable process matrices can be certified in
a semi-device-independent way:
Theorem 5.
A process matrix is certified
to be causally nonseparable in a semi-device-
independent way if and only if it can generate
a noncausal assemblage for some choice of instru-
ments for Alice.
Proof.
If a process matrix is causally separable
then its assemblages will be causal. If the as-
semblage is causal, even though it could in prin-
ciple have been generated by a causally nonsep-
arable process matrix, according to lemma 2 it
can always be reproduced by a causally separable
process matrix and hence this property cannot be
certified.
Note that all requirements for an assemblage
to be causal are linear and positive semidefinite
constraints, hence one can check whether an as-
semblage is causal via SDP.
Accepted in Quantum 2019-07-07, click title to verify. Published under CC-BY 4.0. 9
However, in our semi-device-independent certi-
fication scenario, the only information available
is the process behaviour and Bob’s instruments,
not the assemblage itself. If it were the case that
Bob’s instruments are tomographically complete,
he could obtain full information about the as-
semblage, and check whether it is causal via SDP.
Nevertheless, we show that it is possible to check
whether a given behaviour can certify indefin-
ite causal order in a semi-device-independent
scenario using SDP even without the knowledge
of the assemblage. We do this by rephrasing
our certification task in terms of an unknown
assemblage.
Definition 3’ (Semi-device-independent certific-
ation, with assemblages). Given a behaviour
{p
Q
(
ab|xy
)
}, that arises from unknown instru-
ments on Alice’s side, known instruments {B
b|y
}
on Bob’s side, and an unknown bipartite pro-
cess matrix, one certifies that this process mat-
rix is causally nonseparable in a semi-device-
independent way if
p
Q
(ab|x , B
b|y
) 6= Tr(B
b|y
w
causal
a|x
) (33)
for all a, b, x, y, and for all causal assemblages
{w
causal
a|x
}.
Now we are able to formulate the semi-device-
independent certification problem in terms of
SDP:
given {p
Q
(ab|xy)}, {B
b|y
}
find {w
a|x
}
s.t. p
Q
(ab|xy) = Tr(B
b|y
w
a|x
) a, b, x, y
{w
a|x
} CAUSAL,
(34)
where CAUSAL denotes the set of causal as-
semblages, that is, {w
a|x
} is constrained to
eq. (32).
As in the previous cases, if the problem is in-
feasible, then the process matrix that was used
to generate the process behaviour {p
Q
(
ab|xy
)
} is
certainly causally nonseparable. If the problem
is feasible, then one can use the results presented
in appendix B to explicitly find a causally separ-
able process matrix W
sep
and sets of instruments
{A
a|x
} such that w
a|x
= Tr
A
[(A
a|x
1
B
) W
sep
].
All three SDP formulations we presented in
eqs. (18), (19) and (34) are feasibility problems
which can be turned into optimisation problems
that allow for a robust certification of indefinite
causal order. We discuss this further in section 3.
We now show that not all process matrices can
be certified in a semi-device-independent way, as
some process matrices cannot lead to noncausal
assemblages. The proof is in appendix D.
Theorem 6
(Device-dependent certifiable,
semi-device-independent noncertifiable process
matrix)
.
There exist causally nonseparable pro-
cess matrices that, for any sets of instruments
on Alice’s side, always give rise to causal as-
semblages. That is, causally nonseparable process
matrices that cannot be certified in a semi-device-
independent way.
In particular, let
W L
(
H
A
I
A
O
B
I
B
O
) be a pro-
cess matrix and
W
T
A
be the partial transposition
of
W
with respect to some basis in
L
(
H
A
I
A
O
)
for Alice. If
W
T
A
is causally separable, the as-
semblages generated by
w
a|x
=
Tr
A
[(
A
a|x
1
B
)
W
]
are causal for every set of instruments {A
a|x
}.
We remark that the above theorem strictly ex-
tends proposition 1 which was first proved in
ref. [48]. That is, with the same hypothesis –
that W
T
A
is causally separable we can make a
stronger claim that W cannot be certified as
causally nonseparable even if Bob is treated in a
device-dependent way (is trusted).
In ref. [48], the authors show that, when ex-
tended with an entangled state, the resulting pro-
cess matrix can violate a causal inequality and
can therefore be certified in a device-independent
way. This implies that this extended process
matrix can also be certified in a semi-device-
independent way. Ref. [48] leaves as an open
question the existence of a causally nonseparable
bipartite process matrix that cannot be certified
in a device-independent way even when extended
by entanglement. We remark that this open ques-
tion is also relevant in the context of semi-device-
independent certification.
Another natural question also emerges: is there
a bipartite process matrix that can be certified
to be causally nonseparable in a semi-device-
independent scenario but that cannot be certi-
fied to be causally nonseparable in any device-
independent scenario? Although we believe such
process matrix exists, no example is currently
known.
Accepted in Quantum 2019-07-07, click title to verify. Published under CC-BY 4.0. 10
3 The Quantum Switch
The concepts of certification presented in the
previous section have a natural generalisation to
different multipartite scenarios. We are now go-
ing to illustrate one particular tripartite case by
discussing and presenting some results involving
the quantum switch [22, 35]. In appendix E, we
present a detailed extension of the concepts and
results from the bipartite case, introduced in sec-
tion 2, to the tripartite case in which the quantum
switch is defined, and pave the way to future more
general tripartite and multipartite extensions.
On its first appearance, the quantum switch
was defined as a higher-order transformation that
maps quantum channels into quantum channels
and it can be defined as the following. Let U
A
and
U
B
be two unitary operators that act on the same
space of a target state |ψi
t
. Let |ci
c
:=
α|
0
i
+
β|
1
i,
|α|
2
+
|β|
2
= 1
, be a ‘control’ state that is able
to coherently control the order in which the op-
erations U
A
and U
B
are applied. The quantum
switch acts as following:
switch(U
A
, U
B
) = |0ih0|
c
U
A
U
B
+ |1ih1|
c
U
B
U
A
.
(35)
When applied to the state |ci
c
|ψi
t
we have
switch(U
A
, U
B
)|ci |ψi = α |0i U
A
U
B
|ψi
+ β |1i U
B
U
A
|ψi.
(36)
Physically, the equation above can be under-
stood as the control qubit determining which unit-
ary is going to be applied first on the target
state |ψi. If the control qubit is in the state |
0
i
(α
= 1
, β
= 0
), the unitary U
B
is performed be-
fore the unitary U
A
. If the control qubit is in
the state |
1
i (α
= 0
, β
= 1
), the unitary U
B
is
performed before the unitary U
A
. In general, if
the control qubit is in the state |ci
=
α|
0
i
+
β|
1
i,
α 6
= 0
, β 6
= 0
, the output state will be in a coher-
ent superposition of two different causal orders.
In the process matrix formalism, ref. [21] has
analysed the quantum switch as a four-partite
process matrix of which the first party has only
an output space, which defines the input target
and control states, one party inputs U
A
, another
party inputs U
B
, and a final party obtains the
output control and target states. Here we follow
instead the steps of ref. [27] to associate tripart-
ite process matrices to the quantum switch. This
can be done by absorbing the input target and
control states into the process matrix and setting
the third party with output space of dimension
equal to one. Hence, the quantum switch is de-
scribed by a family of tripartite process matrices
that is shared among three parties, Alice, Bob,
and Charlie, for which Charlie is always in the
future of Alice and Bob, and the causal order
between Alice and Bob may or may not be well
defined. A consequence of the fact that Charlie is
last and his output space H
C
O
has d
= 1
is that
the most general instrument Charlie can perform
is a POVM.
Formally, we define a family of tripartite pro-
cess matrices associated to the quantum switch
according to:
Definition 8
(Quantum switch processes)
.
Let
|w(ψ, α, β)i H
A
I
A
O
B
I
B
O
C
t
I
C
c
I
be
|w (ψ, α, β)i = α |ψi
A
I
|Φ
+
i
A
O
B
I
|Φ
+
i
B
O
C
t
I
|0i
C
c
I
+ β |ψi
B
I
|Φ
+
i
B
O
A
I
|Φ
+
i
A
O
C
t
I
|1i
C
c
I
,
(37)
where
|ψi
is a
d
-dimensional pure state,
α, β
are
complex numbers such that
|α|
2
+
|β|
2
= 1, and
|
Φ
+
i
=
P
d
i=1
|iii
is a maximally entangled unnor-
malised bipartite qudit state, the Choi representa-
tion of the identity channel.
Then, the pure quantum switch processes are a
family of tripartite process matrices given by
W
switch
(ψ, α, β) = |w (ψ, α, β)ihw (ψ, α, β)|.
(38)
When the control state is in a nontrivial su-
perposition of |
0
i and |
1
i, the quantum switch
processes have been shown to have some interest-
ing properties [27, 47]. They are causally non-
separable process matrices, meaning they cannot
be expressed as a convex combination of tripart-
ite process matrices with definite causal ordered
between Alice and Bob, with Charlie in their com-
mon future. Namely, when α 6= 0 and β 6= 0,
W
switch
(ψ, α, β) 6= qW
ABC
+ (1 q)W
BAC
,
(39)
for all |ψi, and all real numbers
0
q
1
. The
exact definitions of causally ordered and general
tripartite process matrices can be found in ap-
pendix E.
However, when Charlie is traced out, the res-
ulting bipartite process matrices shared by Alice
and Bob are causally separable, namely,
Tr
C
c
I
C
t
I
[W
switch
(ψ, α, β)] = qW
AB
+ (1 q)W
BA
,
(40)
for all |ψi, α, and β, where q = |α
2
|.
Accepted in Quantum 2019-07-07, click title to verify. Published under CC-BY 4.0. 11
These causally nonseparable tripartite process
matrices can be certified in a device-dependent
way, since theorem 1 also holds for tripartite
process matrices. Yet, it has been shown in
refs. [27, 47] that the quantum switch processes
cannot be certified in a device-independent way,
as they always lead to causal behaviours for any
choice of instruments of Alice, Bob, and Charlie.
It remains to find out whether these processes can
be certified in semi-device-independent scenarios.
For this purpose, we extend all concepts and
methods from bipartite semi-device-independent
certification. Much like in the bipartite case,
we make different assumptions about the know-
ledge of the operations performed by each party.
We call untrusted (U) a party that is treated
in a device-independent way and trusted (T) a
party that is treated in a device-dependent way,
and we use the convention Alice Bob Charlie
for denoting the parties. For example, a scen-
ario TTU means Alice = T (device-dependent),
Bob = T (device-dependent), and Charlie = U
(device-independent). The four inequivalent semi-
device-independent tripartite scenarios are TTU,
TUU, UTT, and UUT.
The core idea of the certification task remains
the same. For a given process behaviour and
given sets of instruments for the trusted parties,
one needs to check whether it is possible that
this behaviour comes from performing this instru-
ments on a causally separable tripartite process
matrix. We also derive the concepts of general,
process, causally ordered, and causal assemblages
for each scenario. In appendix E, we provide
all details and calculations, including for the tri-
partite device-dependent TTT and -independent
UUU scenarios.
Our next theorem strengthens the previous res-
ult [27] that showed that the quantum switch
processes cannot be certified in a full device-
independent scenario, i.e., in the UUU scenario.
We show that when the instruments of Alice
and Bob are unknown, even if the measurements
performed by Charlie are known, the quantum
switch processes can never be proven to be caus-
ally nonseparable, for any pairs of sets of instru-
ments for Alice and Bob. In other words, we
prove that the quantum switch processes cannot
be certified to be causally nonseparable in the
UUT scenario. The previous result of the full
device-independent scenario can now be seen as
a particular case of the theorem we now present,
whose proof is in appendix F.
Theorem 7.
The quantum switch processes can-
not be certified to be causally nonseparable on a
semi-device-independent scenario where Alice and
Bob are untrusted and Charlie is trusted (UUT).
Moreover, any tripartite process matrix
W
L
(
H
A
I
A
O
B
I
B
O
C
I
), with Charlie in the future of
Alice and Bob, that satisfies
Tr[(A
A
I
A
O
a|x
B
B
I
B
O
b|y
1
C
I
)W
A
I
A
O
B
I
B
O
C
I
] =
qp
AB
(ab|xy) + (1 q)p
BA
(ab|xy),
(41)
for all
a, b, x, y
, where 0
q
1 is a real number,
cannot be certified to be causally nonseparable in
a UUT scenario.
We now show that in the three remaining semi-
device-independent scenarios, TTU, TUU, and
UTT, the quantum switch processes can be cer-
tified to be causally nonseparable, proving that
they can demonstrate stronger noncausal proper-
ties than it was previously known.
For our remaining calculations we use the re-
duced quantum switch process
W
red
:
= Tr
C
t
I
W
switch
|0i,
1
2
,
1
2

. (42)
By choosing a reduced, mixed switch process in
these scenarios, in which the space of the tar-
get state is traced out, we guarantee that the
pure switch process version can also be certified
without performing any measurements on the out-
put target space.
We show that the reduced quantum switch pro-
cess W
red
can be certified in the TTU, TUU, and
UTT scenarios by providing sets of instruments
for the device-independent (untrusted) parties
that, when applied to W
red
, generate TTU-,
TUU-, and UTT-assemblages that are noncausal.
We prove these assemblages to be noncausal by
means of SDP.
To calculate the assemblages, we choose the fol-
lowing instruments for each untrusted party:
A
A
I
A
O
0|0
= B
B
I
B
O
0|0
= |0ih0| |0ih0|, M
C
c
I
0|0
= |+ih+|,
A
A
I
A
O
1|0
= B
B
I
B
O
1|0
= |1ih1| |1ih1|, M
C
c
I
1|0
= |−ih−|,
A
A
I
A
O
0|1
= B
B
I
B
O
0|1
= |+ih+| |+ih+|,
A
A
I
A
O
1|1
= B
B
I
B
O
1|1
= |−ih−| |−ih−|,
(43)
where |±i =
1
2
(|0i ± |1i).
Accepted in Quantum 2019-07-07, click title to verify. Published under CC-BY 4.0. 12
Let us illustrate with the TUU case. To con-
struct the TUU-assemblage, we use the instru-
ments from eq. (43) for the untrusted parties, Bob
and Charlie, according to
w
switch
bc|y z
= Tr
BC
[(1
A
B
b|y
M
c|z
) W
red
] b, c, y, z.
(44)
Then, we show via SDP that
w
switch
bc|y z
6= qw
ABC
bc|y z
+ (1 q)w
BAC
bc|y z
, b, c, y, z,
(45)
proving that the switch process can be certified