Fermat's Library | q-2021-03-08-404 annotated/explained version.

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 identiﬁcation 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 deﬁned 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 [6–9].

In this work we study higher-order interference from the

information-theoretic perspective. Firstly, we reconsider

the deﬁnitions of multi-slit experiments and Sorkin’s

classiﬁcation and notice that: (a) the framework is

deﬁned only for single particles (or single systems), (b)

the interference order is deﬁned with respect to simple

operations of blocking/opening the slits, and (c) the (ﬁnal)

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 ﬁnal 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 classiﬁcation) and

to the number of systems involved. This generalization

offers a shift in the perspective: higher order interference

theories are not deﬁned 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 ﬁnal 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

ﬁndings 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 [10–13] 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 [14–16], 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 ﬁgure 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 redeﬁned 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 inﬂicting 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 redeﬁned 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

ﬁgure 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 ﬁnal

operation consists of intensity measurements, the general-

ized higher-order interference term

˜

I

m

(k) reduces to the

standard higher-order term deﬁned 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 deﬁnition 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 deﬁnition

in terms of the probability of winning the parity game in-

volving m boxes by using a ﬁnite 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 modiﬁed 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 ﬁnite 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

d−1

X

x

1

,...,x

m

=0

P



b = f(s

(d)

~ν,~x

)|x

1

...x

m



−

1

d

,

(5)

which are deﬁned 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 deﬁned in (5) offer a deﬁnition of

higher order interference theories for arbitrary prime d.

Deﬁnition. We deﬁne 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 speciﬁc outputs’ labelling ﬁxed 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 ﬁxed to

be the identity map (i.e. no ﬁnal 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 speciﬁc

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 speciﬁed

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 deﬁnition 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) satisﬁes 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 ﬁrst 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 speciﬁes 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 coefﬁcients

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-

ﬁned 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

deﬁnite 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 modiﬁed 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 ﬁrst 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 deﬁnition (1) remains null also for two par-

ticles, since the average number of particles received by

Bob (or inﬂicted 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 satisﬁes 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

deﬁned 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 ﬁrst

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) speciﬁed

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 ﬁnal

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

, ..., Π

d−1

} 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 ﬁx 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-

ﬁned 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-

ﬁguration 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) speciﬁed by a dit-string ~ν and with no

ﬁnal 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

d−1

x

k

=0

(ω

d

)

αν

k

x

k

= 0.

Let us deﬁne the average taken over states with equal mod-

ulo as follows

ρ

(S)

≡

1

d

m−1

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

, ..., Π

d−1

}. If Alice sends k = 1

quantum systems, the generalized interference term speci-

ﬁed 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

