# Building Multiple Access Channels with a Single Particle

Yujie Zhang  Department of Physics, University of Illinois at Urbana-
Champaign, Urbana, IL 61801, USA  Xinan Chen  Department of Electrical and
Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, IL
61801, USA  Eric Chitambar<EMAIL_ADDRESS>Department of Electrical and
Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, IL
61801, USA

###### Abstract

A multiple access channel describes a situation in which multiple senders are
trying to forward messages to a single receiver using some physical medium. In
this paper we consider scenarios in which this medium consists of just a
single classical or quantum particle. In the quantum case, the particle can be
prepared in a superposition state thereby allowing for a richer family of
encoding strategies. To make the comparison between quantum and classical
channels precise, we introduce an operational framework in which all possible
encoding strategies consume no more than a single particle. We apply this
framework to an $N$-port interferometer experiment in which each party
controls a path the particle can traverse. When used for the purpose of
communication, this setup embodies a multiple access channel (MAC) built with
a single particle.

We provide a full characterization of the $N$-party classical MACs that can be
built from a single particle, and we show that every non-classical particle
can generate a MAC outside the classical set. To further distinguish the
capabilities of a single classical and quantum particle, we relax the locality
constraint and allow for joint encodings by subsets of $1<K\leq N$ parties.
This generates a richer family of classical MACs whose polytope dimension we
compute. We identify a “generalized fingerprinting inequality” as a valid
facet for this polytope, and we verify that a quantum particle distributed
among $N$ separated parties can violate this inequality even when $K=N-1$.
Connections are drawn between the single-particle framework and multi-level
coherence theory. We show that every pure state with $K$-level coherence can
be detected in a semi-device independent manner, with the only assumption
being conservation of particle number.

##  1 Introduction

A quantum particle is fundamentally different than its classical counterpart.
From the second quantization picture, a quantum “particle” can be regarded as
a single mode excitation of some field, and hence it is endowed with certain
wave-like features that a classical particle lacks. Modern experimental
techniques are able to individually address these quantum particles, or
“quanta”, and use them for information processing. Hence it is a practically
relevant endeavor to identify the advantages that a single quantum particle
can offer in some particular information task over a classical particle. This
provides an operational comparison between classical and quantum information
systems in terms of their most basic building block.

In this work, we consider the task of multi-party communication with $N$
spatially-separated senders
$(\mathsf{A}_{1},\mathsf{A}_{2},\cdots\mathsf{A}_{N})$ and one receiver
$(\mathsf{B})$. The receiver $\mathsf{B}$ obtains some output data $b$ that
depends on the collection of messages $(a_{1},a_{2},\cdots,a_{N})$ chosen by
the senders. Ideally, $b$ would be a perfect copy of all the $N$ messages,
$b=(a_{1},a_{2},\cdots,a_{N})$. However in practice there are some physical
limitations that prevent perfect communication. In such scenarios, the
communication is described by the transition probabilities $p(b|a_{1}\cdots
a_{N})$. The distributions $p(b|a_{1}\cdots a_{N})$ collectively represent a
multiple-access channel (MAC) [18, 57]. Ultimately, the probabilities
$p(b|a_{1}\cdots a_{N})$ are determined by the particular physical system used
to transmit the information. The question we raise here is what MACs can be
generated under the restriction that the communication channel be implemented
using only a single particle, with none of its internal degrees of freedom
being accessible. More precisely, information is only allowed to be encoded in
external relational degrees of freedom, such as what particular points in
space-time the particle occupies. We are interested in comparing the MACs that
can be realized when a quantum versus classical particle is used to transmit
information in this way.

This question can be pushed in a variety of different directions. In point-to-
point communication, one very active line of research considers communication
enhancements that can arise when a single quantum particle is subjected to
different configurations of quantum communication devices [38]. For instance,
non-classical effects can be generated when a particle is subjected to two
noisy channels with indefinite causal order [22, 48, 25, 12]. It is also
possible to explore the communication power of a single particle that travels
through channels in a superposition of different trajectories or times [2, 11,
40]. In these strategies, the superposition in trajectories or causal order
have to be determined by an extra control bit, and there are subtleties in
interpreting precisely what types of enhancements are physically realizable
[39]. In this paper, we adopt a more basic model in which quantum
superpositions are limited to just the spatial path traveled by the particle
and accessed by the different senders. The encoding of information is
delocalized among the parties
$(\mathsf{A}_{1},\mathsf{A}_{2},\cdots\mathsf{A}_{N})$, and the encoding is
assumed to be implemented at a definite moment in time. Yet even in this more
familiar and simpler setting, operational advantages of using quantum versus
classical MACs can be identified.

Consider, for example, the task of quantum fingerprinting. In the two-party
scheme, the goal of this task is for receiver $\mathsf{B}$ to decide whether
or not $a_{1}=a_{2}$ based on some partial information sent from
$\mathsf{A}_{1}$ and $\mathsf{A}_{2}$, which represents their “fingerprints”
[10]. While there are many variations to the problem, one version compares the
task when $\mathsf{A}_{1}$ and $\mathsf{A}_{2}$ have pre-shared classical
versus quantum correlations [30, 45, 29]. As observed by Massar [45], a single
quantum particle initially prepared in a spatial superposition state can be
used for $\mathsf{B}$ to decide if $a_{1}=a_{2}$ when
$a_{1},a_{2}\in\\{0,1\\}$, a feat that is impossible with a single classical
particle. In this example, parties $\mathsf{A}_{1}$ and $\mathsf{A}_{2}$
encode the parity of their bit values in the phase of the single-particle
state.

The results of this paper are inspired by this fingerprinting task but go well
beyond it. Mathematically, every classical single-particle fingerprinting
protocol can be described as a point in a polytope, the so-called “classical
polytope”. The best possible classical fingerprinting protocol, in terms of
the probability that $\mathsf{B}$ correctly decides matching inputs, lies on
the boundary of this polytope. Using a single quantum particle allows for
protocols that go beyond this boundary, thereby identifying a genuine quantum
advantage. As we move to more senders and more inputs/outputs, the classical
polytope becomes much more complex, and the classical-quantum boundary is no
longer characterized by the simple fingerprinting task. One goal of this paper
is describe new features that emerge in this higher-dimensional polytope that
do not reduce to two-party fingerprinting.

Other sources of inspiration for this work are a series of recent results
showing different types of single-particle enhancement in quantum
communication. Del Santo and Dakić have devised a protocol that allows for
two-way communication between two parties using a single quantum particle,
whereas the communication is always one-way if a single classical particle is
employed [20]. A cascaded implementation of the Del Santo and Dakić protocol
has also been devised in which one of the parties can gain even more
information through the use of a single particle [36]. Advantages of quantum
particles in the reverse communication setting of two senders and one receiver
have also been discovered [21], and very recently, Horvat and Dakić have found
that the superposition state of a single particle can provide significant
enhancement to the speed of information retrieval in some globally-encoded
data [33]. More generally, methods are known for mapping multi-qubit quantum
information into the spatial or temporal degrees of freedom of a single photon
[23, 4]. These results reveal the resource character of single-particle
superposition states for building enhanced multipartite classical
communication channels. It is natural to consider how powerful this resource
can be for generating classical channels and whether it can be formally
characterized in the context of a quantum resource theory [31, 16, 13].

Traditional studies of quantum-enhanced MACs have focused on the capacity rate
region [59, 35, 41], which quantifies the optimal asymptotic communication
rates between the senders and the receiver. From an information-theoretic
sense, this is perhaps the most natural object to consider. However, capacity
is just one property of a channel, and two different channels can have the
same rate region. Consequently, a comparison of rate regions can be too broad
for the purpose of separating classical and quantum-generated MACs. Our
analysis is fine-grained in that it distinguishes MACs on the level of
individual transition probabilities $p(b|a_{1}\cdots a_{N})$. This has the
advantage that, when expressed in terms of these probabilities, the collection
of MACs generated by a single classical particle forms a convex polytope,
provided the output variable is binary. This allows us to employ standard
techniques from convex analysis to construct experimentally-implementable
methods for certifying non-classical MACs.

The main results of this paper and its organization are as follows. In Section
2, we propose an operational framework for building multiple-access channels
with a single particle based on an $N$-path interferometer experiment. Sender
$\mathsf{A}_{i}$ encodes information along path $i$ using a map that obeys the
central constraint of not increasing the overall particle number (as
characterized in Eq. (9)). Included in these allowed operations are phase
encoding and path blocking [52], the latter is also known as vacuum encoding
[11, 40]. We also introduce communication models in which shared randomness is
introduced and other relaxations on the allowed operations are considered. The
interested reader can jump to Section 2.4 and compare the figures within for a
high-level overview of the different models we consider.

In Section 3 we analyze the structure of classical local MACs in more detail.
In Theorem 1, we show that these MACs are characterized entirely in terms of
vanishing second-order interference terms. Roughly speaking, this means that
the particular linear combination

$I_{2}=p(b|a_{i},a_{j})+p(b|a_{i}^{\prime},a_{j}^{\prime})-p(b|a_{i}^{\prime},a_{j})-p(b|a_{i},a_{j}^{\prime})$

must equal zero for any output $b$ and arbitrary inputs
$a_{i},a_{i}^{\prime},a_{j},a_{j}^{\prime}$ chosen by parties $\mathsf{A}_{i}$
and $\mathsf{A}_{j}$. The quantity $I_{2}$ is well-known in the study of
double-slit experiments [27, 37, 46], and here we prove that its vanishing is
essentially the only constraint that assures the MAC has an implementation
using a single classical particle. A similar observation for binary
input/output MACs was made independently in Ref. [32]. In contrast, every
quantum state with a non-zero off-diagonal term in the path basis can generate
$I_{2}\not=0$, as explicitly shown in Section 4 Proposition 9.

We also consider the family of MACs obtained by partially relaxing the
locality constraints on the encoders and allowing joint encoding schemes among
subgroups of size $K<N$. In low dimensions, the resulting classical polytope
is presented in Section 3.2. For arbitrary $N$ and $K$, we show that the
classical polytope exhibits a tight facet inequality, which we call the
generalized fingerprinting inequality [33]:

$p(0|0,\cdots,0)+\sum_{i=1}^{K+1}p(1|0,\cdots,1_{i},\cdots,0)\leq K+1,$

This inequality is shown to be violated by a fully local quantum MAC in
Section 4, a result previously demonstrated in Ref. [33] but one we slightly
optimize here. Along the way we also derive a number of other structural
properties of single-particle classical and quantum MACs. Finally, in Section
5, we draw a direct connection between our framework and the resource theory
of multi-level coherence. In particular, we design new semi-device independent
witnesses for multi-level coherent states.

Near the completion of this manuscript, we became aware of another paper [34]
by Horvat and Dakić that is similar in spirit to this work. The setup in their
paper also involves local encoding in an $N$-path interformeter, however the
restriction to a single particle is not made and the analysis focuses on the
emergence of higher-order interference effects. The latter refers to realizing
nonzero values for the quantities

$\displaystyle
I_{K}=\sum_{a_{1},\cdots,a_{K}\in\\{0,1\\}}\prod_{i=1}^{K}(-1)^{a_{i}}p(0|a_{1},\cdots
a_{K}),$

with $K=2,\cdots,N$. Notice that $K=2$ corresponds to the second-order
interference given above. The quantity $I_{K}$ arises naturally in $K$-slit
interference experiments, and while quantum mechanics can generate
$I_{2}\not=0$, it is known that $I_{K}=0$ for $K>2$ in all standard single-
particle quantum mechanical setups, an intriguing fact that has motivated
multiple studies into the nature of higher-order interference [54, 53, 58, 42,
19, 34, 52]. In Ref. [34], it is shown that $I_{2K}$ can nevertheless be
nonzero in interferometer experiments involving $K$ particles, while
$I_{K^{\prime}}$ still vanishes in $K$-particle experiments when
$K^{\prime}>2K$. In Section 4.3 of this paper, we describe a similar effect in
single-particle interferometer experiments. Namely, when $K$ parties are
allowed to jointly encode on a quantum system of just one particle using
operations constrained to particle-number conservation, $I_{2K}$ can be
nonzero, but $I_{K^{\prime}}$ vanishes for all $K^{\prime}>2K$. We thus see
Ref. [34] and this work as being complementary and reflecting once again the
richness of $N$-path interforemeter experiments for demonstrating quantum
information primitives.

##  2 Definitions and Operational Framework

Let us now introduce our framework in more detail. In Subsection 2.1, we will
provide a general recipe for building MACs with $M$ quantum particles. Moving
beyond that section, we focus exclusively on the single-particle case with
$M=1$. In Subsections 2.2 and 2.3, the structure of single-particle MACs is
analyzed for both a quantum and classical particle. In Subsection 2.4, we
include shared randomness as an extra resource, which further modifies the
communication setup. Finally, in Subsection 2.5, we partially relax the
locality constraint on the $N$ senders and introduce the idea of $(N,K)$-local
MACs.

###  2.1 MACs with Quantum Particles and Number-Preserving Operations

We model our communication scenario as a generalized $N$-port interferometer
experiment in which sender $\mathsf{A}_{i}$ sits along path $i$ and wishes to
send a classical message $a_{i}$ drawn from set $\mathcal{A}_{i}$ (see Fig.
1). We denote the full collection of senders as
$\bm{\mathsf{A}}=(\mathsf{A}_{1},\mathsf{A}_{2},\cdots,\mathsf{A}_{N})$
Throughout this work we will assume that all message sets are finite, and they
can thus be represented by a set of non-negative integers. For an arbitrary
real number $x$, we denote $[x]:=\\{0,\cdots,\lfloor x\rfloor-1\\}$ so that
$\mathcal{A}_{i}$ is in a one-to-one correspondence with the set
$[|\mathcal{A}_{i}|]$. We will be particularly interested in the binary set
$[2]=\\{0,1\\}$ and its $N$-fold Cartesian product $[2]^{N}:=\\{0,1\\}^{\times
N}$. For a general Cartesian product of input sets $\mathcal{A}_{i}$ we simply
write
$\bm{\mathcal{A}}:=\mathcal{A}_{1}\times\mathcal{A}_{2}\times\cdots\times\mathcal{A}_{N}$,
and likewise for random variables $A_{i}$ we write their joint variable as
$\bm{A}:=A_{1}A_{2}\cdots A_{N}$. For an output set $\mathcal{B}$, the
$N$-sender MACs we consider are stochastic maps
$\mathbf{p}_{B|\bm{A}}:\bm{\mathcal{A}}\to\mathcal{B}$ whose transitions
probabitilies we denote by $p(b|\bm{a})$ for $b\in\mathcal{B}$ and
$\bm{a}\in\bm{\mathcal{A}}$. In this way $\mathbf{p}_{B|\bm{A}}$ can be viewed
as a ($|\mathcal{B}|\cdot{|\bm{\mathcal{A}}|}$)-dimensional vector with
coordinates being $p(b|\bm{a})$.

Figure 1: A physical implementation of the MAC $\mathbf{p}_{B|\bm{A}}$ using a
single particle and a generalized interferometer setup.

In a general $M$-particle communication experiment, an $M$-particle state
$\rho^{\bm{\mathsf{A}}}$ is prepared and sent along the $N$ possible
interferometer paths, with its final destination being the receiver
$\mathsf{B}$. Here $\rho^{\bm{\mathsf{A}}}$ has support on space

$\mathcal{H}^{\bm{\mathsf{A}}}_{M}:=\text{span}\\{|\mathbf{x}\rangle:=|x_{1}\rangle_{\mathsf{A}_{1}}\cdots|x_{N}\rangle_{\mathsf{A}_{N}}\;:\sum_{i=1}^{N}x_{i}=M\\},$
(1)

where $\\{|0\rangle_{\mathsf{A}_{i}},|1\rangle_{\mathsf{A}_{i}},\cdots\\}$ are
number states for the particle along path $i$. We assume the particles are of
the same species, and an additional restriction holds depending on whether
they are fermions or bosons. In the fermionic case, we must have $|x_{i}|\leq
1$ while no such constraint holds for bosons. To encode the message $a_{i}$,
sender $\mathsf{A}_{i}$ performs some completely-positive trace-preserving map
$\mathcal{E}^{\mathsf{A}_{i}}_{a_{i}}$ so that the final state obtained by
$\mathsf{B}$ has the form

$\sigma_{a_{1}\cdots
a_{N}}=\mathcal{E}^{\mathsf{A}_{1}}_{a_{1}}\otimes\cdots\otimes\mathcal{E}^{\mathsf{A}_{N}}_{a_{N}}[\rho^{\bm{\mathsf{A}}}]$
(2)

The decoding by $\mathsf{B}$ is performed using a positive operator-valued
measure (POVM) $\\{\Pi_{b}\\}_{b\in\mathcal{B}}$ so that the generated MAC has
transition probabilities

$p(b|a_{1}\cdots a_{N})=\textrm{Tr}\left[\Pi_{b}(\sigma_{a_{1}\cdots
a_{N}})\right].$ (3)

Here we do not require that the output set $\mathcal{B}$ be equivalent to the
input set $\bm{\mathcal{A}}$. For instance in the task of quantum
fingerprinting described above, $\mathcal{B}=[2]$ and the value $b$ just
represents partial information about the collective inputs
$(a_{1},a_{2},\cdots,a_{N})$.

The crucial aspect of our approach is that we demand a strict accounting of
all particles used in the communication protocol, and we prohibit the use of
more particles than what is present in the initial state $\rho$. Hence, the
local encoding maps $\mathcal{E}^{\mathsf{A}_{i}}_{a_{i}}$ need to be
restricted so that they cannot increase particle number. Even more, to make
this constraint experimentally feasible, we require that each map be
implementable by a process that preserves overall particle number. This can be
modeled by giving party $\mathsf{A}$ access to a collection of ancilla ports
$\mathsf{E}_{1},\mathsf{E}_{2},\cdots,\mathsf{E}_{K}$, with each port
$j=1,\cdots,K$ having its own set of number states
$\\{|0\rangle^{\mathsf{E}_{j}},|1\rangle^{\mathsf{E}_{j}},\cdots\\}$ (see Fig.
2). Here we have temporarily omitted the party-labeling subscript on
$\mathsf{A}$ for simplicity. A valid encoding map will then have a dilation
$U$ on systems $\mathsf{A},\mathsf{E}_{1},\cdots,\mathsf{E}_{K}$ that is
number-preserving. More precisely, for every integer $0\leq J\leq M$, the
dilation $U$ must satisfy

$U\left[|x\rangle_{\mathsf{A}}|x_{1}\rangle_{\mathsf{E}_{1}}\cdots|x_{K}\rangle_{\mathsf{E}_{K}}\right]\in\mathcal{H}^{\mathsf{A}\mathsf{E}_{1}\cdots\mathsf{E}_{K}}_{J}$
(4)

whenever $x+\sum_{i=1}^{K}x_{i}=J$. Since no additional particles can be
introduced along the path to $\mathsf{B}$, we require that the ancilla systems
always begin in the vacuum state
$|0\rangle_{\mathsf{E}}:=|0\rangle_{\mathsf{E}_{1}}\cdots|0\rangle_{\mathsf{E}_{K}}$.
Then every allowed encoding map on system $\mathsf{A}$ will have the form

$\mathcal{E}(\rho^{\mathsf{A}})=\textrm{Tr}_{\mathsf{E}}\left[U(\rho^{\mathsf{A}}\otimes|0\rangle\langle
0|^{\mathsf{E}})U^{\dagger}\right],$ (5)

where $U$ has the block-diagonal form of Eq. (4). It is natural to assume that
each party has access to some local randomness, and so convex combinations of
these maps are also allowed.

######  Definition 1.

A completely positive trace-preserving (CPTP) map is called number-preserving
(N-P) if it can be written as a convex combination of channels each having the
form of Eq. (5).

Figure 2: The number-preserving (N-P) encoding maps have a dilation in which
overall particle number is preserved. The effective channel on system $A$ is
obtained by tracing out the ancilla systems $E_{1},E_{2},\cdots,E_{k}$, and
the output is sent to the decoder.

