Interference as an information-theoretic game
Sebastian Horvat Borivoje Dakić
quant-ph



sebastian.horvat@univie.ac.at
University of Vienna, Faculty of Physics, Vienna Center for Quantum Science and Technology, Boltzmanngasse 5, 1090 Vienna, Austria

borivoje.dakic@univie.ac.at
University of Vienna, Faculty of Physics, Vienna Center for Quantum Science and Technology, Boltzmanngasse 5, 1090 Vienna, Austria
Institute for Quantum Optics and Quantum Information (IQOQI), Austrian Academy of
Sciences, Vienna, Austria



The double slit experiment provides a clear demarcation 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 theories. The tasks involve two parties and communication between them with the goal of winning certain parity games. We show that the order of interference is in one-to-one correspondence with the parity order of these games. Furthermore, we prove the order of interference to be additive under composition of systems both in classical and quantum theory. 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 formulation within the generalized probabilistic framework and prove that tomographic locality implies the additivity of the order of interference under composition. These results shed light on the operational meaning of the order of interference and can be important for the identification of the information-theoretic principles behind second-order interference in quantum theory.   




Interference as an information-theoretic game
    Borivoje Dakić
    17 February 2021
=============================================










§ INTRODUCTION



As Richard Feynman famously put it, “the double slit experiment is absolutely impossible to explain in any classical way and has in it the heart of quantum mechanics. In reality, it contains the only mystery” <cit.>. 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 <cit.> 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 combination of double-slit interferences. The latter served as a motivation for introducing higher-order interference theories which are defined with respect to the order of interference produced in generalized multi-slit experiments <cit.>. Such theories are usually formulated within the framework of generalized probabilistic theories (GPT-s) <cit.>, with quantum theory being only a particular example. This further motivated the search for a set of intuitive physical principles which could explain why experiments should exhibit at most second-order interference <cit.>.

In this work we study higher-order interference from the information-theoretic perspective. Firstly, we reconsider the definitions of multi-slit experiments and Sorkin's classification and notice that: (a) the framework is defined only for single particles (or single systems), (b) the interference order is defined with respect to simple operations of blocking/opening the slits, and (c) the (final) measurement refers exclusively to intensity measurements (average number of particles at a particular location on the screen). We proceed by generalizing this setting to an arbitrary number of particles (systems), arbitrary set of (local) operations and arbitrary final measurements.
The framework for higher-order interference is formulated as an information-theoretic game where we analyze generic scenarios involving classical and quantum systems. Our generalization involves many particles (systems) and their ability to win certain parity games. The order of these games and their winning probabilities are directly related to the order of interference (in Sorkin's classification) and to the number of systems involved. This generalization offers a shift in the perspective: higher order interference theories are not defined by which phenomena are allowed (e.g. by the structure of interference patterns), but by which tasks can or cannot be accomplished within the theory (i.e. their information-processing capacity). Furthermore, our study provides a direct relation between the order of interference and number of systems used in the protocol, and can thus provide a (semi) device-independent way of witnessing the number of particles (systems) present in the process.

In the final section we provide the information-theoretic formulation within the GPT formalism and we study how the order of interference behaves under the composition of systems. We construct a lower bound on the interference order which is additive under composition. In classical and quantum theory, this lower bound coincides with the upper bound, which in turn shows an interesting connection between the order of interference and the composition law. Finally, motivated by the latter, we prove that in generic local-tomographic theories <cit.> the order of interference is indeed additive (under certain additional assumptions that we deem reasonable).

Together with an information-theoretic perspective, our findings can be seen in light of paving an alternative way towards understanding the physical principles behind the order of interference of quantum theory: we suspect that an important clue might be provided by the composition of systems and by the tensor-product structure. The latter would thus contribute to the operational and physical understanding of quantum theory <cit.> 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 <cit.>, information speed <cit.>, quantum acausal processes <cit.>, superposition of orders <cit.> and directions <cit.>, quantum combs <cit.>, quantum switch <cit.> and quantum causal models <cit.>.
  



§ INFORMATION-THEORETIC FORMULATION: PARITY GAMES

In the standard double-slit experiment a particle is sent on a plate pierced by two parallel slits. After passing through the plate, the particle can be detected on a screen. Each slit can be either open (which we denote with 0), or blocked (which we denote with 1). The figure of merit is the interference term 

    I_2=P_00-P_10-P_01+P_11,

where P_x_1x_2 denotes the probability of detecting the particle 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 quantum theory allows the particle to be in spatial superposition, 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 <ref>. 

Let us suppose that the slits are in a certain state (i.e. each slit is either open or blocked) which is completely unknown both to Alice and to Bob; we can thus imagine that an external party (e.g. a referee) has control of the slits and decides whether to block them or not. Moreover, Alice possesses a single particle that she can send towards Bob. On the other side, Bob receives (or not) the particle, performs an arbitrary measurement and outputs a bit b∈{0,1}. We introduce the redefined second order interference term as follows

    Ĩ_2   =1/4[P(0|11)-P(0|10)-P(0|01)+P(0|00)]=
       =1/4∑_x_1,x_2=0^1 P(b=x_1⊕ x_2|x_1x_2)-1/2,

where P(b|x_1x_2) is the probability that Bob outputs b given that the two slits are in states x_1 and x_2. Notice that the term corresponding to both slits being closed can now be non-zero, since Bob's measurement is arbitrary, i.e. does not necessarily refer to measuring the probability of the particle inflicting on a point of the screen (intensity measurement). The probability P(b|x_1x_2) is thus a generalization of P_x_1x_2 from (<ref>) and reduces to the latter only in the case in which Bob performs the intensity measurement. The redefined interference term Ĩ_2 measures the probability of successfully accomplishing the following task (parity game):
 
(a) in each run, the slits are set in some state {x_1,x_2} unknown 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 complete 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 (<ref>) is formulated in a device-independent way <cit.>, relating only inputs and outputs, without any mention of their underlying physical realization. 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 interference experiments), we can generalize her resources to an 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 accessed 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 <ref>. The figure of merit is thus 

    Ĩ_m(k)=1/2^m∑_x_1,...,x_m=0^1 P(b=s_x⃗|x_1...x_m)-1/2,
 
where {x_1,...,x_m} are input bits encoded in the m boxes and s_x⃗≡⊕_i=1^mx_i is the overall parity. In the case in which Alice is constrained to sending only single particles, the boxes are implemented as slits and Bob's final operation consists of intensity measurements, the generalized higher-order interference term Ĩ_m(k) reduces to the standard higher-order term defined in <cit.> (up to normalization):

    I_m= ∑_x_1,...,x_m=0^1 (-1)^∑_j x_j P_x⃗,
 
where x_j=0(1) corresponds to j-th slit being open(closed) and P_x⃗ is the probability of detecting the particle on the screen given that the slits are in state x⃗.

Juxtaposed to the standard definition of m-th order interference theories involving the structure of interference patterns produced by single particles in m-slit experiments, our information-theoretic extension provides a definition in terms of the probability of winning the parity game involving m boxes by using a finite amount of resources. In addition, the latter formulation enables an analysis of the relation of the order of interference and the number of systems 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 characterization 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. Ĩ_m=n(k)(k)≠ 0 and Ĩ_m>n(k)(k)=0.


To recapitulate, the modified multi-slit experiment consists of the following generalizations: (a) instead of one particle, Alice can possess arbitrarily many particles/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 encoded by the boxes.