(deﬁned 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

2k−1

, 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 classiﬁcation, the latter results imply

that quantum theory satisﬁes 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 deﬁned (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 satisﬁes n(k) = k in Sec-

tion IV, here we want to brieﬂy 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 conﬁguration 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 deﬁned 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) satisﬁes

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

ﬁrst 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 coefﬁcients. The same holds

for an arbitrary effect

~

f ∈ Eff(A) representing Bob’s ﬁnal

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 coefﬁcients

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 deﬁned 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 coefﬁcients 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 deﬁning 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

deﬁne 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 satisﬁes

~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 deﬁne 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 ﬁrst point of this deﬁnition simply say that “a system

being localized at some particular subset” means that “the

probability of ﬁnding the system outside of this subset is

null”. The second point is needed in order to select the

minimum possible subset which satisﬁes the ﬁrst 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 ﬁrst

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 deﬁne 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 deﬁne 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 deﬁne 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 satisﬁes L = 2 (with respect to the spe-

ciﬁc which-box measurement as deﬁned 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 satisﬁes 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

deﬁnitions 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 modiﬁcation 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 ﬁnding 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 satisﬁes

(

~

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 satisﬁes 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 coefﬁcients 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 coefﬁcients, 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

d−1

∈ 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 satisﬁes 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 justiﬁcation;

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 satisﬁed 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 brieﬂy 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 ﬁrst 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 ﬁrst

part states that the boxes cannot further “delocalize” the

system, while the second part states that if the probability

of ﬁnding 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 satisﬁes 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

n

2

are

localized respectively at subsets J

n

1

and J

n

2

, where the

latter satisfy (J

n

1

∪ J

n

2

) ⊆ (J

i

1

∪ J

i

2

). Notice that

transformations that entangle the subsystems are not

excluded and are to be expected if the initial states of the

control systems of the two subsystems are localized within

overlapping subsets of the boxes, i.e. if J

i

1

∩ J

i

2

6= ∅.

Additivity of interference. Now we will show that

the conjunction of Assumption 3 with the previous

assumptions implies that interference is additive under

composition of systems. Let us consider a system

composed of two k-th order subsystems. As we have

shown before, the principle of local tomography and

Assumptions 1&2 imply that the locality orders of both

subsystems are L = k. Consequently, this enables

us to choose the following basis for the composite

control state space:



~s

i

1

⊗~s

i

2

, ∀i

1

, i

2

= 1, ..., r

(c)



,

where the single-system states ~s

i

1

and ~s

i

2

are localized

respectively at subsets J

i

1

=

n

j

(i

1

)

1

, ..., j

(i

1

)

|J

i

1

|)

o

and

J

i

2

=

n

j

(i

2

)

1

, ..., j

(i

2

)

|J

i

2

|

o

, with |J

i

1

| ≤ k and |J

i

2

| ≤ k.

From here it is simple to show that two k-th order sys-

tems cannot exhibit more than 2k-th order interference.

Namely, due to the assumption of local tomography, the

most general initial state prepared by Alice is

~v =

X

ik

c

ik

~s

i

1

⊗~s

i

2

⊗~g

k

1

⊗~g

k

2

, (53)

Accepted in Quantum 2021-02-15, click title to verify. Published under CC-BY 4.0. 12

where {~g

k

1

⊗~g

k

2

, ∀k

1

, k

2

} forms a basis for the inter-

nal state space of the composite system. The bold in-

dices i, k stand for i

1

, i

2

, k

1

, k

2

, and c

ik

are real co-

efﬁcients. The composite system is then sent through

the boxes, which implement the input-dependent trans-

formation T

~x

. Finally, Bob performs a measurement

n

~

E

0

, ...,

~

E

d−1

∈ Eff(A),

P

i

~

E

i

= ~u

o

, where ~u is the unit

effect on the total state-space. The conditional probabili-

ties thus follow:

P (b|~x) =

X

ik

c

ik

~

E

b

· [T

~x

(~s

i

1

⊗~s

i

2

⊗~g

k

1

⊗~g

k

2

)]

=

X

ikn

c

ik

~

E

b

·

h

~s

n

1

⊗~s

n

2

⊗ T

(in)

~x

(J

i

1

J

i

2

)

(~g

k

1

⊗~g

k

2

)

i

.

(54)

Since ~x

(J

i

1

J

i

2

)

, as deﬁned in Equation (52), is a string

of at most 2k different inputs, the algebraic order of the

conditional probabilities arising from such processes is

bounded by 2k, which implies that two k-th order systems

produce at most (2k)-th order interference. The procedure

can be trivially generalized to an arbitrary number of

systems, by composing them two-by-two, thus arriving

to the conclusion that the upper bound on interference

is additive under the composition of systems. Together

with the result in Appendix E which proves the additivity

of the lower bound of interference under composition,

this completes the proof that a system composed of

subsystems of orders {n

1

, ..., n

p

} is a (

P

p

i=1

n

i

)-th order

system. Note that this result is valid for the inputs x

i

being elements of a set of cardinality d, with d being an

arbitrary prime number.

We will now brieﬂy summarize and emphasize the

main assumptions and results of this section. In Subsec-

tion 1 we had proved the additivity of interference under

the assumptions of local tomography and independent

operations, without referring at all to the locality of the

boxes’ operations. In Subsection 2, in order to drop the

second assumption, we implemented the notion of locality

via controlled operations, as a natural generalization of the

quantum and classical cases. Besides the principle of local

tomography and the assumption of the existence of the

which-box measurement (Assumption 0), we introduced

three further assumptions on single-(Assumptions 1 & 2)

and composite-system transformations (Assumption 3).

Finally, notice that in this section and overall in the whole

manuscript, we treated locality via controlled operations;

one may however adopt a different view and from the

very start associate to each space(time) region a system,

the transformations on which would automatically be

regarded as local (in quantum theory, such a formulation

would correspond to second-quantization and to local

quantum physics [29], which makes it more compatible

with relativity).

VII Conclusion and Outlook

In this work we introduced a class of information-theoretic

games, which generalize standard multi-slit interference

experiments. The order of interference of a theory is

then seen as the (im)possibility of accomplishing certain

information-processing tasks using ﬁnite resources. These

games essentially characterize how much information can

be decoded from a physical system given that the informa-

tion was encoded in a global property (parity or modulo

of the inputs) of local pieces of information (local inputs).

We showed that within quantum theory, the order of in-

terference of k systems is 2k; it would be interesting to

inspect potential connections of this result to superdense

coding, which states that k qubits can be used to send at

most 2k bits. Moreover, the game formulation can pro-

vide a (semi)-device-independent witness of the particle

number. Finally, even though our work is mainly focused

on conceptual issues, it might inspire novel experimental

tests of higher-order interference (albeit now redeﬁned in

terms of our game); for instance, one could replace slits

with boxes implementing generic unitary operations and

observe how the order of interference scales with the num-

ber of systems. This could then complement the vast ex-

perimental search for higher-order interference [30–33].

Another interesting direction is to take the boxes’ inputs to

be concrete spatio-temporal variables, as in Ref. [34], and

see how this constrains the order of interference achievable

with a ﬁxed amount of resources (e.g. one may perhaps

ﬁnd connections between the order of interference and the

dimensionality of space).

So far there have been several attempts at explaining the

order of interference of quantum theory; however, we

deem that a physically intuitive explanation has not yet

been obtained. The reason for this might be that the sole

question is leading us in the wrong direction. Instead of

asking ourselves why does quantum theory behave in a

particular way in multi-slit experiments (or GPT gener-

alizations thereof), we could ask why does quantum the-

ory restrict the amount of globally-encoded information

(parity/modulo of locally encoded bits/dits) that can be

retrieved from a system. Moreover, what is the relation

between the (im)possibility of such a decoding and the

number of systems used for encoding the information? Is

there any physical argument for why interference should

be additive under composition (e.g. violation of the no-

signalling principle)? How does one even deﬁne the notion

of number of systems in a device-independent scenario (or

ought one to quantify the resources in an alternative man-

ner)? We plan to investigate these and further questions in

future works.

Acknowledgements

The authors thank the three anonymous reviewers for their

insightful comments and suggestions which greatly im-

proved both the content and the form of this manuscript.

The authors thank Markus P. Müller, Joshua Morris and

Accepted in Quantum 2021-02-15, click title to verify. Published under CC-BY 4.0. 13

Nicolás M. Sánchez for helpful discussions. B.D. ac-

knowledges support from an ESQ Discovery Grant of the

Austrian Academy of Sciences (OAW) and the Austrian

Science Fund (FWF) through BeyondC-F7112. S.H. ac-

knowledges support from an ESQ Discovery Grant of the

Austrian Academy of Sciences (OAW).

Bibliography

[1] Feynman, R.P., Leighton, R.B. and Sands, M., 2005.

The Feynman Lectures on Physics: Deﬁnitive Edi-

tion. Pearson Addison-Wesley. ISBN 0-8053-9046-4

[2] Sorkin, R.D., 1994. Quantum mechan-

ics as quantum measure theory. Modern

Physics Letters A, 9(33), pp.3119-3127. DOI:

https://doi.org/10.1142/S021773239400294X

[3] Dakic, B., Paterek, T. and Brukner, C., 2014. Den-

sity cubes and higher-order interference theories.

New Journal of Physics, 16(2), p.023028. DOI:

http://dx.doi.org/10.1088/1367-2630/16/2/023028

[4] Barnum, H., Mueller, M.P. and Ududec, C.,

2014. Higher-order interference and single-system

postulates characterizing quantum theory. New

Journal of Physics, 16(12), p.123029. DOI:

http://dx.doi.org/10.1088/1367-2630/16/12/123029

[5] Lee, C.M. and Selby, J.H., 2017. Higher-order

interference in extensions of quantum theory.

Foundations of Physics, 47(1), pp.89-112. DOI:

https://doi.org/10.1007/s10701-016-0045-4

[6] Barnum, H., Lee, C.M., Scandolo, C.M. and Selby,

J.H., 2017. Ruling out higher-order interference

from purity principles. Entropy, 19(6), p.253. DOI:

https://doi.org/10.3390/e19060253

[7] Ududec, C., Barnum, H. and Emerson, J., 2011.

Three slit experiments and the structure of quantum

theory. Foundations of Physics, 41(3), pp.396-405.

DOI: https://doi.org/10.1007/s10701-010-9429-z

[8] Niestegge, G., 2013. Three-slit experiments and

quantum nonlocality. Foundations of Physics, 43(6),

pp.805-812. DOI: https://doi.org/10.1007/s10701-

013-9719-3

[9] Lee, C.M. and Selby, J.H., 2016. Generalised

phase kick-back: the structure of computa-

tional algorithms from physical principles.

New Journal of Physics, 18(3), p.033023. DOI:

http://dx.doi.org/10.1088/1367-2630/18/3/033023

[10] Hardy, L., 2001. Quantum theory from ﬁve reason-

able axioms. arXiv preprint quant-ph/0101012.

[11] Dakic, B. and Brukner, C. Quantum theory

and beyond: is entanglement special? Deep

Beauty: Understanding the Quantum World

Through Mathematical Innovation (ed. Halvor-

son, H.) (Cambridge Univ. Press, 2011). DOI:

https://doi.org/10.1017/CBO9780511976971.011

[12] Masanes, L. and Mueller, M.P., 2011. A deriva-

tion of quantum theory from physical requirements.

New Journal of Physics, 13(6), p.063001. DOI:

http://dx.doi.org/10.1088/1367-2630/13/6/063001

[13] Chiribella, G., D Ariano, G.M. and Perinotti, P.,

2011. Informational derivation of quantum the-

ory. Physical Review A, 84(1), p.012311. DOI:

http://dx.doi.org/10.1103/PhysRevA.84.012311

[14] Del Santo, F. and Daki

´

c, B., 2018. Two-way

communication with a single quantum particle.

Physical review letters, 120(6), p.060503. DOI:

https://doi.org/10.1103/PhysRevLett.120.060503

[15] Massa, F., Moqanaki, A., Baumeler, Ä., Del

Santo, F., Kettlewell, J.A., Daki

´

c, B. and

Walther, P., 2019. Experimental two-way com-

munication with one photon. Advanced Quan-

tum Technologies, 2(11), p.1900050. DOI:

https://doi.org/10.1002/qute.201900050

[16] Hsu, L.Y., Lai, C.Y., Chang, Y.C., Wu, C.M. and

Lee, R.K., 2020. Inﬁnite information can be car-

ried using a single quantum particle. arXiv preprint

arXiv:2002.10374.

[17] Horvat, S. and Daki

´

c, B., 2019. Quantum en-

hancement to information speed. arXiv preprint

arXiv:1911.11803.

[18] Oreshkov, O., Costa, F. and Brukner, C.,

2012. Quantum correlations with no causal or-

der. Nature communications, 3, p.1092. DOI:

https://doi.org/10.1038/ncomms2076

[19] Feix, A., Araujo, M. and Brukner, C., 2016. Causally

nonseparable processes admitting a causal model.

New Journal of Physics, 18(8), p.083040. DOI:

http://dx.doi.org/10.1088/1367-2630/18/8/083040

[20] Guerin, P.A., Feix, A., Araujo, M. and Brukner,

C., 2016. Exponential communication com-

plexity advantage from quantum superposition

of the direction of communication. Physi-

cal review letters, 117(10), p.100502. DOI:

https://doi.org/10.1103/PhysRevLett.117.100502

[21] Chiribella, G., D Ariano, G.M. and Perinotti,

P., 2008. Quantum circuit architecture. Phys-

ical review letters, 101(6), p.060401. DOI:

https://doi.org/10.1103/PhysRevLett.101.060401

[22] Chiribella, G., D Ariano, G.M., Perinotti,

P. and Valiron, B., 2013. Quantum com-

putations without deﬁnite causal structure.

Physical Review A, 88(2), p.022318. DOI:

https://doi.org/10.1103/PhysRevA.88.022318

[23] Allen, J.M.A., Barrett, J., Horsman, D.C., Lee,

C.M. and Spekkens, R.W., 2017. Quantum

common causes and quantum causal mod-

els. Physical Review X, 7(3), p.031021. DOI:

https://doi.org/10.1103/PhysRevX.7.031021

[24] Brunner, N., Cavalcanti, D., Pironio, S., Scarani,

V. and Wehner, S., 2014. Bell nonlocality. Re-

views of Modern Physics, 86(2), p.419. DOI:

https://doi.org/10.1103/RevModPhys.86.419

[25] Hausladen, P. and Wootters, W.K., 1994.

A ’pretty good’ measurement for distin-

guishing quantum states. Journal of Mod-

ern Optics, 41(12), pp.2385-2390. DOI:

https://doi.org/10.1080/09500349414552221

Accepted in Quantum 2021-02-15, click title to verify. Published under CC-BY 4.0. 14

[26] Cong, W., Cai, Y., Bancal, J.D. and Scarani,

V., 2017. Witnessing irreducible dimension.

Physical review letters, 119(8), p.080401. DOI:

https://doi.org/10.1103/PhysRevLett.119.080401

[27] Aguilar, E.A., Farkas, M., Martinez, D., Al-

varado, M., Carine, J., Xavier, G.B., Barra,

J.F., Canas, G., Pawlowski, M. and Lima, G.,

2018. Certifying an irreducible 1024-dimensional

photonic state using reﬁned dimension witnesses.

Physical Review Letters, 120(23), p.230503. DOI:

https://doi.org/10.1103/PhysRevLett.120.230503

[28] Barrett, J., 2007. Information processing

in generalized probabilistic theories. Phys-

ical Review A, 75(3), p.032304. DOI:

https://doi.org/10.1103/PhysRevA.75.032304

[29] Haag, R., 2012. Local quantum physics: Fields, par-

ticles, algebras. Springer Science & Business Media.

DOI: https://doi.org/10.1007/978-3-642-61458-3

[30] Sinha, U., Couteau, C., Jennewein, T.,

Laﬂamme, R. and Weihs, G., 2010. Ruling

out multi-order interference in quantum me-

chanics. Science, 329(5990), pp.418-421. DOI:

https://doi.org/10.1126/science.1190545

[31] Park, D.K., Moussa, O. and Laﬂamme, R., 2012.

Three path interference using nuclear magnetic res-

onance: a test of the consistency of Born’s rule.

New Journal of Physics, 14(11), p.113025. DOI:

http://dx.doi.org/10.1088/1367-2630/14/11/113025

[32] Kauten, T., Keil, R., Kaufmann, T., Pressl, B.,

Brukner, C. and Weihs, G., 2017. Obtaining

tight bounds on higher-order interferences with

a 5-path interferometer. New Journal of Physics,

19(3), p.033017. DOI: https://doi.org/10.1088/1367-

2630/aa5d98

[33] Lee, K.S., Zhuo, Z., Couteau, C., Wilkowski, D. and

Paterek, T., 2020. Atomic test of higher-order inter-

ference. Physical Review A, 101(5), p.052111. DOI:

https://doi.org/10.1103/PhysRevA.101.052111

[34] Garner, A.J., Krumm, M. and Mueller, M.P.,

2020. Semi-device-independent information pro-

cessing with spatiotemporal degrees of freedom.

Physical Review Research, 2(1), p.013112. DOI:

https://doi.org/10.1103/PhysRevResearch.2.013112

[35] Lomonosov, V. and Rosenthal, P., 2004. The simplest

proof of Burnside’s theorem on matrix algebras. Lin-

ear algebra and its applications, 383, pp.45-47. DOI:

https://doi.org/10.1016/j.laa.2003.08.012

A Equivalence between the game formulation and its dual

In this section we will show that the formulation of higher order interference theories in terms of winning probabilities of

the "modulo" games

˜

I

(d)

m,~ν,f

(k) =

1

d

m

d−1

X

x

1

,...,x

m

=0

P



b = f(s

(d)

~ν,~x

)|x

1

...x

m



−

1

d

= 0, ∀~ν, ∀f (55)

is equivalent to its dual formulation in terms of the dual interference terms

˜

J

(d)

m,~ν,b

=

1

d

m

X

~x

(ω

d

)

P

a

ν

a

x

a

P (b|~x) = 0, ∀~ν, ∀b ∈ {0, ..., d −1}, (56)

where ω

d

= e

i2π/d

is the d-th root of unity.

For convenience, let us ﬁrst introduce the dual terms with an added index α ∈ {1, ..., d −1}:

˜

J

(d)

m,~ν,b,α

≡

1

d

m

X

~x

(ω

d

)

α

P

a

ν

a

x

a

P (b|~x). (57)

We will show that for any dit-string ~ν, the following equivalence holds:

n

˜

I

(d)

m,~ν,f

= 0, ∀f

o

←→

n

˜

J

(d)

m,~ν,b,α

= 0, ∀b ∈ {0, ..., d − 1}, ∀α ∈ {1, ..., d − 1}

o

(58)

Since the order of interference is deﬁned as the vanishing of the interference terms (55) for all ~ν, (58) would imply that

the dual formulation of interference (56) is equivalent to the game formulation (55) (this is so because if the RHS of

equivalence (58) holds for all ~ν, then the dual conditions (56) also hold, since the index α becomes redundant). In what

follows, we will prove that (58) does hold indeed.

In order to simplify the notation, let us introduce the d × d matrix P, whose elements are deﬁned as

4

P

bs

=

1

d

m−1

X

~x

s

(d)

~ν,~x

=s

P (b|~x). (59)

4

Notice that the matrix P depends on the dit-string ~ν, but we do not write it explicitly in the notation in order to simplify the

expressions.

Accepted in Quantum 2021-02-15, click title to verify. Published under CC-BY 4.0. 15

The normalization of probabilities implies that P is a stochastic matrix, i.e.

X

b

P

bs

= 1, ∀s. (60)

The game formulation equations on the left side of the equivalence in (58) can be written as

1

d

m

d−1

X

x

1

,...,x

m

=0

P



b = f(s

(d)

~ν,~x

)|x

1

...x

m



=

1

d

, ∀f →

X

s

P

f(s)s

= 1, ∀f, (61)

which we rewrite succintly as

Tr[Π

f

P ] = 1, ∀f, (62)

where Π

f

≡

P

s

|f(s)ihs| ranges over all d-dimensional permutation matrices (the most general ﬁnite dimensional

reversible transformations are indeed permutations).

On the other hand, the dual conditions on the right side of equivalence (58) assume the following form

(P F )

lk

= δ

k,0

1

√

d

X

j

P

lj

, (63)

where F is the d-dimensional Fourier matrix with elements

(F )

lk

=

1

√

d

(ω

d

)

lk

. (64)

We will ﬁrst show that the dual conditions (63) imply the information-theoretic conditions (62). Assuming that the the

dual conditions (63) hold, we evaluate the trace

Tr[Π

f

P ] = Tr



F

†

Π

f

P F



=

X

kl

(F

†

Π

f

)

kl

(P F )

lk

=

X

l

(F

†

Π

f

)

0l

(P F )

l0

= 1, ∀f. (65)

The ﬁrst step follows from the unitarity of F and the ciclicity of the trace, the third step is due to the dual conditions (63),

and the last step follows from (F

†

Π

f

)

0l

= 1/

√

d. Therefore, conditions (63) imply (62).

In order to prove the converse statement, let us introduce the following new basis β = {|Ei, |e

1

i, ..., |e

d−1

i}, where |Ei

has the following form

|Ei = 1/

√

d(1, 1, ..., 1)

T

, (66)

and the remaining vectors span the orthogonal subspace (they can for instance be chosen as the rows/columns of the

Fourier matrix). The normalization conditions (60) can then be written as

hE|P = hE|, (67)

which implies that the matrix P in the new basis has the following form

P = |EihE|+

X

j

q

j

|e

j

ihE| +

¯

E, (68)

where q

j

are arbitrary complex numbers and

¯

E is a matrix that has support only on the subspace orthogonal to |Ei.

In the new basis β, all permutation matrices have the following form

Π

f

= |EihE| + ∆

f

, (69)

where ∆

f

is again a matrix with no support on |Ei. The latter follows from the fact that the representation of the

permutation group that we are using is reducible to the direct sum of a one-dimensional representation (spanned by the

vector |Ei which is invariant under all permutations) and a (d − 1)-dimensional irreducible representation (here given by

∆

f

). Assuming that the game-conditions (62) hold, we obtain the following

1 = Tr[Π

f

P ] = 1 + Tr



∆

f

¯

E



→ Tr



∆

f

¯

E



= 0, ∀f. (70)

Since the matrices ∆

f

provide an irreducible representation of the permutation group, the Burnside Theorem [35] implies

that they span the set of all (d −1)-dimensional matrices; therefore, Equation (70) implies that

¯

E is necessarily zero. The

matrix P is thus

P = |EihE|+

X

j

q

j

|e

j

ihE| = |qihE|, (71)

Accepted in Quantum 2021-02-15, click title to verify. Published under CC-BY 4.0. 16

where we introduced the vector |qi ≡ |Ei+

P

j

q

j

|e

j

i. Therefore, the sought matrix P F is

(P F )

kl

= hl|qihE|F |ki = δ

k,0

1

√

d

X

j

P

lj

, (72)

where we used

P

d−1

k=0

(ω

d

)

k

= 0 and {|ki; k = 0, ..., d − 1} are the original basis vectors. Hence, equivalence (58)

holds, and thus the game formulation (55) is equivalent to the dual formulation (56). Besides being an interesting

mathematical result, the exact equivalence between these two formulations will be useful for showing that any distribution

that exhibits at most m-th order interference can be written as a linear combination of functions with at most m inputs.

This will consequently be the necessary ingredient for proving that Local Tomography implies the additivity of the order

of interference under the composition of systems.

B Algebraic order for arbitrary d

In this Appendix we are going to extend the mathematical property of Section III to arbitrary d.

Let us consider the modulo games involving m boxes and assume that Alice uses a system of order n < m. In Appendix

A we showed that this is equivalent to the following constraints

˜

J

(d)

m,~ν,b

=

1

d

m

X

~x

(ω

d

)

P

j

ν

j

x

j

P (b|~x) = 0,

∀b ∈ {0, 1, ..., d −1}, ν

j

∈ {0, 1, ..., d −1}, s.t.

X

j

δ

ν

j

,0

< (m −n).

(73)

For compactness, we allow the dit string ~ν to range over all dit-strings with less than (m − n) null components. This

notation speciﬁes which interference terms the equation refers to: if ν

j

6= 0 for j = i

1

, ..., i

l

, the equation 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 (b|~x) as one component of a vector

~

P

b

in a d

m

-dimensional vector space formed by the tensor product of

m d-dimensional spaces, i.e. P (b|~x) =

N

m

i=1

~e

x

i

·

~

P

b

, where



~e

x

j

, x

j

= 0, ..., d −1



span the j-th d-dimensional space.

Equations (73) then imply:

˜

J

(d)

m,~ν,b

=

1

d

m

X

~x

(ω

d

)

P

j

ν

j

x

j

m

O

i=1

~e

x

i

·

~

P

b

=

1

d

m/2

m

O

i=1

~

f

ν

i

·

~

P

b

=

1

d

m/2

λ

~ν,b

= 0, (74)

where the rotated vectors (rows/columns of the d-dimensional Fourier matrix) are deﬁned as

~

f

ν

j

≡

1

√

d

d−1

X

x

j

=0

(ω

d

)

ν

j

x

j

~e

x

j

, (75)

and the coefﬁcients λ

~ν,b

are the components of the vector

~

P

b

in the corresponding basis. Equation (74) states that the

components λ

~ν,b

vanish for all ~ν with more than n non-zero components. The probabilities P (b|~x) can thus be expressed

as

P (b|~x) =

"

m

O

i=1

~e

x

i

#

·





X

~ν

λ

~ν,b

m

O

j=1

~

f

ν

j





=

1

d

m/2

X

ν

1

,...,ν

m

P

j

δ

ν

j

,0

≥(m−n)

(ω

d

)

P

j

ν

j

x

j

λ

~ν,b

, (76)

where we used ~e

x

i

·

~

f

ν

i

=

1

√

d

(ω

d

)

ν

i

x

i

. Since the sum runs only over strings ν with at most n non-zero components,

P (b|~x) can be written as a function of at most n inputs, for every b.

Therefore we have proved that the n-th order interference dual conditions (73), or equivalently, the information-theoretic

formulation (5), provide a set of necessary and sufﬁcient conditions for a distribution to be decomposable into a linear

combination of at most n inputs. Hence, the algebraic order of the distribution P (b|~x) is at most n.

C Proof of Equation (34)

In this Appendix we will show that equations

X

~x

(ω

d

)

α

P

k

ν

k

x

k

ρ

~x

= 0, ∀α ∈ {1, ..., d − 1} (77)

Accepted in Quantum 2021-02-15, click title to verify. Published under CC-BY 4.0. 17

imply the following relations

ρ

(S)

= ρ

(S

0

)

, ∀S, S

0

= 0, ..., d −1, (78)

where ρ

(S)

is deﬁned as

ρ

(S)

≡

1

d

m−1

X

x

1

,...,x

m

(

P

k

ν

k

x

k

)mod d=S

ρ

~x

. (79)

For a start, Equations (77) can be written as

d−1

X

S=0

(ω

d

)

αS

ρ

(S)

= 0, ∀α ∈ {1, ..., d − 1}. (80)

Next, if we introduce the vector ~ρ = (ρ

(0)

, ρ

(1)

, ..., ρ

(d−1)

)

T

, the latter equations can be cast in the following form

F ~ρ =

√

d¯ρ(1, 0, ..., 0)

T

, (81)

where F

kl

= 1/

√

d(ω

d

)

kl

is the d-dimensional Fourier matrix and ¯ρ = 1/d

P

S

ρ

(S)

. Taking the inverse of Equation 81

(i.e. applying F

†

from the left) we obtain

~ρ = ¯ρ(1, 1, ..., 1)

T

, (82)

which is equivalent to

ρ

(S)

= ρ

(S

0

)

= ¯ρ, ∀S, S

0

= 0, ..., d −1. (83)

D Details of the proof of additivity in quantum theory

Here we will write explicitly the expressions for the transformations invoked in the proof of the additivity of interference

under composition in quantum theory (Section 2.2). We will denote the “control” degree of freedom of j-th system with

H

(c

j

)

(the control is simply the path degree of freedom), and its “internal” degree of freedom with H

(int

j

)

. The total

Hilbert space H of the k systems is a tensor product of the single-system Hilbert spaces, i.e.

H = H

(c)

⊗ H

(int)

, (84)

where H

(c)

≡

N

k

j=1

H

(c

j

)

is the composite of the control/path degrees of freedom, and H

(int)

≡

N

k

j=1

H

(int

j

)

is the

composite of the internal degrees of freedom.

Analogously to the single-system case, we introduce the following set of Kraus operators that act on the composite internal

Hilbert space H

(int)

:

(

B

(s)

i

(x

i

1

, ..., x

i

k

),

X

s

B

(s)†

i

(x

i

1

, ..., x

i

k

)B

(s)

i

(x

i

1

, ..., x

i

k

) ≤ 1

)

, (85)

where i stands for i

1

, ..., i

k

, and 1 is the identity operator on H

(int)

. We do not impose any further restrictions on the

latter operators, thereby including also operations that entangle the internal degrees of freedom of the subsystems. The

total transformation implemented by the boxes for a given set of inputs ~x will be represented with the following Kraus

operators that act on the total Hilbert space H:

(

M

(s)

~x

=

X

i

k

O

p=1

|n

(p)

i

p

ihn

(p)

i

p

| ⊗ B

(s)

i

(x

i

1

, ..., x

i

k

)

, (86)

where

n

|n

(p)

i

p

i, ∀i

p

= 1, ..., m

o

forms a basis of the control-space of p-th system H

(c

p

)

.

Let us now suppose that the total system is prepared in the following state

ρ

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

, (87)

where i is short for i

1

, ..., i

k

(and analogously for the other indices), and vectors

n

|φ

(p)

r

p

i, ∀r

p

o

span the internal space of

p-th system H

(int

p

)

.

The boxes then act on the system as follows:

ρ

~x

=

X

s

M

(s)

~x

ρ

0

M

(s)†

~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

), (88)

Accepted in Quantum 2021-02-15, click title to verify. Published under CC-BY 4.0. 18

where

C

ij

(x

i

1

, x

j

1

, ..., x

i

k

, x

j

k

) =

X

s,r,l

c

ijrl

B

(s)

i

(x

i

1

, ..., x

i

k

)

k

O

p=1

|φ

(p)

r

p

ihφ

(p)

l

p

|

!

B

(s)†

j

(x

j

1

, ..., x

j

k

). (89)

As stated in Section 2.2, this implies that k quantum systems constitute a 2k-th order system, since the probability

distributions P(b|~x) arising from processes involving k systems will necessarily be at most of algebraic order 2k.

E A lower bound on interference of generic composite systems

In this Appendix we are going to show that two systems, labelled by (A, B) and respectively of single-system orders

(n

A

, n

B

), can be used to achieve (n

A

+ n

B

)-th order interference.

By deﬁnition, there exist two processes involving single-systems A and B that can win the modulo games with n

A

and

n

B

boxes with some probabilities q

A

> 1/d and q

B

> 1/d. For concreteness, suppose that Alice and Bob play the

modulo game for the unit dit-string ν

i

= 1, ∀i, with (n

A

+ n

B

) boxes, i.e. Bob is supposed to output s

(d)

~x

= (

P

j

x

j

)mod

d. The proof for any other ~ν is completely analogous. The protocol proceeds as follows. Alice sends system A to the

ﬁrst n

A

boxes (i.e. containing inputs {x

1

, ..., x

n

A

}) and system B through the other n

B

boxes (which encode inputs

{x

n

A

+1

, ..., x

n

A

+n

B

}). Upon receiving the systems, Bob performs two separate measurements with outcomes b

(A)

and

b

(B)

and produces a ﬁnal output b =



b

(A)

+ b

(B)



mod d. Here the two systems are treated completely independently:

the only “mixing” between them happens in the ﬁnal step, since Bob’s output depends on both systems’ processes. The

(n

A

+ n

B

)-th order interference term is then

˜

I

(d)

n

A

+n

B

=

1

d

n

A

+n

B

X

x

1

,...x

n

A

+n

B

P



b = s

(d)

~x

|~x



−

1

d

=

1

d

n

A

+n

B

X

x

1

,...x

n

A

+n

B

X

l

P



b

(A)

l

, b

(B)

l

|~x



−

1

d

,

(90)

where the sum runs over all two-outcome measurements which produce the correct modulo, i.e.



b

(A)

l

+ b

(B)

l



mod d =



P

j=1

x

j



mod d. Intuitively, Bob can produce the correct overall modulo, even if he measures wrong single-system

moduli: e.g. for d = 2, if Bob’s single-system outcomes are s

A

⊕1 and s

B

⊕1, where s

A

and s

B

are the correct parities,

he will still produce the correct overall parity, since (s

A

⊕1) ⊕(s

B

⊕1) = s

A

⊕s

B

. Indeed, for arbitrary d, there are in

total (d − 1) wrong single-system outcomes which provide the correct overall output. The interference term is thus

˜

I

(d)

n

A

+n

B

= q

A

q

B

+

d−1

X

i=1

p

(A)

i

p

(B)

d−i

−

1

d

, (91)

where q

A

and q

B

are average winning probabilities for the two systems, while the distribution averages over wrong

outcomes are deﬁned as

p

(A)

i

≡

1

d

n

A

X

x

1

,...,x

n

A

P

(A)



b

(A)

= (s

(d)

~x

+ i)mod d|~x



, (92)

and analogously for system B. Next, we deﬁne weights α

j

and β

j

in the following way

p

(A)

i

= (1 − q

A

)α

i

,

p

(B)

d−i

= (1 − q

B

)β

i

,

(93)

which implies

P

j

α

j

=

P

j

β

j

= 1

5

. Plugging expressions (93) into the interference term we obtain

˜

I

(d)

n

A

+n

B

= q

A

q

B

+ (1 −q

A

)(1 − q

B

)λ −

1

d

, λ ≡

X

j

α

j

β

j

. (94)

By a straightforward application of the method of Lagrange multipliers with constraints

P

j

α

j

= 1 and

P

j

β

j

= 1, one

obtains that the minimum value of λ is

1

d−1

(which is achieved for uniform α

j

, β

j

). Therefore the following inequality

holds:

˜

I

(d)

n

A

+n

B

≥ q

A

q

B

+

1

d − 1

(1 − q

A

)(1 − q

B

) −

1

d

. (95)

The RHS of the latter inequality is equal to zero for q

A

= q

B

= 1/d and is monotonically increasing for q

A

> 1/d, q

B

>

1/d. Thus we constructed a process such that, if the two systems exhibit n

A

-th and n

B

-th order interference, the composite

5

In order for the coeﬃcients α

i

and β

i

to be well deﬁned, we assume that q

A

6= 1 and q

B

6= 1. In the case that either q

A

or

q

B

(or both) are equal to 1, the ﬁrst term in (91) is q

A

q

B

> 1/d, while the second term is non-negative, which makes the overall

interference term positive.

Accepted in Quantum 2021-02-15, click title to verify. Published under CC-BY 4.0. 19

system exhibits (n

A

+ n

B

)-th order interference.

Using the same reasoning, the discussion can be generalized to an arbitrary number of systems, since systems can be

composed two-by-two. Therefore, by the same construction, k systems of orders {n

1

, ..., n

k

} can produce (

P

k

i=1

n

i

)-th

order interference.

Accepted in Quantum 2021-02-15, click title to verify. Published under CC-BY 4.0. 20

Comments

Products

Project