The structure of an N-P map $\mathcal{E}$ can be characterized in terms of its
Kraus operators. Here we restrict attention to $M$ bosons occupying the input
mode of party $\mathsf{A}$ since the fermionic case is formally equivalent to
the $M=1$ bosonic case. Let
$\bm{\mathsf{E}}:=\mathsf{E}_{1},\cdots,\mathsf{E}_{K}$ denote the collection
of all ancilla ports for a given N-P operation. We then write

$U=\sum_{m=0}^{M}|\psi_{m}\rangle\langle m,0|^{\mathsf{A}\bm{\mathsf{E}}}$ (6)

where

$|\psi_{m}\rangle^{\mathsf{A}\bm{\mathsf{E}}}=\sum_{k=0}^{m}|k\rangle|\varphi_{m,m-k}\rangle$
(7)

and $|\varphi_{m,m-k}\rangle$ is an $(m-k)$-particle state for systems
$\bm{\mathsf{E}}$. Let $\\{|\mathbf{e}_{n,\lambda}\rangle\\}_{n,\lambda}$ be
an orthonormal basis of $\mathcal{H}^{\bm{\mathsf{E}}}$ such that
$|\mathbf{e}_{n,\lambda}\rangle$ is an $n$-particle state. Here,
$\lambda=1,\cdots,\binom{n+K-1}{n}$ is ranging over the number of ways $n$
particles can be distributed among the $K$ ancilla ports $\bm{\mathsf{E}}$.
Then a partial contraction with $|\mathbf{e}_{n,\lambda}\rangle$ on systems
$\bm{\mathsf{E}}$ will lead to

$\langle\mathbf{e}_{n,\lambda}|\psi_{m}\rangle^{\mathsf{A}\bm{\mathsf{E}}}=c_{n,\lambda,m}|m-n\rangle$
(8)

with $c_{n,\lambda,m}=0$ if $n>m$. Thus, the induced map on system
$\mathsf{A}$ will have Kraus operators

$\displaystyle E_{n,\lambda}=\sum_{m=n}^{M}c_{n,\lambda,m}|m-n\rangle\langle
m|,$ (9)

with $n=0,\cdots,M$ and $\lambda=1,\cdots,\binom{n+K-1}{n}$. The range of
$\lambda$ can grow unbounded for each value of $n>0$ by taking more ancilla
ports; however when $n=0$, there is only one permissible value of $\lambda$
regardless of the size of $K$. Each $E_{n,\lambda}$ can be seen as a matrix
whose only non-negative elements are on the $n^{\text{th}}$ upper diagonal.
Conversely, suppose we have a complete set of Kraus operators having the form
of Eq. (9). A number-preserving dilation can be formed by defining states
$|\varphi_{m,m-k}\rangle=\sum_{\lambda}c_{m-k,\lambda,m}|\mathbf{e}_{m-k,\lambda}\rangle$
and then using the above construction. We summarize in the following
Proposition

######  Proposition 1.

A CPTP map $\mathcal{E}$ is N-P if and only if it is a convex combination of
CPTP maps, each of which has Kraus operators $\\{E_{n,\lambda}\\}_{n,\lambda}$
satisfying Eq. (9) for some finite $K$.

We note that these operations represent a subset of $U(1)$-covariant
operations [26]. However there is a subtle constraint on the index $\lambda$
when $n=0$ that does not appear in the definition of a $U(1)$-covariant map.

###  2.2 MACs with a Single Quantum Particle

In this work, we focus on MACs that can be generated by a single particle and
so henceforth we will take $M=1$ exclusively. In this case, the structure of a
general N-P map has a particularly nice form. From Eq. (9), a full set of
Kraus operators will have the form $\\{A,B_{\lambda}\\}_{\lambda=1}^{K}$ with
$A=\left(\begin{smallmatrix}1&0\\\ 0&y\end{smallmatrix}\right)$ and
$B_{\lambda}=\left(\begin{smallmatrix}0&z_{\lambda}\\\
0&0\end{smallmatrix}\right)$, and the normalization constraint being
$1=|y|^{2}+\sum_{\lambda}|z_{\lambda}|^{2}$. It is easy to see this map can be
equivalently represented by Kraus operators $\\{A,B\\}$ in which

$\displaystyle A$ $\displaystyle=\begin{pmatrix}1&0\\\ 0&y\end{pmatrix}$
$\displaystyle B$ $\displaystyle=\begin{pmatrix}0&z\\\ 0&0\end{pmatrix}$ (10)

with $z=\sum_{\lambda}|z_{\lambda}|^{2}$. In summary, for $M=1$, an N-P
operation is simply a mixture of amplitude damping channels. Furthermore, to
physically implement them, no more than a single ancilla port $\mathsf{E}_{1}$
is needed, e.g. phase encoding with $|y|=1$ and path blocking with $y=0$ can
be realized with no ancilla port, and an arbitrary damping operation with
$0<y<1$ can be implemented by coupling vacuum state with a beam-spiltter.

######  Definition 2.

For fixed input/output sets $\bm{\mathcal{A}}$ and $\mathcal{B}$, an $N$-local
quantum MAC is any channel in which $p(b|a_{1}\cdots
a_{N})=\textrm{Tr}\left[\Pi_{b}(\sigma_{a_{1}\cdots a_{N}})\right]$, with
$\sigma_{a_{1}\cdots a_{N}}$ being a single-particle state encoded by N-P
operations. The collection of all such channels will be denoted as
$\mathcal{Q}_{N}(\bm{\mathcal{A}};\mathcal{B})$, or simply $\mathcal{Q}_{N}$
when the input/output sets are clear.

It is also interesting to consider the family of MACs that can be generated by
a fixed input state $\rho^{\bm{\mathsf{A}}}$ under the restriction of N-P
encoding. We will write this set as
$\mathcal{Q}_{N}(\bm{\mathcal{A}};\mathcal{B};\rho)$, or simply
$\mathcal{Q}_{N}(\rho)$. According to the formalism introduced here, we thus
have

$\mathcal{Q}_{N}=\bigcup_{\rho\in\mathcal{B}(\mathcal{H}_{1}^{\bm{\mathsf{A}}})}\mathcal{Q}_{N}(\rho).$
(11)

###  2.3 MACs with a Single Classical Particle

The classical case can easily be modeled by taking the initial state
$\rho^{\bm{\mathsf{A}}}$ to be diagonal in the number basis. The classical N-P
operations correspond to $U$ being a permutation in Eq. (4) and the decoding
POVM being a projective measurement in the number basis followed by some post-
processing of the measurement outcome.

To characterize the generated channels, we work this process out in more
detail. Every single-particle classical state has the form

$\rho_{\text{cl}}^{\bm{\mathsf{A}}}=\sum_{i=1}^{N}p_{i}|\mathbf{e}_{i}\rangle\langle\mathbf{e}_{i}|,$
(12)

where $\mathbf{e}_{i}$ is the $i^{\text{th}}$ unit vector and
$|\mathbf{e}_{i}\rangle:=|0\rangle_{\mathsf{A}_{1}}\cdots|1\rangle_{\mathsf{A}_{i}}\cdots|0\rangle_{\mathsf{A}_{N}}$.
This can be understood as sending a classical particle (like a tennis ball)
along path $i$ with probability $p_{i}$. A local N-P operation amounts to
stochastically letting the particle continue along its respective path or
blocking it from reaching $\mathsf{B}$. For each party $\mathsf{A}_{i}$, we
can model this action by an encoding map
$q_{i}:\mathcal{A}_{i}\to\mathcal{M}_{i}:=\\{0,\mathbf{e}_{i}\\}$ with
$q_{i}(0|a_{i})$ being the probability that the particle along path $i$ is
blocked for input $a_{i}$ and $q_{i}(\mathbf{e}_{i}|a_{i})$ being the
probability that it is transmitted. Hence for input state
$|\mathbf{e}_{i}\rangle\langle\mathbf{e}_{i}|$, the state received by
$\mathsf{B}$ is

$\displaystyle\sigma_{a_{i}}$
$\displaystyle=\bigotimes_{j\not=i}|0\rangle\langle
0|^{\mathsf{A}_{j}}\otimes\mathcal{E}^{\mathsf{A}_{i}}_{a_{i}}(|1\rangle\langle
1|)$
$\displaystyle=q_{i}(\mathbf{e}_{i}|a_{i})|\mathbf{e}_{i}\rangle\langle\mathbf{e}_{i}|^{\bm{\mathsf{A}}}+q_{i}(0|a_{i})|0\rangle\langle
0|^{\bm{\mathsf{A}}}.$ (13)

The decoding process of party $B$ is defined by a projective measurement with
classical post-processing. Physically, this amounts to party $B$ examining
each path to see if it contains a particle, and then sampling from
$\mathcal{B}$ with probability distribution $d(b|\mathbf{e}_{i})$ if a
particle is received along path $i$ and distribution $d(b|0)$ if no particle
is received. The stochastic mapping
$d:\cup_{i=1}^{N}\mathcal{M}_{i}\to\mathcal{B}$ with transition probabilities
$d(b|\mathbf{e}_{i})$ is referred to as the decoder, and the channel obtained
after averaging over all input states is

$p(b|a_{1}\cdots
a_{N})=\sum_{i=1}^{N}p_{i}[d(b|0)q_{i}(0|a_{i})+d(b|\mathbf{e}_{i})q_{i}(\mathbf{e}_{i}|a_{i})]$
(14)

######  Definition 3.

Any channel admitting a decomposition like Eq. (14) will be called an
$N$-local classical MAC. For given input/output sets $\bm{\mathcal{A}}$ and
$\mathcal{B}$, we denote the family of all such channels by
$\mathcal{C}_{N}(\bm{\mathcal{A}};\mathcal{B})$, or simply $\mathcal{C}_{N}$.

###  2.4 Shared Randomness Models

Figure 3: When randomness is shared between the source and the decoder, the
decoder knows which path the particle takes, and the generated channels have
the form of Eq. (16). These MACs constitute the set
$\mathcal{C}^{\prime}_{N}(\bm{\mathcal{A}},\mathcal{B})$.

We can modify the communication setup of Fig. 1 by equipping the senders and
receiver with various additional resources. In this section, we introduce
three additional communication models that have clear operational meaning. We
will see that these three models, along with $\mathcal{C}_{N}$ previously
defined, are all equivalent when the output is binary (Proposition 2) , while
they may be distinct when $|\mathcal{B}|>2$ (Tab. 1). Let us begin by
recalling the general definition of a MAC in
$\mathcal{C}_{N}(\bm{\mathcal{A}},\mathcal{B})$:

$p(b|a_{1}\cdots
a_{N})=\sum_{i=1}^{N}p_{i}\sum_{m=0,\mathbf{e}_{i}}d(b|m)q_{i}(m|a_{i}).$ (15)

####  2.4.1 Which-Path Information

Our first generalization allows the decoder to share correlations with the
particle source (see Fig. 3). Operationally, this model captures the scenario
in which the decoder knows which path the particle takes in each run of the
experiment. Crucially in this model, when the decoder receives no particle,
he/she knows which party performed the blocking operation, whereas for
channels in $\mathcal{C}_{N}$ this information is not known. MACs generated in
this scenario will have transition probabilities of the form

$\displaystyle p(b|a_{1}\cdots
a_{N})=\sum_{i=1}^{N}p_{i}\sum_{m=0,\mathbf{e}_{i}}d_{i}(b|m)q_{i}(m|a_{i}),$
(16)

and we denote the collection of these channels by
$\mathcal{C}^{\prime}_{N}(\bm{\mathcal{A}},\mathcal{B})$. Notice that now the
decoding function $d_{i}$ can depend on the path $i$. The set
$\mathcal{C}^{\prime}_{N}(\bm{\mathcal{A}},\mathcal{B})$ arises most naturally
in the context of nonlocal games where the decoder $\mathsf{B}$ (often called
a “referee”) both prepares the particle and receives it in the end [15, 33].

Figure 4: When randomness is shared between the source, the encoders, and the
decoder, the generated channels have the form of Eq. (2.4.2). These MACs
constitute the convex hull of $\mathcal{C}_{N}$ and is denoted by
$\text{conv}[\mathcal{C}_{N}(\bm{\mathcal{A}},\mathcal{B})]$.

####  2.4.2 Global Shared Randomness

An even more general model allows for shared randomness between the particle
source, the encoders, and the decoder (see Fig. 4). In the classical case,
this describes the convex hull of
$\mathcal{C}_{N}(\bm{\mathcal{A}},\mathcal{B})$, denoted by
$\text{conv}[\mathcal{C}_{N}(\bm{\mathcal{A}},\mathcal{B})]$, and a general
MAC in $\text{conv}[\mathcal{C}_{N}(\bm{\mathcal{A}},\mathcal{B})]$ has the
form

$\displaystyle p(b|a_{1}\cdots a_{N})$
$\displaystyle=\sum_{\lambda}t_{\lambda}\sum_{i=1}^{N}p_{i|\lambda}\sum_{\mathclap{m=0,\mathbf{e}_{i}}}d(b|m,\lambda)q_{i}(m|a_{i},\lambda)$
$\displaystyle=\sum_{i=1}^{N}p_{i}\sum_{\lambda}t_{\lambda|i}\sum_{\mathclap{m=0,\mathbf{e}_{i}}}d(b|m,\lambda)q_{i}(m|a_{i},\lambda).$
(17)

One way to interpret the difference between Eqns. (2.4.2) and (16) is that Eq.
(16) still allows for some private randomness in the local encoding
$q_{i}(m|a_{i})$. This is no longer the case for MACs in
$\text{conv}[\mathcal{C}_{N}(\bm{\mathcal{A}},\mathcal{B})]$, and without loss
of generality it can be assumed that the $q_{i}(m|a_{i},\lambda)$ are
deterministic functions in Eq. (2.4.2) since any randomness can be absorbed
into the distributions $t_{\lambda|i}$.

####  2.4.3 Separable MACs

A final classical model we analyze is simply a convex combination of point-to-
point channels between senders $\mathsf{A}_{i}$ and receiver $\mathsf{B}$.
This scenario removes the one-particle constraint entirely while still
maintaining locality. Since we provide a full characterization of these MACs
in Section 3.1, we highlight them in the following definition.

######  Definition 4.

Any $N$-party MAC whose transition probabilities decompose like

$p(b|a_{1}\cdots a_{N})=\sum_{i=1}^{N}p_{i}g_{i}(b|a_{i}),$ (18)

will be called separable. We denote the set of separable MACs by
$\mathcal{C}_{N}^{(\text{sep})}(\bm{\mathcal{A}};\mathcal{B})$, or simply
$\mathcal{C}_{N}^{(\text{sep})}$ when the input/output sets are clear.

Physically, any MAC in
$\mathcal{C}_{N}^{(\text{sep})}(\bm{\mathcal{A}};\mathcal{B})$ can be
implemented by point-to-point communication between party $\mathsf{A}_{i}$ and
$\mathsf{B}$ with probability $p_{i}$ and using a noisy channel with
transition probabilities $g_{i}(b|a_{i})$. Such communication could be
facilitated by introducing more particles to the system or using internal
degrees of freedom of the single particle.

By examining Eqns. (15) – (18), we see that

$\mathcal{C}_{N}(\bm{\mathcal{A}};\mathcal{B})\subseteq\mathcal{C}^{\prime}_{N}(\bm{\mathcal{A}};\mathcal{B})\subseteq\text{conv}[\mathcal{C}_{N}(\bm{\mathcal{A}};\mathcal{B})]\subseteq\mathcal{C}_{N}^{(\text{sep})}(\bm{\mathcal{A}};\mathcal{B}).$
(19)

###  2.5 (N,K)-local MACs with a single classical particle

In both the quantum and classical scenarios considered thus far, spatial
separation is enforced between the parties and they are unable to communicate
with each other. However, we can consider relaxations to the locality
constraint and again compare the powers of classical and quantum MACs [33].
The construction is as follows (See also Fig 5). Let
$S\subseteq\\{1,2,\cdots,N\\}$ represent a subset of $|S|$ paths with $|S|<N$.
We now suppose that all parties belonging to these paths can coordinate their
signal to the receiver. This means that for each choice of messages, the
parties can map a particle traveling along any path in $S$ to any other path
in $S$. Like before, we represent this by a stochastic encoding map
$q_{S}:\bigtimes_{s\in S}\mathcal{A}_{s}\to\mathcal{M}_{S}$ where
$\mathcal{M}_{S}=\\{0,\mathbf{e}_{s}:s\in S\\}$.

Figure 5: A physical implementation of the $(N,K)$-local MAC
$\mathbf{p}_{B|\bm{A}}$ using a single particle, where at most $K$ parties are
allowed to encode jointly (the case $K=2$ is depicted). Classically, the joint
encoding will be simply implemented as a permutation between $K$ paths and the
vacuum ancilla port. The joint encoding will be represented by a stochastic
encoding map $q_{S}:\bigtimes_{s\in S}\mathcal{A}_{s}\to\mathcal{M}_{S}$ where
$\mathcal{M}_{S}=\\{0,\mathbf{e}_{s}:s\in S\\}$

######  Definition 5.

For non-negative integer $K$, a classical MAC will be called $(N,K)$-local if
it can be decomposed as

$p(b|a_{1}\cdots a_{N})=\sum_{\begin{subarray}{c}S\\\
|S|=K\end{subarray}}p_{S}\sum_{m\in\mathcal{M}_{S}}[d(b|m)q_{S}(m|(a_{s})_{s\in
S})],$ (20)

where the outer sum is over all subsets of $\\{1,2,\cdots,N\\}$ whose
cardinality is $K$, and $p_{S}$ is the probability that the particle is
initially prepared in one of the paths belonging to $S$. The collection of all
such MACs will be denoted by
$\mathcal{C}_{N,K}(\bm{\mathcal{A}};\mathcal{B})$, or simply
$\mathcal{C}_{N,K}$. Note that $\mathcal{C}_{N}=\mathcal{C}_{N,1}$.

For the sets $\mathcal{C}_{N,K}$ with $K>1$, even more models can be
considered under the introduction of shared randomness. This is due to the
fact that the receiver need not know which subset of $K$ parties are jointly
encoding, even if the initial particle is known. A somewhat less complex
scenario is when the decoder knows both the initial particle as well as the
jointly encoding parties. MACs generated in this way have the form

$p(b|a_{1}\cdots a_{N})=\sum_{\mathclap{\begin{subarray}{c}S\\\
|S|=K\end{subarray}}}p_{S}\sum_{\mathclap{m\in\mathcal{M}_{S}}}[d_{S}(b|m)q_{S}(m|(a_{s})_{s\in
S})],$ (21)

with $\mathcal{M}_{s}$ being an encoding set consisting of $K+1$ elements
$\\{0,\mathbf{e}_{s}:s\in S\\}$. We denote the collection of these MACs by
$\mathcal{C}_{N,K}^{\prime}(\bm{\mathcal{A}},\mathcal{B})$. Compare this with
the set $\mathcal{C}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$ in Eq. (20), which
consists of MACs in which the decoder $d(b|m)$ does not depend on knowledge of
the encoding parties $S$. We can also consider the convex hull
$\text{conv}[\mathcal{C}_{N}(\bm{\mathcal{A}},\mathcal{B})]$ and the set of
$(N,K)$-separable MACs,
$\mathcal{C}_{N,K}^{(\text{sep})}(\bm{\mathcal{A}},\mathcal{B})$. The latter
consists of MACs having the form

$p(b|a_{1}\cdots a_{N})=\sum_{\begin{subarray}{c}S\\\
|S|=K\end{subarray}}p_{S}g_{S}(b|(a_{s})_{s\in S}).$ (22)

Similar to Eq. (19), we have an inclusion relationship between different
$(N,K)$-local MACs as
$\mathcal{C}_{N,K}(\bm{\mathcal{A}};\mathcal{B})\subseteq\mathcal{C}^{\prime}_{N,K}(\bm{\mathcal{A}};\mathcal{B})\subseteq\text{conv}[\mathcal{C}_{N,K}(\bm{\mathcal{A}};\mathcal{B})]\subseteq\mathcal{C}_{N,K}^{(\text{sep})}(\bm{\mathcal{A}};\mathcal{B})$.
More discussion on the relationships between these classes will be given in
Section 3.3. However, we close this section by making an important observation
for binary-output MACs.