Finally, we can generalize the input bits {x_1...,x_m} to 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_x⃗,^(d)≡ (∑_i=1^m_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 

    Ĩ_m,,f^(d)(k)=1/d^m∑_x_1,...,x_m=0^d-1 P(b=f(s_,x⃗^(d))|x_1...x_m)-1/d,

which are defined for all reversible functions f that map dits into dits. Operationally, these functions take into account 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. (<ref>) introduces only a minus sign. The games defined in (<ref>) offer a definition of higher order interference theories for arbitrary prime d. 
definition

We define n(k)-theories as theories that satisfy the following two properties:
 
(i) all processes produce Ĩ_m>n(k),,f^(d)(k)=0 for all reversible 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 Ĩ_m=n(k),,f^(d)(k)≠ 0, for at least one dit-string  with components _i ∈{1...,d-1}.
 
Notice that the (non)existence of the required process for a specific outputs' labelling fixed by f implies the (non)existence of the analogous process for any other labelling f' (since Bob can always relabel his outcomes independently of the process). Therefore, throughout this manuscript, we will only construct proofs of existence of processes which exhibit Ĩ_m=n(k),,f^(d)(k)≠ 0 for f fixed to be the identity map (i.e. no final relabelling) and we will thereby omit the index f. Moreover, whenever we omit the index , we refer to the unit dit-string, i.e. _i=1, ∀ i. Therefore, the term Ĩ_m^(d)(k) will correspond to the specific game in which Bob's goal is to output s_x⃗=(∑_i x_i)mod d. We acknowledge that the additional games specified by the labels  and f may at the moment seem redundant; however, we will need to take them into account in the proofs regarding higher-order interference and we will thus keep them in the definition of n(k)-theories. As we will show later, all conclusions regarding the order of interference 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⃗=(∑_i x_i)mod d is completely 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 Ĩ_m,,f^(d)(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 inputs. 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 knowing 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 definitions 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 classical and quantum theory and investigate their power to win the parity games. We will show that the order of interference n(k) satisfies the relation

    n(k)=kn(1),

where n(1) is the order of single-system interference (for classical theory, n(1)=1, while for quantum theory, n(1)=2) and n(k) is the interference order achievable using k systems. Moreover, we will show that this relation holds in generic GPT-s that satisfy the local tomography principle and certain additional assumptions.

Before proceeding further, we will first show an important mathematical property that relates the order of interference to the algebraic order of the probability distributions P(b|x⃗).



§ 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 algebraic order of P(b|x⃗) is at most n. Here we will consider the d=2 case, while the general case is addressed in Appendix <ref>.

Let us consider the parity game involving m boxes and assume that Alice uses one system of order n<m. By definition, this means that the interference terms (<ref>) vanish for all parity games involving more than n boxes, which can be written in a concise form as follows:

    Ĩ_m,σ⃗^(2)=1/2^m∑_x⃗(-1)^∑_j σ_j x_jP(0|x⃗)=0,
       ∀σ_j∈{0,1 },   s.t.  ∑_j σ_j>n.

For compactness, we introduced the m-component bit string σ⃗, that specifies which interference term the latter equation refers to: if σ_j=1 for j=i_1,...,i_l, the 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(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 (<ref>) then imply that for all ∑_j σ_j>n:

    Ĩ_m,σ⃗^(2)(k=1)   =1/2^m∑_x⃗(-1)^∑_j σ_j x_je⃗_x_1⊗...⊗e⃗_x_m·P⃗=
       =1/2^m/2f⃗_σ_1⊗...⊗f⃗_σ_m·P⃗=1/2^m/2λ_σ⃗=0,

where we introduced the rotated vectors

    f⃗_σ_j≡1/√(2)(e⃗_0+(-1)^σ_je⃗_1 ).
  
The terms λ_σ⃗ are components of vector P⃗ in the new basis spanned by the rotated vectors f⃗_σ_j. Equation (<ref>) then states that the components λ_σ⃗ are zero if ∑_j σ_j>n. The probabilities P(0|x⃗) can thus be expressed as

    P(0|x⃗)   =[⊗_i=1^me⃗_x_i] ·[∑_σ⃗λ_σ⃗⊗_j=1^mf⃗_σ_j]=
       =1/2^m/2∑_σ_1,...,σ_m 
    ∑_jσ_j≤ n(-1)^∑_j σ_j x_jλ_σ⃗,

where we used e⃗_x_i·f⃗_σ_i=2^-1/2(-1)^σ_ix_i. Therefore, P(0|x⃗) is a linear combination of functions of at most n different inputs:

    P(0|x⃗)=∑_l=1^n∑_i_1,...,i_l c^(l)_i_1,...,i_lg^(l)(x_i_1,...,x_i_l),

where we introduced the functions 

    g^(l)(x_i_1,...,x_i_l)=(-1)^∑_a=1^l x_i_a,

and the coefficients 

    c^(l)_i_1,...,i_l=1/2^m/2λ⃗_σ⃗^(l)_(i_1,...,i_l),   (σ⃗^(l)_(i_1,...,i_l))_s=∑_r=1^lδ_s,i_r.

Next, in order to tackle the problem for arbitrary d, for each set of generalized interference terms {Ĩ^(d)_m,,f, ∀, f} we introduce its dual terms {J̃^(d)_m,,α,b, ∀; ∀ b ∈{0,...,d-1}} as 

    J̃^(d)_m,,b=1/d^m∑_x⃗(ω_d)^∑_a  _a x_a P(b|x⃗),

where ω_d=e^i2π/d is the d-th root of unity. For the d=2 case, the dual terms coincide with the ones defined in terms of the game formulation (<ref>); however, this is not the case for d>2. Nevertheless, in Appendix <ref> we show that the generalized interference term Ĩ^(d)_m,,f from (<ref>) 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 interference by analysing the behaviour of its dual, which can often be more tractable. Indeed, by this method we show in Appendix <ref> that the conclusion derived in (<ref>) 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.   



§ 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 <ref>, 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 experiment, 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) labelled by x_1 and x_2. If the particle is classical, i.e. has a definite trajectory, Bob's output can in each run depend on the state of at most one box. The conditional probabilities describing the process can thus be decomposed as follows:

    P(b|x_1x_2)=q_1 P_1(b|x_1)+ q_2 P_2(b|x_2),

where q_i is the probability of Alice sending the particle through i-th box and P_i(b|x_i) is the conditional probability of Bob outputting b given that the particle was sent through i-th box. The modified interference term therefore vanishes:

    Ĩ_2^(2)(k=1)   =1/4∑_x_1,x_2=0^1P(b=x_1 ⊕ x_2|x_1x_2)-1/2
       =1/4∑_x_1,x_2=0^1 (-1)^x_1+x_2P(0|x_1x_2)=0.

Intuitively, the knowledge about the state of one box does not increase the probability of correctly guessing the inputs' parity with respect to a random guess. The same reasoning holds for arbitrary prime d, implying that Ĩ_2^(d)(k=1)=0 for one classical particle.
 
Multiple systems. Now, what if Alice possesses two classical particles? Let us for the moment assume that the boxes are implemented by slits (as in the original double-slit experiment) and that Alice in each run sends deterministically one particle towards the first slit and the other towards 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 perfectly accomplish the required task, thereby generating Ĩ_2^(2)(k=2)=1/2. On the other hand, the standard interference definition (<ref>) remains null also for two particles, since the average number of particles received by Bob (or inflicted on the screen) is equal to 1 regardless of the inputs' parity. This shows the difference between the standard formulation and our game formulation, as the latter 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 localized 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 Ĩ_m^(d)(k)=0, while if k≥ m, he can in principle deterministically accomplish the required task and thus generate Ĩ_m^(d)(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 Ĩ_m,,f^(d) (as already noted, this reasoning would not be valid if d was not a prime number).

Therefore, classical theory satisfies n(k)=k, meaning that k classical systems can exhibit at most k-th order interference.



§ QUANTUM RESOURCES

Contrasted to classical mechanics, quantum theory allows spatial superpositions of physical objects, which can generate a non-zero interference term I_2, even with a single particle. On the other hand, higher order interference terms I_j>2 defined in multi-slit experiments remain null even in quantum theory (see for instance <cit.>). In this section we show that analogous statements hold for the generalized interference terms Ĩ_m,,f^(d)(k=1) and provide an extension to more particles (systems). Let us first look into the simplest case, i.e. one particle and two boxes.



 §.§ 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 implement binary inputs x_1,x_2. The quantum state is given by

    |ψ⟩_0=1/√(2)( |1⟩+|2⟩),
 
where |1⟩ and |2⟩ are 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

    |ψ⟩_x_1,x_2=1/√(2)( e^ix_1π|1⟩+e^ix_2π|2⟩).

Therefore, Bob receives the particle in the following states (up to global phases) 

    |ψ⟩=1/√(2)( |1⟩+|2⟩),    if x_1⊕ x_2=0,
    1/√(2)( |1⟩-|2⟩),    if x_1⊕ x_2=1,

which are orthogonal and thus perfectly distinguishable, thereby enabling Bob to deterministically decode the parity x_1⊕ x_2 and to produce Ĩ_2^(2)(k=1)=1/2.

The previous result holds for binary inputs; now suppose that the parties are playing the modulo game (<ref>) specified by dit string =(_1,_2), i.e. Bob's goal is to output s_x⃗,^(d)=(_1 x_1+_2 x_2) mod  d (we assume there is no final relabelling, i.e. that f is the identity; as we already argued, all other cases follow automatically). The players can employ the following strategy.

As in the binary case, let Alice prepare her particle in the state 

    |ψ⟩_0=1/√(2)( |1⟩+|2⟩),
 
where |1⟩ and |2⟩ are states corresponding to the two paths, and let the boxes apply local phase shifts as follows

    |ψ⟩_x_1,x_2   =1/√(2)( ω_d^-_1 x_1|1⟩+ω_d^_2 x_2|2⟩)
       =1/√(2)( |1⟩+(ω_d)^s_x⃗,^(d)|2⟩),

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

    Ĩ_2,^(d)   =1/d^2∑_x_1x_2P(b=s_x⃗,|x_1x_2)-1/d
       =1/d∑_s(Π_s ρ^(s))-1/d,

where

    ρ^(s)≡1/d∑_x_1,x_2 
     s_x⃗,^(d)=sρ_x⃗,

and ρ_x⃗=|ψ⟩_x_1,x_2⟨ψ|.

Let us choose Bob's POVM to be a “pretty good measurement” <cit.>, which in our case reduces to a set of projectors up to normalization, i.e.

    Π_s=αρ^(s),

where α is a normalization constant. The latter can be easily calculated by requiring ∑_s Π_s=1, thereby obtaining α=2/d.

The interference term is then

    Ĩ_2,^(d)= 1/d∑_s( 2/dρ^(s)ρ^(s))-1/d=1/d>0.

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 protocols.


 §.§ 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.



  §.§.§ Single systems
 
For a start, let us fix the resources to one quantum system, without restricting its internal degrees of freedom. The resource 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 sophisticated 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=∑_i,j,k,l c_ijkl|i⟩⟨j|⊗|ϕ_k⟩⟨ϕ_l|,

where {|i⟩, i=1,...,m} denote states representing defined paths directed towards the m boxes, while {|ϕ_k⟩} 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 representing the action of the i-th box with

    {B_i^(k)(x_i),   ∑_k B_i^(k)†(x_i)B_i^(k)(x_i)≤1},
 
where the operators B_i^(k)(x_i) act on the internal Hilbert space of the system. Notice that we allow the transformations 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⃗=∑_i=1^m|i⟩⟨i|⊗ B_i^(k)(x_i)}.

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 configuration of inputs there is only one Kraus operator, i.e.

    M_x⃗=∑_i=1^m|i⟩⟨i|⊗ U_i(x_i),

