Interference as an information-theoretic game
Sebastian Horvat
1
and Borivoje Dakić
1,2
1
University of Vienna, Faculty of Physics, Vienna Center for Quantum Science and Technology, Boltzmanngasse 5, 1090 Vienna, Austria
2
Institute for Quantum Optics and Quantum Information (IQOQI), Austrian Academy of Sciences, Vienna, Austria
17 February 2021
The double slit experiment provides a clear de-
marcation between classical and quantum theory,
while multi-slit experiments demarcate quantum and
higher-order interference theories. In this work we
show that these experiments pertain to a broader
class of processes, which can be formulated as
information-processing tasks, providing a clear cut
between classical, quantum and higher-order theo-
ries. The tasks involve two parties and communica-
tion between them with the goal of winning certain
parity games. We show that the order of interfer-
ence is in one-to-one correspondence with the parity
order of these games. Furthermore, we prove the
order of interference to be additive under composi-
tion of systems both in classical and quantum the-
ory. The latter result can be used as a (semi)device-
independent witness of the number of particles in the
quantum setting. Finally, we extend our game formu-
lation within the generalized probabilistic framework
and prove that tomographic locality implies the addi-
tivity of the order of interference under composition.
These results shed light on the operational meaning
of the order of interference and can be important for
the identification of the information-theoretic prin-
ciples behind second-order interference in quantum
theory.
I Introduction
As Richard Feynman famously put it, “the double slit
experiment is absolutely impossible to explain in any clas-
sical way and has in it the heart of quantum mechanics.
In reality, it contains the only mystery” [1]. Indeed, the
most common way of introducing quantum theory and its
basic tenets is via the double-slit experiment, in which a
single particle is shown to produce an interference pattern
when sent through two slits, in contrast to classical theory
in which this effect is missing. Much later, Sorkin [2]
analyzed multi-slit experiments (i.e. generalizations of
the double slit experiment to three or more slits) and
noticed that quantum mechanics exhibits second-order
interference only, meaning that any measurement pattern
produced by a quantum system is reducible to the com-
bination of double-slit interferences. The latter served
Sebastian Horvat: sebastian.horvat@univie.ac.at
Borivoje Dakić: borivoje.dakic@univie.ac.at
as a motivation for introducing higher-order interference
theories which are defined with respect to the order of
interference produced in generalized multi-slit experi-
ments [3]. Such theories are usually formulated within the
framework of generalized probabilistic theories (GPT-s)
[4, 5], with quantum theory being only a particular exam-
ple. This further motivated the search for a set of intuitive
physical principles which could explain why experiments
should exhibit at most second-order interference [69].
In this work we study higher-order interference from the
information-theoretic perspective. Firstly, we reconsider
the definitions of multi-slit experiments and Sorkin’s
classification and notice that: (a) the framework is
defined only for single particles (or single systems), (b)
the interference order is defined with respect to simple
operations of blocking/opening the slits, and (c) the (final)
measurement refers exclusively to intensity measurements
(average number of particles at a particular location on
the screen). We proceed by generalizing this setting to an
arbitrary number of particles (systems), arbitrary set of
(local) operations and arbitrary final measurements. The
framework for higher-order interference is formulated as
an information-theoretic game where we analyze generic
scenarios involving classical and quantum systems. Our
generalization involves many particles (systems) and their
ability to win certain parity games. The order of these
games and their winning probabilities are directly related
to the order of interference (in Sorkin’s classification) and
to the number of systems involved. This generalization
offers a shift in the perspective: higher order interference
theories are not defined by which phenomena are allowed
(e.g. by the structure of interference patterns), but
by which tasks can or cannot be accomplished within
the theory (i.e. their information-processing capacity).
Furthermore, our study provides a direct relation between
the order of interference and number of systems used
in the protocol, and can thus provide a (semi) device-
independent way of witnessing the number of particles
(systems) present in the process.
In the final section we provide the information-theoretic
formulation within the GPT formalism and we study how
the order of interference behaves under the composition of
systems. We construct a lower bound on the interference
order which is additive under composition. In classical
and quantum theory, this lower bound coincides with
the upper bound, which in turn shows an interesting
connection between the order of interference and the
Accepted in Quantum 2021-02-15, click title to verify. Published under CC-BY 4.0. 1
arXiv:2003.12114v4 [quant-ph] 17 Feb 2021
composition law. Finally, motivated by the latter, we
prove that in generic local-tomographic theories [28] the
order of interference is indeed additive (under certain
additional assumptions that we deem reasonable).
Together with an information-theoretic perspective, our
findings can be seen in light of paving an alternative way
towards understanding the physical principles behind the
order of interference of quantum theory: we suspect that
an important clue might be provided by the composition
of systems and by the tensor-product structure. The latter
would thus contribute to the operational and physical
understanding of quantum theory [1013] and provide
indications for potential developments of post-quantum
theories. Moreover, our work deepens the connection
between interference and information processing which
has already been alluded to in various contexts involving
two-way communication [1416], information speed [17],
quantum acausal processes [18], superposition of orders
[19] and directions [20], quantum combs [21], quantum
switch [22] and quantum causal models [23].
II Information-theoretic formulation:
Parity games
In the standard double-slit experiment a particle is sent on
a plate pierced by two parallel slits. After passing through
the plate, the particle can be detected on a screen. Each slit
can be either open (which we denote with 0), or blocked
(which we denote with 1). The figure of merit is the inter-
ference term
I
2
= P
00
P
10
P
01
+ P
11
, (1)
where P
x
1
x
2
denotes the probability of detecting the par-
ticle at a point on the screen given that the slits are in
states x
1
and x
2
. Notice that we explicitly included the
term which corresponds to the situation in which both slits
are closed, despite it being necessarily zero (i.e. P
11
=
0). Classical mechanics predicts I
2
= 0, while quan-
tum theory allows the particle to be in spatial superposi-
tion, thereby enabling the possibility of generating a non-
vanishing I
2
.
In order to reformulate this experiment as an information-
theoretic task, let us consider the scenario involving two
parties, Alice and Bob, located at opposite sides of the
plate, as shown in Figure 1. Let us suppose that the slits are
in a certain state (i.e. each slit is either open or blocked)
which is completely unknown both to Alice and to Bob;
we can thus imagine that an external party (e.g. a referee)
has control of the slits and decides whether to block them
or not. Moreover, Alice possesses a single particle that she
can send towards Bob. On the other side, Bob receives (or
not) the particle, performs an arbitrary measurement and
outputs a bit b {0, 1}. We introduce the redefined sec-
Figure 1: Alice and Bob are located at opposite sides of
a pierced plate with two slits, each of which can be either
open or blocked depending on their input bits {x
1
, x
2
}. Alice
sends her particle through the slits towards Bob, who, upon
receiving the particle, generates an output bit b.
ond order interference term as follows
˜
I
2
=
1
4
[P (0|11) P(0|10) P (0|01) + P (0|00)] =
=
1
4
1
X
x
1
,x
2
=0
P (b = x
1
x
2
|x
1
x
2
)
1
2
,
(2)
where P (b|x
1
x
2
) is the probability that Bob outputs b
given that the two slits are in states x
1
and x
2
. Notice
that the term corresponding to both slits being closed can
now be non-zero, since Bob’s measurement is arbitrary,
i.e. does not necessarily refer to measuring the probability
of the particle inflicting on a point of the screen (inten-
sity measurement). The probability P (b|x
1
x
2
) is thus a
generalization of P
x
1
x
2
from (1) and reduces to the latter
only in the case in which Bob performs the intensity mea-
surement. The redefined interference term
˜
I
2
measures
the probability of successfully accomplishing the follow-
ing task (parity game):
(a) in each run, the slits are set in some state {x
1
, x
2
} un-
known both to Alice and to Bob;
(b) Alice prepares her particle and sends it through the slits
towards Bob;
(c) Bob receives (or not) the particle, and, in order to com-
plete the task, must output the parity s
~x
x
1
x
2
.
Bob does not have any prior information about the inputs,
which is why a uniform average is taken. We stress that
the state of the particle sent by Alice does not depend on
the inputs x
1
and x
2
, since the latter are unknown to her.
Notice that expression (2) is formulated in a device-
independent way [24], relating only inputs and outputs,
without any mention of their underlying physical realiza-
tion. It is therefore natural to generalize the scenario by
replacing slit operations with generic black boxes, which
implement arbitrary local operations depending on their
inputs. The boxes can thus perform any operation (e.g. in
quantum theory, general completely-positive maps): the
only restriction stems from the operations being local.
Moreover, instead of constraining Alice to sending only
single particles (as it is also the case for standard interfer-
ence experiments), we can generalize her resources to an
Accepted in Quantum 2021-02-15, click title to verify. Published under CC-BY 4.0. 2
arbitrary number of systems and analyze how the winning
probability depends on the number of systems used in the
process (as we will see in the next section, the game can
be won even in classical theory, by using two particles).
Additionally, the particles/systems sent by Alice can have
any internal structure (e.g. spin) that can be potentially ac-
cessed by the black boxes.
Analogously to the generalization of the standard double-
slit experiment to multi-slit experiments, we can further
generalize the scenario to an arbitrary number of boxes m.
In this case, Alice sends her resources, which consist of k
systems, towards Bob, whose task is to output the overall
parity of the boxes’ inputs, as depicted in Figure 2. The
figure of merit is thus
˜
I
m
(k) =
1
2
m
1
X
x
1
,...,x
m
=0
P (b = s
~x
|x
1
...x
m
)
1
2
, (3)
where {x
1
, ..., x
m
} are input bits encoded in the m boxes
and s
~x
m
i=1
x
i
is the overall parity. In the case in
which Alice is constrained to sending only single parti-
cles, the boxes are implemented as slits and Bob’s final
operation consists of intensity measurements, the general-
ized higher-order interference term
˜
I
m
(k) reduces to the
standard higher-order term defined in [2] (up to normal-
ization):
I
m
=
1
X
x
1
,...,x
m
=0
(1)
P
j
x
j
P
~x
, (4)
where x
j
= 0(1) corresponds to j-th slit being
open(closed) and P
~x
is the probability of detecting the par-
ticle on the screen given that the slits are in state ~x.
Juxtaposed to the standard definition of m-th order inter-
ference theories involving the structure of interference pat-
terns produced by single particles in m-slit experiments,
our information-theoretic extension provides a definition
in terms of the probability of winning the parity game in-
volving m boxes by using a finite amount of resources. In
addition, the latter formulation enables an analysis of the
relation of the order of interference and the number of sys-
tems involved in the process (e.g., as we will see in the next
section, the m-th order parity game can be won using m
classical particles). We therefore introduce the characteri-
zation of higher-order theories in terms of functions n(k),
where n refers to the maximum order of interference that
can be exhibited using k systems, i.e.
˜
I
m=n(k)
(k) 6= 0 and
˜
I
m>n(k)
(k) = 0.
To recapitulate, the modified multi-slit experiment con-
sists of the following generalizations: (a) instead of
one particle, Alice can possess arbitrarily many parti-
cles/systems of arbitrary internal structure, (b) the slits are
replaced by black boxes which implement generic local
operations depending on their pertaining input bits, (c) the
screen is replaced by Bob who is supposed to generate an
output corresponding to the overall parity of the inputs en-
coded by the boxes.
Finally, we can generalize the input bits {x
1
..., x
m
} to
Figure 2: Alice possesses a finite amount of resources that
she sends towards Bob through m black boxes. The lat-
ter implement arbitrary local operations depending on their
pertaining inputs {x
1
, ..., x
m
}. Upon receiving the resources,
Bob performs an arbitrary operation and generates an output
bit b.
dits, i.e. elements of a set with cardinality d. Throughout
this manuscript we will assume that d is a prime number,
the reason of which will be clearer later. In this case we
introduce a class of games in which Bob is supposed to
decode one of the weighted sums modulo d of the inputs,
i.e. s
(d)
~x,~ν
(
P
m
i=1
ν
i
x
i
)mod d, where ~ν is a dit-string with
components ν
i
{1..., d 1}. Given that Alice is using
k systems, the generalized interference terms are then
˜
I
(d)
m,~ν,f
(k) =
1
d
m
d1
X
x
1
,...,x
m
=0
P
b = f(s
(d)
~ν,~x
)|x
1
...x
m
1
d
,
(5)
which are defined for all reversible functions f that map
dits into dits. Operationally, these functions take into ac-
count the potential relabelling of Bob’s outputs. Notice
that for d = 2 there was no need for specifying this, since
relabelling Bob’s output in Eq. (3) introduces only a mi-
nus sign. The games defined in (5) offer a definition of
higher order interference theories for arbitrary prime d.
Definition. We define n(k)-theories as theories that
satisfy the following two properties:
(i) all processes produce
˜
I
(d)
m>n(k),~ν,f
(k) = 0 for all re-
versible functions f, all dit-strings ~ν with components
ν
i
{1..., d 1}, and for all prime d 2;
(ii) for some prime d 2, there exists at least one
process that produces
˜
I
(d)
m=n(k),~ν,f
(k) 6= 0, for at least
one dit-string ~ν with components ν
i
{1..., d 1}.
Notice that the (non)existence of the required process
for a specific outputs’ labelling fixed by f implies the
(non)existence of the analogous process for any other la-
belling f
0
(since Bob can always relabel his outcomes in-
dependently of the process). Therefore, throughout this
manuscript, we will only construct proofs of existence of
processes which exhibit
˜
I
(d)
m=n(k),~ν,f
(k) 6= 0 for f fixed to
be the identity map (i.e. no final relabelling) and we will
thereby omit the index f . Moreover, whenever we omit
the index ~ν, we refer to the unit dit-string, i.e. ν
i
= 1, i.
Therefore, the term
˜
I
(d)
m
(k) will correspond to the specific
game in which Bob’s goal is to output s
~x
= (
P
i
x
i
)mod
Accepted in Quantum 2021-02-15, click title to verify. Published under CC-BY 4.0. 3
d. We acknowledge that the additional games specified
by the labels ~ν and f may at the moment seem redun-
dant; however, we will need to take them into account in
the proofs regarding higher-order interference and we will
thus keep them in the definition of n(k)-theories. As we
will show later, all conclusions regarding the order of in-
terference of classical, quantum and higher-order theories
will hold for arbitrary prime d 2.
Winning the parity games can be seen as a truly “global”
task, in the sense that Bob needs to produce an output that
depends on all the local inputs in each run. For suppose
that Bob receives all but one input, say the j-th one: in
this case, the overall modulo s
~x
= (
P
i
x
i
)mod d is com-
pletely unknown to Bob. The same conclusion holds if
Bob does not receive more inputs or even if he does not
receive any information at all. Therefore, the interference
term
˜
I
(d)
m,~ν,f
(k) is zero irrespectively of whether Bob lacks
knowledge about one or about all inputs. Here we can
see the importance of assuming that d is a prime number:
if it was not, then, in some cases, Bob would be able to
guess the overall modulo with a probability greater than
1
d
even with having no information about one or more in-
puts. A simple example is the following one: assume that
d = 4, m = 2, and that Bob is supposed to output the
value (x
1
+ 2x
2
)mod d (i.e. ν
1
= 1, ν
2
= 2); by know-
ing the value of x
1
, Bob’s winning probability will be
1
2
,
which is larger than
1
d
, essentially due to d being divisible
by ν
2
. This would cause several complications in our def-
initions and proofs, which is why we will simply restrict d
to be prime (while still letting it to be arbitrarily large).
In the subsequent sections, we are going to focus on classi-
cal and quantum theory and investigate their power to win
the parity games. We will show that the order of interfer-
ence n(k) satisfies the relation
n(k) = kn(1), (6)
where n(1) is the order of single-system interference (for
classical theory, n(1) = 1, while for quantum theory,
n(1) = 2) and n(k) is the interference order achievable
using k systems. Moreover, we will show that this relation
holds in generic GPT-s that satisfy the local tomography
principle and certain additional assumptions.
Before proceeding further, we will first show an impor-
tant mathematical property that relates the order of inter-
ference to the algebraic order of the probability distribu-
tions P (b|~x).
III Algebraic order of the probability
distributions
In this section we are going to show that any distribution
which does not exhibit higher than n-th order interference
can be written as a linear combination of functions of at
most n different inputs, or, in other words, that the alge-
braic order of P(b|~x) is at most n. Here we will consider
the d = 2 case, while the general case is addressed in Ap-
pendix A.
Let us consider the parity game involving m boxes and as-
sume that Alice uses one system of order n < m. By def-
inition, this means that the interference terms (3) vanish
for all parity games involving more than n boxes, which
can be written in a concise form as follows:
˜
I
(2)
m,~σ
=
1
2
m
X
~x
(1)
P
j
σ
j
x
j
P (0|~x) = 0,
σ
j
{0, 1}, s.t.
X
j
σ
j
> n.
(7)
For compactness, we introduced the m-component bit
string ~σ, that specifies which interference term the latter
equation refers to: if σ
j
= 1 for j = i
1
, ..., i
l
, the equa-
tion states that the order of interference involving boxes
i
1
, ..., i
l
is equal to zero (l can be any integer between n+1
and m).
Let us regard P (0|~x) as one component of a vector
~
P
in a 2
m
-dimensional vector space formed by the tensor
product of m two-dimensional spaces, i.e. P (0|~x) =
~e
x
1
... ~e
x
m
·
~
P , where ~e
x
j
=0,1
span the j-th two-
dimensional space. Equations (7) then imply that for all
P
j
σ
j
> n:
˜
I
(2)
m,~σ
(k = 1) =
1
2
m
X
~x
(1)
P
j
σ
j
x
j
~e
x
1
... ~e
x
m
·
~
P =
=
1
2
m/2
~
f
σ
1
...
~
f
σ
m
·
~
P =
1
2
m/2
λ
~σ
= 0,
(8)
where we introduced the rotated vectors
~
f
σ
j
1
2
(~e
0
+ (1)
σ
j
~e
1
) . (9)
The terms λ
~σ
are components of vector
~
P in the new ba-
sis spanned by the rotated vectors
~
f
σ
j
. Equation (8) then
states that the components λ
~σ
are zero if
P
j
σ
j
> n. The
probabilities P (0|~x) can thus be expressed as
P (0|~x) =
"
m
O
i=1
~e
x
i
#
·
X
~σ
λ
~σ
m
O
j=1
~
f
σ
j
=
=
1
2
m/2
X
σ
1
,...,σ
m
P
j
σ
j
n
(1)
P
j
σ
j
x
j
λ
~σ
,
(10)
where we used ~e
x
i
·
~
f
σ
i
= 2
1/2
(1)
σ
i
x
i
. Therefore,
P (0|~x) is a linear combination of functions of at most n
different inputs:
P (0|~x) =
n
X
l=1
X
i
1
,...,i
l
c
(l)
i
1
,...,i
l
g
(l)
(x
i
1
, ..., x
i
l
), (11)
where we introduced the functions
g
(l)
(x
i
1
, ..., x
i
l
) = (1)
P
l
a=1
x
i
a
, (12)
and the coefficients
c
(l)
i
1
,...,i
l
=
1
2
m/2
~
λ
~σ
(l)
(i
1
,...,i
l
)
,
~σ
(l)
(i
1
,...,i
l
)
s
=
l
X
r=1
δ
s,i
r
.
(13)
Accepted in Quantum 2021-02-15, click title to verify. Published under CC-BY 4.0. 4
Next, in order to tackle the problem for arbi-
trary d, for each set of generalized interference
terms
n
˜
I
(d)
m,~ν,f
, ~ν, f
o
we introduce its dual terms
n
˜
J
(d)
m,~ν,α,b
, ~ν; b {0, ..., d 1}
o
as
˜
J
(d)
m,~ν,b
=
1
d
m
X
~x
(ω
d
)
P
a
ν
a
x
a
P (b|~x), (14)
where ω
d
= e
i2π/d
is the d-th root of unity. For the
d = 2 case, the dual terms coincide with the ones de-
fined in terms of the game formulation (3); however, this
is not the case for d > 2. Nevertheless, in Appendix A we
show that the generalized interference term
˜
I
(d)
m,~ν,f
from
(5) vanishes for all relabellings f and all dit-strings ~ν if
and only if
˜
J
(d)
m,ν,b
= 0, for all b = 0, ..., d 1 and for
all ~ν. This allows us to characterize the order of interfer-
ence by analysing the behaviour of its dual, which can of-
ten be more tractable. Indeed, by this method we show in
Appendix B that the conclusion derived in (12) holds for
arbitrary d, i.e. that any distribution that exhibits at most
m-th order interference can be written as a linear sum of
functions which depend on at most m dits.
IV Classical resources
Now we are going to analyze the generalized interference
terms achievable within classical theory. Here we will
keep the analysis at an informal and intuitive level; a more
formal treatment will be given at the end of Section V,
where classical theory will be regarded as a special case of
quantum theory.
Single systems. For a start, let us focus on the simplest
scenario, i.e. the generalization of the double slit experi-
ment, in which Alice sends a single particle through two
boxes towards Bob (for now we stick to binary inputs, i.e.
d = 2). Recall that the two boxes can implement arbitrary
local operations (not only blocking/opening the slits) la-
belled by x
1
and x
2
. If the particle is classical, i.e. has a
definite trajectory, Bob’s output can in each run depend on
the state of at most one box. The conditional probabilities
describing the process can thus be decomposed as follows:
P (b|x
1
x
2
) = q
1
P
1
(b|x
1
) + q
2
P
2
(b|x
2
), (15)
where q
i
is the probability of Alice sending the particle
through i-th box and P
i
(b|x
i
) is the conditional proba-
bility of Bob outputting b given that the particle was sent
through i-th box. The modified interference term therefore
vanishes:
˜
I
(2)
2
(k = 1) =
1
4
1
X
x
1
,x
2
=0
P (b = x
1
x
2
|x
1
x
2
)
1
2
=
1
4
1
X
x
1
,x
2
=0
(1)
x
1
+x
2
P (0|x
1
x
2
) = 0.
(16)
Intuitively, the knowledge about the state of one box does
not increase the probability of correctly guessing the in-
puts’ parity with respect to a random guess. The same rea-
soning holds for arbitrary prime d, implying that
˜
I
(d)
2
(k =
1) = 0 for one classical particle.
Multiple systems. Now, what if Alice possesses two classi-
cal particles? Let us for the moment assume that the boxes
are implemented by slits (as in the original double-slit ex-
periment) and that Alice in each run sends deterministi-
cally one particle towards the first slit and the other to-
wards the second slit. If the parity of the slits’ states is
x
1
x
2
= 0, then Bob either receives both particles on
his side or he receives no particles at all; alternatively, if
the parity is 1, Bob receives exactly one particle. Thus,
by simply counting the number of received particles, Bob
can in each run determine the inputs’ parity and can per-
fectly accomplish the required task, thereby generating
˜
I
(2)
2
(k = 2) = 1/2. On the other hand, the standard
interference definition (1) remains null also for two par-
ticles, since the average number of particles received by
Bob (or inflicted on the screen) is equal to 1 regardless of
the inputs’ parity. This shows the difference between the
standard formulation and our game formulation, as the lat-
ter allows Bob to measure coincidences, and not only the
average particle number (i.e. intensity).
We proceed by analysing the fully general scenario with
m boxes that implement arbitrary local transformations
and assume that Alice’s resources consist of k classical
objects, be it particles, conglomerates of particles or local-
ized wave packets. For this reason, it is clear that Alice’s
resources cannot interact with more than k boxes, which
means that Bob’s output can depend on at most k inputs:
if k < m, Bob’s output is equivalent to a random guess
and
˜
I
(d)
m
(k) = 0, while if k m, he can in principle de-
terministically accomplish the required task and thus gen-
erate
˜
I
(d)
m
(k) = 1 1/d (if Alice sends one system per
box, Bob can in principle retrieve all inputs). The same
reasoning holds for all the other interference terms
˜
I
(d)
m,~ν,f
(as already noted, this reasoning would not be valid if d
was not a prime number).
Therefore, classical theory satisfies n(k) = k, meaning
that k classical systems can exhibit at most k-th order in-
terference.
V Quantum resources
Contrasted to classical mechanics, quantum theory allows
spatial superpositions of physical objects, which can gen-
erate a non-zero interference term I
2
, even with a single
particle. On the other hand, higher order interference
terms I
j>2
defined in multi-slit experiments remain null
even in quantum theory (see for instance [2]). In this
section we show that analogous statements hold for the
generalized interference terms
˜
I
(d)
m,~ν,f
(k = 1) and pro-
vide an extension to more particles (systems). Let us first
look into the simplest case, i.e. one particle and two boxes.
Accepted in Quantum 2021-02-15, click title to verify. Published under CC-BY 4.0. 5
1 Two boxes
We start by considering the case d = 2. Let us suppose
that Alice possesses a single quantum particle and sends it
in spatial superposition towards the two boxes, which im-
plement binary inputs x
1
, x
2
. The quantum state is given
by
|ψi
0
=
1
2
(|1i + |2i) , (17)
where |1i and |2iare states corresponding to the two paths.
Next, suppose that each box interacts with the particle
by applying a local phase-shift φ
i
= x
i
π. After passing
through the boxes, the state is
|ψi
x
1
,x
2
=
1
2
e
ix
1
π
|1i + e
ix
2
π
|2i
. (18)
Therefore, Bob receives the particle in the following states
(up to global phases)
|ψi =
(
1
2
(|1i + |2i) , if x
1
x
2
= 0,
1
2
(|1i |2i) , if x
1
x
2
= 1,
(19)
which are orthogonal and thus perfectly distinguishable,
thereby enabling Bob to deterministically decode the par-
ity x
1
x
2
and to produce
˜
I
(2)
2
(k = 1) = 1/2.
The previous result holds for binary inputs; now suppose
that the parties are playing the modulo game (5) specified
by dit string ~ν = (ν
1
, ν
2
), i.e. Bob’s goal is to output
s
(d)
~x,~ν
= (ν
1
x
1
+ ν
2
x
2
)mod d (we assume there is no final
relabelling, i.e. that f is the identity; as we already argued,
all other cases follow automatically). The players can em-
ploy the following strategy.
As in the binary case, let Alice prepare her particle in the
state
|ψi
0
=
1
2
(|1i + |2i) , (20)
where |1i and |2iare states corresponding to the two paths,
and let the boxes apply local phase shifts as follows
|ψi
x
1
,x
2
=
1
2
ω
ν
1
x
1
d
|1i + ω
ν
2
x
2
d
|2i
=
1
2
|1i + (ω
d
)
s
(d)
~x,~ν
|2i
,
(21)
where the last equality is valid up to a global phase.
Upon receiving the latter state, Bob performs a d-outcome
POVM {Π
0
, ..., Π
d1
} corresponding to the d moduli; the
interference term is then
˜
I
(d)
2,~ν
=
1
d
2
X
x
1
x
2
P (b = s
~x,~ν
|x
1
x
2
)
1
d
=
1
d
X
s
Tr
Π
s
ρ
(s)
1
d
,
(22)
where
ρ
(s)
1
d
X
x
1
,x
2
s
(d)
~x,~ν
=s
ρ
~x
, (23)
and ρ
~x
= |ψi
x
1
,x
2
hψ|.
Let us choose Bob’s POVM to be a “pretty good measure-
ment” [25], which in our case reduces to a set of projectors
up to normalization, i.e.
Π
s
= αρ
(s)
, (24)
where α is a normalization constant. The latter can be eas-
ily calculated by requiring
P
s
Π
s
= 1, thereby obtaining
α =
2
d
.
The interference term is then
˜
I
(d)
2,~ν
=
1
d
X
s
Tr
2
d
ρ
(s)
ρ
(s)
1
d
=
1
d
> 0. (25)
We have thus shown that a single quantum particle can be
used to exhibit second order interference for any d. Notice
that in this protocol we have not used the internal degree
of freedom of the particle and we thus expect that larger
interference values may arise in more sophisticated proto-
cols.
2 General case
Here we analyze the fully general scenario involving
arbitrary local operations and arbitrary measurements. We
start by constraining Alice’s resources to a single quantum
system and afterwards we extend our considerations to
the case of multiple systems.
2.1 Single systems
For a start, let us fix the resources to one quantum system,
without restricting its internal degrees of freedom. The re-
source can thus be an electron, an atom or any localized
quantum system that can be prepared in coherent spatial
superposition using a beam splitter or some more sophis-
ticated mechanism. The local operations implemented by
the m boxes will be represented as CP maps acting on the
internal degrees of freedom of the system.
The most general state Alice can prepare is given by
ρ
0
=
X
i,j,k,l
c
ijkl
|iihj| |φ
k
ihφ
l
|, (26)
where {|ii, i = 1, ..., m} denote states representing de-
fined paths directed towards the m boxes, while {|φ
k
i}
span the Hilbert space of the internal degrees of freedom
of the system (the dimension of which is arbitrary). The
matrix elements c
ijkl
need to satisfy certain conditions in
order for ρ
0
to be a legitimate quantum state, but we will
not specify them since this constraint is not relevant for
what follows.
Each box implements a local CP-map that depends on its
corresponding input. We denote the Kraus operators rep-
resenting the action of the i-th box with
(
B
(k)
i
(x
i
),
X
k
B
(k)
i
(x
i
)B
(k)
i
(x
i
) 1
)
, (27)
Accepted in Quantum 2021-02-15, click title to verify. Published under CC-BY 4.0. 6
where the operators B
(k)
i
(x
i
) act on the internal Hilbert
space of the system. Notice that we allow the transfor-
mations to be non-trace-preserving, since they can destroy
the system, as for instance in the case of slits. Since the
boxes act locally on the system, the total transformation
implemented by the boxes is a CP-map with the following
Kraus operators:
(
M
(k)
~x
=
m
X
i=1
|iihi| B
(k)
i
(x
i
)
)
. (28)
The Kraus operators of the total map are thus obtained by
conditioning the Kraus operators of the local maps on the
path degree of freedom. For example, in the case that the
local operators are unitary transformations, for each con-
figuration of inputs there is only one Kraus operator, i.e.
M
~x
=
m
X
i=1
|iihi| U
i
(x
i
), (29)
where U
i
(x
i
) are unitary operators. Let us now inspect
how the general CP-maps in (28) act on the input state
(26). After passing through the boxes, the state of the sys-
tem is
ρ
~x
=
X
k
M
(k)
~x
ρ
0
M
(k)
~x
=
X
i,j
|iihj| C
ij
(x
i
, x
j
),
(30)
where, in order to simplify the expression, we introduced
the following operators
C
ij
(x
i
, x
j
)
X
knm
c
ijnm
B
(k)
i
(x
i
) |φ
n
ihφ
m
|B
(k)
j
(x
j
).
(31)
Next, let us suppose that Alice and Bob are playing the
modulo game (5) specified by a dit-string ~ν and with no
final relabelling (all other cases follow automatically). No-
tice that for m > 2 and for any α {1, ..., d 1}, the
following property holds
X
~x
(ω
d
)
α
P
k
ν
k
x
k
ρ
~x
=
=
X
i,j
|iihj|
X
~x
(ω
d
)
α
P
k
ν
k
x
k
C
ij
(x
i
, x
j
) = 0,
(32)
where ω
d
e
i2π/d
. This is so because the ten-
sors C
ij
depend on at most two inputs and because
P
d1
x
k
=0
(ω
d
)
αν
k
x
k
= 0.
Let us define the average taken over states with equal mod-
ulo as follows
ρ
(S)
1
d
m1
X
x
1
,...,x
m
(
P
k
ν
k
x
k
)mod d=S
ρ
~x
. (33)
As we show in Appendix C, equations (32) then imply
ρ
(S)
= ρ
(S
0
)
¯ρ, S, S
0
= 0, ..., d 1. (34)
Since all average states ρ
(S)
are equal, Bob cannot dis-
tinguish them by any means. Formally, Bob performs a
measurement consisting of d outcomes and represented by
a generic POVM {Π
0
, ..., Π
d1
}. If Alice sends k = 1
quantum systems, the generalized interference term speci-
fied by the dit-string ~ν necessarily vanishes for m > 2:
˜
I
(d)
m>2,~ν
(k = 1) =
1
d
Tr
"
X
S
Π
S
ρ
(S)
#
1/d
=
1
d
Tr[ ¯ρ] 1/d = 0.
(35)
A resource consisting of one quantum system is enough
to produce non-vanishing second order interference (for
binary inputs, it can even raise the interference term
to its maximum possible value); on the other hand, for
m > 2, there is no difference between sending one
quantum system and sending no resource at all. This
drastic difference can be traced down to (32), where the
tensors C
ij
couple at most two inputs x
i
and x
j
. This is
because quantum states are described by (1, 1) tensors,
i.e. density matrices. The latter constraint arises through
the Born rule, which essentially sets quantum interference
to the second order [3].
2.2 Multiple systems and additivity of interference
Next, let us suppose that Alice’s resources consist of more
than one quantum system, say, in general, k of them. We
assume that the systems are distinguishable and thus de-
scribed by the tensor product of the single-system Hilbert
spaces. The most general state prepared by Alice is then
ρ
0
=
X
i,j,r,l
c
ijrl
k
O
p=1
h
|n
(p)
i
p
ihn
(p)
j
p
| |φ
(p)
r
p
ihφ
(p)
l
p
|
i
, (36)
where i is short for (i
1
, ..., i
k
) and analogously for
the other indices. The vectors
n
|n
(p)
i
p
i, i
p
= 1, ..., m
o
span the spatial Hilbert space of the p-th system, while
n
|φ
(p)
r
p
i, r
p
o
span its internal degrees of freedom (the di-
mensionality of which is arbitrary).
After passing through the boxes, the state is transformed
to
ρ
~x
=
X
i,j
k
O
p=1
h
|n
(p)
i
p
ihn
(p)
j
p
|
i
C
ij
(x
i
1
, x
j
1
, ..., x
i
k
, x
j
k
),
(37)
where {C
ij
} are operators depending on at most 2k inputs
(defined in the same fashion as in the single-system case,
see Eq. (31)). Here we again assumed that the action of
the boxes is represented by local CP-maps conditioned on
the path degrees of freedom of the systems (see Appendix
D for details). The crucial difference with respect to the
single system case is that the expressions (32) are now
valid only if m > 2k. Analogously to the single-system
case, one comes to the following conclusion
˜
I
(d)
m>2k,~ν
(k) = 0. (38)
Accepted in Quantum 2021-02-15, click title to verify. Published under CC-BY 4.0. 7
We therefore showed that k quantum systems cannot
produce more than 2k-th order interference. Now we
are going to show that k systems can produce 2k-th
order interference. For binary inputs (i.e. d = 2),
Alice and Bob can partition the 2k boxes into pairs
{(x
1
, x
2
), ..., (x
2k1
, x
2k
)} and for each pair use the pro-
tocol described in Section 1; Bob can thus perfectly de-
code the parity of each pair, which enables him to win the
game with unit probability. For d > 2, the proof is not so
straightforward, since the protocol involving one particle
and two boxes does not raise the interference term to its
maximum value as it does for binary inputs. Nevertheless,
in Appendix E we derive a general result which shows that
k generic systems of single-system orders {n
1
, ..., n
k
}can
produce (
P
k
i=1
n
i
)-th order interference, for any d 2
(this statement is independent of the underlying physical
theory). Therefore, k quantum systems (i.e. systems of
order two) can produce 2k-th order interference.
According to our classification, the latter results imply
that quantum theory satisfies n(k) = 2k, meaning that
k quantum systems can produce at most 2k-th order inter-
ference
1
.
Moreover, since the order of interference depends sharply
on the number of particles used in the process, it can be
used as a semi-device-independent witness of the number
of particles. More precisely, one can extract a lower bound
on the number of particles present in the process from
purely operational quantities (i.e. conditional probability
distributions P (b|~x)). This witness is not fully device-
independent, since one must still assume that the under-
lying mechanism obeys quantum theory and that the par-
ticle number is well defined (the latter assumption can be
violated if the resources consist of e.g. coherent states of
light). Additionally, even though the boxes’ operations can
be mutually spacelike separated (and therefore the boxes
cannot mutually signal their local inputs to each other),
each box’s operation must still be timelike separated from
Bob (since the systems must in the end be sent from the
boxes towards Bob). Thus, one cannot exclude the pos-
sibility that a box signals its local input towards Bob by
sending some additional system, which had not been pre-
viously sent by Alice. Our particle witness can be seen as
similar to device independent dimension witnesses, where
instead of the number of particles, one aims to certify the
Hilbert space dimension of the underlying system [26, 27].
Classical theory revisited. Even though we already
showed that classical theory satisfies n(k) = k in Sec-
tion IV, here we want to briefly explicate how the lat-
ter can be seen by treating classical theory as a special
1
Notice that the same result holds also for indistinguish-
able quantum systems. In that case, the composite Hilbert
space is the (anti)symmetric subspace of the tensor product of
the single-system Hilbert spaces. Therefore, the order of inter-
ference cannot be higher than the one achievable by indistin-
guishable systems, since further constraints are imposed on the
allowed states and transformations. Moreover, the additivity of
the lower bound proved in Appendix E holds for any systems,
including also indistinguishable quantum systems. This implies
that all quantum systems satisfy n(k) = 2 k.
case of quantum theory. We simply need to restrict the
one-particle-states sent by Alice to be block diagonal in
the spatial basis, and the multi-particle-states to be block-
diagonal in the configuration space basis. The internal de-
grees of freedom can remain quantum (since it does not
affect our result): here we thus regard “classical theory”
to mean “quantum theory with no spatial coherence”. A
general classical k-particle-state is then:
ρ
0
=
X
i,r,l
c
irl
k
O
p=1
h
|n
(p)
i
p
ihn
(p)
i
p
| |φ
(p)
r
p
ihφ
(p)
l
p
|
i
, (39)
where the notation is the same as before. Analogously to
the quantum case, the transformed state is
ρ
~x
=
X
i
k
O
p=1
h
|n
(p)
i
p
ihn
(p)
i
p
|
i
C
i
(x
i
1
, ..., x
i
k
), (40)
where C
i
(x
i
1
, ..., x
i
k
) are tensors as the ones defined in
the quantum case. Since the transformed state is a lin-
ear combination of terms, each of which depends on at
most k inputs, we recover the result that classical theory
(i.e. quantum theory with no spatial coherence) satisfies
n(k) = k.
VI Higher-order interference theories
1 Independent operations
In Appendix E we constructed a proof that k generic sys-
tems of orders {n
1
, ..., n
k
} can exhibit
P
i
n
i
-th order in-
terference, for any d 2. The latter provides a lower
bound which is additive in the interference order. On the
other hand, we saw that in classical and quantum theory,
this lower bound coincides with the upper bound, i.e. these
theories satisfy n(k) = kn(1). In what follows, we will
discuss the extendability of this relation to a broader class
of theories. In this subsection we will assume that the
boxes act independently on each subsystem and show that
additivity follows straightforwardly from the principle of
local tomography [28]; in the next subsection we will drop
this restriction, but in order to prove our statement we will
need to introduce further assumptions.
We adopt the standard formalism of generalized proba-
bilistic theories (GPTs) [28], and suppose that Alice pos-
sesses k systems. The state space of the j-th system is a
convex set that will be denoted with St(A
j
), and we re-
gard it as a subset of a real vector space A
j
. The set of
transformations consists of linear maps acting on A
j
, and
will be denoted with Transf(A
j
). Finally, the set of effects
Eff(A
j
) consists of linear functionals that map states into
probabilities and can thus be regarded as subset of the dual
vector space A
j
.
Now we proceed with specifying how systems compose.
We assume the principle of local tomography [28], which
states that the state of a composite system can be fully
characterized by measurements performed separately on
Accepted in Quantum 2021-02-15, click title to verify. Published under CC-BY 4.0. 8
each subsystem. Under this assumption, the compos-
ite state space of Alice’s systems, which we denote with
St(A), is a subset of the tensor product of the subsystems’
vector spaces, i.e. St(A) A
1
... A
k
. Moreover,
the composite space of effects Eff(A) is a subset of the
tensor product of the single-systems’ dual vector spaces,
i.e. Eff(A) A
1
... A
k
. Furthermore, as men-
tioned above, in this subsection we will assume that the
boxes act independently on the subsystems; we will dis-
cuss the general scenario in the next subsection. We want
to show that under the above assumptions, k systems of
orders {n
1
, ..., n
k
} cannot exhibit more than
P
i
n
i
-th or-
der interference. Together with the lower bound derived
in Appendix E, this will imply that k systems of orders
{n
1
, ..., n
k
} constitute a
P
i
n
i
-th order system. Let us
first focus on binary inputs, i.e. d = 2.
An arbitrary state ~s St(A) prepared by Alice can be writ-
ten as a linear combination of the tensor product of single
system states: ~s =
P
i
a
i
~s
(1)
i
1
... ~s
(k)
i
k
, where i is short
for i
1
, ..., i
k
, and a
i
are real coefficients. The same holds
for an arbitrary effect
~
f Eff(A) representing Bob’s final
measurement, i.e.
~
f =
P
i
b
i
~
f
(1)
i
1
...
~
f
(k)
i
k
. Since we
consider only single-system operations, the overall trans-
formation of the boxes on the composite system is given by
T
~x
= T
(1)
~x
...T
(k)
~x
, where T
(j)
~x
Transf(A
j
) are input-
dependent transformations acting on the j-th system. For
d = 2, the m-th order interference term for an arbitrary
process is then:
˜
I
(2)
m
(k) =
1
2
m
X
~x
(1)
P
a
x
a
P (0|~x)
=
1
2
m
X
i,j
a
i
b
j
X
~x
(1)
P
a
x
a
"
k
O
p=1
~
f
(p)
j
p
#
·
k
O
p
0
=1
T
(p
0
)
~x
~s
(p
0
)
i
p
0
=
1
2
m
X
i,j
a
i
b
j
X
~x
(1)
P
a
x
a
k
Y
p=1
P
(p)
~x
,
(41)
where P
(p)
~x
~
f
(p)
j
p
·T
(p)
~x
~s
(p)
i
p
are probabilities arising from
the single system processes involving p-th system (for sim-
plicity we omitted indices i, j). Therefore, we see that due
to local tomography and the restriction to single-system
operations, the interference term decouples into a linear
combination of products of single-system processes. As it
was shown in Section III, the probability distribution per-
taining to any process involving a system of order n
p
can
be written as a linear combination of functions of at most
n
p
inputs:
P
(p)
~x
=
X
i
1
,...,i
n
p
c
(p)
i
1
,...,i
n
p
f
(p)
(x
i
1
, ..., x
i
n
p
). (42)
Therefore, if N
P
p
n
p
< m, the interference term
necessarily vanishes:
˜
I
(2)
m
(k) =
X
i
1
,...,i
N
a
i
1
,...,i
N
X
~x
(1)
P
a
x
a
g(x
i
1
, ..., x
i
N
) = 0,
(43)
where we introduced for simplicity the coefficients
a
i
1
,...,i
N
and functions g(x
i
1
, ..., x
i
N
), the exact forms of
which are of no relevance.
In order to show that the latter results holds for arbitrary
prime d, we just need to take a look at the dual interference
terms defined in Section III. Given our assumptions, one
arrives to the generalization of (41):
˜
J
(d)
m,~ν,b
(k) =
1
d
m
X
i,j
a
i
b
j
X
~x
(ω
d
)
P
a
ν
a
x
a
k
Y
p=1
P
(p)
b,~x
.
(44)
By assumption, the probabilities P
(p)
b,~x
=
~
f
(p)
b,j
p
· T
(p)
~x
~s
(p)
i
p
pertaining to p-th system do not exhibit more than n
p
-th
order interference and can thus be expressed as a linear
combination of functions depending on at most n
p
inputs,
as we showed in Appendix B. Therefore, if N
P
p
n
p
<
m, then
˜
J
(d)
m,~ν,b
(k) vanishes for all ~ν, b. Since the dual for-
mulation is equivalent to the game formulation (see Ap-
pendix A), this implies that the k systems cannot be used
to achieve more than
P
j
n
j
-th order interference for any
prime d.
On a side note, one may wonder whether the above proof
could be applied to general non-independent transforma-
tions, since local tomography implies that all transforma-
tions can be written as a linear combination of independent
transformations, i.e. T
~x
=
P
i
c
i
(~x)
N
k
p=1
T
(p)
i
p
~x
. How-
ever, due to the coefficients c
i
(~x) being explicitly depen-
dent on ~x, our proof would not be valid in general. There-
fore, in order to drop the assumption of independent trans-
formations, we will characterize the locality of the boxes’
operations in the next subsection.
2 Non-independent operations and locality
In the previous section we proved that under the as-
sumptions of (i) local tomography, and (ii) independent
operations, a system composed of k systems of orders
(n
1
, ..., n
k
) is a (
P
j
n
j
)-th order system. Notice that
within the proof we did not need to specify anything
about the transformations T
~x
and we did not impose the
notion of locality of the boxes’ actions. On the other
hand, in quantum (and classical) theory we proved a
stronger statement: additivity follows without assumption
(ii); however, in that case we explicitly implemented
the notion of locality by conditioning the boxes’ actions
on the path degrees of freedom of the systems. In what
follows, we will provide an analogous analysis in the
context of GPTs, thereby dropping assumption (ii). We
will start by defining the relevant concepts for single
systems.
In order to generalize the quantum proof from Section
V to GPTs, we need to introduce controlled operations,
which means that we will treat the degrees of freedom of
the systems as composed of the “path” degree of freedom
(which will serve as the control) and the “internal”
degrees of freedom (on which the information will be
encoded). Let us start by considering a single-system
Accepted in Quantum 2021-02-15, click title to verify. Published under CC-BY 4.0. 9
A. We denote the state space of the control degrees of
freedom with St(A
(c)
) A
(c)
, and the state space of the
internal degrees of freedom with St(A
(int)
) A
(int)
,
where A
(c)
and A
(int)
are real vector spaces. Assuming
local tomography, the total state space of system A will
then be St(A) A
(c)
A
(int)
. Analogously, we can
define the spaces of effects as subspaces of the dual vector
spaces, i.e. Eff(A
(c)
) A
(c)
, Eff(A
(int)
) A
(int)
, and
Eff(A) A
(c)
A
(int)
. Now we will characterize the
state space of the control degree of freedom.
Assumption 0. Let us assume that there exists an
m-outcome measurement for the control degree of
freedom corresponding to the following set of effects
n
~
f
(1)
, ...,
~
f
(m)
Eff(A
(c)
);
P
i
~
f
(i)
= ~u
(c)
o
, where
~u
(c)
is the unit effect, i.e. the effect that satisfies
~u
(c)
·~v = 1, ~v St(A
(c)
). The physical meaning of the
latter is that each effect
~
f
(i)
gives the probability of the
system being found at box i. We will thus refer to this
measurement as the “which-box measurement”.
Let us also define subsets of boxes J =
j
1
, , ..., j
|J|
I, where I {1, 2, ..., m}, and introduce the coarse-
grained effects
~
f
(J)
P
|J|
i=1
~
f
(j
i
)
, with |J| being the
cardinality of J. Effect
~
f
(J)
thus outputs the probability
of the system being found at the subset of boxes J I.
We will say that an arbitrary state ~v St(A
(c)
) is
localized at subset J if:
~
f
(J)
·~v = 1
2
;
J
0
, J
0
J
~
f
(J
0
)
·~v > 0.
The first point of this definition simply say that “a system
being localized at some particular subset” means that “the
probability of finding the system outside of this subset is
null”. The second point is needed in order to select the
minimum possible subset which satisfies the first point
and thus select a unique subset.
We will now consider a basis S = {~s
1
, ..., ~s
r
(c)
} of A
(c)
,
with ~s
i
St(A
(c)
), and r
(c)
being the dimension of A
(c)
.
If the theory describing our system was classical, then
r
(c)
= m, and we could choose a basis consisting of states
localized at each box, i.e.
~
f
(i)
· ~s
j
= δ
ij
. On the other
hand, if we consider quantum theory, then r
(c)
= m
2
, and
we can construct a basis S = {~s
j
1
j
2
, j
1
, j
2
= 1, ..., m}
such that each of its elements ~s
j
1
j
2
is localized at subset
{j
1
, j
2
}. One example of such a basis is the following:
states ~s
jj
correspond to the classical states localized at
each box, i.e. ~s
jj
= |jihj|, whereas, for j
1
< j
2
, states
~s
j
1
j
2
and ~s
j
2
j
1
correspond to the superposition states
~s
j
1
j
2
= |j
1
j
2
i
x
hj
1
j
2
| and ~s
j
2
j
1
= |j
1
j
2
i
y
hj
1
j
2
|, where
|j
1
j
2
i
x
(|j
1
i + |j
2
i) and |j
1
j
2
i
y
(|j
1
i + i |j
2
i) (see
for instance [10]). Here we see that the state-space of
quantum theory can be spanned by states, each of which
is localized at most at two boxes. On the other hand,
all states in classical theory can be spanned by states,
2
Or equivalently: J
0
, J
0
J =
~
f
(J
0
)
· ~v = 0.
each of which is localized at one box. Tentatively, one
may guess from the latter that there is a strong relation
between the “localizability” of the state-space of a theory
with respect to the “which-box measurement” and the
order of interference of the theory
3
. In what follows, we
will analyze this relation and show that it does indeed
hold under certain assumptions. However, we will first
formalize the notion of the “localizability” with respect to
the “which-box measurement” by introducing the notion
of “locality order”.
Locality order. Let us focus on a generic state-space
of the control degree of freedom St(A
(c)
) (while still
assuming that there exists the which-box measurement,
i.e. Assumption 0), and consider an arbitrary basis
S = {~s
1
, ..., ~s
r
(c)
} of A
(c)
, with ~s
i
St(A
(c)
). The
elements of S can be localized at various boxes’ subsets,
and these subsets consist in general of different numbers
of boxes (i.e. the subsets have different cardinalities).
Let us define l
S
N to be the maximum among these
numbers, meaning that each element of S is localized
within at most l
S
different boxes. Formally, for each
basis S = {~s
1
, ..., ~s
r
(c)
} we define the parameter l
S
in the
following way:
i, (J
i
I) , s.t. (~s
i
is localized at J
i
) & (|J
i
| l
S
) .
(45)
Naturally, different basis choices S correspond to different
values of l
S
. We will define the locality order L as the
minimum l
S
among all possible basis, i.e. L min
S
l
S
,
and denote a basis that achieves this value of l
S
with
S
(there can be many different basis that achieve the
minimum value; we will simply take S
to be one of
them). Therefore, the parameter l
S
is associated to each
basis S, whereas the locality order L is associated to
the theory, together with the “which-box measurement”.
Quantum theory satisfies L = 2 (with respect to the spe-
cific which-box measurement as defined in Assumption
0), since there exists a complete basis whose elements
consist of superpositions of at most two boxes (see the
example from the previous paragraph), and there is no
basis with all of its elements localized at single boxes
(classical theory of course satisfies L = 1). Note that a
hypothetical theory could also satisfy L = m, meaning
that any basis must contain at least one “completely
de-localized” state. Now we are ready to state our main
definitions and assumptions, which will formalize the
notion of local operations.
Assumption 1. Here we will introduce the notion
of locality of the boxes’ operations. As before, we
3
A similar reasoning motivated the construction of the den-
sity cube theory which is a third-order-interference theory ob-
tained as a modification of quantum theory, by replacing den-
sity matrices (tensors with two indices) with tensors with three
indices (the so called density cubes). Translated to our frame-
work, such a state space is spanned by states, each of which is
localized at most at three boxes [3].
Accepted in Quantum 2021-02-15, click title to verify. Published under CC-BY 4.0. 10
will label with S
= {~s
1
, ..., ~s
r
(c)
} one of the ba-
sis of the control degree of freedom, which satisfy
l
S
= min
S
l
S
= L. Each of the states ~s
n
is localized
at subset J
n
=
n
j
(n)
1
, ..., j
(n)
|J
n
|
o
, with |J
n
| L. Let us
now suppose that a system A is initially prepared in the
product state ~s
i
~g, where ~s
i
S
, and ~g St(A
(int)
).
The initial state is thus localized within the subset of
boxes J
i
I. We deem it natural to assume that the
boxes act in such a way that (i) the transformed state
is still localized within subset J
i
(i.e. the boxes cannot
“delocalize” the system), and (ii) the transformed state
cannot depend on inputs pertaining to boxes outside of J
i
(i.e. if the probability of finding the system at some box is
null, then the system should not be affected by that box).
We will formalize point (i) by requiring that the boxes
implement transformations T
~x
on the input state (~s
i
~g)
in such a way that the output state satisfies
(
~
f
(J)
~e) · T
~x
(~s
i
~g) = 0, (46)
for all coarse-grained effects
~
f
(J)
with J J
i
= , and
arbitrary effects ~e Eff(A
(int)
). Equation (46) thus states
that one cannot steer the control degree of freedom of the
output state into a state which is localized outside of the
initial subset J
i
(i.e. this is what we mean that the output
state is localized within J
i
). The most general form of the
action of the transformations T
~x
that satisfies the above
requirements is the following:
T
~x
(~s
i
~g) =
X
n
J
n
J
i
~s
n
T
(i,n)
~x
(J
i
)
~g, (47)
where the sum runs over those basis states pertaining to
S
which are localized within the initial subset, i.e. each
basis state ~s
n
S
is localized within subset J
n
, with
J
n
J
i
. The transformations T
(i,n)
~x
(J
i
)
are linear operators
on A
(int)
and depend only on inputs contained within
subset J
i
, i.e. ~x
(J
i
)
x
j
(i)
1
, ..., x
j
(i)
|J
i
|
, where we used
the notation J
i
=
n
j
(i)
1
, ..., j
(i)
|J
i
|
o
. Moreover, all addi-
tional coefficients that may appear in front of each term of
the sum are for simplicity absorbed in the operators T
(i,n)
~x
(J
i
)
(also, note that the vectors T
(i,n)
~x
(J
i
)
~g A
(int)
may generally
lie outside of the internal state space St(A
(int)
)).
Relation between the locality order and the order
of interference. Now we will show that Assumption
1 and the principle of local tomography imply a strong
relation between the order of interference and the locality
order. Consider a general instance of our game which
consists of Alice preparing her system in an arbitrary
state, sending it through the boxes and Bob performing a
generic measurement, thereby producing the conditional
probabilities P (b|~x). Let us introduce a basis for the
internal degrees of freedom {~g
1
, ..., ~g
r
(int)
}, where r
(int)
is the dimension of the internal vector space A
(int)
.
According to the principle of local tomography, any initial
state ~v St(A) can be written as
~v =
X
i,j
c
ij
~s
i
~g
j
, (48)
where c
ij
are real coefficients, and ~s
i
S
. The boxes
implement a transformation T
~x
, and Bob’s d-outcome
measurement is modelled via a generic set of effects
n
~
E
0
, ...,
~
E
d1
Eff(A),
P
i
~
E
i
= ~u
o
, where ~u is the unit
effect on the total state-space. The conditional probability
is thus
P (b|~x) =
X
i,j
c
ij
~
E
b
· (T
~x
~s
i
~g
j
) =
=
X
i,j,n
J
n
J
i
c
ij
~
E
b
·
~s
n
T
(i,n)
~x
(J
i
)
~g
j
,
(49)
where in the second equality we used Assumption 1.
Each transformation T
(i,n)
~x
(J
i
)
depends only on inputs within
subset J
i
. Therefore, for a given theory with locality order
L, the probabilities P (b|~x) are at most of algebraic order
L. Now we can see a direct connection to the order of in-
terference: indeed, as proven in Section III and Appendix
B, if a distribution exhibits k-th order interference, then
its algebraic order is k. Thus, if a system can exhibit k-th
order interference, then Assumption 1 implies that the
theory satisfies L k.
Next, we will introduce a further assumption which will
relate the possible transformations implementable by the
boxes to the locality order of the theory, and show that
together with the previous assumptions, it implies L = k.
Assumption 2. Let us suppose that the locality or-
der of our system is L, meaning that all states can be
written as linear combinations of states, each of which
is localized in subsets of at most L boxes. Moreover,
there exist states which cannot be decomposed into linear
combinations of states, each of which is localized at less
than L boxes. We assume the following: there exists at
least one state ~v St(A) and one set of transformations
{T
~x
, ~x}, such that the transformed state T
~x
~v is of
algebraic order L, i.e. it cannot be decomposed into a
combination of terms, each of which depends on less
than L inputs. Let us heuristically illustrate the meaning
and motivation of this assumption with a simple example
involving two boxes and a system described by a theory
with locality order L = 2. Let us take for the moment
that our assumption does not hold, i.e. that all states and
transformations in the theory give rise only to states with
algebraic order 1. This means that for any state ~v St(A)
and any set of transformations {T
x
1
x
2
, x
1
, x
2
}, the
following holds:
T
x
1
,x
2
~v =
X
i
~s
i
T
(v,i)
x(i)
~g
i
, (50)
where ~s
i
S
, ~g
i
St(A
(int)
). The inputs x(i) can be
either x
1
or x
2
depending on i, which makes each of the
Accepted in Quantum 2021-02-15, click title to verify. Published under CC-BY 4.0. 11
operators T
(v,i)
x(i)
depend only on one input. On the other
hand, if we considered a system of locality order L = 1
(e.g. classical theory), then a general output state T
x
1
,x
2
~v
within that theory would have a similar form to the one
in Equation (50): it would still be a linear combination
of terms, each of which depends only on one input.
Thus, if our assumption did not hold, a system of locality
order 2 would encode the inputs in the qualitatively same
way as a system of order 1. In order to introduce a
difference between systems of different orders, we will
assume that a system of order L can produce a state with
algebraic order L. This assumption is rather technical
and admittedly requires further physical justification;
however, in this work we will take it at face value and
show that, together with the other assumptions, it implies
additivity of interference under composition. Moreover,
note that the assumption is satisfied by quantum theory:
namely, if the system is prepared in a superposition
of two boxes, there exist local transformations that
encode the two inputs on the state (e.g. local phase
gates) in such a way that the transformed state cannot be
decomposed into a linear combination of terms, each of
which depends only on one input. On the other hand,
superpositions of more than two boxes still give rise only
to distributions of algebraic order 2, which is related to the
fact that the quantum density matrix is a tensor with two
indices (which essentially sets the locality order to L = 2).
L = k. Let us now briefly show how the conjunction of
our assumptions implies L = k. Namely, Assumption
2 directly implies that if the system cannot exhibit more
than k-th order interference, then L k, since for L > k
there would exist states and transformations that produce
probabilities of algebraic order larger than k which would
exhibit more than k-th order interference. On the other
hand, as we have seen before, Assumption 1 and the
principle of local tomography imply L k. Hence,
the conjunction of the latter statements implies that the
locality order of a k-th order system is L = k.
Assumption 3. Up until now, the discussion has
been focused only on single systems; now we will
specify how the boxes act on composite systems. In
sub-section 1 we had assumed that the boxes act in-
dependently on the subsystems; here we want to drop
this assumption. Let us consider a system composed
of two subsystems. We will label the basis that achieve
the minimal locality order for the first and second
subsystem respectively with S
1
and S
2
. Suppose that
the system is prepared in the following product state
~s
i
1
~s
i
2
~g
1
~g
2
A
(c)
1
A
(c)
2
A
(int)
1
A
(int)
2
,
where ~g
1
and ~g
2
are arbitrary internal states of the two
subsystems, and ~s
i
1
S
1
, ~s
i
2
S
2
, are localized
respectively at subsets J
i
1
=
n
j
(i
1
)
1
, ..., j
(i
1
)
|J
i
1
|
o
I and
J
i
2
=
n
j
(i
2
)
1
, ..., j
(i
2
)
|J
i
2
|
o
I. Since the two subsystems
are localized respectively at J
i
1
and J
i
2
, we will say that
the composite system is localized at J
i
1
J
i
2
. Now we
will introduce the action of the boxes on the composite
system as a direct generalization of Assumption 1.
Namely, we will demand that (i) the composite control
degree of freedom of the transformed state can be steered
only into states localized within J
i
1
J
i
2
, and (ii) the
transformed state depends only on inputs contained within
subset J
i
1
J
i
2
. Analogously to Assumption 1., the first
part states that the boxes cannot further “delocalize” the
system, while the second part states that if the probability
of finding either of the subsystems at some box is 0, then
the composite system should not be affected by the action
of that box. Thus we see that this assumption states that
if two subsystems of a composite system are localized
at subsets J
i
1
and J
i
2
, then the transformations acts on
the composite system, as if the latter was a single system
localized at subset J
i
1
J
i
2
. The most general form of the
transformations T
~x
that satisfies the above requirements is
T
~x
(~s
i
1
~s
i
2
~g
1
~g
2
)
=
X
n
1
n
2
(J
n
1
J
n
2
)
(J
i
1
J
i
2
)
~s
n
1
~s
n
2
T
(in)
~x
(J
i
1
,J
i
2
)
(~g
1
~g
2
) ,
(51)
where we introduced the input strings
~x
(J
i
1
,J
i
2
)
(x
j
(i
1
)
1
, ..., x
j
(i
1
)
|J
i
1
|
, x
j
(i
2
)
1
, ..., x
j
(i
2
)
|J
i
2
|
), (52)
and the bold index n stands for n
1
n
2
. Each of the transfor-
mations T
(in)
~x
(J
i
1
,J
i
2
)
is a linear operator on A
(int)
1
A
(int)
2
that depends on inputs ~x
(J
i
1
,J
i
2
)
. The sum in Equation
(51) runs over states which are localized within the
union of the initial subsets, i.e. states ~s
n
1
and ~s