######  Proposition 2.

$\mathcal{C}_{N,K}(\bm{\mathcal{A}};[2])=\mathcal{C}_{N,K}^{(\text{sep})}(\bm{\mathcal{A}};[2])$
for arbitrary input set $\bm{\mathcal{A}}$ and any $K\geq 1$.

###### Proof.

Clearly
$\mathcal{C}_{N,K}(\bm{\mathcal{A}};[2])\subseteq\mathcal{C}_{N,K}^{(\text{sep})}(\bm{\mathcal{A}};[2])$,
conversely Let $p(b|\mathbf{a})=\sum_{i=1}^{N}p_{S}g_{S}(b|(a_{s})_{s\in S})$
be an arbitrary separable MAC with $b\in\\{0,1\\}$. Consider the deterministic
decoder $d(0|0)=1$ and $d(1|\mathbf{e}_{i})=1$ for all $i$, and encoders
$q_{S}(0|(a_{s})_{s\in S})=g_{S}(0|(a_{s})_{s\in S})$ and
$q_{S}(\mathbf{e}_{S}|(a_{s})_{s\in S})=g_{S}(1|(a_{s})_{s\in S})$, where
$\mathbf{e}_{S}$ can be any fixed element in $\mathcal{M}_{S}$. With these
choices, we can construct any point in
$\mathcal{C}_{N,K}^{(\text{sep})}(\bm{\mathcal{A}};[2])$ with point in
$\mathcal{C}_{N,K}(\bm{\mathcal{A}};[2])$ ∎

##  3 Classical MACs

Let us now examine in more detail the structure of the classical sets
$\mathcal{C}_{N}(\bm{\mathcal{A}};\mathcal{B})$ and
$\mathcal{C}_{N,K}(\bm{\mathcal{A}};\mathcal{B})$. This will allow us to make
a comparison with quantum MACs in the next section. Following the standard
approach [9], we envision each MAC in
$\mathcal{C}_{N,K}(\bm{\mathcal{A}};\mathcal{B})$ as a point
$\mathbf{p}_{B|\bm{A}}$ in
($|\mathcal{B}|\times\prod_{k=1}^{N}|\mathcal{A}_{k}|$)-dimensional Euclidean
space with coordinates $(p(b|a_{1}\cdots
a_{N}))_{b\in\mathcal{B},a_{i}\in\mathcal{A}_{i}}$. To proceed with our
analysis, the question of whether or not
$\mathcal{C}_{N,K}(\bm{\mathcal{A}};\mathcal{B})$ is convex is vitally
important. As a consequence of Proposition 2 above, when $|\mathcal{B}|=2$ the
set $\mathcal{C}_{N,K}(\bm{\mathcal{A}};[2])$ is a convex polytope whose
vertices are deterministic $K$-party MACs, which are those satisfying
$p(b|a_{1}\cdots a_{N})=p(b|a_{i_{1}},\cdots,a_{i_{K}})\in\\{0,1\\}$ for
$\\{i_{1},\cdots,i_{K}\\}\subseteq\\{1,\cdots,N\\}$. Considering all possible
groupings of $K$ parties with
$M=\max\\{|\mathcal{A}_{1}|,\cdots,|\mathcal{A}_{N}|\\}$, we see there are no
more than $\binom{N}{K}2^{M^{K}}$ such vertices, denoted by
$\mathbf{v}_{\lambda}$, and $\mathcal{C}_{N,K}$ is the polytope contained in
their convex hull; i.e.

$\mathbf{p}_{B|\bm{A}}\in\mathcal{C}_{N,K}\quad\Leftrightarrow\quad\mathbf{p}_{B|\bm{A}}=\sum_{\lambda}p_{\lambda}\mathbf{v}_{\lambda}$
(23)

for a valid probability distribution $(p_{\lambda})_{\lambda}$.

Before moving forward, let us first recall a few general facts about convex
and affine sets (see Ref. [5] for the details). An affine subspace
$\mathcal{A}\subset\mathbb{R}^{d}$ is a collection of points that is closed
under affine combinations, i.e. linear combinations of the form
$\sum_{i}\lambda_{i}\mathbf{v}_{i}$ with $\sum_{i}\lambda_{i}=1$. A collection
of points $\\{\mathbf{v}_{0},\mathbf{v}_{1},\cdots\mathbf{v}_{l}\\}$ in
$\mathbb{R}^{d}$ are called affinely independent if the $l$ vectors
$\\{\mathbf{v}_{1}-\mathbf{v}_{0},\cdots,\mathbf{v}_{l}-\mathbf{v}_{0}\\}$ are
linearly independent. An affine subspace $\mathcal{A}$ is said to have
dimension $\dim\mathcal{A}$ if the maximum number of affinely independent
points it contains is $\dim\mathcal{A}+1$. For an arbitrary collection of
points $\mathcal{P}\subset\mathbb{R}^{d}$, its dimension is the dimension of
the smallest affine subspace that contains $\mathcal{P}$. If all the vectors
in $\mathcal{P}$ are known to satisfy a system of $k$ linearly independent
equations, then Gaussian elimination shows that $\mathcal{P}$ is contained in
an affine subspace of dimension $d-k$. If, further, $d-k+1$ affinely
independent vectors are shown to exist in $\mathcal{P}$, then $\mathcal{P}$
has dimension $d-k$.

Let $\mathcal{P}$ be a convex polytope. For a fixed
$\mathbf{r}\in\mathbb{R}^{d}$ and $s\in\mathbb{R}$, we say that an inequality
$\mathbf{v}\cdot\mathbf{r}\leq s$ is “valid” for a $\mathcal{P}$ if it is
satisfied by every $\mathbf{v}\in\mathcal{P}$. Valid inequalities of a
polytope are useful when trying to certify that some element $\mathbf{v}$ is
not a member of $\mathcal{P}$ since it suffices to show that $\mathbf{v}$ does
not satisfy the particular relation $\mathbf{v}\cdot\mathbf{r}\leq s$, a
simple linear calculation. On the other hand, if $\mathbf{v}$ satisfies the
inequality, then in general one cannot conclude that
$\mathbf{v}\in\mathcal{P}$; additional conditions are needed to certify
membership. Specifically, the Weyl-Minkowski Theorem states that any
$d$-dimensional polytope $\mathcal{P}$ can be characterized by a finite family
of valid and “tight” inequalities. In other words,

$\mathbf{v}\in\mathcal{P}\Leftrightarrow\mathcal{P}=\\{\mathbf{v}\in\mathbb{R}^{d}\;|\>\mathbf{v}\cdot\mathbf{r}_{\lambda}\leq
s_{\lambda},\;\forall\lambda=1,\cdots,n\\}.$ (24)

Associated with each inequality $\mathbf{v}\cdot\mathbf{r}_{\lambda}\leq
s_{\lambda}$ is the hyperplane
$H_{\lambda}=\\{\mathbf{v}\;|\;\mathbf{v}\cdot\mathbf{r}_{\lambda}=s_{\lambda}\\}$,
and since $\mathcal{P}$ is $d$-dimensional, its intersection with
$H_{\lambda}$ forms a $(d-1)$-dimensional affine subspace. The property $\dim
H_{\lambda}\cap\mathcal{P}=d-1$ is what it means for the corresponding
inequality to be tight, and hence a point $\mathbf{v}$ is an element of
$\mathcal{P}$ if and only if it satisfies a finite family of valid and tight
inequalities. In the language of quantum information science, these are known
as tight Bell Inequalities [44, 50].

Returning to the problem at hand, we aim to compute tight Bell Inequalities
for the polytope $\mathcal{C}_{N,K}(\bm{\mathcal{A}};\mathcal{B})$. Moving
from the V-representation of $\mathcal{C}_{N,K}(\bm{\mathcal{A}};\mathcal{B})$
given in Eq. (23) to an H-representation in the form of Eq. (24) can be a
formidable task. We rely mainly on numerical software such as PORTA, which for
small dimensions performs the calculation using the Fourier-Motzkin
elimination method in a short amount of time [14]. However, we are able to
analytically prove that the so-called fingerprinting inequality (see Eq. (49))
is a tight Bell Inequality for arbitrary $N$ and $K$ when dealing with binary
inputs and output. This is done in Section 3.2.3 by first calculating the
dimension of $\mathcal{C}_{N,K}([2]^{N};[2])$ and then showing that a
sufficiently large number of affinely independent points saturate the
inequality. The case of $N$-local MACs (i.e. $K=1$) is special in that its
dimension is $N+1$ and the only inequalities are positivity constraints. We
turn next to establishing this result.

###  3.1 $N$-Local and Separable MACs

In this section, we aim to characterize the sets of $N$-local MACs
$\mathcal{C}_{N}(\bm{\mathcal{A}};\mathcal{B})$. As indicated above,
$\mathcal{C}_{N}(\bm{\mathcal{A}};\mathcal{B})$ is a convex polytope when
$|\mathcal{B}|=2$, whereas this fails to be the case when $|\mathcal{B}|>2$
(see Section 3.3). To provide a unified treatment based on convexity, we will
therefore consider
$\text{conv}[\mathcal{C}_{N}(\bm{\mathcal{A}};\mathcal{B})]$ and the more
general $\mathcal{C}_{N}^{(\text{sep})}(\bm{\mathcal{A}};\mathcal{B})$ when
$|\mathcal{B}|>2$.

Important quantities in our study of $N$-local polytopes are the so-called
second-order interference [8, 27, 37, 54]. The physical meaning of this name
originates from double-slit experiments, as will be described more in Section
4. However, for the moment we simply identify it as a particular linear
functional on the set of $N$-partite MACs [7]. For two parties with binary
inputs, the second-order interference is given by

$I_{2}=p(0|0,0)+p(0|1,1)-p(0|0,1)-p(0|1,0).$ (25)

As we add more parties and more inputs/outputs, we consider this basic linear
combination for certain pairs of two-party inputs. For a given MAC
$\mathbf{p}_{B|\bm{A}}$, let $\mathcal{M}^{(i,j)}(\mathbf{p}_{B|\bm{A}})$
denote the set of all two-sender MACs obtained by fixing different inputs for
$a_{k}$, $k\not=i,j$. Then define $I_{2}^{(i,j)}(\mathbf{p}_{B|\bm{A}})$ as:

$\displaystyle\max\;$
$\displaystyle\left|p(b|a_{i},a_{j})+p(b|a_{i}^{\prime},a_{j}^{\prime})-p(b|a_{i},a_{j}^{\prime})-p(b|a_{i}^{\prime},a_{j})\right|$
s.t
$\displaystyle\;\;\mathbf{p}_{B|A_{i}A_{j}}\in\mathcal{M}^{(i,j)}(\mathbf{p}_{B|\bm{A}})$
$\displaystyle\;\;b\in\mathcal{B},\;\;a_{i},a_{i}^{\prime}\in\mathcal{A}_{i},\;\;a_{j},a_{j}^{\prime}\in\mathcal{A}_{j}.$
(26)

If $I_{2}^{(i,j)}(\mathbf{p}_{B|\bm{A}})=0$, then parties $\mathsf{A}_{i}$ and
$\mathsf{A}_{j}$ cannot demonstrate any nonzero second-level interference
using $\mathbf{p}_{B|\bm{A}}$, regardless of what inputs the other parties
choose and what output is considered.

######  Definition 6.

The set of all $N$-sender MACs $\bm{\mathcal{A}}\to\mathcal{B}$ whose second-
order interference vanish for all $i,j$ will be denoted by
$\mathfrak{I}_{N}(\bm{\mathcal{A}};\mathcal{B})$; i.e.

$\mathbf{p}_{B|\bm{A}}\in\mathfrak{I}_{N}(\bm{\mathcal{A}};\mathcal{B})\Leftrightarrow
I_{2}^{(i,j)}(\mathbf{p}_{B|\bm{A}})=0\;\;\;\forall(i,j).$ (27)

The main result of this section is that
$\mathfrak{I}_{N}(\bm{\mathcal{A}};\mathcal{B})$ corresponds precisely to the
set of $N$ separable MACs. For binary input/output MACs, this fact has also
been independently established in the Masters Thesis of Horvat Ref.[32]. Here
we prove the relationship for arbitrary inputs and outputs.

######  Theorem 1.

$\mathcal{C}^{(\text{sep})}_{N}(\bm{\mathcal{A}};\mathcal{B})=\mathfrak{I}_{N}(\bm{\mathcal{A}};\mathcal{B})$
(28)

for any $\bm{\mathcal{A}}$ and $\mathcal{B}$.

Since
$\mathcal{C}^{(\text{sep})}_{N}(\bm{\mathcal{A}};[2])=\mathcal{C}_{N}(\bm{\mathcal{A}};[2])$
(as shown in Proposition 2), this theorem immediately implies the following.

######  Corollary 1.

$\mathcal{C}_{N}(\bm{\mathcal{A}};[2])=\mathfrak{I}_{N}(\bm{\mathcal{A}};[2])$
(29)

for any $\bm{\mathcal{A}}$.

We now turn to the proof of Theorem 1. From a direct evaluation of
$I_{2}^{(i,j)}(\mathbf{p}_{B|\bm{A}})$ for any separable
$\mathbf{p}_{B|\bm{A}}$ given in Eq. (18), it is easy to verify that
$\mathcal{C}^{(\text{sep})}_{N}(\bm{\mathcal{A}};\mathcal{B})\subseteq\mathfrak{I}_{N}(\bm{\mathcal{A}};\mathcal{B})$.

To prove the converse, the main idea will be to identify the extreme points of
$\mathfrak{I}_{N}(\bm{\mathcal{A}};\mathcal{B})$. Recall that a MAC
$\mathbf{p}_{B|\bm{A}}\in\mathfrak{I}_{N}(\bm{\mathcal{A}};\mathcal{B})$ is
extremal if it cannot be decomposed into a convex combination of other MACs
belonging to $\mathfrak{I}_{N}(\bm{\mathcal{A}};\mathcal{B})$, i.e.
$\mathbf{p}_{B|\bm{A}}\not=\lambda\mathbf{p}_{B|\bm{A}}^{\prime}+(1-\lambda)\mathbf{p}_{B|\bm{A}}^{\prime\prime}$
for distinct
$\mathbf{p}_{B|\bm{A}}^{\prime},\mathbf{p}_{B|\bm{A}}^{\prime\prime}\in\mathfrak{I}_{N}(\bm{\mathcal{A}};\mathcal{B})$
and $\lambda\in(0,1)$. We will show that every extremal MAC in
$\mathfrak{I}_{N}(\bm{\mathcal{A}};\mathcal{B})$ is local deterministic. This
means that it has the form

$p(b|a_{1}\cdots a_{N})=\delta_{bf(a_{i})}$ (30)

for some party $\mathsf{A}_{i}$ and function
$f:\mathcal{A}_{i}\to\mathcal{B}$. Since these MACs belong to
$\mathcal{C}^{(\text{sep})}_{N}(\bm{\mathcal{A}};\mathcal{B})$, it follows
that
$\mathfrak{I}_{N}(\bm{\mathcal{A}};\mathcal{B})\subseteq\mathcal{C}^{(\text{sep})}_{N}(\bm{\mathcal{A}};\mathcal{B})$.
We first prove the case when $\bm{\mathcal{A}}=[2]\times[2]$.

######  Lemma 1.

Every extremal MAC in $\mathfrak{I}_{2}([2]\times[2];\mathcal{B})$ is local
deterministic, and therefore
$\mathfrak{I}_{N}([2]\times[2];\mathcal{B})\subseteq\mathcal{C}^{(\text{sep})}_{N}([2]\times[2];\mathcal{B})$.

###### Proof.

We begin by expressing
$\mathfrak{I}_{2}([2]\times[2];\mathcal{B})=\\{p_{B|\bm{A}}\;|\;\text{such
that Eqns. \eqref{Eq:I2-cons-1} -- \eqref{Eq:I2-cons-3} hold}\\}$:

$\displaystyle 1$
$\displaystyle=\sum_{b\in\mathcal{B}}p(b|a_{1},a_{2}),\forall(a_{1},a_{2})\neq(1,1)$
(31a) $\displaystyle 0$ $\displaystyle=p(b|0,0)+p(b|1,1)-p(b|0,1)-p(b|1,0)$
(31b) $\displaystyle 0$ $\displaystyle\leq p(b|a_{1},a_{2}).$ (31c)

Note that $1=\sum_{b}p(b|1,1)$ is also implied when Eqns. (31a) and (31b)
hold. If we consider MACs in $\mathfrak{I}_{2}([2]\times[2];\mathcal{B})$ as
elements of $\mathbb{R}^{4|\mathcal{B}|}$ (with components
$p(b|a_{1},a_{2})$), then $\hat{p}_{B|\bm{A}}$ is extremal if and only if
$4|\mathcal{B}|$ linearly independent constraints are binding (i.e. tight)
among those listed in Eqns. (31a)–(31c). We see that Eqns. (31a) and (31b)
represent $3+|\mathcal{B}|$ equality constraints. Thus, the remaining binding
constraints must come from (31c). Hence if $\hat{p}_{B|\bm{A}}$ is extremal,
then it has at least $4|\mathcal{B}|-(3+|\mathcal{B}|)=3|\mathcal{B}|-3$
vanishing probabilities $\hat{p}(b|a_{1},a_{2})$.

For the case when $|\mathcal{B}|=2$, an extremal $\hat{p}_{B|\bm{A}}$ must
have at least $3$ vanishing probabilities. Equations (31a) and (31b) then
imply that the only possibilities for
$(\hat{p}(0|0,0),\hat{p}(0|0,1),\hat{p}(0|1,0),\hat{p}(0|1,1))$ are
$(0,0,0,0)$, $(1,1,1,1)$, $(0,1,0,1)$, $(1,0,1,0)$, $(0,0,1,1)$, and
$(1,1,0,0)$. Each of these corresponds to a deterministic local MAC (i.e
having the form of Eq. (30)).

For the case when $|\mathcal{B}|=3$, an extremal $\hat{p}_{B|\bm{A}}$ must
have at least $6$ vanishing probabilities, and let us consider these for each
output $b\in\\{0,1,2\\}$. If there is some $b^{\prime}$ such that
$\hat{p}(b^{\prime}|a_{i},a_{j})=0$ for three (or more) distinct input pairs,
then Eq. (31b) implies that it also vanishes for the fourth input pair. In
this event, outcome $b^{\prime}$ occurs with zero probability and
$\hat{p}_{B|\bm{A}}$ reduces to an extremal MAC with $|\mathcal{B}|=2$; i.e.
it is a local deterministic MAC. The only other alternative is that for each
$b\in\\{0,1,2\\}$, the probabilities $\hat{p}(b|a_{i},a_{j})$ vanish for
exactly two input pairs $(a_{i},a_{j})$. Hence only two nonzero terms can
appear on the right-hand side of Eq. (31b) for each $b\in\\{0,1,2\\}$. This
means, up to relabeling, we must have relationships of the form
$1=\hat{p}(0|0,0)=\hat{p}(0|0,1)$, $\hat{p}(1|1,1)=\hat{p}(1|1,0)>0$, and
$\hat{p}(2|1,1)=\hat{p}(2|1,0)>0$. However, Eq. (31a) then does not represent
three additional linearly independent constraints, and so $\hat{p}_{B|\bm{A}}$
cannot be extremal.

For $|\mathcal{B}|>3$, the lemma is easily proven by induction. Indeed,
suppose that every extremal MAC is local deterministic for
$|\mathcal{B}|=N\geq 3$. Then consider an extremal MAC $\hat{p}_{B|\bm{A}}$ in
$\mathfrak{I}_{2}([2]\times[2];[N+1])$. By the above observation, there must
be at least $3|\mathcal{B}|-3$ vanishing probabilities. Consequently, there
will be at least one outcome $b^{\prime}$ such that
$\hat{p}(b^{\prime}|a_{i},a_{j})=0$ for three (or more) distinct input pairs
provided $3|\mathcal{B}|-3>2|\mathcal{B}|$, which is true since
$|\mathcal{B}|=N+1\geq 4$. Thus, Eq. (31b) requires that
$\hat{p}(b^{\prime}|a_{i},a_{j})$ vanishes for the fourth input pair as well.
Like before, this means that outcome $b^{\prime}$ occurs with zero
probability. Hence $\hat{p}_{B|\bm{A}}$ is extremal in
$\mathfrak{I}_{2}([2]\times[2];[N])$, which by our inductive assumption means
that $\hat{p}_{B|\bm{A}}$ is local deterministic.