where U_i(x_i) are unitary operators. Let us now inspect how the general CP-maps in (<ref>) act on the input state (<ref>). After passing through the boxes, the state of the system is

    ρ_x⃗=∑_k M^(k)_x⃗ρ_0 M^(k)†_x⃗=∑_i,j|i⟩⟨j|⊗ C_ij(x_i,x_j),

where, in order to simplify the expression, we introduced the following operators

    C_ij(x_i,x_j)≡∑_knmc_ijnm B_i^(k)(x_i)|ϕ_n⟩⟨ϕ_m|B_j^(k)†(x_j).

Next, let us suppose that Alice and Bob are playing the modulo game (<ref>) specified by a dit-string  and with no final relabelling (all other cases follow automatically). Notice that for m>2 and for any α∈{1,...,d-1}, the following property holds

    ∑_x⃗ (ω_d)^α∑_k _k x_kρ_x⃗=
       = ∑_i,j|i⟩⟨j|⊗∑_x⃗ (ω_d)^α∑_k  _k x_k C_ij(x_i,x_j)=0,

where ω_d≡ e^i2π/d. This is so because the tensors C_ij depend on at most two inputs and because ∑_x_k=0^d-1 (ω_d)^α_k x_k=0.

Let us define the average taken over states with equal modulo as follows

    ρ^(S)≡1/d^m-1∑_x_1,...,x_m 
     (∑_k _k x_k)mod d=Sρ_x⃗.

As we show in Appendix <ref>, equations (<ref>) then imply

    ρ^(S)=ρ^(S')≡ρ̅,   ∀ S,S'=0,...,d-1.

Since all average states ρ^(S) are equal, Bob cannot distinguish 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 specified by the dit-string  necessarily vanishes for m>2: 

    Ĩ_m>2,^(d)(k=1)   =1/d [∑_S Π_S ρ^(S)] - 1/d 
       =  1/d [ 1ρ̅] -1/d = 0.

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 (<ref>), 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 <cit.>.



  §.§.§ 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 described by the tensor product of the single-system Hilbert spaces. The most general state prepared by Alice is then

    ρ_0=∑_𝐢,𝐣,𝐫,𝐥 c_𝐢𝐣𝐫𝐥⊗_p=1^k[|n^(p)_i_p⟩⟨n^(p)_j_p|⊗|ϕ^(p)_r_p⟩⟨ϕ^(p)_l_p|],

where 𝐢 is short for (i_1,...,i_k) and analogously for the other indices. The vectors {|n^(p)_i_p⟩, ∀ i_p=1,...,m} span the spatial Hilbert space of the p-th system, while {|ϕ^(p)_r_p⟩, ∀ r_p} span its internal degrees of freedom (the dimensionality of which is arbitrary).

After passing through the boxes, the state is transformed to

    ρ_x⃗=∑_𝐢,𝐣⊗_p=1^k[|n^(p)_i_p⟩⟨n^(p)_j_p|]⊗ C_𝐢𝐣(x_i_1,x_j_1,...,x_i_k,x_j_k),

where { C_𝐢𝐣} are operators depending on at most 2k inputs (defined in the same fashion as in the single-system case, see Eq. (<ref>)). 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 <ref> for details). The crucial difference with respect to the single system case is that the expressions (<ref>) are now valid only if m>2k. Analogously to the single-system case, one comes to the following conclusion

    Ĩ_m>2k,^(d)(k)=0.

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 protocol described in Section <ref>; Bob can thus perfectly decode 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 <ref> we derive a general result which shows that k generic systems of single-system orders {n_1,...,n_k} can produce (∑_i=1^k n_i)-th order interference, for any d≥2 (this statement is independent of the underlying physical theory). Therefore, k quantum systems (i.e. systems of order two) can produce 2k-th order interference.

According to our classification, the latter results imply that quantum theory satisfies n(k)=2k, meaning that k quantum systems can produce at most 2k-th order interference[Notice that the same result holds also for indistinguishable 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 interference cannot be higher than the one achievable by indistinguishable systems, since further constraints are imposed on the allowed states and transformations. Moreover, the additivity of the lower bound proved in Appendix <ref> holds for any systems, including also indistinguishable quantum systems. This implies that all quantum systems satisfy n(k)=2k.].

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 underlying mechanism obeys quantum theory and that the particle number is well defined (the latter assumption can be violated if the resources consist of e.g. coherent states of light). Additionally, even though the boxes' operations can be mutually spacelike separated (and therefore the boxes cannot mutually signal their local inputs to each other), each box's operation must still be timelike separated from Bob (since the systems must in the end be sent from the boxes towards Bob). Thus, one cannot exclude the possibility that a box signals its local input towards Bob by sending some additional system, which had not been previously 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 <cit.>.

Classical theory revisited. Even though we already showed that classical theory satisfies n(k)=k in Section <ref>, here we want to briefly explicate how the latter can be seen by treating  classical theory as a special case of quantum theory. We simply need to restrict the one-particle-states sent by Alice to be block diagonal in the spatial basis, and the multi-particle-states to be block-diagonal in the configuration space basis. The internal degrees 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=∑_𝐢,𝐫,𝐥 c_𝐢𝐫𝐥⊗_p=1^k[|n^(p)_i_p⟩⟨n^(p)_i_p|⊗|ϕ^(p)_r_p⟩⟨ϕ^(p)_l_p|],