∎

We next consider the set
$\mathfrak{I}_{2}(\mathcal{A}_{1}\times\mathcal{A}_{2};\mathcal{B})$ for
arbitrary $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$. It follows as a corollary
of Lemma 1 that
$\mathfrak{I}_{2}(\mathcal{A}_{1}\times\mathcal{A}_{2};\mathcal{B})\subseteq\mathcal{C}^{(\text{sep})}_{2}(\mathcal{A}_{1}\times\mathcal{A}_{2};\mathcal{B})$.
This can be seen by considering binary representations of the inputs
$a_{1}=a_{11}\cdots a_{1m}$ and $a_{2}=a_{21}\cdots a_{2n}$, where
$a_{1i},a_{2j}\in[2]$. For simplicity, suppose that $m=n=2$, but the general
case follows by the same reasoning. Suppose that
$p(b|a_{11}a_{12},a_{21}a_{22})$ are transition probabilities for a MAC in
$\mathfrak{I}_{2}([4]\times[4];[2])$. The key observation is that for each
fixed values of $a_{12}$ and $a_{22}$, the probabilities
$p(b|a_{11}a_{12},a_{21}a_{22})$ describe a MAC in
$\mathfrak{I}_{2}([2]\times[2];\mathcal{B})$ with inputs $a_{11}$ and
$a_{21}$. By Lemma 1, we have a separable decomposition of
$p(b|a_{11}a_{12},a_{21}a_{22})$ as:

$\displaystyle\lambda
p(b|a_{11}a_{12},a_{22})+(1-\lambda)p(b|a_{12},a_{21}a_{22}).$

Next, we let only $a_{11}$ and $a_{22}$ vary. In doing so we observe that
$p(b|a_{11}a_{12},a_{22})\in\mathfrak{I}_{2}([2]\times[2];\mathcal{B})$ so
that

$\displaystyle
p(b|a_{11}a_{12},a_{22})=\lambda_{2}p(b|a_{11}a_{12})+(1-\lambda_{2})p(b|a_{12},a_{22}).$

Similar reasoning for a varying $a_{12}$ and $a_{21}$ allows us to decompose

$\displaystyle p(b|a_{12},a_{21}a_{22})$
$\displaystyle=\lambda_{3}p(b|a_{12},a_{22})+(1-\lambda_{3})p(b|a_{21}a_{22}).$

Thus $p(b|a_{11}a_{12},a_{21}a_{22})$ becomes

$\displaystyle\mu_{1}p(b|a_{12},a_{22})+\mu_{2}p(b|a_{11}a_{12})+\mu_{3}p(b|a_{21}a_{22})$

for some probabilities $\mu_{i}$. Finally, by letting just the inputs $a_{12}$
and $a_{22}$ vary, we obtain the decomposition

$\displaystyle p(b|a_{11}a_{12},a_{21}a_{22})$ $\displaystyle=\mu_{1}(\nu
p(b|a_{12})+(1-\nu)p(b|a_{22}))$
$\displaystyle+\mu_{2}p(b|a_{11}a_{12})+\mu_{3}p(b|a_{21}a_{22}).$

Clearly this is an element of
$\mathcal{C}^{(\text{sep})}_{2}(\mathcal{A}_{1}\times\mathcal{A}_{2};\mathcal{B})$.
In general, for inputs $a_{1}=a_{11}\cdots a_{1m}$ and $a_{2}=a_{21}\cdots
a_{2n}$, one considers varying each pair of binary inputs $(a_{1i},a_{2j})$ to
construct a separable decomposition.

This binary splitting technique also works to scale up the number of parties.
Specifically if $p(b|\mathbf{a})$ are transition probabilities for an
$N$-sender MAC in $\mathfrak{I}_{N}(\bm{\mathcal{A}};\mathcal{B})$, then one
fixes the inputs for all but two senders. What remains is a two-party MAC in
$\mathfrak{I}_{2}(\mathcal{A}_{1}\times\mathcal{A}_{2};\mathcal{B})$ that can
be separated between the two non-fixed senders. On each of the remaining
branches, again fix all but two of the senders, and a further separation can
be performed. Reiterating this procedure, one arrives at an $N$-party
separable MAC. These arguments thus establish
$\mathfrak{I}_{N}(\bm{\mathcal{A}};\mathcal{B})\subseteq\mathcal{C}^{(\text{sep})}_{N}(\bm{\mathcal{A}};\mathcal{B})$.

###  3.2 Binary $(N,K)$-Local Channels

We next turn to $(N,K)$-local MACs. In this section we restrict attention to
binary inputs and output (i.e. $\mathcal{A}_{i}=\mathcal{B}=[2]$), and to
simplify the notation, we write
$\mathcal{C}_{N,K}=\mathcal{C}_{N,K}([2]^{N};[2])$. A more general discussion
on MACs $\mathcal{C}_{N}(\bm{\mathcal{A}};\mathcal{B})$ with arbitrary inputs
and outputs will be given in the supplementary [1]. In light of Proposition 2,
every MAC in $\mathcal{C}_{N,K}$ is separable and therefore has a
decomposition like Eq. (22).

Much of our analysis will involve generalizing the $I_{2}$ quantity given in
Eq. (25). This can be done by considering the expression

$\displaystyle
I_{K}=\sum_{a_{1},\cdots,a_{K}\in\\{0,1\\}}\prod_{i=1}^{K}(-1)^{a_{i}}p(0|a_{1}\cdots
a_{K}),$ (32)

which is the $K^{\text{th}}$-order interference [54]. For $N$ parties, take
$S\subseteq\\{1,\cdots,N\\}$ with $|S|=K$, and let
$\mathcal{M}^{(S)}(\mathbf{p}_{B|\bm{A}})$ be the collection of $K$-sender
MACs obtained by fixing different inputs for $a_{i}\in\\{0,1\\}$ with
$i\not\in S$. Then define the quantity

$\displaystyle
I_{K}^{(S)}(\mathbf{p}_{B|\bm{A}}):=\max\left\\{\sum_{a_{1},\cdots,a_{K}\in\\{0,1\\}}\prod_{i=1}^{K}(-1)^{a_{i}}p(0|a_{1}\cdots
a_{K})\;\bigg{|}\;\mathbf{p}_{B|A_{1},\cdots,A_{K}}\in\mathcal{M}^{(S)}(\mathbf{p}_{B|\bm{A}})\right\\}.$
(33)

The condition $I_{K}^{(S)}(\mathbf{p}_{B|\bm{A}})=0$ means that parties $S$
have no $K^{\text{th}}$-order interference in the MAC $\mathbf{p}_{B|\bm{A}}$.
We let $\mathfrak{I}_{N,K}$ denote the collection of MACs such that
$I^{(S)}_{K+1}(\mathbf{p}_{B|\bm{A}})=0$ for all $S\subseteq\\{1,\cdots,N\\}$
with $|S|=K+1$. One can simply observe that
$\mathfrak{I}_{N,1}\subset\mathfrak{I}_{N,2}\subset\cdots\subset\mathfrak{I}_{N,N}$
by definition. Notice that $\mathfrak{I}_{N,1}=\mathfrak{I}_{N}([2]^{N};[2])$,
with the latter introduced in the previous section.

It is easy to see that $\mathcal{C}_{N,K}\subseteq\mathfrak{I}_{N,K}$. Indeed
by convexity it suffices to observe that
$\sum_{a_{K+1}\in\\{0,1\\}}(-1)^{a_{K+1}}p(0|a_{1},\cdots,a_{K})=0$ for all
choices of $a_{1},\cdots,a_{K}$. However, unlike the case for
$\mathcal{C}_{N,1}$, the converse inclusion is not true for $K>1$ and more
constraints are needed to characterize $\mathcal{C}_{N,K}$ than just vanishing
$(K+1)^{\text{th}}$-order interference. Nevertheless, $\mathcal{C}_{N,K}$ and
$\mathfrak{I}_{N,K}$ have the same dimension, as we demonstrate next.

####  3.2.1 The Dimension of $\mathcal{C}_{N,K}$

As explained above, $\mathcal{C}_{N,K}$ is a polytope in
$\mathbb{R}^{2^{N+1}}$. To compute the dimension of $\mathcal{C}_{N,K}$, we
will first show that its elements satisfy $2^{N}+\sum_{k=K+1}^{N}\binom{N}{k}$
linearly independent equations. We then show that
$2^{N+1}-2^{N}-\sum_{k=K+1}^{N}\binom{N}{k}+1$ affinely independent points
belong to $\mathcal{C}_{N,K}$. From this, we obtain the following theorem

######  Theorem 2.

$\dim\mathcal{C}_{N,K}=\sum_{k=0}^{K}\binom{N}{k}$.

###### Proof.

Each $\mathbf{p}_{B|\bm{A}}\in\mathcal{C}_{N,K}$ satisfies $2^{N}$
normalization conditions $1=p(0|a_{1}\cdots a_{N})+p(1|a_{1},\cdots,a_{N})$,
with $a_{i}\in\\{0,1\\}$. To facilitate our analysis, instead of working in
the previous transition coordinates $p(0|a_{1}\cdots a_{N})$, we introduce
interference coordinates, whose definition is based on the $I_{K}$ equalities
in Eq. (32):

$\displaystyle\bigcup_{k\in\\{0,\cdots,N\\}}\bigcup_{\begin{subarray}{c}S\subseteq\\{1,\cdots,N\\}\\\
|S|=k\end{subarray}}\left\\{q(S):=(-1)^{k}\sum_{\begin{subarray}{c}a_{s}\in\\{0,1\\}\\\
s\in S\end{subarray}}\prod_{i\in S}(-1)^{a_{i}}p(0|a_{1}\cdots
a_{N})\;\bigg{|}\;\text{$a_{j}=0$ for $j\not\in S$}\right\\}.$ (34)

There are $\sum_{k=0}^{N}{{N}\choose{k}}=2^{N}$ elements in this set, which is
the same as the original set of transition coordinates $p(0|a_{1}\cdots
a_{N})$. Now we show that they are also linearly independent. For $|S|=k$,
consider the specific interference coordinate with $S=\\{1,\cdots,k\\}$

$q(S)=(-1)^{k}\sum_{\begin{subarray}{c}a_{s}\in\\{0,1\\}\\\ s\in
S\end{subarray}}\prod_{i\in S}(-1)^{a_{i}}p(0|a_{1}\cdots
a_{k},\overbrace{0\cdots 0}^{N-k}).$ (35)

Focus on the term $p(0|\overbrace{1\cdots 1}^{k},\overbrace{0\cdots 0}^{N-k})$
which appears in this term. Different interference coordinates $q(S^{\prime})$
with $|S^{\prime}|=k$ can be obtained by permuting the $0$’s and $1$’s, yet,
for each permutation there will be exactly one and only one distinct
probability term in the sum that is conditioned on $k$ values of $1$. Hence,
the different permutations generate $\binom{N}{k}$ linearly independent
coordinates. By the same reasoning, as we consider different
$k^{\prime}\in\\{0,\cdots,N\\}$, the coordinates $q(S^{\prime})$ with
$|S^{\prime}|=k^{\prime}$ will be linearly independent from the coordinates
$q(S)$ with $|S|=k<k^{\prime}$. In total, we obtain
$\sum_{k=0}^{N}{{N}\choose{k}}=2^{N}$ linearly independent coordinates.

We can thus represent each point $\mathbf{p}_{B|\bm{A}}\in\mathcal{C}_{N,K}$
in the interference coordinates. In doing so, we use the above observation
that $I_{k}^{(S)}(\mathbf{p}_{B|\bm{A}})=0$ for all $k=|S|\geq K+1$. This
indicates that $\mathbf{p}_{B|\bm{A}}$ has coordinates $q(S)=0$ for all
$|S|\geq K+1$, and therefore the dimension of $(N,K)$-local MAC
$\mathcal{C}_{N,K}$ can be upper bounded by:

$\dim\mathcal{C}_{N,K}\leq\sum_{k=0}^{K}\binom{N}{k}.$ (36)

To compute a lower bound on $\dim\mathcal{C}_{N,K}$, we are going to form a
family of affinely independent points. Consider first the constant MAC that
has transition probabilities

$\displaystyle p(0|a_{1}\cdots a_{N})$ $\displaystyle=0\qquad\forall
a_{1},\cdots,a_{N}$ (37)

which has interference coordinates $q(S)=0$ for all
$S\subseteq\\{1,\cdots,N\\}$. Next, for each $S\subseteq\\{1,\cdots,N\\}$ with
$1\leq|S|\leq K$, consider the $(N,K)$-local MAC $\mathbf{p}_{B|\bm{A}}^{(S)}$
defined by transition probabilities

$\displaystyle p(0|a_{1}\cdots a_{N})=g_{S}(0|(a_{s})_{s\in S})=\prod_{s\in
S}\delta_{1,a_{s}}.$ (38)

When $S=\emptyset$, we define $\mathbf{p}_{B|\bm{A}}^{(\emptyset)}$ as the
constant MAC with

$p(0|a_{1}\cdots a_{N})=1\qquad\forall a_{1},\cdots,a_{N}.$ (39)

It is straightforward to verify that $\mathbf{p}_{B|\bm{A}}^{(S)}$ has
interference coordinates $q(S^{\prime})=1$ if $S^{\prime}=S$ and
$q(S^{\prime})=0$ if $S^{\prime}\not=S$. In other words, in interference
coordinates, the MACs we have constructed in Eqns. (38) and (39) correspond
precisely to the standard unit vectors, while the MAC in Eq. (37) corresponds
to the all zero vector. Clearly, this generates a set of
$\sum_{k=0}^{K}\binom{N}{k}+1$ affinely independent points belonging to
$\mathcal{C}_{N,K}$. In summary, the dimension of the $\mathcal{C}_{N,K}$
polytope is $\sum_{k=0}^{K}\binom{N}{k}$ for any $1\leq K\leq N$.

Note that we can use the same coordinates and affinely independent points
(Eqs. (34) and (38)) to arrive at
$\dim\mathfrak{I}_{N,K}=\sum_{k=0}^{K}\binom{N}{k}$. ∎

######  Remark.

For $K=1$, Theorem 2 says that the dimension of $\mathcal{C}_{N}([2]^{N};[2])$
is $N+1$ and the interference coordinates we introduced in Eq. (34) are:

$\displaystyle\\{p(b|\mathbf{e}_{0}),p(b|\mathbf{e}_{1})-p(b|\mathbf{e}_{0}),\cdots,p(b|\mathbf{e}_{N})-p(b|\mathbf{e}_{0})\\}.$
(40)

with $p(b|\mathbf{e}_{i})=p(b|0,\cdots,1_{i},\cdots,0)$ for $i\neq 0$ and
$p(b|\mathbf{e}_{0})=p(b|0,\cdots,0)$. In this case, it is more natural to
work in the transition coordinates

$\displaystyle\\{p(b|\mathbf{e}_{0}),p(b|\mathbf{e}_{1}),\cdots,p(b|\mathbf{e}_{N})\\}.$
(41)

For any $L\in\\{1,\cdots,N\\}$ and any permutation on the input set, one can
show that

$\displaystyle p(b|\overbrace{1\cdots 1}^{L},\overbrace{0\cdots
0}^{N-L})=-(L-1)p(b|\mathbf{e}_{0})+\sum_{i=1}^{L}p(b|\mathbf{e}_{i})$ (42)

for every $b\in\mathcal{B}$. Hence according to Theorem 1, the only
constraints on these coordinates for them to define a MAC in
$\mathcal{C}_{N}([2]^{N};[2])$ is positivity:

$\displaystyle 0\leq-(|S|-1)p(b|\mathbf{e}_{0})+\sum_{s\in
S}p(b|\mathbf{e}_{s})\leq 1$ (43)

for all $S\subseteq\\{1,\cdots,N\\}$.

The proof of Eq. (42) follows by induction on $N$. Clearly it is true when
$N=1$, so suppose it holds for arbitrary $N\geq 1$. Consider an $(N+1)$-sender
MAC $\mathbf{p}_{B|A_{1},\cdots
A_{N+1}}\in\mathfrak{I}_{N+1}([2]^{N+1};\mathcal{B})$. If we fix the input
value of any party to be zero, then what remains is an $N$-sender MAC. Hence
by inductive assumption, for any $L=1,\cdots,N$ and any permutation, it holds
that

$\displaystyle p(b|\overbrace{1,\cdots,1,}^{L}\overbrace{0,\cdots,0}^{N+1-L})$
$\displaystyle=-(L-1)p(b|\mathbf{e}_{0})+\sum_{i=1}^{L}p(b|\mathbf{e}_{i}).$
(44)

It just remains to prove the case when $L=N+1$. Since
$\mathbf{p}_{B|A_{1},\cdots,A_{N+1}}\in\mathfrak{I}_{N+1}([2]^{N+1};\mathcal{B})$,
we have

$\displaystyle p(b|\overbrace{1\cdots 1}^{N+1})=$ $\displaystyle
p(b|\overbrace{1\cdots 1}^{N-1},0,1)+p(b|\overbrace{1\cdots 1}^{N-1},1,0)$
$\displaystyle-p(b|\overbrace{1\cdots 1}^{N-1},0,0)$ $\displaystyle=$
$\displaystyle-(L-1)p(b|\mathbf{e}_{0})+\sum_{i=1}^{N+1}p(b|\mathbf{e}_{i}),$
(45)

where the second equation follows from Eq. (44) and its parties’ permutation.
This proves the claim.

####  3.2.2 $(3,2)$-Local MACs

The $\mathcal{C}_{3,2}$ polytope is formed by the set of correlations
generated according to Eq. (22) with $N=3$ and $K=2$. From Theorem 2, our
analysis involves a seven-dimensional affine subspace with 38 vertices. Upon
running the PORTA software, we find there are 96 facet inequalities
characterizing the polytope $\mathcal{C}_{3,2}$, with 16 of them being
positivity constraints. By removing equivalent inequalities that can be
obtained by relabelling the inputs and output, we find the following three
nontrivial inequalities (see also [32]):

$\displaystyle p(0|000)+p(1|001)+p(1|010)+p(1|100)\leq 3$ (46) $\displaystyle
p(0|000)+p(1|001)+p(1|010)+p(0|101)\leq 3$ (47) $\displaystyle
p(0|000)+p(1|001)+p(1|010)+p(1|011)$
$\displaystyle{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}p(0|000)+p(1|010)+p(1|011)}+p(0|111)\leq
4.$ (48)

Among these, only the first one is symmetric among the senders. It is of
particular interest in our investigation, and we will refer to it as the
fingerprinting inequality in what follows. The reference to “fingerprinting"
is due to the fact that Eq. (46) can be interpreted in terms of a task that
loosely resembles the two-party fingerprinting task described in the
introduction. To see that, when relabeling all the inputs in Eq. (46), we will
obtain an inequality of the form:

$p(0|111)+p(1|110)+p(1|101)+p(1|001)\leq 3.$

If we assume the input bit of each party is given uniformly at random, Eqs.
(46) and its relabled counterpart imply that the probability the decoder can
decide whether $a_{1}=a_{2}=a_{3}$ is at most $3/4$, classically.

Moving beyond $\mathcal{C}_{3,2}$ to general $\mathcal{C}_{N,K}$ polytopes can
be done by working in a larger affine subspace. However, it becomes
increasingly more resource-intensive to perform the numerical analysis since
the number of vertices increases exponentially. Therefore, instead of trying
to fully characterize the polytopes $\mathcal{C}_{N,K}$, we will consider just
a few useful facets for each of them.

$N$-local MACs $\mathcal{C}_{N}{(\bm{\mathcal{A}},\mathcal{B})}$ | Inclusion relations | Propositions
---|---|---
Arbitrary inputs and binary output | $\mathcal{C}_{N}=\mathcal{C}_{N}^{\prime}=\text{conv}[\mathcal{C}_{N}]=\mathcal{C}_{N}^{(\text{sep})}$ | Prop. 2
Binary inputs and arbitrary output | $\mathcal{C}_{N}\subset^{\dagger}\mathcal{C}_{N}^{\prime}=\text{conv}[\mathcal{C}_{N}]=\mathcal{C}_{N}^{(\text{sep})}$ | Prop. 4, Prop. 5
Arbitrary inputs and arbitrary output | $\mathcal{C}_{N}\subset^{\dagger}\mathcal{C}^{\prime}_{N}\subset\text{conv}[\mathcal{C}_{N}]\subset\mathcal{C}_{N}^{(\text{sep})}$ | Prop. 16
Table 1: A comparison of $N$-party classical MACs and the corresponding
propositions. The inclusion $\subset$ is proper for all $N\geq 1$. The
inclusion $\subset^{\dagger}$ is proper only for $N>1$ whereas it becomes a
trivial equivalence when $N=1$.

####  3.2.3 The Generalized Fingerprinting Inequality

To identify facet inequalities for higher-dimensional $\mathcal{C}_{N,K}$, we
invoke the idea of “lifting” a Bell inequality, which has been previously used
in the study of nonlocality [55][50]. The basic idea is to identify a facet
inequality for $\mathcal{C}_{N-1,K}$ and then generalize its structure by the
addition of one more party. To verify that this constructed inequality indeed
defines a valid facet of $\mathcal{C}_{N,K}$, it suffices to show to that it
is satisfied by $\dim\mathcal{C}_{N,K}$ affinely independent points [50].

Having computed the dimension of $\dim\mathcal{C}_{N,K}$ in Section 2, we will
specifically apply this procedure to lift inequality (46) to higher-
dimensional polytopes. Let us consider the $(N,K)$-local generalized
fingerprinting inequalities, which, up to a relabeling of inputs and
permutation of parties, have the form

$p(0|\overbrace{0\cdots
0}^{N})+\sum_{i=1}^{K+1}p(1|\overbrace{0\cdots,1_{i},\cdots
0}^{K+1},\overbrace{0\cdots 0}^{N-K-1})\leq K+1.$ (49)

Here, $1_{i}$ means that party $\mathsf{A}_{i}$ has input $1$. When $N=3$ and
$K=2$, we obtain the fingerprinting inequality studied above; when $N=2$, and
$K=1$, the corresponding inequality can be derived from $I_{2}$ equality Eq.
25 along with a positivity constrains $p(0|1,1)\geq 0$. These inequalities has
been previously studied in Ref. [33], although its tightness as a facet
inequality of $\mathcal{C}_{N,K}$ was not considered. One can easily check
that these inequalities cannot be violated by any correlation with the
decomposition Eq. (22) for a given $N$ and $K$. Furthermore based on Theorem
2, the dimension of $\mathcal{C}_{N,K}$ is $\sum_{k=0}^{K}{N\choose{k}}$.
Therefore, to show that Eq. (49) is a valid facet of the $\mathcal{C}_{N,K}$
polytope, it is sufficient to find $\sum_{k=0}^{K}{N\choose{k}}$ affinely
independent MACs that saturate it.

######  Proposition 3.

The $(N,K)$-party generalized fingerprinting inequalities are valid
inequalities of the $\mathcal{C}_{N,K}$ polytope.

###### Proof.

The list of affinely independent points saturating the inequality in Eq. (49)
is not unique, and here we construct one using MACs similar to those in the
proof of Theorem 2. Among the $\sum_{k=0}^{K}{N\choose{k}}+1$ affinely
independent points constructed in Theorem 2 (Eqns. (37) – (39)), a total of
$\sum_{k=0}^{K}{N\choose{k}}-K-1$ will saturate the inequality in Eq. (49). In
particular, it will not be saturated by the constant MAC, with
$p(0|a_{1}\cdots a_{N})=1$, as well as the MACs with $p(0|a_{1}\cdots
a_{N})=\prod_{s\in S}\delta_{1,a_{s}}$ for $|S|=1$ and
$S\subset\\{1,\cdots,K+1\\}$. We replace $K+1$ of these points by MACs defined
by

$p(0|a_{1}\cdots a_{N})=\prod_{\begin{subarray}{c}j=1\\\
j\not=i\end{subarray}}^{K+1}\delta_{0,a_{j}},$ (50)

for each $i\in\\{1,\cdots,K+1\\}$. Each of these is an $(N,K)$-local MAC since
it only depends on the inputs of $K$ parties, and it can be readily seen to
saturate the inequality in Eq. (49). They are also affinely independent from
each other and from the $\sum_{k=0}^{K}{N\choose{k}}-K-1$ previous points
since they have probability values $p(0|a_{1}\cdots a_{N})$ equaling $1$ when
only one or fewer parties have an input equaling $1$. In summary, we have
identified $\sum_{k=0}^{K}{N\choose{k}}$ affinely independent points
saturating Inequality (49). This inequality and all its permutations are thus
valid facets of the $\mathcal{C}_{N,K}$ polytope. ∎

###  3.3 Beyond Binary $(N,K)$-Local MACs

We now draw some general conclusions about $(N,K)$-local MACs.

####  3.3.1 Polytope Dimension and Generalized Fingerprinting Inequalities

The dimension of $\mathcal{C}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$ for general
input/output sets can be computed using the same argumentation as in Section
3.2.1. For simplicity we assume that $|\mathcal{A}_{i}|=|\mathcal{A}|$ for all
parties $\mathsf{A}_{i}$. Then one finds

######  Theorem 3.

$\dim\mathcal{C}_{N,K}(\bm{\mathcal{A}},\mathcal{B})=(|\mathcal{B}|-1)\sum_{k=0}^{K}(|\mathcal{A}|-1)^{k}\binom{N}{k}$
(51)

While in general $\mathcal{C}_{N,K}(\bm{\mathcal{A}};\mathcal{B})$ is a proper
subset of $\mathfrak{I}_{N,K}(\bm{\mathcal{A}};\mathcal{B})$, the two sets
have the same dimension:

$\displaystyle\dim\mathfrak{I}_{N,K}(\bm{\mathcal{A}};\mathcal{B})=\dim{\mathcal{C}_{N,K}(\bm{\mathcal{A}};\mathcal{B})}=\dim{\mathcal{C}^{\prime}_{N,K}(\bm{\mathcal{A}};\mathcal{B})}$
$\displaystyle=\dim{\text{conv}[\mathcal{C}_{N,K}(\bm{\mathcal{A}};\mathcal{B})]}=\dim{\mathcal{C}_{N,K}^{(\text{sep})}(\bm{\mathcal{A}};\mathcal{B})}.$
(52)

Details on its proof is provided in the supplementary [1]. We can likewise
extend the generalized fingerprinting inequality to more outputs. That is, we
have

$-p(b|\overbrace{0,\cdots,0}^{N})+\sum_{i=1}^{K+1}p(b|\overbrace{0,\cdots,1_{i},\cdots,0}^{K+1},\overbrace{0,\cdots,0}^{N-K-1})\leq
K,$ (53)

for all $b\in\mathcal{B}$ and all other inequalities obtained by relabeling
inputs and permuting parties. These are valid facets for
$\mathcal{C}_{N,K}^{(\text{sep})}(\bm{\mathcal{A}};\mathcal{B})$, as can be
shown by following the procedure taken in Proposition 3 .

$(N,K)$-local MACs $\mathcal{C}_{N,K}{(\bm{\mathcal{A}},\mathcal{B})}$ | Inclusion relations | Propositions
---|---|---
$|\mathcal{B}|=2$ | $\mathcal{C}_{N,K}=\mathcal{C}_{N,K}^{\prime}=\text{conv}[\mathcal{C}_{N,K}]=\mathcal{C}_{N,K}^{(\text{sep})}$ | Prop. 2
$K+1\geq|\mathcal{B}|>2$ | $\mathcal{C}_{N,K}\subset^{\dagger}\mathcal{C}_{N,K}^{\prime}=\text{conv}[\mathcal{C}_{N,K}]=\mathcal{C}_{N,K}^{(\text{sep})}$ | Prop. 17, Prop. 18
$|\mathcal{B}|>K+1$ | $\mathcal{C}_{N,K}\subset^{\dagger}\mathcal{C}_{N,K}^{\prime}\subset\text{conv}[\mathcal{C}_{N,K}]\subset\mathcal{C}_{N,K}^{(\text{sep})}$ | Prop. 16
Table 2: A comparison of $(N,K)$-party classical MACs for $K\geq 2$. The
inclusion notation is the same as in Table 1.

####  3.3.2 Non-Convexity and Separating Different Classes of $(N,K)$-Local
MACs

In Section 2.4, we introduced four classes of MACs,
$\mathcal{C}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$,
$\mathcal{C}^{\prime}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$,
$\text{conv}[\mathcal{C}_{N,K}(\bm{\mathcal{A}},\mathcal{B})]$, and
$\linebreak\mathcal{C}^{(\text{sep})}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$. We
have seen in Proposition 2 that they are all equivalent when
$|\mathcal{B}|=2$. This is a special case, however, and the general inclusion
and convexity structure will be discussed in this section. The results are
summarized in Table 1 for $K=1$ and Table 2 for $K>1$ (with addition
information given in the supplementary [1]). Here we assume the cardinality of
the input sets $\mathcal{A}_{i}$ and the output $\mathcal{B}$ are all greater
than one.

######  Proposition 4.

For $|\mathcal{B}|>2$ and $N\geq 2$, the set
$\mathcal{C}_{N}(\bm{\mathcal{A}},\mathcal{B})$ is non-convex; hence
$\mathcal{C}_{N}(\bm{\mathcal{A}},\mathcal{B})\not=\mathcal{C}^{\prime}_{N}(\bm{\mathcal{A}},\mathcal{B})$.

###### Proof.

It suffices to prove the statement for $\mathcal{C}_{2}([2]^{2};[3])$.
Consider
$\mathbf{p}^{\prime}_{B|A_{1}A_{2}},\mathbf{p}^{\prime\prime}_{B|A_{1}A_{2}}\in\mathcal{C}_{2}([2]^{2};[3])$
having respective coordinates $p^{\prime}(b|a_{1},a_{2})=g_{1}(b|a_{1})$, with
$g_{1}(0|0)=1$ and $g_{1}(1|1)=1$, and
$p^{\prime\prime}(b|a_{1},a_{2})=g_{2}(b|a_{2})$, with
$g_{2}(0|0)=g_{2}(1|0)=1/2$ and $g_{2}(2|1)=1$. We will show their mixture
$\mathbf{p}_{B|A_{1},A_{2}}=\lambda\mathbf{p}^{\prime}_{B|A_{1},A_{2}}+(1-\lambda)\mathbf{p}^{\prime\prime}_{B|A_{1},A_{2}}$
does not belong to $\mathcal{C}_{2}([2]^{2};[3])$ for $\lambda\in(0,1)$. For
if it did, then by Eq. (14) we could write

$\displaystyle\lambda
g_{1}(b|a_{1})+(1-\lambda)g_{2}(b|a_{2})=\sum_{i=1}^{2}p_{i}\sum_{\mathclap{m=0,\mathbf{e}_{i}}}d(b|m)q_{i}(m|a_{i}).$
(54)

Define $g_{i}^{\prime}(b|a_{i})=\sum_{m=0,\mathbf{e}_{i}}d(b|m)q_{i}(m|a_{i})$
and suppose that

$\lambda
g_{1}(b|a_{1})+(1-\lambda)g_{2}(b|a_{2})=p_{1}g_{1}^{\prime}(b|a_{1})+p_{2}g_{2}^{\prime}(b|a_{2}).$

Then $p(0|1,1)=p(1|0,1)=p(2|a_{1},0)=0$ for $a_{1}=0,1$ implies
$g_{1}^{\prime}(0|1)=g_{2}^{\prime}(0|1)=0$,
$g_{1}^{\prime}(1|0)=g_{2}^{\prime}(1|1)=0$, and $g_{1}^{\prime}(2|a_{1})=0$
for $a_{1}=0,1$. Hence

$\displaystyle p(0|0,1)$ $\displaystyle=\lambda
g_{1}(0|0)=p_{1}g^{\prime}_{1}(0|0)+p_{2}g^{\prime}_{2}(0|1)=p_{1}g^{\prime}_{1}(0|0).$
(55)

Hence we have $g_{1}^{\prime}(b|a_{1})\propto g_{1}(b|a_{1})$ for all
$b,a_{1}$. By normalization, they must, in fact be equal. A similar argument
shows $g_{2}^{\prime}(b|a_{2})=g_{2}(b|a_{2})$.

$\begin{split}g_{1}(b|a_{1})&=\sum_{m=0,\mathbf{e}_{1}}d(b|m)q_{1}(m|a_{1})\\\
g_{2}(b|a_{2})&=\sum_{m=0,\mathbf{e}_{2}}d(b|m)q_{2}(m|a_{2}).\end{split}$

With $g_{1}$ being a deterministic MAC, we must have that $d(b|0)\in\\{0,1\\}$
and $0=d(2|0)$. By considering
$1=g_{2}(2|1)=d(2|0)q_{2}(0|1)+d(2|\mathbf{e}_{2})q_{2}(\mathbf{e}_{2}|1)=d(2|\mathbf{e}_{2})q_{2}(\mathbf{e}_{2}|1)$,
we then have $d(2|\mathbf{e}_{2})=1$. But since $d(b|0)\in\\{0,1\\}$, it
follows that $g_{2}$ cannot output values $\\{0,1,2\\}$ each with nonzero
probability. As this is a contradiction, we conclude that
$\mathcal{C}_{2}([2]^{2};[3])$ is non-convex. On the other hand, since
$\mathcal{C}^{\prime}_{2}([2]^{2};[3])$ is convex by Proposition 2, it follows
that
$\mathcal{C}_{N}(\bm{\mathcal{A}},\mathcal{B})\neq\mathcal{C}^{\prime}_{N}(\bm{\mathcal{A}},\mathcal{B})$.

∎

######  Remark.

The convexity of $\mathcal{C}_{N}(\bm{\mathcal{A}};[2])$ is established in
Proposition 2 essentially by absorbing the decoding function
$d:\cup_{i=1}^{N}\mathcal{M}_{i}\to\\{0,1\\}$ into the encoding functions
$q_{i}:\mathcal{A}_{i}\to\mathcal{M}_{i}$, where
$\mathcal{M}_{i}=\\{0,\mathbf{e}_{i}\\}$. The is possible because
$|\mathcal{B}|\leq|\mathcal{M}_{i}|$ in the binary-output case. The non-
convexity shown in Proposition 4 follows from the fact that $|\mathcal{B}|=3$
and so $|\mathcal{B}|>|\mathcal{M}_{i}|$; hence it is not possible to absorb
the decoder into the encoders.

While $\mathcal{C}_{N}([2]^{N};\mathcal{B})$ is non-convex for
$|\mathcal{B}|>2$, if shared randomness between the particle source and
receiver is allowed, then convexity can be restored by absorbing the encoding
function into the decoding function.

######  Proposition 5.

$\mathcal{C}^{\prime}_{N}([2]^{N};\mathcal{B})=\mathcal{C}_{N}^{(\text{sep})}([2]^{N};\mathcal{B})$
for arbitrary output set $\mathcal{B}$.

###### Proof.

For $p(b|\mathbf{a})=\sum_{i=1}^{N}p_{i}g_{i}(b|a_{i})$ we define decoders
with $d_{i}(b|0)=g_{i}(b|0)$ and $d_{i}(b|\mathbf{e}_{i})=g_{i}(b|1)$, as well
as deterministic encoders $q_{i}(0|0)=1$ and $q_{i}(\mathbf{e}_{i}|1)=1$. With
these choices, $\sum_{i=1}^{N}p_{i}g_{i}(b|a_{i})$ has the form of Eq. (16). ∎

However, as shown in Proposition 16 and the following remark (whose proof is
given in supplementary material [1]), this no longer holds when the input sets
are not binary, i.e. $\mathcal{C}_{N}^{\prime}(\bm{\mathcal{A}},\mathcal{B})$
with $|\mathcal{B}|>2$ and $|\mathcal{A}_{i}|>2$ will no longer be convex.

######  Proposition 6.

For $|\mathcal{B}|>K+1$ and $|\mathcal{A}_{i}|>2$ for some party
$\mathsf{A}_{i}$, the set
$\mathcal{C}_{N,K}^{\prime}(\bm{\mathcal{A}},\mathcal{B})$ is non-convex;
hence
$\mathcal{C}_{N,K}^{\prime}(\bm{\mathcal{A}},\mathcal{B})\not=\text{conv}[\mathcal{C}_{N,K}(\bm{\mathcal{A}},\mathcal{B})]$.

######  Remark.

When $|\mathcal{B}|>K+1$ and $|\mathcal{A}_{i}|>2$, one can also have
$\text{conv}[\mathcal{C}_{N,K}(\bm{\mathcal{A}},\mathcal{B})]\neq\mathcal{C}_{N,K}^{(\text{sep})}(\bm{\mathcal{A}},\mathcal{B})$[1]

Similarly propositions 17 and 18 discussing the relation specifically between
different $(N,K)$-local MACs with $K\geq 2$ can be found below while their
proofs and other discussions are also given in detail in the supplementary [1]
and the results are summarized in Table 2.

######  Proposition 7.

For $|\mathcal{B}|>2$, the set
$\mathcal{C}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$ is non-convex; hence
$\mathcal{C}_{N,K}(\bm{\mathcal{A}},\mathcal{B})\not=\mathcal{C}^{\prime}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$.

######  Proposition 8.

$\mathcal{C}^{\prime}_{N,K}(\bm{\mathcal{A}};\mathcal{B})=\mathcal{C}_{N,K}^{(\text{sep})}(\bm{\mathcal{A}};\mathcal{B})$
for arbitrary input sets $\bm{\mathcal{A}}$ and output set $|\mathcal{B}|\leq
K+1$.

##  4 Quantum MACs

###  4.1 Quantum Violation of $N$-Local Classical MAC

According to Theorem 1, an $N$-partite binary MAC can be generated by a single
classical particle if and only if the interference term $I_{2}$ vanishes for
every pair of parties. In contrast, quantum mechanics allows for single
particles to demonstrate nonzero interference, a fact demonstrated most
conspicuously in a double-slit experiment [27, 37, 46]. Let us here describe a
simplified version of this effect. Suppose that a particle is prepared in a
superposition of two paths
$|\psi\rangle=x|0\rangle_{\mathsf{A}_{1}}|1\rangle_{\mathsf{A}_{2}}+y|1\rangle_{\mathsf{A}_{1}}|0\rangle_{\mathsf{A}_{2}}$.
The particle is then subjected to interference described by the path
transformation

$\displaystyle\frac{1}{\sqrt{2}}(|0\rangle_{\mathsf{A}_{1}}|1\rangle_{\mathsf{A}_{2}}+|1\rangle_{\mathsf{A}_{1}}|0\rangle_{\mathsf{A}_{2}})$
$\displaystyle\to|1\rangle_{\mathsf{B}_{1}}|0\rangle_{\mathsf{B}_{2}}$
$\displaystyle\frac{1}{\sqrt{2}}(|0\rangle_{\mathsf{A}_{1}}|1\rangle_{\mathsf{A}_{2}}-|1\rangle_{\mathsf{A}_{1}}|0\rangle_{\mathsf{A}_{2}})$
$\displaystyle\to|0\rangle_{\mathsf{B}_{1}}|1\rangle_{\mathsf{B}_{2}}.$ (56)

In the end, if the particle is found in path $\mathsf{B}_{1}$ we say this is
“outcome $0$” and if it is found in path $\mathsf{B}_{2}$ it is “outcome $1$.”
According to Born’s Rule, the probability of outcome $0$ is

$\frac{1}{2}|x+y|^{2}=\frac{1}{2}|x|^{2}+\frac{1}{2}|y|^{2}+Re(xy^{*}).$ (57)

The term $\frac{1}{2}|x|^{2}$ we can recognize as the probability of outcome
$0$ if path $\mathsf{A}_{1}$ is blocked prior to the interference, and
similarly, $\frac{1}{2}|y|^{2}$ is the probability of outcome $0$ if path
$\mathsf{A}_{2}$ blocked. If we let $0/1$ denote the event of
blocked/unblocked path, then we can rewrite Eq. (57) as