where the notation is the same as before. Analogously to the quantum case, the transformed state is 

    ρ_x⃗=∑_𝐢⊗_p=1^k[|n^(p)_i_p⟩⟨n^(p)_i_p|]⊗ C_𝐢(x_i_1,...,x_i_k),

where C_𝐢(x_i_1,...,x_i_k) are tensors as the ones defined in the quantum case. Since the transformed state is a linear combination of terms, each of which depends on at most k inputs, we recover the result that classical theory (i.e. quantum theory with no spatial coherence) satisfies n(k)=k.



§ HIGHER-ORDER INTERFERENCE THEORIES



 §.§ Independent operations

In Appendix <ref> we constructed a proof that k generic systems of orders {n_1,...,n_k} can exhibit ∑_in_i-th order interference, 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 <cit.>; 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 probabilistic theories (GPTs) <cit.>, and suppose that Alice possesses k systems. The state space of the j-th system is a convex set that will be denoted with St(A_j), and we regard 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  <cit.>, which states that the state of a composite system can be fully characterized by measurements performed separately on each subsystem. Under this assumption, the composite 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 mentioned above, in this subsection we will assume that the boxes act independently on the subsystems; we will discuss 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 ∑_in_i-th order interference. Together with the lower bound derived in Appendix <ref>, this will imply that k systems of orders {n_1,...,n_k} constitute a ∑_in_i-th order system. Let us first focus on binary inputs, i.e. d=2.
 
An arbitrary state s⃗∈ St(A) prepared by Alice can be written as a linear combination of the tensor product of single system states: s⃗=∑_𝐢 a_𝐢s⃗^(1)_i_1⊗...⊗s⃗^(k)_i_k, where 𝐢 is short for i_1,...,i_k, and a_𝐢 are real coefficients. The same holds for an arbitrary effect f⃗∈ Eff(A) representing Bob's final measurement, i.e. f⃗=∑_𝐢 b_𝐢f⃗^(1)_i_1⊗...⊗f⃗^(k)_i_k. Since we consider only single-system operations, the overall transformation of the boxes on the composite system is given by T_x⃗=T_x⃗^(1)⊗...⊗ T_x⃗^(k), where T_x⃗^(j)∈ 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:


    Ĩ_m^(2)(k)=1/2^m∑_x⃗(-1)^∑_a x_aP(0|x⃗)
       =1/2^m∑_𝐢,𝐣a_𝐢b_𝐣∑_x⃗(-1)^∑_a x_a[⊗_p=1^kf⃗^(p)_j_p] ·[⊗_p'=1^kT^(p')_x⃗s⃗_i_p'^(p')]
       =1/2^m∑_𝐢,𝐣a_𝐢b_𝐣∑_x⃗(-1)^∑_a x_a∏_p=1^kP^(p)_x⃗,


where P^(p)_x⃗≡f⃗^(p)_j_p· T^(p)_x⃗s⃗_i_p^(p) are probabilities arising from the single system processes involving p-th system (for simplicity we omitted indices 𝐢,𝐣). 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 <ref>, the probability distribution pertaining 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⃗=∑_i_1,...,i_n_p c^(p)_i_1,...,i_n_pf^(p)(x_i_1,...,x_i_n_p).

Therefore, if N≡∑_p n_p<m, the interference term necessarily vanishes:

    Ĩ_m^(2)(k)=∑_i_1,...,i_Na_i_1,...,i_N∑_x⃗ (-1)^∑_a x_ag(x_i_1,...,x_i_N)=0,

where we introduced for simplicity the coefficients a_i_1,...,i_N and functions g(x_i_1,...,x_i_N), the exact forms of which are of no relevance.

In order to show that the latter results holds for arbitrary prime d, we just need to take a look at the dual interference terms defined in Section <ref>. Given our assumptions, one arrives to the generalization of (<ref>):

    J̃_m,,b^(d)(k)=1/d^m∑_𝐢,𝐣a_𝐢b_𝐣∑_x⃗(ω_d)^∑_a _a x_a∏_p=1^kP^(p)_b,x⃗.

By assumption, the probabilities P^(p)_b,x⃗=f⃗^(p)_b,j_p· T^(p)_x⃗s⃗_i_p^(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 <ref>. Therefore, if N≡∑_p n_p<m, then J̃_m,,b^(d)(k) vanishes for all , b. Since the dual formulation is equivalent to the game formulation (see Appendix <ref>), this implies that the k systems cannot be used to achieve more than ∑_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 transformations, since local tomography implies that all transformations can be written as a linear combination of independent transformations, i.e. T_x⃗=∑_𝐢c_𝐢(x⃗)⊗_p=1^kT^(p)_i_px⃗. However, due to the coefficients c_𝐢(x⃗) being explicitly dependent on x⃗, our proof would not be valid in general. Therefore, in order to drop the assumption of independent transformations, we will characterize the locality of the boxes' operations in the next subsection.



 §.§ Non-independent operations and locality

In the previous section we proved that under the assumptions of (i) local tomography, and (ii) independent operations, a system composed of k systems of orders (n_1,...,n_k) is a (∑_j n_j)-th order system. Notice that within the proof we did not need to specify anything about the transformations T_x⃗ and we did not impose the notion of locality of the boxes' actions. On the other hand, in quantum (and classical) theory we proved a stronger statement: additivity follows without assumption (ii); however, in that case we explicitly implemented the notion of locality by conditioning the boxes' actions on the path degrees of freedom of the systems. In what follows, we will provide an analogous analysis in the context of GPTs, thereby dropping assumption (ii). We will start by defining the relevant concepts for single systems.

In order to generalize the quantum proof from Section <ref> 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 A. We denote the state space of the control degrees of freedom with St(A^(c)) ⊂ A^(c), and the state space of the internal degrees of freedom with St(A^(int))  ⊂ A^(int), where A^(c) and A^(int) are real vector spaces. Assuming local tomography, the total state space of system A will then be St(A) ⊂ A^(c)⊗ A^(int). Analogously, we can define the spaces of effects as subspaces of the dual vector spaces, i.e. Eff(A^(c)) ⊂  A^(c)*, Eff(A^(int)) ⊂ A^(int)*, and Eff(A) ⊂ A^(c)*⊗ A^(int)*. Now we will characterize the state space of the control degree of freedom.



Assumption 0. Let us assume that there exists an m-outcome measurement for the control degree of freedom corresponding to the following set of effects {f⃗^(1),...,f⃗^(m)∈Eff(A^(c));  ∑_i f⃗^(i)=u⃗^(c)}, where u⃗^(c) is the unit effect, i.e. the effect that satisfies u⃗^(c)·v⃗=1,∀v⃗∈ St(A^(c)). The physical meaning of the latter is that each effect f⃗^(i) gives the probability of the system being found at box i. We will thus refer to this measurement as the “which-box measurement”. 



Let us also define subsets of boxes J= {j_1,,...,j_|J|}⊆ I, where I ≡{1,2,...,m}, and introduce the coarse-grained effects f⃗^(J)≡∑_i=1^|J|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[Or equivalently: ∀ J',  J' ∩ J = ∅   →   f⃗^(J')·v⃗=0.];

  * ∀ J',    J' ⊂ J   →   f⃗^(J')·v⃗>0.

The first point of this definition simply say that “a system being localized at some particular subset” means that “the probability of finding the system outside of this subset is null”. The second point is needed in order to select the minimum possible subset which satisfies the first point and thus select a unique subset.
 
We will now consider a basis S={s⃗_1,...,s⃗_r^(c)} of A^(c), with s⃗_i ∈ St(A^(c)), and r^(c) being the dimension of A^(c). If the theory describing our system was classical, then r^(c)=m, and we could choose a basis consisting of states localized at each box, i.e. f⃗^(i)·s⃗_j=δ_ij. On the other hand, if we consider quantum theory, then r^(c)=m^2, and we can construct a basis S={s⃗_j_1j_2,∀ j_1,j_2=1,...,m } such that each of its elements s⃗_j_1j_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=|j⟩⟨j|, whereas, for j_1<j_2, states s⃗_j_1j_2 and s⃗_j_2j_1 correspond to the superposition states s⃗_j_1j_2=|j_1j_2⟩_x⟨j_1j_2| and s⃗_j_2j_1=|j_1j_2⟩_y⟨j_1j_2|, where |j_1j_2⟩_x ∼(|j_1⟩+|j_2⟩) and |j_1j_2⟩_y ∼(|j_1⟩+i|j_2⟩) (see for instance <cit.>). 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, 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[A similar reasoning motivated the construction of the density cube theory which is a third-order-interference theory obtained as a modification of quantum theory, by replacing density matrices (tensors with two indices) with tensors with three indices (the so called density cubes). Translated to our framework, such a state space is spanned by states, each of which is localized at most at three boxes <cit.>.]. In what follows, we will analyze this relation and show that it does indeed hold under certain assumptions. However, we will first formalize the notion of the “localizability” with respect to the “which-box measurement” by introducing the notion of “locality order”.



Locality order. Let us focus on a generic state-space of the control degree of freedom St(A^(c)) (while still assuming that there exists the which-box measurement, i.e. Assumption 0), and consider an arbitrary basis S={s⃗_1,...,s⃗_r^(c)} of A^(c), with s⃗_i ∈ St(A^(c)). The elements of S can be localized at various boxes' subsets, and these subsets consist in general of different numbers of boxes (i.e. the subsets have different cardinalities). Let us define l_S ∈ℕ to be the maximum among these numbers, meaning that each element of S is localized within at most l_S different boxes. Formally, for each basis S={s⃗_1,...,s⃗_r^(c)} we define the parameter l_S in the following way:

    ∀ i,   ∃( J_i ⊆ I ),   s.t.  (s⃗_i  is localized at  J_i) &(|J_i|≤ l_S ).

Naturally, different basis choices S correspond to different values of l_S. We will define the locality order L as the minimum l_S among all possible basis, i.e. L≡min_S l_S, and denote a basis that achieves this value of l_S with S^* (there can be many different basis that achieve the minimum value; we will simply take S^* to be one of them). Therefore, the parameter l_S is associated to each basis S, whereas the locality order L is associated to the theory, together with the “which-box measurement”. Quantum theory satisfies L=2 (with respect to the specific which-box measurement as defined in Assumption 0), since there exists a complete basis whose elements consist of superpositions of at most two boxes (see the example from the previous paragraph), and there is no basis with all of its elements localized at single boxes (classical theory of course satisfies L=1). Note that a hypothetical theory could also satisfy L=m, meaning that any basis must contain at least one “completely de-localized” state. Now we are ready to state our main definitions and assumptions, which will formalize the notion of local operations.



Assumption 1. Here we will introduce the notion of locality of the boxes' operations. As before, we will label with S^*={s⃗_1,...,s⃗_r^(c)} one of the basis 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={j_1^(n),...,j_|J_n|^(n)}, with |J_n| ≤ L. Let us now suppose that a system A is initially prepared in the product state s⃗_i ⊗g⃗, where s⃗_i ∈ S^*, and g⃗∈St(A^(int)). The initial state is thus localized within the subset of boxes J_i ⊆ I. We deem it natural to assume that the boxes act in such a way that (i) the transformed state is still localized within subset J_i (i.e. the boxes cannot “delocalize” the system), and (ii) the transformed state cannot depend on inputs pertaining to boxes outside of J_i (i.e. if the probability of finding the system at some box is null, then the system should not be affected by that box). We will formalize point (i) by requiring that the boxes implement transformations T_x⃗ on the input state (s⃗_i ⊗g⃗) in such a way that the output state satisfies

    (f⃗^(J)⊗e⃗) · T_x⃗(s⃗_i ⊗g⃗)=0,

for all coarse-grained effects f⃗^(J) with J ∩ J_i = ∅, and arbitrary effects e⃗∈Eff(A^(int)). Equation (<ref>) thus states that one cannot steer the control degree of freedom of the output state into a state which is localized outside of the initial subset J_i (i.e. this is what we mean that the output state is localized within J_i). The most general form of the action of the transformations T_x⃗ that satisfies the above requirements is the following:

    T_x⃗(s⃗_i ⊗g⃗)=∑_n 
     J_n ⊆ J_is⃗_n⊗ T^(i,n)_x⃗^(J_i)g⃗,

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={j^(i)_1,...,j^(i)_|J_i|}. Moreover, all additional coefficients that may appear in front of each term of the sum are for simplicity absorbed in the operators T^(i,n)_x⃗^(J_i) (also, note that the vectors T^(i,n)_x⃗^(J_i)g⃗∈ A^(int) may generally lie outside of the internal state space St(A^(int))).
 




Relation between the locality order and the order of interference. Now we will show that Assumption 1 and the principle of local tomography imply a strong relation between the order of interference and the locality order. Consider a general instance of our game which consists of Alice preparing her system in an arbitrary state, sending it through the boxes and Bob performing a generic measurement, thereby producing the conditional probabilities P(b|x⃗). Let us introduce a basis for the internal degrees of freedom {g⃗_1,...,g⃗_r^(int)}, where r^(int) is the dimension of the internal vector space A^(int). According to the principle of local tomography, any initial state v⃗∈St(A) can be written as

    v⃗=∑_i,jc_ijs⃗_i ⊗g⃗_j,

where c_ij are real coefficients, and s⃗_i ∈ S^*. The boxes implement a transformation T_x⃗, and Bob's d-outcome measurement is modelled via a generic set of effects {E⃗_0,...,E⃗_d-1∈Eff(A), ∑_i E⃗_i=u⃗}, where u⃗ is the unit effect on the total state-space. The conditional probability is thus

    P(b|x⃗)   =∑_i,j c_ijE⃗_b ·( T_x⃗s⃗_i⊗g⃗_j)=
       =∑_i,j,n 
     J_n ⊆ J_i c_ijE⃗_b ·(s⃗_n⊗ T^(i,n)_x⃗^(J_i)g⃗_j ),

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 interference: indeed, as proven in Section <ref> and Appendix <ref>, if a distribution exhibits k-th order interference, then its algebraic order is k. Thus, if a system can exhibit k-th order interference, then Assumption 1 implies that the theory satisfies L≥ k.

Next, we will introduce a further assumption which will relate the possible transformations implementable by the boxes to the locality order of the theory, and show that together with the previous assumptions, it implies L=k.



Assumption 2. Let us suppose that the locality order 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_1x_2, ∀ x_1,x_2}, the following holds:

    T_x_1,x_2v⃗=∑_i s⃗_i ⊗ T^(v,i)_x(i)g⃗_i,

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 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_2v⃗ within that theory would have a similar form to the one in Equation (<ref>): it would still be a linear combination of terms, each of which depends only on one input. Thus, if our assumption did not hold, a system of locality order 2 would encode the inputs in the qualitatively same way as a system of order 1. In order to introduce a difference between systems of different orders, we will assume that a system of order L can produce a state with algebraic order L. This assumption is rather technical and admittedly requires further physical justification; however, in this work we will take it at face value and show that, together with the other assumptions, it implies additivity of interference under composition. Moreover, note that the assumption is satisfied by quantum theory: namely, if the system is prepared in a superposition of two boxes, there exist local transformations that encode the two inputs on the state (e.g. local phase gates) in such a way that the transformed state cannot be decomposed into a linear combination of terms, each of which depends only on one input. On the other hand, superpositions of more than two boxes still give rise only to distributions of algebraic order 2, which is related to the fact that the quantum density matrix is a tensor with two indices (which essentially sets the locality order to L=2).



𝐋=𝐤. Let us now briefly show how the conjunction of our assumptions implies L=k. Namely, Assumption 2 directly implies that if the system cannot exhibit more than k-th order interference, then L≤ k, since for L> k there would exist states and transformations that produce probabilities of algebraic order larger than k which would exhibit more than k-th order interference.
On the other hand, as we have seen before, Assumption 1 and the principle of local tomography imply L≥ k. Hence, the conjunction of the latter statements implies that the locality order of a k-th order system is L=k.



Assumption 3. Up until now, the discussion has been focused only on single systems; now we will specify how the boxes act on composite systems. In sub-section <ref> we had assumed that the boxes act independently on the subsystems; here we want to drop this assumption. Let us consider a system composed of two subsystems. We will label the basis that achieve the minimal locality order for the first and second subsystem respectively with S_1^* and S_2^*. Suppose that the system is prepared in the following product state s⃗_i_1⊗s⃗_i_2⊗g⃗_1 ⊗g⃗_2 ∈ A_1^(c)⊗ A_2^(c)⊗ A_1^(int)⊗ A_2^(int), 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={j_1^(i_1),...,j_|J_i_1|^(i_1)}⊆ I and J_i_2={j_1^(i_2),...,j_|J_i_2|^(i_2)}⊆ I. Since the two subsystems are localized respectively at J_i_1 and J_i_2, we will say that the composite system is localized at J_i_1∪ J_i_2. Now we will introduce the action of the boxes on the composite system as a direct generalization of Assumption 1. Namely, we will demand that (i) the composite control degree of freedom of the transformed state can be steered only into states localized within J_i_1∪ J_i_2, and (ii) the transformed state depends only on inputs contained within subset J_i_1∪ J_i_2. Analogously to Assumption 1., the first part states that the boxes cannot further “delocalize” the system, while the second part states that if the probability of finding either of the subsystems at some box is 0, then the composite system should not be affected by the action of that box. Thus we see that this assumption states that if two subsystems of a composite system are localized at subsets J_i_1 and J_i_2, then the transformations acts on the composite system, as if the latter was a single system localized at subset J_i_1∪ J_i_2. The most general form of the transformations T_x⃗ that satisfies the above requirements is

    T_x⃗(s⃗_i_1⊗s⃗_i_2⊗g⃗_1 ⊗g⃗_2)
       =∑_n_1n_2 
     (J_n_1∪ J_n_2)
    ⊆ (J_i_1∪ J_i_2)s⃗_n_1⊗s⃗_n_2⊗ T^(𝐢𝐧)_x⃗^(J_i_1,J_i_2)(g⃗_1 ⊗g⃗_2),
 
where we introduced the input strings

    x⃗^(J_i_1,J_i_2)≡ (x_j_1^(i_1),...,x_j_|J_i_1|^(i_1),x_j_1^(i_2),...,x_j_|J_i_2|^(i_2)),

and the bold index 𝐧 stands for n_1n_2. Each of the transformations T^(𝐢𝐧)_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 (<ref>) 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≠∅.
 


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={j^(i_1)_1,...,j^(i_1)_|J_i_1|)} and J_i_2={j^(i_2)_1,...,j^(i_2)_|J_i_2|}, with |J_i_1|≤ k and |J_i_2|≤ k. From here it is simple to show that two k-th order systems 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⃗=∑_𝐢𝐤c_𝐢𝐤s⃗_i_1⊗s⃗_i_2⊗g⃗_k_1⊗g⃗_k_2,
 
where {g⃗_k_1⊗g⃗_k_2, ∀ k_1,k_2} forms a basis for the internal state space of the composite system. The bold indices 𝐢,𝐤 stand for i_1,i_2,k_1,k_2, and c_𝐢𝐤 are real coefficients. The composite system is then sent through the boxes, which implement the input-dependent transformation T_x⃗. Finally, Bob performs a measurement {E⃗_0,...,E⃗_d-1∈Eff(A), ∑_i E⃗_i=u⃗}, where u⃗ is the unit effect on the total state-space. The conditional probabilities thus follow:

    P(b|x⃗)=∑_𝐢𝐤 c_𝐢𝐤E⃗_b ·[ T_x⃗(s⃗_i_1⊗s⃗_i_2⊗g⃗_k_1⊗g⃗_k_2) ]
       =∑_𝐢𝐤𝐧 c_𝐢𝐤E⃗_b ·[s⃗_n_1⊗s⃗_n_2⊗ T^(𝐢𝐧)_x⃗^(J_i_1J_i_2)(g⃗_k_1⊗g⃗_k_2) ].

Since x⃗^(J_i_1J_i_2), as defined in Equation (<ref>), 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 <ref> 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 (∑_i=1^p 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 briefly summarize and emphasize the main assumptions and results of this section. In Subsection <ref> 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 <ref>, 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 <cit.>, which makes it more compatible with relativity).



§ 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 finite resources. These games essentially characterize how much information can be decoded from a physical system given that the information 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 interference 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 provide 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 redefined 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 number of systems. This could then complement the vast experimental search for higher-order interference <cit.>. Another interesting direction is to take the boxes' inputs to be concrete spatio-temporal variables, as in Ref. <cit.>, and see how this constrains the order of interference achievable with a fixed amount of resources (e.g. one may perhaps find 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 generalizations thereof), we could ask why does quantum theory 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 define the notion of number of systems in a device-independent scenario (or ought one to quantify the resources in an alternative manner)? We plan to investigate these and further questions in future works.   



The authors thank the three anonymous reviewers for their insightful comments and suggestions which greatly improved both the content and the form of this manuscript. The authors thank Markus P. Müller, Joshua Morris and Nicolás M. Sánchez for helpful discussions. B.D. acknowledges support from an ESQ Discovery Grant of the Austrian Academy of Sciences (OAW) and the Austrian Science Fund (FWF) through  BeyondC-F7112. S.H. acknowledges support from an ESQ Discovery Grant of the Austrian Academy of Sciences (OAW).



tocsectionBibliography
00

feynman Feynman, R.P., Leighton, R.B. and Sands, M., 2005. The Feynman Lectures on Physics: Definitive Edition. Pearson Addison-Wesley. ISBN 0-8053-9046-4 

sorkin Sorkin, R.D., 1994. Quantum mechanics as quantum measure theory. Modern Physics Letters A, 9(33), pp.3119-3127. https://doi.org/10.1142/S021773239400294X

cubes Dakic, B., Paterek, T. and Brukner, C., 2014. Density cubes and higher-order interference theories. New Journal of Physics, 16(2), p.023028. http://dx.doi.org/10.1088/1367-2630/16/2/023028

single system 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. http://dx.doi.org/10.1088/1367-2630/16/12/123029

higher extension Lee, C.M. and Selby, J.H., 2017. Higher-order interference in extensions of quantum theory. Foundations of Physics, 47(1), pp.89-112. https://doi.org/10.1007/s10701-016-0045-4

ruling out 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. https://doi.org/10.3390/e19060253

ududec 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. https://doi.org/10.1007/s10701-010-9429-z

niestegge Niestegge, G., 2013. Three-slit experiments and quantum nonlocality. Foundations of Physics, 43(6), pp.805-812. https://doi.org/10.1007/s10701-013-9719-3

kickback Lee, C.M. and Selby, J.H., 2016. Generalised phase kick-back: the structure of computational algorithms from physical principles. New Journal of Physics, 18(3), p.033023. http://dx.doi.org/10.1088/1367-2630/18/3/033023

hardy Hardy, L., 2001. Quantum theory from five reasonable axioms. arXiv preprint quant-ph/0101012. 

dakic Dakic, B. and Brukner, C. Quantum theory and beyond: is entanglement special? Deep Beauty: Understanding the Quantum World Through Mathematical Innovation (ed. Halvorson, H.) (Cambridge Univ. Press, 2011). https://doi.org/10.1017/CBO9780511976971.011

masanes Masanes, L. and Mueller, M.P., 2011. A derivation of quantum theory from physical requirements. New Journal of Physics, 13(6), p.063001. http://dx.doi.org/10.1088/1367-2630/13/6/063001

chiri Chiribella, G., D Ariano, G.M. and Perinotti, P., 2011. Informational derivation of quantum theory. Physical Review A, 84(1), p.012311. http://dx.doi.org/10.1103/PhysRevA.84.012311

2way Del Santo, F. and Dakić, B., 2018. Two-way communication with a single quantum particle. Physical review letters, 120(6), p.060503. https://doi.org/10.1103/PhysRevLett.120.060503

2wayexp Massa, F., Moqanaki, A., Baumeler, Ä., Del Santo, F., Kettlewell, J.A., Dakić, B. and Walther, P., 2019. Experimental two-way communication with one photon. Advanced Quantum Technologies, 2(11), p.1900050. https://doi.org/10.1002/qute.201900050

infinite Hsu, L.Y., Lai, C.Y., Chang, Y.C., Wu, C.M. and Lee, R.K., 2020. Infinite information can be carried using a single quantum particle. arXiv preprint arXiv:2002.10374.

infospeed Horvat, S. and Dakić, B., 2019. Quantum enhancement to information speed. arXiv preprint arXiv:1911.11803.

Brukner Oreshkov, O., Costa, F. and Brukner, C., 2012. Quantum correlations with no causal order. Nature communications, 3, p.1092. https://doi.org/10.1038/ncomms2076

orders Feix, A., Araujo, M. and Brukner, C., 2016. Causally nonseparable processes admitting a causal model. New Journal of Physics, 18(8), p.083040. http://dx.doi.org/10.1088/1367-2630/18/8/083040

directions Guerin, P.A., Feix, A., Araujo, M. and Brukner, C., 2016. Exponential communication complexity advantage from quantum superposition of the direction of communication. Physical review letters, 117(10), p.100502. https://doi.org/10.1103/PhysRevLett.117.100502

combs Chiribella, G., D Ariano, G.M. and Perinotti, P., 2008. Quantum circuit architecture. Physical review letters, 101(6), p.060401. https://doi.org/10.1103/PhysRevLett.101.060401

switch Chiribella, G., D Ariano, G.M., Perinotti, P. and Valiron, B., 2013. Quantum computations without definite causal structure. Physical Review A, 88(2), p.022318. https://doi.org/10.1103/PhysRevA.88.022318

causal models Allen, J.M.A., Barrett, J., Horsman, D.C., Lee, C.M. and Spekkens, R.W., 2017. Quantum common causes and quantum causal models. Physical Review X, 7(3), p.031021. https://doi.org/10.1103/PhysRevX.7.031021

device Brunner, N., Cavalcanti, D., Pironio, S., Scarani, V. and Wehner, S., 2014. Bell nonlocality. Reviews of Modern Physics, 86(2), p.419. https://doi.org/10.1103/RevModPhys.86.419

pretty good Hausladen, P. and Wootters, W.K., 1994. A 'pretty good' measurement for distinguishing quantum states. Journal of Modern Optics, 41(12), pp.2385-2390. https://doi.org/10.1080/09500349414552221

witness1 Cong, W., Cai, Y., Bancal, J.D. and Scarani, V., 2017. Witnessing irreducible dimension. Physical review letters, 119(8), p.080401. https://doi.org/10.1103/PhysRevLett.119.080401

witness2 Aguilar, E.A., Farkas, M., Martinez, D., Alvarado, 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 refined dimension witnesses. Physical Review Letters, 120(23), p.230503. https://doi.org/10.1103/PhysRevLett.120.230503

bare Barrett, J., 2007. Information processing in generalized probabilistic theories. Physical Review A, 75(3), p.032304. https://doi.org/10.1103/PhysRevA.75.032304

local qm Haag, R., 2012. Local quantum physics: Fields, particles, algebras. Springer Science & Business Media. https://doi.org/10.1007/978-3-642-61458-3

exp1 Sinha, U., Couteau, C., Jennewein, T., Laflamme, R. and Weihs, G., 2010. Ruling out multi-order interference in quantum mechanics. Science, 329(5990), pp.418-421. https://doi.org/10.1126/science.1190545

exp2 Park, D.K., Moussa, O. and Laflamme, R., 2012. Three path interference using nuclear magnetic resonance: a test of the consistency of Born's rule. New Journal of Physics, 14(11), p.113025. http://dx.doi.org/10.1088/1367-2630/14/11/113025

exp3 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. https://doi.org/10.1088/1367-2630/aa5d98

exp4 Lee, K.S., Zhuo, Z., Couteau, C., Wilkowski, D. and Paterek, T., 2020. Atomic test of higher-order interference. Physical Review A, 101(5), p.052111. https://doi.org/10.1103/PhysRevA.101.052111

spatio-temp Garner, A.J., Krumm, M. and Mueller, M.P., 2020. Semi-device-independent information processing with spatiotemporal degrees of freedom. Physical Review Research, 2(1), p.013112. https://doi.org/10.1103/PhysRevResearch.2.013112

burnside Lomonosov, V. and Rosenthal, P., 2004. The simplest proof of Burnside's theorem on matrix algebras. Linear algebra and its applications, 383, pp.45-47. https://doi.org/10.1016/j.laa.2003.08.012












§ 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

    Ĩ_m,,f^(d)(k)=1/d^m∑_x_1,...,x_m=0^d-1 P(b=f(s_,x⃗^(d))|x_1...x_m)-1/d=0,   ∀, ∀ f

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

    J̃^(d)_m,,b=1/d^m∑_x⃗(ω_d)^∑_a  _a x_a P(b|x⃗)=0,   ∀,   ∀ b∈{0,...,d-1},

where ω_d=e^i2π/d is the d-th root of unity.

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

    J̃^(d)_m,,b,α≡1/d^m∑_x⃗(ω_d)^α∑_a _a x_a P(b|x⃗).

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

    {Ĩ_m,,f^(d)=0,   ∀ f	}⟷{J̃^(d)_m,,b,α=0, ∀ b∈{0,...,d-1}, ∀α∈{1,...,d-1}}

Since the order of interference is defined as the vanishing of the interference terms (<ref>) for all , (<ref>) would imply that the dual formulation of interference (<ref>) is equivalent to the game formulation (<ref>) (this is so because if the RHS of equivalence (<ref>) holds for all , then the dual conditions (<ref>) also hold, since the index α becomes redundant). In what follows, we will prove that (<ref>) does hold indeed.

In order to simplify the notation, let us introduce the d × d matrix P, whose elements are defined as[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.]

    P_bs=1/d^m-1∑_x⃗
     s_,x⃗^(d)=sP(b|x⃗).

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

    ∑_b P_bs=1,   ∀ s.

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

    1/d^m∑_x_1,...,x_m=0^d-1 P(b=f(s_,x⃗^(d))|x_1...x_m)=1/d,   ∀ f   →  ∑_s P_f(s)s=1,   ∀ f,

which we rewrite succintly as

    [Π_f P]=1,   ∀ f,

where Π_f ≡∑_s |f(s)⟩⟨s| ranges over all d-dimensional permutation matrices (the most general finite dimensional reversible transformations are indeed permutations).

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

    (PF)_lk=δ_k,01/√(d)∑_j P_lj ,

where F is the d-dimensional Fourier matrix with elements

    (F)_lk=1/√(d) (ω_d)^lk.

We will first show that the dual conditions (<ref>) imply the information-theoretic conditions (<ref>). Assuming that the the dual conditions (<ref>) hold, we evaluate the trace

    [Π_f P]= [F^†Π_f P F]= ∑_kl (F^†Π_f)_kl (PF)_lk=∑_l (F^†Π_f)_0l (PF)_l0=1, ∀ f.

The first step follows from the unitarity of F and the ciclicity of the trace, the third step is due to the dual conditions (<ref>), and the last step follows from (F^†Π_f)_0l=1/√(d). Therefore, conditions (<ref>) imply (<ref>).

In order to prove the converse statement, let us introduce the following new basis β={|E⟩, |e_1⟩,...,|e_d-1⟩}, where |E⟩ has the following form

    |E⟩=1/√(d) (1,1,...,1)^T,

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 (<ref>) can then be written as

    ⟨E|P=⟨E|,

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

    P= |E⟩⟨E| + ∑_j q_j |e_j⟩⟨E| + E̅,

where q_j are arbitrary complex numbers and E̅ is a matrix that has support only on the subspace orthogonal to |E⟩.

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

    Π_f= |E⟩⟨E| + Δ_f,

where Δ_f is again a matrix with no support on |E⟩. 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 |E⟩ which is invariant under all permutations) and a (d-1)-dimensional irreducible representation (here given by Δ_f). Assuming that the game-conditions (<ref>) hold, we obtain the following

    1= [Π_fP]= 1+  [Δ_f E̅] →[Δ_f E̅]=0,   ∀ f.

Since the matrices Δ_f provide an irreducible representation of the permutation group, the Burnside Theorem <cit.> implies that they span the set of all (d-1)-dimensional matrices; therefore, Equation (<ref>) implies that E̅ is necessarily zero. The matrix P is thus

    P= |E⟩⟨E| + ∑_j q_j |e_j⟩⟨E| = |q⟩⟨E|,

where we introduced the vector |q⟩≡|E⟩+ ∑_j q_j|e_j⟩. Therefore, the sought matrix PF is 

    (PF)_kl=⟨l|q|⟨%s|⟩EF |k⟩= δ_k,01/√(d)∑_j P_lj,

where we used ∑_k=0^d-1 (ω_d)^k=0 and {|k⟩; k=0,...,d-1} are the original basis vectors. Hence, equivalence (<ref>) holds, and thus the game formulation (<ref>) is equivalent to the dual formulation (<ref>).
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.



§ ALGEBRAIC ORDER FOR ARBITRARY D

In this Appendix we are going to extend the mathematical property of Section <ref> 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 <ref> we showed that this is equivalent to the following constraints

    J̃^(d)_m,,b=1/d^m∑_x⃗(ω_d)^∑_j _j x_jP(b|x⃗)=0,
       ∀ b∈{0,1,...,d-1}, _j∈{0,1,...,d-1},   s.t.  ∑_j δ__j,0<(m-n).

For compactness, we allow the dit string  to range over all dit-strings with less than (m-n) null components. This notation specifies which interference terms the equation refers to: if _j≠ 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⃗)=⊗_i=1^me⃗_x_i·P⃗_b, where {e⃗_x_j, x_j=0,...,d-1} span the j-th d-dimensional space. Equations (<ref>) then imply:

    J̃^(d)_m,,b=1/d^m∑_x⃗(ω_d)^∑_j _j x_j⊗_i=1^me⃗_x_i·P⃗_b=1/d^m/2⊗_i=1^mf⃗__i·P⃗_b=1/d^m/2λ_,b=0,

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

    f⃗__j≡1/√(d)∑_x_j=0^d-1 (ω_d)^_j x_je⃗_x_j,
  