$\displaystyle Re(xy^{*})=p(0|1,1)-p(0|0,1)-p(0|1,0).$ (58)

Since $p(0|0,0)=0$, as both paths are being blocked, we can add this to the
right-hand side. A comparison with Eq. (25) shows that $I_{2}=|Re(xy^{*})|$ in
this simple path-blocking interference setup. It is referred to as second-
order interference since it is quadratic in the wave-function amplitudes, and
it is nonzero if and only if both amplitudes are nonzero.

The setup just described falls under the communication scenario of Fig. 1.
Namely the “path blocking” action of $\mathsf{A}_{1}$ or $\mathsf{A}_{2}$ is a
valid N-P operation, and thus the fact that $I_{2}=Re(xy^{*})$ implies
$\mathcal{C}_{2}$ is a strict subset of $\mathcal{Q}_{2}$. Even stronger,
every non-classical pure state (i.e. one with a nonzero superposition of
paths) is capable of generating a MAC outside the set $\mathcal{C}_{2}$. A
natural question is whether the same holds for mixed states, and whether an
even higher value of $I_{2}$ can be achieved by using an encoding scheme other
than path blocking. To answer this question, let us define for an arbitrary
state $\rho\in\mathcal{H}^{\mathsf{A}_{1}\cdots\mathsf{A}_{N}}_{1}$ the
quantities

$I_{2}^{(i,j)}(\rho):=\max\\{I^{(i,j)}_{2}(\mathbf{p}_{B|\bm{A}})\;:\;\mathbf{p}_{B|\bm{A}}\in\mathcal{Q}_{N}(\rho)\\}.$
(59)

In other words, $I_{2}^{(i,j)}(\rho)$ is the largest value of $I_{2}$ that can
be achieved between parties $i$ and $j$ using state $\rho$ and N-P encoding.
The following theorem shows these values directly correspond to the off-
diagonal matrix elements of $\rho$.

######  Proposition 9.

For $\rho\in\mathcal{H}^{\bm{\mathsf{A}}}_{1}$ let
$\rho_{ij}=\langle\mathbf{e}_{i}|\rho|\mathbf{e}_{j}\rangle$. Then
$I_{2}^{(i,j)}(\rho)=4|\rho_{ij}|$. Moreover, this value can be attained by
parties $i$ and $j$ performing a $\\{0,\pi\\}$ encoding, i.e.
$\mathcal{E}_{a}(X)=\sigma_{z}^{a}(X)\sigma_{z}^{a}$ for $a\in\\{0,1\\}$ and
$\sigma_{z}=|0\rangle\langle 0|+e^{i\pi}|1\rangle\langle 1|$.

###### Proof.

As discussed in Eq. (10), every N-P operation
$\mathcal{E}_{a}^{\mathsf{A}_{i}}$ on qubit system $\mathsf{A}_{i}$ is
characterized by Kraus operators
$\left\\{\left(\begin{smallmatrix}x_{a,k}^{i}&0\\\
0&y_{a,k}^{i}\end{smallmatrix}\right),\left(\begin{smallmatrix}0&z_{a,k}^{i}\\\
0&0\end{smallmatrix}\right)\right\\}_{k}$ such that
$\sum_{k}|x_{a,k}^{i}|^{2}=\sum_{k}(|y_{a,k}^{i}|^{2}+|z_{a,k}^{i}|^{2})=1$.
Notice that

$\displaystyle\mathcal{E}_{a_{i}}^{\mathsf{A}_{i}}\otimes\mathcal{E}_{a_{j}}^{\mathsf{A}_{j}}(|00\rangle\langle
00|)$ $\displaystyle=|00\rangle\langle 00|$
$\displaystyle\mathcal{E}_{a_{i}}^{\mathsf{A}_{i}}\otimes\mathcal{E}_{a_{j}}^{\mathsf{A}_{j}}(|10\rangle\langle
10|)$ $\displaystyle=\lambda_{a_{i}}^{i}|10\rangle\langle
10|+(1-\lambda_{a_{i}}^{i})|00\rangle\langle 00|$
$\displaystyle\mathcal{E}_{a_{i}}^{\mathsf{A}_{i}}\otimes\mathcal{E}_{a_{j}}^{\mathsf{A}_{j}}(|01\rangle\langle
01|)$ $\displaystyle=\lambda_{a_{j}}^{j}|01\rangle\langle
01|+(1-\lambda_{a_{j}}^{j})|00\rangle\langle 00|$
$\displaystyle\mathcal{E}_{a_{i}}^{\mathsf{A}_{i}}\otimes\mathcal{E}_{a_{j}}^{\mathsf{A}_{j}}(|01\rangle\langle
10|)$ $\displaystyle=\kappa_{a_{i},a_{j}}|01\rangle\langle 10|$ (60)

in which
$\kappa_{a_{i},a_{j}}=\sum_{k,k^{\prime}}x^{i}_{a_{i},k}y^{j}_{a_{j},k^{\prime}}(y^{i}_{a_{i},k}x^{j}_{a_{j},k^{\prime}})^{*}$
and $\lambda_{a}^{i}=\sum_{k}|y^{i}_{a,k}|^{2}$. If
$\mathcal{E}^{\overline{\mathsf{A}_{i}\mathsf{A}_{j}}}$ is any local N-P map
collectively performed by all parties other than $\mathsf{A}_{i}$ and
$\mathsf{A}_{j}$, it can then be easily seen that

$\displaystyle(\mathcal{E}_{0}^{\mathsf{A}_{i}}-\mathcal{E}_{1}^{\mathsf{A}_{i}})$
$\displaystyle\otimes(\mathcal{E}_{0}^{\mathsf{A}_{j}}-\mathcal{E}_{1}^{\mathsf{A}_{j}})\otimes\mathcal{E}^{\overline{\mathsf{A}_{i}\mathsf{A}_{j}}}(\rho)$
$\displaystyle=\kappa\rho_{ij}|\mathbf{e}_{i}\rangle\langle\mathbf{e}_{j}|+\kappa^{*}\rho_{ji}^{*}|\mathbf{e}_{j}\rangle\langle\mathbf{e}_{i}|,$
(61)

where

$\kappa=\kappa_{0,0}+\kappa_{1,1}-\kappa_{0,1}-\kappa_{1,0}.$ (62)

For any decoding POVM $\\{\Pi_{0},\Pi_{1}\\}$ we have

$\displaystyle I_{2}^{(i,j)}(\rho)$
$\displaystyle=\textrm{Tr}\left[\Pi_{0}\left(\kappa\rho_{ij}|\mathbf{e}_{i}\rangle\langle\mathbf{e}_{j}|+\kappa^{*}\rho_{ji}^{*}|\mathbf{e}_{j}\rangle\langle\mathbf{e}_{i}|\right)\right]$
$\displaystyle\leq|\kappa\rho_{ij}|\leq 4|\rho_{ij}|,$ (63)

where the last inequality follows from the triangle inequality and the fact
that $\Pi_{0}\leq\mathbb{I}$. The inequalities are saturated when choosing
$\\{0,\pi\\}$ phase encoding and $\Pi_{0}=|\psi_{ij}\rangle\langle\psi_{ij}|$,
where
$\displaystyle|\psi_{ij}\rangle=\frac{1}{\sqrt{2}}(|\mathbf{e}_{i}\rangle+\frac{\rho_{ij}^{*}}{|\rho_{ij}|}|\mathbf{e}_{j}\rangle)$.
∎

###  4.2 Quantum Violation of $(N,K)$-Local Classical MACs

For $K>1$, the polytope $\mathcal{C}_{N,K}$ is constrained by the vanishing of
all $I_{K+1}$ expressions (see Eq. (32)) as well as other non-trivial facets.
We just showed that quantum states can violate the $I_{2}$ equality using N-P
operations. However, for $K>1$ this is no longer possible. To see this
explicitly, consider the $I_{3}$ expression for parties $S=\\{i,j,k\\}$. Using
the notation of Proposition 9, for any
$\rho\in\mathcal{H}_{1}^{\bm{\mathsf{A}}}$ the relevant encoding for $I_{3}$
is

$\displaystyle(\mathcal{E}_{0}^{\mathsf{A}_{k}}-\mathcal{E}_{1}^{\mathsf{A}_{k}})\otimes(\mathcal{E}_{0}^{\mathsf{A}_{i}}-\mathcal{E}_{1}^{\mathsf{A}_{i}})\otimes(\mathcal{E}_{0}^{\mathsf{A}_{j}}-\mathcal{E}_{1}^{\mathsf{A}_{j}})\otimes\mathcal{E}^{\overline{\mathsf{A}_{i}\mathsf{A}_{j}\mathsf{A}_{k}}}(\rho)$
$\displaystyle=(\mathcal{E}_{0}^{\mathsf{A}_{k}}-\mathcal{E}_{1}^{\mathsf{A}_{k}})(\kappa\rho_{ij}^{*}|\mathbf{e}_{i}\rangle\langle\mathbf{e}_{j}|+\kappa^{*}\rho_{ji}|\mathbf{e}_{j}\rangle\langle\mathbf{e}_{i}|)=0,$
(64)

where $\kappa$ is defined in Eq. (62). The second equality holds because
$\mathcal{E}_{a_{k}}^{\mathsf{A}_{k}}$ is an N-P operation and so
$\mathcal{E}_{a_{k}}^{\mathsf{A}_{k}}(|\mathbf{e}_{i}\rangle\langle\mathbf{e}_{j}|)=|\mathbf{e}_{i}\rangle\langle\mathbf{e}_{j}|$.
One can easily extend this argument to show that $I_{K+1}=0$ for all $K>1$
when the quantum encodings are required to be $N$-local, N-P operations.

Ultimately, the vanishing of $I_{3}$ for quantum MACs is a consequence of
Born’s Rule [54, 19], and it has been experimentally verified [53]. Recently,
it was shown by Rozema et al. that $I_{3}$ and all higher-order interference
must vanish in any multi-path interferometer experiment using path-blocking
operations [52]. Equation (64) offers a slight generalization in that the
encoding maps $\mathcal{E}_{a_{k}}^{\mathsf{A}_{k}}$ need not just be a path-
blocking operation but rather any NP-operation. Nevertheless, the spirit of
the trace argument presented in Ref. [52] is implicit here since Eq. (64) is a
traceless operator.

While quantum mechanics cannot violate the $I_{K+1}=0$ constraints of
$\mathcal{C}_{N,K}$ for $K>1$, it is possible for quantum systems to violate
some of the other facet inequalities. For example, in the case of
$(3,2)$-local MACs, all channels in $\mathcal{C}_{3,2}([2]^{3};[2])$ must
satisfy Eqs. (46)–(48), namely

$\displaystyle p(0|000)+p(1|001)+p(1|010)+p(1|100)\leq 3$ $\displaystyle
p(0|000)+p(1|001)+p(1|010)+p(0|101)\leq 3$ $\displaystyle
p(0|000)+p(1|001)+p(1|010)+p(1|011)$
$\displaystyle{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}p(0|000)+p(1|010)+p(1|011)}+p(0|111)\leq
4.$

However, by using the equal superposition state
$\sqrt{1/3}(|100\rangle+|010\rangle+|001\rangle)$, it is possible to generate
a MAC in $\mathcal{Q}_{3,1}([2]^{3};[2])$ for which the left-hand side attains
a value of $3.66$, $3.15$ and $4.66$ correspondingly.

In this section we will generalize this example by demonstrating
$\mathcal{Q}_{N,1}([2]^{N};[2])\not\subset\mathcal{C}_{N,N-1}([2]^{N};[2])$
for every $N$. In other words, $N$ quantum parties restricted to local
encodings can generate a MAC that cannot be simulated using $N$ classical
parties with the locality restriction relaxed on all but one party. This
result was previously shown in Ref. [33] and given the interpretation that
quantum mechanics allows for a greater “information speed” with respect to
communicating information shared among spatially separated senders. As in Ref.
[33], we show this result by finding a violation of the $(N,N-1)$-party
generalized fingerprinting inequality,

$p(0|\overbrace{0,\cdots,0}^{N})+\sum_{i=1}^{N}p(1|\overbrace{0,\cdots,1_{i},\cdots,0}^{N})\leq
N,$ (65)

which we have proven to be a valid facet of $\mathcal{C}_{N,N-1}$ in
Proposition 3. Here we provide a slightly improved quantum strategy than the
one presented in Ref. [33], and we are thus able to obtain a larger violation
in many cases.

To show the quantum violation, we suppose the quantum particle is prepared in
an equal superposition among $N$ paths, that is,
$|\Psi_{N}\rangle=\frac{1}{\sqrt{N}}\sum_{i=1}^{N}|\mathbf{e}_{i}\rangle$ with
$|\mathbf{e}_{i}\rangle=|0\rangle_{A_{1}}\cdots|1\rangle_{A_{i}}\cdots|0\rangle_{A_{N}}$.
Consider the local phase encoding map for party $\mathsf{A}_{i}$ characterized
by two angles $(\theta_{i},\phi_{i})$:
$\mathcal{E}^{\mathsf{A}_{i}}_{0}(\rho)=U(\theta_{i})\rho U(-\theta_{i})$ and
$\mathcal{E}^{\mathsf{A}_{i}}_{1}(\rho)=U(\phi_{i}+\theta_{i})\rho
U(-\phi_{i}-\theta_{i})$, where $U(\theta)=|0\rangle\langle
0|+e^{i\theta}|1\rangle\langle 1|$. With this encoding, Eq. (65) becomes

$\textrm{Tr}[\Pi_{0}(\sigma_{0\cdots
0})]+\sum_{i=1}^{N}\textrm{Tr}[\Pi_{1}(\sigma_{0\cdots 1_{i}\cdots 0})]\leq
N,$ (66)

where $\sigma_{a_{1}\cdots
a_{N}}=\mathcal{E}^{\mathsf{A}_{1}}_{a_{1}}\otimes\cdots\otimes\mathcal{E}^{\mathsf{A}_{N}}_{a_{N}}(|\Psi_{N}\rangle\langle\Psi_{N}|)$
and $\\{\Pi_{0},\Pi_{1}\\}$ is the decoding POVM. From Helstrom’s Theorem
[28], the maximum value of the left-hand side is $\frac{1}{2}(N+1+\left\lVert
M\right\rVert_{1})$, where $\left\lVert
M\right\rVert_{1}=\textrm{Tr}{\sqrt{M^{\dagger}M}}$ and

$M=\sum_{i=1}^{N}\sigma_{0\cdots 1_{i}\cdots 0}-\sigma_{0\cdots 0}.$ (67)

A violation of the generalized fingerprinting inequality can then be cast as
the condition $\delta>0$ in which

$\delta=\frac{1}{2}\left(\left\lVert M\right\rVert_{1}-N+1\right).$ (68)

Notice that
$\mathcal{E}^{\mathsf{A}_{1}}_{0}\otimes\cdots\otimes\mathcal{E}^{\mathsf{A}_{N}}_{0}$
is a global unitary, and since the trace norm is invariant under a global
unitary, it can be factored out. Therefore, $M$ can be simply characterized as
an $N\times N$ matrix of the form

$\displaystyle
M=\frac{1}{N}\begin{pmatrix}N-1&N-3+e^{i\phi_{1}}+e^{-i\phi_{2}}&\cdots&N-3+e^{i\phi_{1}}+e^{-i\phi_{N}}\\\
N-3+e^{i\phi_{2}}+e^{-i\phi_{1}}&N-1&\cdots&N-3+e^{i\phi_{2}}+e^{-i\phi_{N}}\\\
\vdots&\vdots&\vdots&\vdots\\\
N-3+e^{i\phi_{N}}+e^{-i\phi_{1}}&N-3+e^{i\phi_{N}}+e^{-i\phi_{2}}&\cdots&N-1\end{pmatrix}.$
(69)

This matrix depends on $N$ parameters and there appears to be no easy way to
compute its trace norm. Nevertheless, after performing exhaustive numerical
searches for small $N$, we find that a maximal violation can be obtained with
some simple encoding strategies (see Table 3). This strategy consists of
setting $\phi_{1}=\phi$, $\phi_{2}=-\phi$, $\phi_{i}=\pi,\leavevmode\nobreak\
\forall i\neq 1,2$. In this case $M$ will be simplified as:

$M=\frac{1}{N}(4\mathbb{I}+(N-3)|\Psi_{N}\rangle\langle\Psi_{N}|-|\Psi_{N}^{{}^{\prime}}\rangle\langle\Psi_{N}^{{}^{\prime}}|-|\Psi_{N}^{{}^{\prime\prime}}\rangle\langle\Psi_{N}^{{}^{\prime\prime}}|),$
(70)

where
$|\Psi_{N}^{{}^{\prime}}\rangle=\frac{1}{\sqrt{N}}\left(e^{i\phi}|\mathbf{e}_{1}\rangle+\sum_{i\neq
1}^{N}|\mathbf{e}_{i}\rangle\right)$ and
$|\Psi_{N}^{{}^{\prime\prime}}\rangle=\frac{1}{\sqrt{N}}\left(|\mathbf{e}_{2}\rangle+e^{i\phi}\sum_{i\neq
2}^{N}|\mathbf{e}_{i}\rangle\right)$. With these simplifications, we can set a
new basis
$|\mathbf{e}_{1}^{\prime}\rangle=|\mathbf{e}_{1}\rangle,|\mathbf{e}_{2}^{\prime}\rangle=|\mathbf{e}_{2}\rangle$,
and
$|\mathbf{e}_{3}^{\prime}\rangle=\frac{1}{\sqrt{N-2}}\sum_{i=3}^{N}|\mathbf{e}_{i}\rangle$
(for $N=2$, there is no need for the third basis). Hence the matrix $M$ can be
expressed as:

$M=M_{3}\oplus\frac{4}{N}\bar{\mathbb{I}},$ (71)

with $M_{3}$ written in the subspace
$\\{|\mathbf{e}^{\prime}_{1}\rangle,|\mathbf{e}^{\prime}_{2}\rangle,|\mathbf{e}^{\prime}_{3}\rangle\\}$
and $\bar{\mathbb{I}}$ is identity in the orthogonal subspace:

$\displaystyle
M_{3}=\frac{1}{N}\begin{pmatrix}N-1&N-3+2e^{i\phi}&\sqrt{N-2}(N-4+e^{i\phi})\\\
N-3+2e^{-i\phi}&N-1&\sqrt{N-2}(N-4+e^{-i\phi})\\\
\sqrt{N-2}(N-4+e^{-i\phi})&\sqrt{N-2}(N-4+e^{i\phi})&(N-2)(N-5)+4\end{pmatrix},$
(72)

Number of parties $N$ | Quantum violation $\delta$
---|---
2 | 1
3 | 0.6667
4 | 0.1250
5 | 0.0333
6 | 0.0139
Table 3: Quantum violation $\delta$ for different generalized fingerprinting
inequality based on full numerical search over $N$ phase parameters.

Since $\textrm{Tr}{M}=N-1$, a necessary condition for $\delta>0$ is that
$\lambda_{\min}<0$, where $\lambda_{\min}$ is the smallest eigenvalue $M_{3}$.
Moreover, from the Cauchy Interlace Theorem, $M_{3}$ will have at most one
negative eigenvalue since its first and second leading principal minors are
positive. Therefore, the quantum violation can be expressed as

$\delta=\max\\{0,-\lambda_{\min}\\}.$ (73)

The smallest eigenvalue of a $3\times 3$ matrix is analytically calculable.
Two useful criteria can be obtained as follows:

(1) Quantum violation $\delta>0$ if and only if

$\displaystyle\cos{\phi}\neq 1$ $\displaystyle\text{if}\leavevmode\nobreak\
N=2,3$ (74) $\displaystyle\cos{\phi}\geq\frac{(N-2)(N-3)-4}{(N-2)(N-3)}\quad$
$\displaystyle\text{if}\leavevmode\nobreak\ N>3$ (75)

(2) Maximal quantum violation $\delta$ is given as:

$\displaystyle\delta=\frac{2}{N}$ $\displaystyle\text{if}\leavevmode\nobreak\
N=2,3$ (76) $\displaystyle\delta=\frac{1}{N(N-2)(N-3)}\quad$
$\displaystyle\text{if}\leavevmode\nobreak\ N>3$ (77)

which is achieved at $\phi=\pi$ for $N=2,3$ and
$\cos\phi=\frac{53-105N+71N^{2}-20N^{3}+2N^{4}}{2(N-2)^{2}(N-3)^{2}}$ for
$N>3$. Surprisingly, these violation saturate the maximal violation in Table 3
where we were considering all phase encoding strategies.

######  Remark.

The optimal encoding strategy for achieving the maximal quantum violation Eq.
(77) is not unique. We can get the same violation with other encoding
strategies: e.g. for even $N$, $\phi_{i}=\phi\leavevmode\nobreak\
\leavevmode\nobreak\ \forall i\leq\frac{N}{2}$ and $\phi_{i}=-\phi$ otherwise
[33]; for odd $N$, $\phi_{N}=\pi$, $\phi_{i}=\phi\leavevmode\nobreak\
\leavevmode\nobreak\ \forall i\leq\lfloor\frac{N}{2}\rfloor$ and
$\phi_{i}=-\phi$ otherwise.

###  4.3 Beyond $N$-Local Quantum Channels

In the previous section, we showed that $N$-local quantum MACs have a much
richer structure than $N$-local classical MACs, and they cannot even be
simulated using $(N,K)$-local classical MACs for any $K<N$. Here we consider
other structural properties of quantum MACs. Similar to our consideration of
$(N,K)$-local classical MACs, we can relax the locality constraint in
$N$-local quantum MACs by allowing $K$ parties to collaborate and perform a
joint N-P encoding across all their subsystems. For some collection of parties
$S$, we will write $\mathcal{E}^{(\mathsf{A}_{s})_{s}}_{(a_{s})_{s}}$ to
denote the joint map performed on systems $\bigotimes_{s\in
S}\mathcal{H}^{\mathsf{A}_{s}}$ for collective input
$(a_{s})_{s}\in\bigtimes_{s\in S}\mathcal{A}_{s}$. Channels that are built in
this fashion will be called $(N,K)$-local quantum MACs, denoted as
$\mathcal{Q}_{N,K}$. We will first show that MACs in $\mathcal{Q}_{N,K}$ can
demonstrate higher-order intereference; more specifically, the $I_{2K}$
equality can be violated. We then calculate the dimension of binary
$(N,K)$-local quantum MACs $\mathcal{Q}_{N,1}([2]^{N};[2])$ and generalize
this result to arbitrary inputs and output.

######  Proposition 10.

For $K\leq\lfloor\frac{N}{2}\rfloor$, a state
$\rho\in\mathcal{H}_{1}^{\bm{\mathsf{A}}}$ can produce a quantum MAC in
$\mathcal{Q}_{N,K}$ that exhibits non-vanishing $2K$-order interference if and
only if it has some off-diagonal term $\rho_{ij}\neq 0$ .

###### Proof.

Clearly, for an incoherent state $\rho$ with $\rho_{ij}=0$ for all $i\neq j$,
the state is incoherent and it cannot even violate any $I_{K+1}$ equality.
Conversely, suppose that $\rho_{ij}\not=0$. To get a quantum violation for the
$I_{2K}$ equality, let us consider two $K$-collaborating groups $S_{i}$ and
$S_{j}$ with $i\in S_{i}$, $j\in S_{j}$, and $S_{i}\cap S_{j}=\emptyset$. Each
group performs a $\\{0,\pi\\}$ phase encoding on path $i$ and $j$ conditioned
on the parity of their inputs in $S_{i}$ and $S_{j}$ respectively, i.e.
$\mathcal{E}^{(\mathsf{A}_{s})_{s\in S_{i}}}_{(a_{s})_{s\in
S_{i}}}(X)=\bigotimes_{s\in
S_{i}\setminus\\{i\\}}\text{id}^{\mathsf{A}_{s}}\otimes(\sigma_{z}^{\oplus_{s\in
S}a_{s}})^{\mathsf{A}_{i}}(X)(\sigma_{z}^{\oplus_{s\in
S}a_{s}})^{\mathsf{A}_{i}}$ where $\sigma_{z}=|0\rangle\langle
0|+e^{i\pi}|1\rangle\langle 1|$. The decoder then measures with POVM
$\left\\{\Pi_{0}=|\psi_{ij}\rangle\langle\psi_{ij}|^{\bm{\mathsf{A}}},\;\Pi_{1}=\mathbb{I}-\Pi_{0}\right\\}$,
where
$\displaystyle|\psi_{ij}\rangle=\frac{1}{\sqrt{2}}\left(|\mathbf{e}_{i}\rangle+\frac{\rho_{ij}^{*}}{|\rho_{ij}|}|\mathbf{e}_{j}\rangle\right)$.
With this scheme, we can achieve $I^{(S_{i}\cup
S_{j})}_{2K}=2^{2K}|\rho_{ij}|$. ∎

######  Remark.

Similarly, for any $k\leq 2K$, we can obtain nonzero $k^{\text{th}}$-order
interference $I^{(S_{i}\cup S_{j})}_{k}(\rho)=2^{k}|\rho_{ij}|$ by choosing
disjoint $S_{i},S_{j}\in\\{1,\cdots,N\\}$ such that $|S_{i}|+|S_{j}|=k$. In
fact, for each $k\leq 2K$, we can achieve maximal $k^{\text{th}}$-order
interference $I^{(S_{i}\cup S_{j})}_{k}(\rho)=2^{k-1}$ by a maximally
coherence state on parties $\mathsf{A}_{i}$ and $\mathsf{A_{j}}$ with
$|\rho_{ij}|=1/2$. However, for a general quantum state
$\rho^{\bm{\mathsf{A}}}$ shared between $N$ senders, it remains open what
strategy extracts maximal higher-order interference.

In Theorem 2, we demonstrated that $\mathcal{C}_{N,K}$ violate $I_{K}$
equality but has vanishing $(K+1)$-order interference, thus has at most
$K$-order interference, analogously, we will show here that $I_{2K+1}$ can not
be violated by any quantum MAC in $\mathcal{Q}_{N,K}$.

######  Proposition 11.

A quantum MAC in $\mathcal{Q}_{N,K}$ can have at most $2K$-order interference.

###### Proof.

As discussed in Section 4.2, MACs in $\mathcal{Q}_{N}$ can exhibit second
order interference, whereas they never violate the $I_{3}$ equality. Now, we
will to generalize this result and demonstrate that any given MAC
$\mathbf{p}_{B|\bm{A}}\in\mathcal{Q}_{N,K}$ always satisfies $I_{2K+1}=0$. For
a general quantum state
$\rho=\sum_{ij}\rho_{ij}|\mathbf{e}_{i}\rangle\langle\mathbf{e}_{j}|\in\mathcal{H}^{\bm{\mathsf{A}}}$,
we have

$\displaystyle\sigma_{a_{1}\cdots a_{N}}$
$\displaystyle=\mathcal{E}^{(\mathsf{A}_{s})_{s\in S_{1}}}_{(a_{s})_{s\in
S_{1}}}\otimes\cdots\otimes\mathcal{E}^{(\mathsf{A}_{s})_{s\in
S_{G}}}_{(a_{s})_{s\in S_{G}}}[\rho]$
$\displaystyle=\sum_{ij}\mathcal{E}^{(\mathsf{A}_{s})_{s\in
S_{I}}}_{(a_{s})_{s\in S_{I}}}\otimes\mathcal{E}^{(\mathsf{A}_{s})_{s\in
S_{J}}}_{(a_{s})_{s\in
S_{J}}}[\rho_{ij}|\mathbf{e}_{i}\rangle\langle\mathbf{e}_{j}|],$ (78)

where we have $G$ different groups with $|S_{i}|\leq K$, $S_{i}\cap
S_{j}=\emptyset$ for any $i,j\in\\{1,\cdots,G\\}$ ($i\neq j$) and
$\bigcup_{i=1}^{G}S_{i}=\\{1,\cdots,N\\}$. To get the last equality, we assume
$i\in S_{I}$ and $j\in S_{J}$, and thus only
$\mathcal{E}^{(\mathsf{A}_{s})_{s\in S_{I}}}_{(a_{s})_{s\in S_{I}}}$ and
$\mathcal{E}^{(\mathsf{A}_{s})_{s\in S_{J}}}_{(a_{s})_{s\in S_{J}}}$ act non-
trivially on the operator
$\rho_{ij}|\mathbf{e}_{i}\rangle\langle\mathbf{e}_{j}|$ since these maps are
N-P operations; i.e. $\mathcal{E}^{(\mathsf{A}_{s})_{s\in
S_{K}}}_{(a_{s})_{s\in
S_{K}}}[|\mathbf{e}_{i}\rangle\langle\mathbf{e}_{j}|]=|\mathbf{e}_{i}\rangle\langle\mathbf{e}_{j}|$
for any $S_{I}\cap S_{K}=\emptyset$ and $S_{J}\cap S_{K}=\emptyset$. Hence,
the $I^{(S)}_{2K+1}(\rho)$ quantity for a given $S$ with $|S|=2K+1$ becomes

$\displaystyle
I^{(S)}_{2K+1}(\rho)=\textrm{Tr}{[\Pi_{0}\sum_{\mathclap{\begin{subarray}{c}a_{s}\in\\{0,1\\}\\\
s\in S\end{subarray}}}(-1)^{\oplus_{i\in S}a_{i}}\sigma_{a_{1}\cdots
a_{N}}]}=0,$ (79)

where the final equality holds because each map on
$\rho_{ij}|\mathbf{e}_{i}\rangle\langle\mathbf{e}_{j}|$ depends on at most
$|S_{I}\cup S_{J}|\leq 2K$ inputs, but the summation is over $2K+1$
parameters. ∎

This observation is intimately connected to the conclusion drawn in [34],
where the authors noted that classical and quantum theories exhibit different
levels of interference depending on the number of particles used in the
experiment. Here we observe a similar result except in a different operational
setting: a single particle is still used, but a different numbers of parties
are allowed to collaborate.

Finally in this section, we study the dimension of the set
$\mathcal{Q}_{N,K}$. For simplicity, here we restrict our attention to the
binary channel and defer the proof of the more general
$\mathcal{Q}_{N,K}(\bm{\mathcal{A}};\mathcal{B})$ to Proposition S4 in [1].

######  Proposition 12.

$\dim\mathcal{Q}_{N,K}([2]^{N};[2])=\sum_{k=0}^{2K}\binom{N}{k}$ for
$K\leq\lfloor\frac{N}{2}\rfloor$, $\dim\mathcal{Q}_{N,K}([2]^{N};[2])=2^{N}$
for $\lfloor\frac{N}{2}\rfloor<K\leq N$

###### Proof.

Let us first consider the case when $K\leq\lfloor\frac{N}{2}\rfloor$. The set
$\mathcal{Q}_{N,K}([2]^{N};[2])$ lives in a $(2\cdot 2^{N})$-dimensional
space, and there are $2^{N}$ normalization condition for each
$\mathbf{p}_{B|\bm{A}}\in\mathcal{Q}_{N}([2]^{N};[2])$. Additionally,
Proposition 11 shows that any $\mathbf{p}_{B|\bm{A}}\in\mathcal{Q}_{N,K}$ is
constrained to have vanishing $I_{2K+1}$ and any higher-order interference.
This means that there are a total of $2^{N}+\sum^{N}_{k=2K+1}\binom{N}{k}$
constraints. Hence, we have

$\dim\mathcal{Q}_{N,K}([2]^{N};[2])\leq\sum_{k=0}^{2K}\binom{N}{k}.$ (80)

To lower bound $\dim\mathcal{Q}_{N,K}([2]^{N};[2])$, we use a subset of the
interference coordinates, originally defined in Eq. (34) by keeping
$k\in\\{0,\cdots,2K\\}$ only:

$\displaystyle\bigcup_{k\in\\{0,\cdots,2K\\}}\bigcup_{\begin{subarray}{c}S\subseteq\\{1,\cdots,N\\}\\\
|S|=k\end{subarray}}\left\\{q(S)\coloneqq(-1)^{k}\sum_{\begin{subarray}{c}a_{s}\in\\{0,1\\}\\\
s\in S\end{subarray}}\prod_{i\in S}(-1)^{a_{i}}p(0|a_{1}\cdots
a_{N})\;\bigg{|}\;\text{$a_{j}=0$ for $j\not\in S$}\right\\}.$ (81)

We consider two classes of points:
(i) Classical MACs: This is the set of $\sum_{k=0}^{K}{N\choose{k}}+1$
affinely independent points in $\mathcal{C}_{N,K}$ as we discussed in Theorem
2 (Eq. 38). Since these MACs are in $\mathcal{C}_{N,K}$, they are also in
$\mathcal{Q}_{N,K}$.
(ii) Quantum MACs: we consider quantum state
$|\psi\rangle^{\mathsf{A}_{i}\mathsf{A}_{j}}=\frac{1}{\sqrt{2}}(|\mathbf{e}_{i}\rangle+|\mathbf{e}_{j}\rangle)$
(with $|\rho_{ij}|=\frac{1}{2}$) shared between parties $i\in S_{i}$, $j\in
S_{j}$ and disjoint groups $S_{i}\cap S_{j}=\emptyset$, then we can construct
quantum MAC $\mathbf{p}^{(S)}_{B|\bm{A}}$ as in Proposition 10 and the remark
below. This quantum MAC can demonstrate maximal $k^{\text{th}}$-order
interference among and only among senders $S=S_{i}\cup S_{j}$ where $|S|=k$.
The above strategy applies for different groups $S$ with $K<|S|\leq 2K$.
Clearly, there are in total $\sum_{k=K+1}^{2K}\binom{N}{k}$ such quantum MACs.

Points in class (i) do not violate $I_{k}$ equalities for any $k>K$ hence have
$q(S)=0$ for any $|S|>K$, while each point considered in class (ii) violates
one and only one $I_{k}$ equality for integer $k=|S|>K$. Specifically, it has
$q(S)=2^{k-1}$ but $q(S^{\prime})=0$ for any $S^{\prime}\neq S$ and
$|S^{\prime}|\geq k$ (For any $S^{\prime}$ we can find one element
$s^{\prime}\in S^{\prime}$ but $s^{\prime}\notin S$, and therefore
$q(S^{\prime})$ will vanish since the quantum MAC
$\mathbf{p}^{(S)}_{B|\bm{A}}$ doesn’t depend on input $a_{s^{\prime}}$). Hence
these points form a upper-triangular matrix and thus are affinely independent.
e.g. the upper-traingular matrix for $\mathcal{Q}_{3,1}$ is:

$\blockarray{c(rrrrrrrr)}q(\emptyset)\leavevmode\nobreak\ \leavevmode\nobreak\
&01000111\\\ q(\\{1\\})\leavevmode\nobreak\ \leavevmode\nobreak\ 00100-1-10\\\
q(\\{2\\})\leavevmode\nobreak\ \leavevmode\nobreak\ 00010-10-1\\\
q(\\{3\\})\leavevmode\nobreak\ \leavevmode\nobreak\ 000010-1-1\\\
q(\\{1,2\\})\leavevmode\nobreak\ \leavevmode\nobreak\ 00000200\\\
q(\\{1,3\\})\leavevmode\nobreak\ \leavevmode\nobreak\ 00000020\\\
q(\\{2,3\\})\leavevmode\nobreak\ \leavevmode\nobreak\ 00000002\\\ ,$ (82)

where the first five columns correspond to the classical MACs, and the sixth
to final columns are $\mathbf{p}^{(S)}_{B|\bm{A}}$ introduced above with
$|S|=2$.

In total then, we obtain a collection of $\sum_{k=0}^{2K}\binom{N}{k}+1$
affinely independent points belonging to $\mathcal{Q}_{N,K}$. Hence we have:

$\dim{\mathcal{Q}_{N,K}}\geq\sum_{k=0}^{2K}\binom{N}{k}.$ (83)

In summary, the dimension of the $\mathcal{Q}_{N,K}$ polytope is
$\sum_{k=0}^{2K}\binom{N}{k}$ for any $1\leq K\leq\lfloor\frac{N}{2}\rfloor$.
Following the same line of reasoning, we can also deduce that
$\dim\mathcal{Q}_{N,K}=\sum_{k=0}^{N}\binom{N}{k}=2^{N}$ for
$\lfloor\frac{N}{2}\rfloor<K\leq N$ ∎

######  Proposition 13.

for $K\leq\lfloor\frac{N}{2}\rfloor$ and $|\mathcal{A}_{i}|=|\mathcal{A}|$ ,
we have

$\dim\mathcal{Q}_{N,K}(\bm{\mathcal{A}},\mathcal{B})=(|\mathcal{B}|-1)\sum_{k=0}^{2K}(|\mathcal{A}|-1)^{k}\binom{N}{k}.$

The proof is given in the supplementary [1]

######  Remark.

The dimension of $(N,K)$-local quantum MAC $\mathcal{Q}_{N,K}$ coincides with
the dimension of $(N,2K)$-local classical MACs $\mathcal{C}_{N,2K}$. However,
the two sets are distinct, that is, $\mathcal{Q}_{N,K}\neq\mathcal{C}_{N,2K}$
in general. For instance, for $N=3$ and $K=1$, the separation can be directly
seen from the quantum violation of fingerprinting inequality in Section 4.2.
For the simplest case with $N=2$ and $K=1$ however, this separation is less
obvious. We detail a proof for $\mathcal{Q}_{2,1}\neq\mathcal{C}_{2,2}$ in the
supplementary [1] and conclude it as the following proposition .

######  Proposition 14.

$\mathcal{Q}_{2,1}([2]^{2};[2])\neq\mathcal{C}_{2,2}([2]^{2};[2])$.

##  5 Connections with Multi-Level Coherence

###  5.1 The Channel Discrimination Task and Multi-Level Coherence of Pure
States

In quantum resource theories, channel discrimination tasks have been used as a
way to witness different types of resourceful states [56]. Here we would now
like to relate our framework to the notion of multi-level coherence, which has
recently been studied in the resource theory of coherence [43, 51]. We begin
by reviewing some elements of this theory [3, 6]. For a $d$-dimensional
quantum system, one begins by fixing an orthonormal basis
$\\{|i\rangle\\}_{i=1}^{d}$ referred to as the incoherent basis. Any state
$\rho\in\mathcal{B}(\mathbb{C}^{d})$ that is diagonal in the incoherent basis
is called incoherent, and we denote the collection of all such states as
$\mathcal{I}$. Then all states not belonging to $\mathcal{I}$, i.e. all states
with non-vanishing off-diagonal terms, are considered to be a resource.

In what sense is a state $\rho\not\in\mathcal{I}$ a resource? One answer can
be found in the context of phase discrimination games [17, 7, 47, 49], a
special case of channel discrimination games. In its most basic form, a phase
discrimination game is a two-party communication task in which Alice first
encodes one of many possible phases $\\{\theta_{k}\\}_{k}$, with respective
probabilities $\\{p_{k}\\}_{k}$, in a $d$-dimensional quantum state
$\rho\in\mathcal{B}(\mathbb{C}^{d})$ by applying the unitary
$U(\theta_{k})=\sum_{j=0}^{d-1}e^{ij\theta_{k}}|j\rangle\langle j|$. Bob
receives the state $\rho_{k}:=U(\theta_{k})\rho U(-\theta_{k})$ and attempts
to determine the encoded variable $k$. As a figure of merit for how well the
state $\rho$ can support the transmission of a phase ensemble
$\Theta=\\{(p_{k},\theta_{k})\\}_{k}$, one could consider the maximum average
success probability

$p_{\Theta}^{*}(\rho)=\max_{\\{\Pi_{k}\\}_{k}}\sum_{k}p_{k}\textrm{Tr}\left[\rho_{k}\Pi_{k}\right],$
(84)

where the maximization is taken over all POVMs $\\{\Pi_{k}\\}_{k}$ on Bob’s
end. Notice that if Alice attempts to encode in an incoherent state, the
information of $k$ is lost: $U(\theta_{k})\delta U(-\theta_{k})=\delta$ for
all $\theta_{k}$ and all $\delta\in\mathcal{I}$. From this we see