and the coefficients λ_,b are the components of the vector P⃗_b in the corresponding basis. Equation (<ref>) 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⃗)=[⊗_i=1^me⃗_x_i] ·[∑_λ_,b⊗_j=1^mf⃗__j]=1/d^m/2∑__1,...,_m 
    ∑_jδ__j,0≥ (m-n)(ω_d)^∑_j _j x_jλ_,b,

where we used e⃗_x_i·f⃗__i=1/√(d)(ω_d)^_ix_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 (<ref>), or equivalently, the information-theoretic formulation (<ref>), provide a set of necessary and sufficient 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.




§ PROOF OF EQUATION (<REF>)

In this Appendix we will show that equations

    ∑_x⃗ (ω_d)^α∑_k _k x_kρ_x⃗=0,   ∀α∈{1,...,d-1}

imply the following relations

    ρ^(S)=ρ^(S'),   ∀ S,S'=0,...,d-1,

where ρ^(S) is defined as

    ρ^(S)≡1/d^m-1∑_x_1,...,x_m 
     (∑_k _k x_k)mod d=Sρ_x⃗.

For a start, Equations (<ref>) can be written as

    ∑_S=0^d-1 (ω_d)^α Sρ^(S)=0,   ∀α∈{1,...,d-1}.

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,

where F_kl=1/√(d)(ω_d)^kl is the d-dimensional Fourier matrix and ρ̅=1/d∑_S ρ^(S). Taking the inverse of Equation <ref> (i.e. applying F^† from the left) we obtain

    ρ⃗ = ρ̅(1,1,...,1)^T,

which is equivalent to 

    ρ^(S)=ρ^(S')=ρ̅,   ∀ S,S'=0,...,d-1.




§ 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 <ref>). 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),

where H^(c)≡⊗_j=1^k H^(c_j) is the composite of the control/path degrees of freedom, and H^(int)≡⊗_j=1^k 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)(x_i_1,...,x_i_k),   ∑_s B_𝐢^(s)†(x_i_1,...,x_i_k)B_𝐢^(s)(x_i_1,...,x_i_k)≤1},

where 𝐢 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⃗=∑_𝐢⊗_p=1^k|n^(p)_i_p⟩⟨n^(p)_i_p|⊗ B_𝐢^(s)(x_i_1,...,x_i_k)},

where {|n^(p)_i_p⟩, ∀ i_p=1,...,m } 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=∑_𝐢,𝐣,𝐫,𝐥 c_𝐢𝐣𝐫𝐥⊗_p=1^k[|n^(p)_i_p⟩⟨n^(p)_j_p|⊗|ϕ^(p)_r_p⟩⟨ϕ^(p)_l_p|],

where 𝐢 is short for i_1,...,i_k (and analogously for the other indices), and vectors {|ϕ^(p)_r_p⟩, ∀ r_p} span the internal space of p-th system H^(int_p).

The boxes then act on the system as follows:

    ρ_x⃗=∑_s M^(s)_x⃗ρ_0 M^(s)†_x⃗=∑_𝐢,𝐣⊗_p=1^k[|n^(p)_i_p⟩⟨n^(p)_j_p|]⊗ C_𝐢𝐣(x_i_1,x_j_1,...,x_i_k,x_j_k),