$p_{\Theta}^{*}(\mathcal{I}):=p_{\Theta}^{*}(\delta)=\max_{\\{\Pi_{k}\\}_{k}}\sum_{k}p_{k}\textrm{Tr}\left[\delta\Pi_{k}\right]\leq\max_{k}p_{k}\leavevmode\nobreak\
\forall\delta\in\mathcal{I}.$ (85)

One of the main results established in Refs. [47, 49] is that for any state
$\rho\not\in\mathcal{I}$,

$\max_{\Theta=\\{(p_{k},\theta_{k})\\}}\frac{p^{*}_{\Theta}(\rho)}{p^{*}_{\Theta}(\mathcal{I})}>1.$
(86)

Thus every coherent state offers an advantage in some phase discrimination
game.

The bound of Eq. (86) has been tightened in Ref. [51] by considering multi-
level quantum coherence. To explain this, let us say that the coherence rank
of a pure state $|\psi\rangle\in\mathbb{C}^{d}$ is the number of nonzero
coherent amplitudes it possesses [43]. That is, given the expansion
$|\psi\rangle=\sum_{i=1}^{d}c_{i}|i\rangle$, the coherence rank of
$|\psi\rangle$ is
$\text{crk}(|\psi\rangle)=\left|\\{c_{i}\;|\;c_{i}\not=0\\}\right|$. Beyond
pure states, the coherence rank of a density matrix $\rho$ can be defined as

$\text{crk}(\rho)=\min_{\\{p_{i},|\psi_{i}\rangle\\}}\max_{i}\text{crk}(|\psi_{i}\rangle),$
(87)

where the minimization is taken over all ensembles
$\\{p_{i},|\psi_{i}\rangle\\}$ such that
$\rho=\sum_{i}p_{i}|\psi_{i}\rangle\langle\psi_{i}|$. A state is said to have
($K+1$)-level coherence if its coherence rank is $K+1$, and the set of all
states with coherence rank no more than $K$ will be denoted by
$\mathcal{I}_{K}$. Clearly

$\mathcal{I}=\mathcal{I}_{1}\subset\mathcal{I}_{2}\subset\cdots\subset\mathcal{I}_{d}=\mathcal{B}(\mathbb{C}^{d}).$

For the special case of noisy maximally coherent states
$\rho=(1-\lambda)\mathbb{I}/d+\lambda|\Psi_{d}\rangle\langle\Psi_{d}|$ with
coherence rank $K+1$, Ref. [51] has strengthened Eq. (86) to read

$\max_{\Theta=\\{(p_{k},\theta_{k})\\}}\frac{p_{\Theta}^{*}(\rho)}{p_{\Theta}^{*}(\sigma)}>1\qquad\forall\sigma\in\mathcal{I}_{K}.$
(88)

Whether such an inequality holds for general states of coherence rank $K+1$
remains an open problem. However in Theorem 4 and the following remark, we
show that it is true for pure states after generalizing the phase
discrimination game into a channel discrimination game. That is, if
$|\psi\rangle\langle\psi|$ has coherence rank $K+1$, then

$\max_{\mathcal{E}=\\{(p_{k},\mathcal{E}_{k})\\}}\frac{p_{\mathcal{E}}^{*}(\rho)}{p_{\mathcal{E}}^{*}(\sigma)}>1\qquad\forall\sigma\in\mathcal{I}_{K},$
(89)

where similarly the maximum average success probability is
$p_{\mathcal{E}}^{*}(\rho)=\max_{\\{\Pi_{k}\\}_{k}}\sum_{k}p_{k}\textrm{Tr}\left[\mathcal{E}_{k}(\rho)\Pi_{k}\right]$.
This is a consequence of the following theorem.

######  Theorem 4.

For $|\psi\rangle\in\mathcal{H}^{\mathsf{A}_{1},\cdots,\mathsf{A}_{N}}_{1}$,
$\text{crk}(|\psi\rangle)=K+1$ if and only if it violates at least one
$(N,K)$-party generalized fingerprinting inequality.

###### Proof.

By definition, an $N$-level state without $(K+1)$-level coherence can be
written as $\rho=\sum_{i}p_{i}|\psi_{i}\rangle\langle\psi_{i}|$ where
$|\psi_{i}\rangle$ has coherent rank no more than $K$ and thus has support on
a subspace $\mathcal{H}_{1}^{\mathsf{A}_{i_{1}}\cdots\mathsf{A}_{i_{K}}}$.
States of this form will only admit MACs having transition probabilities

$\displaystyle p(0|a_{1},\cdots,a_{N})$
$\displaystyle=\textrm{Tr}\left\\{\Pi_{0}\left[\mathcal{E}^{\mathsf{A}_{1}}_{a_{1}}\otimes\cdots\otimes\mathcal{E}^{\mathsf{A}_{N}}_{a_{N}}\left(\rho^{\bm{\mathsf{A}}}\right)\right]\right\\}$
$\displaystyle=\sum_{i}p_{i}g_{i}(0|a_{i_{1}},\cdots,a_{i_{K}}),$ (90)

where
$\textrm{Tr}\left\\{\Pi_{0}\left[\mathcal{E}^{\mathsf{A}_{i_{1}}}_{a_{i_{1}}}\otimes\cdots\otimes\mathcal{E}^{\mathsf{A}_{i_{K}}}_{a_{i_{K}}}\left(|\psi_{i}\rangle\langle\psi_{i}|\right)\right]\right\\}=g_{i}(0|a_{i_{1}},\cdots,a_{i_{K}})$
with
$\mathcal{E}^{\mathsf{A}_{1}}_{a_{1}}\otimes\cdots\otimes\mathcal{E}^{\mathsf{A}_{N}}_{a_{N}}$
being arbitrary encoding operation, and $\\{\Pi_{0},\mathbb{I}-\Pi_{0}\\}$
being any decoding POVM. If the encoding maps are required to be N-P
operations, these MACs will belong to $\mathcal{C}_{N,K}$, and thus they
cannot violate any $(N,K)$-generalized fingerprinting inequality.

To show that the converse is also true for pure state, let us consider an
arbitrary pure state $|\psi\rangle=\sum_{i=1}^{N}c_{i}|\mathbf{e}_{i}\rangle$
in $\mathcal{H}_{1}^{\bm{\mathsf{A}}}$ with coherent rank
$\text{crk}{|\psi\rangle}=K+1$. Without loss of generality, we assume the
state has non-zero amplitude $c_{i}\neq 0$ for $i\in\\{1,\cdots,K+1\\}$ and
consider the $(N,K)$-party generalized fingerprinting inequality among the
first $K+1$ parties of the form of Eq. (49). Since $|\psi\rangle$ only has
support on a subspace
$\mathcal{H}_{1}^{{\mathsf{A}_{1}}\cdots{\mathsf{A}_{K+1}}}$, we can treat the
$(N,K)$-party generalized fingerprinting inequality as a $(K+1,K)$-party
generalized fingerprinting inequality among the first $K+1$ parties with all
the other parties having fixed inputs. And then we will show the violation of
this inequality based on the violation we obtained for maximally coherent
state in section 4.2

To begin with, let us rewrite the quantum state
$|\psi\rangle=\frac{1}{\sqrt{K+1}}\sum_{i=1}^{K+1}|\mathbf{e}_{i}\rangle$ in
terms of the $(K+1)$-party maximally coherent state $|\Psi_{K+1}\rangle$ as:
$|\psi\rangle=C|\Psi_{K+1}\rangle$, where $C$ is the coefficient matrix
$C=\sqrt{K+1}\text{diag}[c_{1},\dots,c_{K+1}]$. Since the map
$\mathcal{E}_{a_{i}}^{\mathsf{A}_{i}}$ we used in defining $M$ in Eq. (67)
consists of diagonal unitaries, we can define a similar matrix $M^{\prime}$
for any pure state $|\psi\rangle\langle\psi|$ as:

$\displaystyle M^{\prime}:$
$\displaystyle=M(|\Psi_{K+1}\rangle\langle\Psi_{K+1}|)=M(C^{\dagger}|\Psi_{K+1}\rangle\langle\Psi_{K+1}|C)$
$\displaystyle=C^{\dagger}M(|\Psi_{K+1}\rangle\langle\Psi_{K+1}|)C=C^{\dagger}MC.$
(91)

In Section 4.2, we have shown that $\textrm{Tr}{M}=K$ but $\left\lVert
M\right\rVert_{1}>K$ for some specific encoding strategies, which implies that
there exists some normalized vector
$|\alpha\rangle=\sum_{i=1}^{K+1}\alpha_{i}|\mathbf{e}_{i}\rangle$ such that
$\langle\alpha|M|\alpha\rangle<0$. Based on this result, for an pure state
with $(K+1)$-coherent rank, we can define a normalized vector
$|\alpha^{\prime}\rangle=\frac{1}{\sqrt{N_{C}}}C^{-1}|\alpha\rangle$, where
$N_{C}$ is the normalization factor. Hence we can easily observe that:

$\displaystyle\langle\alpha^{\prime}|M^{\prime}|\alpha^{\prime}\rangle$
$\displaystyle=\frac{1}{N_{C}}\langle\alpha|C^{\dagger-1}C^{\dagger}MCC^{-1}|\alpha\rangle$
$\displaystyle=\frac{1}{N_{C}}\langle\alpha|M|\alpha\rangle<0.$ (92)

Thus, $M^{\prime}$ is not positive semi-definite. Since
$\textrm{Tr}{M^{\prime}}=K$ still holds, we have $\left\lVert
M^{\prime}\right\rVert_{1}>K$, which implies quantum violation $\delta>0$ in
Eq. (68).

To summarize, by using the same encoding strategy we have found for the
maximally coherent state $|\Psi_{K+1}\rangle$ in section 4.2, we can always
obtain a quantum violation of a $(N,K)$-party generalized fingerprinting
inequality for any pure state as long as it has $(K+1)$-level coherence. We
can apply the same strategy above for any $N-1\geq K\geq 1$, the violation of
different $(N,K)$-party generalized fingerprinting inequality will then herald
the existence of different level of coherence for a given pure state. ∎

######  Remark.

If $\rho=|\psi\rangle\langle\psi|$ is a pure state with
$\text{crk}(\rho)=K+1$, we can take
$\mathcal{E}=\\{(p_{k},\mathcal{E}_{k})\\}_{k=0}^{1}$ being the channel
ensemble with $p_{0}=\frac{1}{K+1}$, $p_{1}=\frac{K}{K+1}$ and
$\mathcal{E}_{k}$ given by:

$\begin{split}&\mathcal{E}_{0}=\mathcal{E}^{\mathsf{A}_{1}}_{0}\otimes\cdots\otimes\mathcal{E}^{\mathsf{A}_{K}}_{0}\\\
&\mathcal{E}_{1}=\frac{1}{K}\sum_{i=1}^{K}\mathcal{E}^{\mathsf{A}_{1}}_{0}\otimes\cdots\otimes\mathcal{E}^{\mathsf{A}_{i}}_{1}\otimes\cdots\otimes\mathcal{E}^{\mathsf{A}_{K}}_{0},\end{split}$
(93)

where $\mathcal{E}^{\mathsf{A}}_{i}$ can be any N-P operation. The maximum
average success probability will then be expressed as:

$\displaystyle
p_{\mathcal{E}}^{*}(\sigma)=\max_{\\{\Pi_{k}\\}_{k}}\sum_{k}p_{k}\textrm{Tr}\left[\mathcal{E}_{k}(\rho)\Pi_{k}\right]=\max[I_{\text{F}}]$
(94)

with:

$I_{\text{F}}=\frac{1}{K+1}\left(p(0|\overbrace{0\cdots
0}^{K})+\sum_{i=1}^{K}p(1|\overbrace{0\cdots,1_{i},\cdots 0}^{K})\right)$

From Theorem 4, we have that

$p_{\mathcal{E}}^{*}(\rho)>p_{\mathcal{E}}^{*}(\sigma)=\frac{K}{K+1}\quad\forall\sigma\in\mathcal{I}_{K}$
(95)

An important consequence of this corollary is that a state must have
$(K+1)$-level coherence whenever it can win with probability greater than
$\frac{K}{K+1}$ the channel discrimination game given by the channel ensemble
in Eq. (93). There is no information one needs to assume about the measurement
device a priori nor the channels themselves besides their inability to
increase particle number. Hence we conclude that the channel discrimination
task here, or the $(N,K)$-party generalized fingerprinting inequality Eq.
(49), is a semi-device-independent witness of multilevel coherence, and it is
capable of measuring all pure multi-level coherent states.

###  5.2 Three-Level Coherence Witness

For $K+1=3$, we have a stronger inequality-based criterion for three-level
coherence, and the violation of this inequality is both necessary and
sufficient for a large class of three-level quantum state.

######  Lemma 2.

A quantum state has multilevel coherence if and only if
$\left\lVert{\tilde{M}}(\rho)\right\rVert_{1}>1$, where ${\tilde{M}}(\rho)$ is
the associate comparison matrix of $\rho$:

###### Proof.

As showed in Theorem 1 of [51], a quantum state $\rho$ has three-level
coherence if and only if its associated comparison matrix ${\tilde{M}}(\rho)$
is not positive-semidefinite or equivalently
$\left\lVert{\tilde{M}}(\rho)\right\rVert_{1}>1$, where $\left\lVert
A\right\rVert_{1}$ is the trace norm of A: $\left\lVert
A\right\rVert_{1}=\textrm{Tr}{\sqrt{A^{\dagger}A}}$ and the associated
comparison matrix is defined as:

${\tilde{M}}(A)_{ij}=\left\\{\begin{array}[]{ll}&|A|_{ii}\quad\text{if}\leavevmode\nobreak\
\leavevmode\nobreak\ i=j\\\ -&|A|_{ij}\quad\text{if}\leavevmode\nobreak\
\leavevmode\nobreak\ i\neq j\end{array}\right.$ (96)

. ∎

######  Proposition 15.

A three-level quantum state $\rho$ has multi-level coherence if it violates
fingerprinting inequality Eq. (49). The converse is also true if
$U^{\dagger}\rho U$ is a non-negative matrix for some unitary $U$.

###### Proof.

From Theorem 4, if a state $\rho$ has rank at most 2, it does not violate the
fingerprinting inequality.

Conversely, consider a state
$\rho\in\mathcal{B}(\mathcal{H}_{1}^{\mathsf{A}_{1}\mathsf{A}_{2}\mathsf{A}_{3}})$.
As has been discussed in section 4.2, the violation of fingerprinting
inequality is equivalent to
$\left\lVert\mathcal{E}_{M}(\rho)\right\rVert_{1}>2$. If we take the
$\\{0,\pi\\}$ phase encoding strategy with
$\mathcal{E}_{a}(X)=\sigma_{z}^{a}(X)\sigma_{z}^{a}$ for $a\in\\{0,1\\}$ and
$\sigma_{z}=|0\rangle\langle 0|+e^{i\pi}|1\rangle\langle 1|$, it is easy to
see that:

${M}(A)_{ij}=\left\\{\begin{array}[]{ll}&2A_{ii}\quad\text{if}\leavevmode\nobreak\
\leavevmode\nobreak\ i=j\\\ -&2A_{ij}\quad\text{if}\leavevmode\nobreak\
\leavevmode\nobreak\ i\neq j\end{array}\right.,$ (97)

where $M(A)$ is defined similar as in Eq. (67).

For a three-level coherent state $\rho$ in
$\mathcal{H}_{1}^{\mathsf{A}_{1}\mathsf{A}_{2}\mathsf{A}_{3}}$, ${{M}}(\rho)$
has a similar form as the associate comparison matrix ${\tilde{M}}(\rho)$.
More precisely, if $U^{\dagger}\rho U$ is a non-negative matrix for some
unitary $U$, we will have
$2{\tilde{M}}(\rho^{\mathsf{A}_{1}\mathsf{A}_{2}\mathsf{A}_{3}})=U^{\dagger}{M}(\rho^{\mathsf{A}_{1}\mathsf{A}_{2}\mathsf{A}_{3}})U$,
hence from Eq.(68):

$\delta=\frac{1}{2}(4+\left\lVert{M}(\rho)\right\rVert_{1})=\frac{1}{2}(4+2\left\lVert{\tilde{M}}(\rho)\right\rVert_{1})>3.$
(98)

∎

######  Remark.

However, the conclusions drawn in Theorem 4 and Proposition 15 are not true
for some three-level coherent mixed states with complex matrix elements. One
counterexample can be found based on the following state:

$\rho=\begin{pmatrix}\frac{1}{8}&\frac{1}{12}&\frac{1}{6}\\\
\frac{1}{12}&\frac{1}{8}&\frac{i}{8}\\\
\frac{1}{6}&-\frac{i}{8}&\frac{3}{4}.\end{pmatrix}$

One can check $\left\lVert{\tilde{M}}(\rho)\right\rVert>1$, which indicates
that it has multi-level coherence from Lemma 2; however, it can not violate
fingerprinting inequality with any phase encoding and decoding strategy.
Actually, it can not violate any inequality in $\mathcal{C}_{3,2}$ polytope
(Eqns. (46), (47) and (48)) with phase encoding strategy. Whether there is a
quantum violation for a more general encoding strategy is yet unknown.

##  6 Discussion

The study of multiple-access channels in this paper provides an operational
comparison between classical and quantum information processing in the context
of multi-party communication. We have focused on a fine-grained analysis of
the MACs that can be generated using only a single classical/quantum particle
without touching any of its internal degrees of freedom, combined with a
restricted type of encoding. The main results we have established focus on
characterizing different MACs and showing the separation between classical
MACs and quantum MACs in an operational way. Standard quantum fingerprinting
can be seen as just one of many different enhancements that emerge when using
quantum MACs. We have also analyzed the situation in which the locality
constraints on the encoders are partially relaxed and a richer structure of
these MACs was revealed.

In particular, we have identified the generalized fingerprinting inequalities
as valid facets for different $(N,K)$-local classical MACs. This provides one
route for quantifying the quantum advantage of a single quantum particle in
multi-party communication scenarios. Further, $N$-local quantum MACs can
outperform $N$-party classical MACs, even when $N-1$ of the parties are
allowed to collaborate. Finally, we have highlighted the connection of our
framework to the resource theory of multilevel coherence and provided a semi-
device independent approach to witnessing multi-level coherence for a quantum
state.

Our operational framework for analyzing the multiple-access channel is
important, not only for showing the fundamental differences between a
classical particle and a quantum particle with spatial superposition, but also
for quantum enhanced multi-party communication and potential applications in
sensing of complex quantum systems due to the connection to multi-level
coherence [51, 24].

There are many questions remaining from our investigation. We have identified
the generalized fingerprinting inequality as a valid facet for all
$\mathcal{C}_{N,K}$ polytopes. It would be interesting to identify other
facets, something which is infeasible to do using the standard numerical
approach. A related question is to decide which of the $\mathcal{C}_{N,K}$
polytopes can be violated by a given $N$-partite quantum state and how large
such a violation can be. For the case of $\mathcal{Q}_{N,K}$, we showed that
the $I_{2K}$ equality can be violated for all non-classical states, yet the
maximal violation for a given state is still unknown. Additionally, in Section
4.2 we found a quantum violation of the $(N,N-1)$-party generalized
fingerprinting inequality that scales like $N^{-3}$, which is consistent with
the previous results of Ref. [33]. It would be good to know whether an
$O(N^{-3})$ violation is optimal, for not only the generalized fingerprinting
inequality but also for all other facets of
$\mathcal{C}_{N,N-1}([2]^{N};[2])$. It would also be interesting to further
pursue the connection between general multi-level coherent states and the
$(N,K)$-local facet inequalities. Finally, the current results we have
obtained are based on using just a one single particle. A natural next
question is how the classical and quantum MACs compare when more than one
particle or multiple internal degrees of freedom are utilized.

##  7 Acknowledgments

This work was supported by NSF Award 1839177. The authors thank Virginia
Lorenz, Paul Kwiat, Andreas Winter and Kai Shinbrough for helpful discussions