where 

    C_𝐢𝐣(x_i_1,x_j_1,...,x_i_k,x_j_k)=∑_s,𝐫,𝐥 c_𝐢𝐣𝐫𝐥 B_𝐢^(s)(x_i_1,...,x_i_k) ( ⊗_p=1^k|ϕ^(p)_r_p⟩⟨ϕ^(p)_l_p|) B_𝐣^(s)†(x_j_1,...,x_j_k).

As stated in Section <ref>, 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.


§ 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 definition, 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_x⃗^(d)=(∑_j x_j) mod d. The proof for any other  is completely analogous. The protocol proceeds as follows. Alice sends system A to the first 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 final output b=(b^(A)+b^(B)) mod d. Here the two systems are treated completely independently: the only “mixing” between them happens in the final step, since Bob's output depends on both systems' processes. The (n_A+n_B)-th order interference term is then

    Ĩ_n_A+n_B^(d)   =1/d^n_A+n_B∑_x_1,...x_n_A+n_B P(b=s_x⃗^(d)|x⃗) - 1/d
    =1/d^n_A+n_B∑_x_1,...x_n_A+n_B∑_l P(b^(A)_l,b^(B)_l|x⃗) - 1/d,

where the sum runs over all two-outcome measurements which produce the correct modulo, i.e. (b^(A)_l+b^(B)_l) mod d=(∑_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 

    Ĩ_n_A+n_B^(d)=q_A q_B+∑_i=1^d-1p_i^(A)p_d-i^(B)- 1/d,
 
where q_A and q_B are average winning probabilities for the two systems, while the distribution averages over wrong outcomes are defined as

    p_i^(A)≡1/d^n_A∑_x_1,...,x_n_AP^(A)(b^(A)=(s_x⃗^(d)+i)mod  d|x⃗),
 
and analogously for system B. Next, we define weights α_j and β_j in the following way

    p_i^(A)=(1-q_A)α_i,
    
    p_d-i^(B)=(1-q_B)β_i,

which implies ∑_j α_j= ∑_j β_j =1[In order for the coefficients α_i and β_i to be well defined, we assume that q_A≠ 1 and q_B≠ 1. In the case that either q_A or q_B (or both) are equal to 1, the first term in (<ref>) is q_Aq_B>1/d, while the second term is non-negative, which makes the overall interference term positive.]. Plugging expressions (<ref>) into the interference term we obtain

    Ĩ_n_A+n_B^(d)=q_A q_B + (1-q_A)(1-q_B)λ -1/d,   λ≡∑_j α_j β_j.

By a straightforward application of the method of Lagrange multipliers with constraints ∑_j α_j=1 and ∑_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:

    Ĩ_n_A+n_B^(d)≥ q_A q_B + 1/d-1(1-q_A)(1-q_B) -1/d.

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 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 (∑_i=1^k n_i)-th order interference.

