during the preparation of this manuscript.

## References

  * [1] _See Supplemental Material at [] for proofs of the proposition 6, 7, 8, 13, 14 and theorem 3_.
  * Abbott et al. [2018] Alastair A. Abbott, Julian Wechs, Dominic Horsman, Mehdi Mhalla, and Cyril Branciard.  Communication through coherent control of quantum channels, 2018.
  * Äberg [2006] Johan Äberg.  Quantifying superposition, 2006.
  * Arrazola and Lütkenhaus [2014] Juan Miguel Arrazola and Norbert Lütkenhaus.  Quantum communication with coherent states and linear optics.  _Phys. Rev. A_ , 90:042335, Oct 2014.  doi: 10.1103/PhysRevA.90.042335.  URL https://link.aps.org/doi/10.1103/PhysRevA.90.042335.
  * Barvinok [2002] A. Barvinok.  _A Course in Convexity_.  Graduate studies in mathematics. American Mathematical Society, 2002.
  * Baumgratz et al. [2014] T. Baumgratz, M. Cramer, and M. B. Plenio.  Quantifying coherence.  _Phys. Rev. Lett._ , 113:140401, Sep 2014.  doi: 10.1103/PhysRevLett.113.140401.  URL https://link.aps.org/doi/10.1103/PhysRevLett.113.140401.
  * Biswas et al. [2017] Tanmoy Biswas, María García Díaz, and Andreas Winter.  Interferometric visibility and coherence.  _Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences_ , 473(2203):20170170, 2017.  doi: 10.1098/rspa.2017.0170.  URL https://doi.org/10.1098/rspa.2017.0170.
  * Born [1926] Max Born.  Zur quantenmechanik der stoßvorgänge.  _Zeitschrift für Physik_ , 37(12):863–867, Dec 1926.  ISSN 0044-3328.  doi: 10.1007/BF01397477.  URL https://doi.org/10.1007/BF01397477.
  * Brunner et al. [2014] Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani, and Stephanie Wehner.  Bell nonlocality.  _Rev. Mod. Phys._ , 86:419–478, Apr 2014.  doi: 10.1103/RevModPhys.86.419.  URL https://link.aps.org/doi/10.1103/RevModPhys.86.419.
  * Buhrman et al. [2001] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf.  Quantum fingerprinting.  _Phys. Rev. Lett._ , 87:167902, Sep 2001.  doi: 10.1103/PhysRevLett.87.167902.  URL https://link.aps.org/doi/10.1103/PhysRevLett.87.167902.
  * Chiribella and Kristjánsson [2019] Giulio Chiribella and Hlér Kristjánsson.  Quantum shannon theory with superpositions of trajectories.  _Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences_ , 475(2225):20180903, 2019.  doi: 10.1098/rspa.2018.0903.  URL https://doi.org/10.1098/rspa.2018.0903.
  * Chiribella et al. [2018] Giulio Chiribella, Manik Banik, Some Sankar Bhattacharya, Tamal Guha, Mir Alimuddin, Arup Roy, Sutapa Saha, Sristy Agrawal, and Guruprasad Kar.  Indefinite causal order enables perfect quantum communication with zero capacity channel, 2018.
  * Chitambar and Gour [2019] Eric Chitambar and Gilad Gour.  Quantum resource theories.  _Rev. Mod. Phys._ , 91:025001, Apr 2019.  doi: 10.1103/RevModPhys.91.025001.  URL https://link.aps.org/doi/10.1103/RevModPhys.91.025001.
  * Christof and Löbel [1997] T. Christof and A. Löbel.  _porta, URL http://porta.zib.de_ , 1997.  URL http://porta.zib.de/.
  * Cleve et al. [2004] R. Cleve, P. Hoyer, B. Toner, and J. Watrous.  Consequences and limits of nonlocal strategies.  In _Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004._ , pages 236–249, 2004.  doi: 10.1109/CCC.2004.1313847.  URL https://doi.org/10.1109/CCC.2004.1313847.
  * Coecke et al. [2016] Bob Coecke, Tobias Fritz, and Robert W. Spekkens.  A mathematical theory of resources.  _Information and Computation_ , 250:59 – 86, 2016.  ISSN 0890-5401.  doi: https://doi.org/10.1016/j.ic.2016.02.008.  URL http://www.sciencedirect.com/science/article/pii/S0890540116000353.  Quantum Physics and Logic.
  * Coles [2016] Patrick J. Coles.  Entropic framework for wave-particle duality in multipath interferometers.  _Phys. Rev. A_ , 93:062111, Jun 2016.  doi: 10.1103/PhysRevA.93.062111.  URL https://link.aps.org/doi/10.1103/PhysRevA.93.062111.
  * Cover and Thomas [2006] Thomas M. Cover and Joy A. Thomas.  _Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing)_.  Wiley-Interscience, USA, 2006.  ISBN 0471241954.  doi: 10.5555/1146355.  URL https://dl.acm.org/doi/10.5555/1146355.
  * Dakić et al. [2014] B Dakić, T Paterek, and Č Brukner.  Density cubes and higher-order interference theories.  _New Journal of Physics_ , 16(2):023028, feb 2014\.  doi: 10.1088/1367-2630/16/2/023028.  URL https://doi.org/10.1088%2F1367-2630%2F16%2F2%2F023028.
  * Del Santo and Dakić [2018] Flavio Del Santo and Borivoje Dakić.  Two-way communication with a single quantum particle.  _Phys. Rev. Lett._ , 120:060503, Feb 2018.  doi: 10.1103/PhysRevLett.120.060503.  URL https://link.aps.org/doi/10.1103/PhysRevLett.120.060503.
  * Del Santo and Dakić [2020] Flavio Del Santo and Borivoje Dakić.  Coherence equality and communication in a quantum superposition.  _Phys. Rev. Lett._ , 124:190501, May 2020.  doi: 10.1103/PhysRevLett.124.190501.  URL https://link.aps.org/doi/10.1103/PhysRevLett.124.190501.
  * Ebler et al. [2018] Daniel Ebler, Sina Salek, and Giulio Chiribella.  Enhanced communication with the assistance of indefinite causal order.  _Phys. Rev. Lett._ , 120:120502, Mar 2018.  doi: 10.1103/PhysRevLett.120.120502.  URL https://link.aps.org/doi/10.1103/PhysRevLett.120.120502.
  * Garcia-Escartin and Chamorro-Posada [2013] Juan Carlos Garcia-Escartin and Pedro Chamorro-Posada.  swap test and hong-ou-mandel effect are equivalent.  _Phys. Rev. A_ , 87:052330, May 2013.  doi: 10.1103/PhysRevA.87.052330.  URL https://link.aps.org/doi/10.1103/PhysRevA.87.052330.
  * Giovannetti et al. [2011] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone.  Advances in quantum metrology.  _Nature Photonics_ , 5(4):222–229, Apr 2011.  ISSN 1749-4893.  doi: 10.1038/nphoton.2011.35.  URL https://doi.org/10.1038/nphoton.2011.35.
  * Goswami et al. [2020] K. Goswami, Y. Cao, G. A. Paz-Silva, J. Romero, and A. G. White.  Increasing communication capacity via superposition of order.  _Phys. Rev. Research_ , 2:033292, Aug 2020.  doi: 10.1103/PhysRevResearch.2.033292.  URL https://link.aps.org/doi/10.1103/PhysRevResearch.2.033292.
  * Gour and Spekkens [2008] Gilad Gour and Robert W Spekkens.  The resource theory of quantum reference frames: manipulations and monotones.  _New Journal of Physics_ , 10(3):033023, mar 2008\.  doi: 10.1088/1367-2630/10/3/033023.  URL https://doi.org/10.1088%2F1367-2630%2F10%2F3%2F033023.
  * Grangier et al. [1986] P Grangier, G Roger, and A Aspect.  Experimental evidence for a photon anticorrelation effect on a beam splitter: A new light on single-photon interferences.  _Europhysics Letters (EPL)_ , 1(4):173–179, feb 1986.  doi: 10.1209/0295-5075/1/4/004.  URL https://doi.org/10.1209%2F0295-5075%2F1%2F4%2F004.
  * Helstrom [1969] Carl W. Helstrom.  Quantum detection and estimation theory.  _Journal of Statistical Physics_ , 1(2):231–252, Jun 1969.  ISSN 1572-9613.  doi: 10.1007/BF01007479.  URL https://doi.org/10.1007/BF01007479.
  * Horn et al. [2005a] Rolf T. Horn, S. A. Babichev, Karl-Peter Marzlin, A. I. Lvovsky, and Barry C. Sanders.  Single-qubit optical quantum fingerprinting.  _Phys. Rev. Lett._ , 95:150502, Oct 2005a.  doi: 10.1103/PhysRevLett.95.150502.  URL https://link.aps.org/doi/10.1103/PhysRevLett.95.150502.
  * Horn et al. [2005b] Rolf T. Horn, A. J. Scott, Jonathan Walgate, Richard Cleve, A. I. Lvovsky, and Barry C. Sanders.  Classical and quantum fingerprinting with shared randomness and one-sided error.  _Quantum Inf. Comput._ , 5, 2005b.
  * Horodecki and Oppenheim [2013] Michał Horodecki and Jonathan Oppenheim.  (quantumness in the context of) resource theories.  _International Journal of Modern Physics B_ , 27(01n03):1345019, 2013.  doi: 10.1142/S0217979213450197.  URL https://doi.org/10.1142/S0217979213450197.
  * Horvat [2019] Sebastian Horvat.  Quantum superposition as a resource for quantum communication.  Master’s thesis, University of Zagreb, Croatia, 2019.
  * Horvat and Dakić [2021a] Sebastian Horvat and Borivoje Dakić.  Quantum enhancement to information acquisition speed.  _New Journal of Physics_ , 23(3):033008, mar 2021a.  doi: 10.1088/1367-2630/abe9d4.  URL https://doi.org/10.1088/1367-2630/abe9d4.
  * Horvat and Dakić [2021b] Sebastian Horvat and Borivoje Dakić.  Interference as an information-theoretic game.  _Quantum_ , 5:404, March 2021b.  ISSN 2521-327X.  doi: 10.22331/q-2021-03-08-404.  URL https://doi.org/10.22331/q-2021-03-08-404.
  * Hsieh et al. [2008] M. Hsieh, I. Devetak, and A. Winter.  Entanglement-assisted capacity of quantum multiple-access channels.  _IEEE Transactions on Information Theory_ , 54(7):3078–3090, 2008.  doi: 10.1109/TIT.2008.924726.  URL https://doi.org/10.1109/TIT.2008.924726.
  * Hsu et al. [2020] Li-Yi Hsu, Ching-Yi Lai, You-Chia Chang, Chien-Ming Wu, and Ray-Kuang Lee.  Carrying an arbitrarily large amount of information using a single quantum particle.  _Phys. Rev. A_ , 102:022620, Aug 2020.  doi: 10.1103/PhysRevA.102.022620.  URL https://link.aps.org/doi/10.1103/PhysRevA.102.022620.
  * Jacques et al. [2005] V. Jacques, E. Wu, T. Toury, F. Treussart, A. Aspect, P. Grangier, and J.-F. Roch.  Single-photon wavefront-splitting interference.  _The European Physical Journal D - Atomic, Molecular, Optical and Plasma Physics_ , 35(3):561–565, Sep 2005.  ISSN 1434-6079.  doi: 10.1140/epjd/e2005-00201-y.  URL https://doi.org/10.1140/epjd/e2005-00201-y.
  * Kristjánsson et al. [2019] Hlér Kristjánsson, Giulio Chiribella, Sina Salek, Daniel Ebler, and Matthew Wilson.  Resource theories of communication, 2019.
  * Kristjánsson et al. [2020] Hlér Kristjánsson, Giulio Chiribella, Sina Salek, Daniel Ebler, and Matthew Wilson.  Resource theories of communication.  _New Journal of Physics_ , 22(7):073014, jul 2020\.  doi: 10.1088/1367-2630/ab8ef7.
  * Kristjánsson et al. [2020] Hlér Kristjánsson, Wenxu Mao, and Giulio Chiribella.  Single-particle communication through correlated noise, 2020.
  * Leditzky et al. [2020] Felix Leditzky, Mohammad A. Alhejji, Joshua Levin, and Graeme Smith.  Playing games with multiple access channels.  _Nature Communications_ , 11(1):1497, Mar 2020\.  ISSN 2041-1723.  doi: 10.1038/s41467-020-15240-w.  URL https://doi.org/10.1038/s41467-020-15240-w.
  * Lee and Selby [2017] Ciarán M. Lee and John H. Selby.  Higher-order interference in extensions of quantum theory.  _Foundations of Physics_ , 47(1):89–112, Jan 2017\.  ISSN 1572-9516.  doi: 10.1007/s10701-016-0045-4.  URL https://doi.org/10.1007/s10701-016-0045-4.
  * Levi and Mintert [2014] Federico Levi and Florian Mintert.  A quantitative theory of coherent delocalization.  _New Journal of Physics_ , 16(3):033007, mar 2014\.  doi: 10.1088/1367-2630/16/3/033007.  URL https://doi.org/10.1088%2F1367-2630%2F16%2F3%2F033007.
  * Masanes [2003] Ll Masanes.  Tight bell inequality for d-outcome measurements correlations.  _Quantum Info. Comput._ , 3(4):345–358, July 2003.  ISSN 1533-7146.  doi: 10.5555/2011528.2011532.  URL https://dl.acm.org/doi/10.5555/2011528.2011532.
  * Massar [2005] S. Massar.  Quantum fingerprinting with a single particle.  _Phys. Rev. A_ , 71:012310, Jan 2005.  doi: 10.1103/PhysRevA.71.012310.  URL https://link.aps.org/doi/10.1103/PhysRevA.71.012310.
  * Merzbacher [1998] E. Merzbacher.  _Quantum Mechanics_.  Wiley, 1998.  ISBN 9780471887027.
  * Napoli et al. [2016] Carmine Napoli, Thomas R. Bromley, Marco Cianciaruso, Marco Piani, Nathaniel Johnston, and Gerardo Adesso.  Robustness of coherence: An operational and observable measure of quantum coherence.  _Phys. Rev. Lett._ , 116:150502, Apr 2016.  doi: 10.1103/PhysRevLett.116.150502.  URL https://link.aps.org/doi/10.1103/PhysRevLett.116.150502.
  * Oreshkov et al. [2012] Ognyan Oreshkov, Fabio Costa, and Časlav Brukner.  Quantum correlations with no causal order.  _Nature Communications_ , 3(1):1092, Oct 2012\.  ISSN 2041-1723.  doi: 10.1038/ncomms2076.  URL https://doi.org/10.1038/ncomms2076.
  * Piani et al. [2016] Marco Piani, Marco Cianciaruso, Thomas R. Bromley, Carmine Napoli, Nathaniel Johnston, and Gerardo Adesso.  Robustness of asymmetry and coherence of quantum states.  _Phys. Rev. A_ , 93:042107, Apr 2016.  doi: 10.1103/PhysRevA.93.042107.  URL https://link.aps.org/doi/10.1103/PhysRevA.93.042107.
  * Pironio [2005] Stefano Pironio.  Lifting bell inequalities.  _Journal of Mathematical Physics_ , 46(6):062112, 2005.  doi: 10.1063/1.1928727.  URL https://doi.org/10.1063/1.1928727.
  * Ringbauer et al. [2018] Martin Ringbauer, Thomas R. Bromley, Marco Cianciaruso, Ludovico Lami, W. Y. Sarah Lau, Gerardo Adesso, Andrew G. White, Alessandro Fedrizzi, and Marco Piani.  Certification and quantification of multilevel quantum coherence.  _Phys. Rev. X_ , 8:041007, Oct 2018.  doi: 10.1103/PhysRevX.8.041007.  URL https://link.aps.org/doi/10.1103/PhysRevX.8.041007.
  * Rozema et al. [2020] Lee A. Rozema, Zhao Zhuo, Tomasz Paterek, and Borivoje Dakić.  Higher-order interference in quantum physics, 2020.
  * Sinha et al. [2010] Urbasi Sinha, Christophe Couteau, Thomas Jennewein, Raymond Laflamme, and Gregor Weihs.  Ruling out multi-order interference in quantum mechanics.  _Science_ , 329(5990):418–421, 2010.  ISSN 0036-8075.  doi: 10.1126/science.1190545.  URL https://science.sciencemag.org/content/329/5990/418.
  * Sorkin [1994] Rafael D. Sorkin.  Quantum mechanics as quantum measure theory.  _Modern Physics Letters A_ , 09(33):3119–3127, 1994.  doi: 10.1142/S021773239400294X.  URL https://doi.org/10.1142/S021773239400294X.
  * Svetlichny [1987] George Svetlichny.  Distinguishing three-body from two-body nonseparability by a bell-type inequality.  _Phys. Rev. D_ , 35:3066–3069, May 1987.  doi: 10.1103/PhysRevD.35.3066.  URL https://link.aps.org/doi/10.1103/PhysRevD.35.3066.
  * Takagi and Regula [2019] Ryuji Takagi and Bartosz Regula.  General resource theories in quantum mechanics and beyond: Operational characterization via discrimination tasks.  _Phys. Rev. X_ , 9:031053, Sep 2019.  doi: 10.1103/PhysRevX.9.031053.  URL https://link.aps.org/doi/10.1103/PhysRevX.9.031053.
  * Tse and Viswanath [2005] David Tse and Pramod Viswanath.  _Fundamentals of Wireless Communication_.  Cambridge University Press, Cambridge, 2005.  ISBN 9780521845274.  doi: 10.1017/CBO9780511807213.  URL https://doi.org/10.1017/CBO9780511807213.
  * Ududec et al. [2011] Cozmin Ududec, Howard Barnum, and Joseph Emerson.  Three slit experiments and the structure of quantum theory.  _Foundations of Physics_ , 41(3):396–405, Mar 2011.  ISSN 1572-9516.  doi: 10.1007/s10701-010-9429-z.  URL https://doi.org/10.1007/s10701-010-9429-z.
  * Winter [2001] A. Winter.  The capacity of the quantum multiple-access channel.  _IEEE Transactions on Information Theory_ , 47(7):3059–3065, 2001.  doi: 10.1109/18.959287.  URL https://doi.org/10.1109/18.959287.

##  8 Supplementary material

Here we provide detailed proofs of proposition 16, 17 and 18 for the inclusion
relation between different classical MACs in section 8.1; proposition 13 and
theorem 5 for the dimension of classical and quantum MACs for arbitary inputs
and output in section 8.2; and proposition 14 for the separation between the
most simple classical MACs $\mathcal{C}_{2,2}([2]^{2},[2])$ and quantum MACs
$\mathcal{Q}_{2}([2]^{2},[2])$ in section 8.3

###  8.1 Separation and convexity of $(N,K)$-local Classical MACs

######  Proposition 16.

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})]$.

###### Proof.

We consider the extreme case of one party $N=1$ and $K=1$; i.e. one-local MACs
$\mathcal{C}^{\prime}_{1}([3];[3])$. Note that in this case we always have
$\mathcal{C}^{\prime}_{1}(\bm{\mathcal{A}};\mathcal{B})=\mathcal{C}_{1}(\bm{\mathcal{A}};\mathcal{B})$.
Let $\mathbf{p}^{\prime}_{B|A}\in\mathcal{C}^{\prime}_{1}([3];[3])$ have
coordinates $p^{\prime}(b|0)=\delta_{b,0}$ and
$p^{\prime}(b|1)=p^{\prime}(b|2)=\delta_{b,2}$, and let
$\mathbf{p}^{\prime\prime}_{B|A}\in\mathcal{C}^{\prime}_{1}([3];[3])$ have
coordinates $p^{\prime\prime}(b|1)=\delta_{b,1}$ and
$p^{\prime\prime}(b|0)=p^{\prime\prime}(b|2)=\delta_{b,2}$. We will show their
mixture
$\mathbf{p}_{B|A}=\lambda\mathbf{p}^{\prime}_{B|A}+(1-\lambda)\mathbf{p}^{\prime\prime}_{B|A}$
does not belong to $\mathcal{C}^{\prime}_{1}([3];[3])$ for $\lambda\in(0,1)$.
For if it does, we could write

$\displaystyle p(2|2)=\lambda
p^{\prime}(2|2)+(1-\lambda)p^{\prime\prime}(2|2)=\sum_{m\in\\{0,\mathbf{e}_{1}\\}}d(2|m)q(m|2)=1$

This implies that there exist $m\in\\{0,\mathbf{e}_{1}\\}$ such that
$d(2|m)=1$. Without loss of generality, we let $d(2|0)=1$, and so
$d(1|0)=d(0|0)=0$. This means that

$\displaystyle p(0|a_{1})$
$\displaystyle=d(0|\mathbf{e}_{1})q(\mathbf{e}_{1}|a_{1})$ $\displaystyle
p(1|a_{1})$ $\displaystyle=d(1|\mathbf{e}_{1})q(\mathbf{e}_{1}|a_{1}).$

However, this easily leads to a contradiction. The mixture $\mathbf{p}_{B|A}$
has coordinates $\\{p(0|0),p(0|1)\\}=\\{\lambda,0\\}$ which requires
$q(\mathbf{e}_{1}|0)\neq 0$ and $q(\mathbf{e}_{1}|1)=0$. Likewise,
$\mathbf{p}_{B|A}$ has coordinates $\\{p(1|0),p(1|1)\\}=\\{0,1-\lambda\\}$
which can only be obtained when $q(\mathbf{e}_{1}|0)=0$ and
$q(\mathbf{e}_{1}|1)\neq 0$. Therefore, $\mathbf{p}_{B|A}$ cannot belong to
$\mathcal{C}^{\prime}_{1}([3];[3])$. ∎

######  Remark.

In fact, a distinction between $\text{conv}[\mathcal{C}_{N}]$ and
$\mathcal{C}^{(\text{sep})}_{N}$ can also be seen that is
$\text{conv}[\mathcal{C}_{N}(\bm{\mathcal{A}},\mathcal{B})]\neq\mathcal{C}_{N}^{(\text{sep})}(\bm{\mathcal{A}},\mathcal{B})$
when $|\mathcal{B}|>2$ and $|\mathcal{A}_{i}|>2$. As a simple example,
consider the one-local MACs $\text{conv}[\mathcal{C}_{1}([3];[3])]$ and
$\mathcal{C}^{(\text{sep})}_{1}([3];[3])$. The latter consists of all channels
$[3]\to[3]$ (including the identity); in contrast, the former must be built by
the exchange of just a single particle, and therefore all such channels will
have a bounded capacity of one bit.

For $K>1$, the problem is even more intricate, from proposition 2 in the main
text, we know that the four classes of $(N,K)$-local MACs are all equivalent
when $|\mathcal{B}|=2$; the counterexample in proposition 16 also be applied
to $(N,K)$-local MACs as long as $|\mathcal{B}|>\mathcal{M}_{s}=K+1$ since
$\prod_{i\in S}|\mathcal{A}_{i}|>\mathcal{M}_{s}$ always holds, thus, we can
conclude that $\mathcal{C}^{\prime}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$,
$\text{conv}[\mathcal{C}_{N,K}(\bm{\mathcal{A}},\mathcal{B})]$, and
$\mathcal{C}^{(\text{sep})}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$ are distinct
when $|\mathcal{B}|>K+1$. For the remaining cases, their relation are provided
by the following two propositions.

######  Proposition 17.

For $|\mathcal{B}|>2$ and $N>K\geq 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})$.

###### Proof.

We consider
$\mathbf{p}^{\prime}_{B|A_{1}A_{2}A_{3}},\mathbf{p}^{\prime\prime}_{B|A_{1}A_{2}A_{3}}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\
\mathbf{p}^{\prime\prime\prime}_{B|A_{1}A_{2}A_{3}}\in\mathcal{C}_{3,2}([2]^{3};[3])$
having coordinates $p^{\prime}(b|a_{1},a_{2},a_{3})=g_{12}(b|a_{1},a_{2})$,
$p^{\prime\prime}(b|a_{1},a_{2},a_{3})=g_{13}(b|a_{1},a_{3})$ and
$p^{\prime\prime}(b|a_{1},a_{2},a_{3})=g_{23}(b|a_{2},a_{3})$ with
$g_{S}(0|0,0)=1$, $g_{S}(1|0,1)=1$, $g_{S}(2|1,0)=1$ and $g_{S}(2|1,1)=1$ for
any $S\in\\{13,13,23\\}$. We will show their mixture
$\mathbf{p}_{B|A_{1}A_{2}A_{3}}=\lambda_{1}\mathbf{p}^{\prime}_{B|A_{1}A_{2}A_{3}}+\lambda_{2}\mathbf{p}^{\prime}_{B|A_{1}A_{2}A_{3}}+(1-\lambda_{1}-\lambda_{2})\mathbf{p}^{\prime\prime}_{B|A_{1}A_{2}A_{3}}$
does not belong to $\mathcal{C}_{3,2}([2]^{3};[3])$ for $\lambda_{1}\in(0,1)$
and $\lambda_{2}\in(0,1-\lambda_{1})$. For if it did, then by Eq. (14) in the
main text we could write $p(b|a_{1},a_{2},a_{3})$ as:

$\displaystyle\lambda_{1}g_{12}(b|a_{1},a_{2})+\lambda_{1}g_{13}(b|a_{1},a_{3})+(1-\lambda_{1}-\lambda_{2})g_{23}(b|a_{2},a_{3})=\sum_{S}p_{S}\sum_{m\in\mathcal{M}_{S}}d(b|m)q_{S}(m|(a_{s})_{s\in
S}).$ (99)

Since $g_{S}$ are all extreme points, one can verify that
$p(b|a_{1},a_{2},a_{3})$ has unique decomposition similarly as what we did in
proposition 4, thus the previous equation implies that:

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

Since $g_{S}$ are all deterministic MAC with three different outputs
conditional on different inputs, we should have
$d(b|0)=d(b^{\prime}|\mathbf{e}_{1})=d(b^{\prime\prime}|\mathbf{e}_{2})=d(b^{\prime\prime\prime}|\mathbf{e}_{3})=1$
for some $b\neq b^{\prime}\neq b^{\prime\prime}\neq b^{\prime\prime\prime}$.
This contradicts with the fact $|\mathcal{B}|=3$ hence
$\mathbf{p}_{B|A_{1}A_{2}A_{3}}$ is not in
$\mathcal{C}^{\prime}_{3,2}([2]^{3};[3])$ and
$\mathcal{C}^{\prime}_{3,2}([2]^{3};[3])$ is non-convex. On the other hand, as
has been shown in Proposition 18, $\mathcal{C}^{\prime}_{3,2}([2]^{3};[3])$ is
convex, we have in general
$\mathcal{C}_{N,K}(\bm{\mathcal{A}};\mathcal{B})\neq\mathcal{C}^{\prime}_{N,K}(\bm{\mathcal{A}};\mathcal{B})$.
∎

While $\mathcal{C}_{N,K}(\bm{\mathcal{A}};\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 if $|\mathcal{B}|\leq
K+1$.

######  Proposition 18.

$\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$.

###### Proof.

Clearly
$\mathcal{C}^{\prime}_{N,K}(\bm{\mathcal{A}};\mathcal{B})\subset\mathcal{C}_{N,K}^{(\text{sep})}(\bm{\mathcal{A}};\mathcal{B})$.
Conversely, we can construct a deterministic decoder by $d_{S}(0|0)=1$ and
$d_{S}(b|\mathbf{\tilde{e}}_{b})=1$, and encoders by $q_{S}(0|(a_{s})_{s\in
S})=g_{S}(0|(a_{s})_{s\in S})$ and $q_{S}(\mathbf{\tilde{e}}_{b}|(a_{s})_{s\in
S})=g_{S}(b|(a_{s})_{s\in S})$, where $\mathbf{\tilde{e}}_{b}$ is the
$b^{\text{th}}$ non-zero element in $\mathcal{M}_{S}$. Thus, we have that any
MAC having form Eq. (22) in the main text can be written as Eq. (21). ∎

Different from Proposition 2 in the main text, the shared randomness in the
$(N,K)$-local setting is crucial. Without knowing the grouping $S$, the
decoder will not be able to correctly associate the encoding $\mathbf{e}_{i}$
to the group of parties that sent it.

###  8.2 Dimensions of $(N,K)$-local Classical MACs and quantum MACs

In this section, we extend Theorem 2 and Proposition 9 in the main text to the
case of arbitrary inputs $\mathcal{A}_{i}$ and output $\mathcal{B}$. These
theorem, proposition and their proofs are similar to our original results. To
proceed this section, the notations have to be generalized as follows.

To begin with, any MAC in $\mathcal{C}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$ or
$\mathcal{Q}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$ can be envisioned as a point
$\mathbf{p}_{B|\bm{A}}$ in
($|\mathcal{B}|\cdot\prod_{k=1}^{N}|\mathcal{A}_{k}|$)-dimensional Euclidean
space with transition coordinates
$(p(b|a_{1},\cdots,a_{N}))_{b\in\mathcal{B},a_{i}\in\mathcal{A}_{i}}$. To
facilitate our analysis, we first introduce new interference coordinates
analogous to Eq. (39) in the main text:

$\displaystyle\bigcup_{b\in\mathcal{B}}\bigcup_{\begin{subarray}{c}k\in\\{0,\cdots,N\\}\\\
S\subseteq\\{1,\cdots,N\\}\\\
|S|=k\end{subarray}}\bigcup_{\begin{subarray}{c}\alpha_{s}\in\mathcal{A}_{s}\backslash\\{0\\}\\\
s\in
S\end{subarray}}\left\\{q(b,S,\\{\alpha_{s}\\}_{s}):=(-1)^{k}\sum_{\begin{subarray}{c}a_{s}\in\\{0,\alpha_{s}\\}\\\
s\in S\end{subarray}}\prod_{i\in
S}f(a_{i})p(b|a_{1},\cdots,a_{N})\;\bigg{|}\;\text{$a_{j}=0$ for $j\not\in
S$}\right\\},$ (100)

where $f(a_{i})=1$ if $a_{i}=0$ and $f(a_{i})=-1$ when $a_{i}\neq 0$. These
new coordinates will have extra dependence on the output $b$ and nonzero input
set $\\{\alpha_{s}\\}_{s}$ comparing to Eq. (39). One can easily check that
there are exactly $|\mathcal{B}|\cdot\prod_{k=1}^{N}|\mathcal{A}_{k}|$
elements in this basis since

$|\mathcal{B}|\cdot\sum_{k=0}^{N}\sum_{i_{1}=1}^{N}\sum^{N}_{i_{2}>i_{1}}\cdots\sum^{N}_{i_{k}>i_{k-1}}(|\mathcal{A}_{i_{1}}|-1)\times\cdots\times(|\mathcal{A}_{i_{k}}|-1)=|\mathcal{B}|\cdot\prod_{k=1}^{N}|\mathcal{A}_{k}|.$

This equality can be established as follows. We define the polynomial
function:

$p(x)\coloneqq\prod_{k=1}^{N}[(|\mathcal{A}_{k}|-1)+x]=\sum_{k=0}^{N}a_{k}x^{k},$

with the coefficients of the polynomial given as:

$a_{k}=\sum_{i_{1}=1}^{N}\sum^{N}_{i_{2}>i_{1}}\cdots\sum^{N}_{i_{k}>i_{k-1}}(|\mathcal{A}_{i_{1}}|-1)\times\cdots\times(|\mathcal{A}_{i_{k}}|-1).$

Hence,

$\prod_{k=1}^{N}|\mathcal{A}_{k}|=p(1)=\sum_{k=0}^{N}a_{k}=\sum_{k=0}^{N}\sum_{i_{1}=1}^{N}\sum^{N}_{i_{2}>i_{1}}\cdots\sum^{N}_{i_{k}>i_{k-1}}(|\mathcal{A}_{i_{1}}|-1)\times\cdots\times(|\mathcal{A}_{i_{k}}|-1).$

Next, we identify a linearly independent set of MACs using the interference
coordinates. For a fixed $b$, $S$, and $\\{\alpha_{s}\\}_{s}$, the coordinate
$q(b,S,\\{\alpha_{s}\\}_{s})$ is a linear combination of transition
coordinates, of which one and only one has output $b$ and $k$ inputs belonging
to $\\{\alpha_{s}\\}_{s}$ with all others being 0. By the same reasoning as
for theorem 2 in the main text, these new interference coordinates are linear
independent when we consider all choices of grouping $S$, input set
$\\{\alpha_{s}\\}_{s}$ and output $b$. Therefore we can safely using the new
interference basis in Eq. (100) to discuss any given point
$\mathbf{p}_{B|\bm{A}}$ in both $\mathcal{C}_{N,K}$ and $\mathcal{Q}_{N,K}$

######  Theorem 5.

$\dim\mathcal{C}_{N,K}(\bm{\mathcal{A}},\mathcal{B})=(|\mathcal{B}|-1)\sum_{k=0}^{K}(|\mathcal{A}|-1)^{k}\binom{N}{k}$
with all $|\mathcal{A}_{i}|=|\mathcal{A}|$ for simplicity.

###### Proof.

Each $\mathbf{p}_{B|\bm{A}}\in\mathcal{C}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$
satisfies $\prod_{k=1}^{N}|\mathcal{A}_{k}|$ normalization conditions $1=\sum
p(b|a_{1},\cdots,a_{N})$, with $a_{i}\in[\mathcal{A}_{i}]$. As observed
before, $I_{K+1}^{(S)}(\mathbf{p}_{B|\bm{A}})=0$ for all $|S|\geq K+1$ for
binary inputs/output case. It is easy to extend these constraints to arbitrary
inputs/output by simply considering inputs/output relabeling, and hence we can
write each point in a subset of the interference coordinates in Eq. (100):

$\displaystyle\bigcup_{\begin{subarray}{c}b\in\mathcal{B}\\\
b\neq|\mathcal{B}|-1\end{subarray}}\bigcup_{\begin{subarray}{c}k\in\\{0,\cdots,K\\}\\\
S\subseteq\\{1,\cdots,N\\}\\\
|S|=k\end{subarray}}\bigcup_{\begin{subarray}{c}\alpha_{s}\in\mathcal{A}_{s}\backslash\\{0\\}\\\
s\in
S\end{subarray}}\left\\{q(b,S,\\{\alpha_{s}\\}_{s}):=(-1)^{k}\sum_{\begin{subarray}{c}a_{s}\in\\{0,\alpha_{s}\\}\\\
s\in S\end{subarray}}\prod_{i\in
S}f(a_{i})p(b|a_{1},\cdots,a_{N})\;\bigg{|}\;\text{$a_{j}=0$ for $j\not\in
S$}\right\\},$ (101)

with all the other elements being redundant. e.g. for $k\geq K+1$, the terms
are actually zero (no $k^{\text{th}}$-order interference for $k\geq K+1$) and
for $b=|B|-1$, the information can be retrieved from the normalization
constraints.

There are $(|\mathcal{B}|-1)\sum_{k=0}^{K}(|\mathcal{A}|-1)^{k}\binom{N}{k}$
elements in above set, which upper bound the dimension of
$\dim\mathcal{C}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$

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

To compute a lower bound on $\dim\mathcal{C}_{N,K}$ we need to form a family
of affinely independent points. To get enough affinely independent points, we
consider the following family of $(N,K)$-local classical MACs (i.e. having the
form of Eq. (15)):

$\begin{split}&p(b|a_{1},\cdots,a_{N})=\delta_{b\beta},\qquad\beta\in\mathcal{B}\\\
&p(b|a_{1},\cdots,a_{N})=d(b|0)q_{S}(0|(a_{s})_{s\in S})=\prod_{s\in
S}\delta_{\alpha_{s},a_{s}}\delta_{b\beta},\qquad\text{$\forall\beta\in[|\mathcal{B}|-1]$
and $\alpha_{s}\in\mathcal{A}_{s}\backslash\\{0\\}$},\end{split}$ (103)

and for $S\subseteq\\{1,\cdots,N\\}$ with $1\leq|S|\leq K$. These MACs have
exactly one interference coordinate being $1$ (only when the inputs set
$\\{\alpha_{s}\\}_{s}$ and output $b$ match with the coordinate in Eq. (100))
and obviously from $\mathcal{C}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$. In total
then, we obtain a collection of
$(|\mathcal{B}|-1)\sum_{k=0}^{K}(|\mathcal{A}|-1)^{k}\binom{N}{k}+1$ affinely
independent points. Hence we have:

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

In summary, the dimension of the
$\mathcal{C}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$ polytope is
$(|\mathcal{B}|-1)\sum_{k=0}^{K}(|\mathcal{A}|-1)^{k}\binom{N}{k}$ for any
$1\leq K\leq N$.

Note the above calculation also works for
$\mathcal{C}^{\prime}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$,
$\text{conv}[\mathcal{C}_{N,K}(\bm{\mathcal{A}},\mathcal{B})]$,
$\mathcal{C}^{\text{sep}}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$ and
$\mathfrak{I}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$ since all the above
constraints and affinely points constructed in Eq.
(LABEL:Eq:_new_affine_points) work for all of them. ∎

######  Remark.

Theorem 5 says the dimension
$\mathfrak{J}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$ is
$(|\mathcal{B}|-1)\sum_{k=0}^{K}(|\mathcal{A}|-1)^{k}\binom{N}{k}$ with new
coordinates we introduced in Eq. (101). With these coordinates. In fact, for
any $L\in\\{1,\cdots,N\\}$ and any permutation $\pi$ on parties, we have

$\displaystyle
p(b|\overbrace{\alpha_{1},\cdots,\alpha_{L}}^{L},\overbrace{0,\cdots,0}^{N-L})=\sum_{k=0}^{K}\sum_{\begin{subarray}{c}S\subset\\{1,\cdots,L\\}\\\
|S|=k\end{subarray}}q(b,S,\\{\alpha_{s}\\}_{s})$ (105)

######  Proposition 13.

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

###### Proof.

The set $\mathcal{Q}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$ lives in a
$(|\mathcal{B}|\cdot\prod_{i=1}^{N}|\mathcal{A}_{i}|)$-dimensional space, and
there are also $\prod_{i=1}^{N}|\mathcal{A}_{i}|$ normalization condition for
each $\mathbf{p}_{B|\bm{A}}\in\mathcal{Q}_{N}(\bm{\mathcal{A}},\mathcal{B})$.
Additionally, proposition 8 shows that
$\mathbf{p}_{B|\bm{A}}\in\mathcal{Q}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$ can
not violate $I_{2K+1}$ equality and obviously any higher order equality (The
proposition works for arbitrary inputs/output), which introduces some extra
constraints. And hence, we can write each point in a subset of the
interference coordinates in Eq. (100) with $k\in\\{0,\cdots,2K\\}$ and
$b\neq|\mathcal{B}|-1$:

$\displaystyle\bigcup_{\begin{subarray}{c}b\in\mathcal{B}\\\
b\neq|\mathcal{B}|-1\end{subarray}}\bigcup_{\begin{subarray}{c}k\in\\{0,\cdots,2K\\}\\\
S\subseteq\\{1,\cdots,N\\}\\\
|S|=k\end{subarray}}\bigcup_{\begin{subarray}{c}\alpha_{s}\in\mathcal{A}_{s}\backslash\\{0\\}\\\
s\in
S\end{subarray}}\left\\{q(b,S,\\{\alpha_{s}\\}_{s}):=(-1)^{k}\sum_{\begin{subarray}{c}a_{s}\in\\{0,\alpha_{s}\\}\\\
s\in S\end{subarray}}\prod_{i\in
S}f(a_{i})p(b|a_{1},\cdots,a_{N})\;\bigg{|}\;\text{$a_{j}=0$ for $j\not\in
S$}\right\\},$ (106)

There are only
$(|\mathcal{B}|-1)\sum_{k=0}^{K}(|\mathcal{A}|-1)^{k}\binom{N}{k}$ element in
above set, which upper bound the dimension of
$\dim\mathcal{Q}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$

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

To proceed to get the lower bound, we consider the following two classes of
points:
(i) Classical MACS: We consider the set of
$(|\mathcal{B}|-1)\sum_{k=0}^{K}(|\mathcal{A}|-1)^{k}\binom{N}{k}$ affinely
independent points in $\mathcal{C}_{N,K}$ as we discussed in Eq.
(LABEL:Eq:_new_affine_points). This MACs are obviously are also in
$\mathcal{Q}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$.
(ii) Quantum MACS: We consider quantum MACs generated by quantum state
$|\psi\rangle^{\mathsf{A}_{i}\mathsf{A}_{j}}=\frac{1}{\sqrt{2}}(|\mathbf{e}_{i}\rangle+|\mathbf{e}_{j}\rangle)$
shared between party $i\in S_{i}$, $j\in S_{j}$ and disjoint groups $S_{i}\cap
S_{j}=\emptyset$. Each group performs a $\\{0,\pi\\}$ phase encoding on sender
$i$ or $j$ conditional on the ‘parity’ of their inputs, 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}^{P_{S}[(a_{s})_{s\in
S}]})^{\mathsf{A}_{i}}(X)(\sigma_{z}^{P_{S}[(a_{s})_{s\in
S}]})^{\mathsf{A}_{i}}$ where $\sigma_{z}=|0\rangle\langle
0|+e^{i\pi}|1\rangle\langle 1|$ with the parity function $P_{S}[(a_{s})_{s\in
S}]$ depending on the input set $\\{\alpha_{s}\\}_{s\in S_{i}\cup S_{j}}$ as:

$\displaystyle P_{S}[(a_{s})_{s\in S}]=\sum_{s\in
S}\delta_{\alpha_{s},a_{s}}\text{(mod) $2$}$ (108)

The decoder then measures with POVM
$\Pi_{b}=|\psi\rangle\langle\psi|^{\mathsf{A}_{i}\mathsf{A}_{j}}$and
$\Pi_{|\mathcal{B}|-1}=\mathbb{I}-|\psi\rangle\langle\psi|^{\mathsf{A}_{i}\mathsf{A}_{j}}$.
This quantum MAC can demonstrate maximal $k^{\text{th}}$-order interference
among and only among senders $S=S_{i}\cup S_{j}$ with $|S|=k$, input set
$\\{\alpha_{s}\\}_{s}$ and output $b$, this strategy applies for all groups
$S$ with $K<|S|\leq 2K$, input sets $\\{\alpha_{s}\\}_{s\in S_{i}\cup S_{j}}$
and outputs $b$, then we can obtain
$(|\mathcal{B}|-1)\sum_{k=K+1}^{2K}(|\mathcal{A}|-1)^{k}\binom{N}{k}$
different MACs

Points in class (i) do not violate $I_{k}$ equalities for any $k>K$ hence have
$q(b,S,\\{\alpha_{s}\\}_{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 has $q(b,S,\\{\alpha_{s}\\}_{s})=2^{k-1}$ but
$q(b^{\prime},S^{\prime},\\{\alpha^{\prime}_{s}\\}_{s})=0$ for any
$S^{\prime}\neq S$ and $|S^{\prime}|\geq k$ or
$\\{\alpha^{\prime}_{s}\\}_{s}\neq\\{\alpha_{s}\\}_{s}$ or $b\neq b^{\prime}$
by a similar reasoning as for proposition 9. Hence the collection of these
points form a upper-triangular matrix similarly as Eq. (87), thus being
affinely linear independent. In total then, we obtain a collection of
$(|\mathcal{B}|-1)\sum_{k=0}^{2K}(|\mathcal{A}|-1)^{k}\binom{N}{k}+1$ affinely
independent points belonging to
$\mathcal{Q}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$. Hence we have:

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

In summary, the dimension of the
$\mathcal{Q}_{N,K}(\bm{\mathcal{A}},\mathcal{B})$ polytope is
$(|\mathcal{B}|-1)\sum_{k=0}^{K}(|\mathcal{A}|-1)^{k}\binom{N}{k}$ for any
$1\leq K\leq\lfloor\frac{N}{2}\rfloor$, and obviously we can similarly
conclude that
$\mathcal{Q}_{N,K}(\bm{\mathcal{A}},\mathcal{B})=(|\mathcal{B}|-1)\sum_{k=0}^{K}(|\mathcal{A}|-1)^{k}\binom{N}{k}=(|\mathcal{B}|-1)\prod_{s\in
S}|\mathcal{A}_{s}|$ for $\lfloor\frac{N}{2}\rfloor<K\leq N$ ∎

###  8.3 Separation of $\mathcal{Q}_{2,1}([2]^{2};[2])$ and
$\mathcal{C}_{2,2}([2]^{2};[2])$

As we alluded to earlier, in general, while they have the same dimensions,
$\mathcal{Q}_{N,K}$ are fundamentally different from $\mathcal{C}_{N,2K}$.
Here we give a proof for the simplest case with $N=2$, $K=1$ and binary
inputs/output, i.e.,
$\mathcal{Q}_{2,1}([2]^{2};[2])\neq\mathcal{C}_{2,2}([2]^{2};[2])$.

######  Proposition 14.

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

###### Proof.

Consider the MAC $\mathbf{p}_{B|A_{1}A_{2}}$ given by
$p(0|a_{1}a_{2})=\delta_{0,a_{1}}\delta_{0,a_{2}}$, which is clearly in
$\mathcal{C}_{2,2}([2]^{2};[2])$ since $\mathcal{C}_{2,2}([2]^{2};[2])$
contains all channels from $[2]^{2}$ to [2]. Assume, towards a contradiction,
that this channel is in $\mathcal{Q}_{2,1}([2]^{2};[2])$ as well. Suppose that
the senders $\mathsf{A}_{1}$ and $\mathsf{A}_{2}$ share the state $\rho$
having support on $\mathcal{H}_{1}^{\mathsf{A}_{1}\mathsf{A}_{2}}$, then we
have

$\displaystyle
p(0|00)=\textrm{Tr}\left[\Pi_{0}\left(\mathcal{E}_{0}^{\mathsf{A}_{1}}\otimes\mathcal{E}_{0}^{\mathsf{A}_{2}}(\rho)\right)\right],$
$\displaystyle
p(0|01)=\textrm{Tr}\left[\Pi_{0}\left(\mathcal{E}_{0}^{\mathsf{A}_{1}}\otimes\mathcal{E}_{1}^{\mathsf{A}_{2}}(\rho)\right)\right].$

Notice that the channel $\mathbf{p}_{B|A_{1}A_{2}}$ cannot be expressed as a
convex combination of two channels; therefore, $\rho$ must in fact be a pure
state $|\psi\rangle\langle\psi|$. Let
$\rho^{\prime}=\mathcal{E}_{0}^{\mathsf{A}_{1}}\otimes\text{id}^{\mathsf{A}_{2}}(|\psi\rangle\langle\psi|)$,
then

$\displaystyle p(0|00)$
$\displaystyle=\textrm{Tr}\left[\Pi_{0}\left(\text{id}^{\mathsf{A}_{1}}\otimes\mathcal{E}_{0}^{\mathsf{A}_{2}}(\rho^{\prime})\right)\right],$
$\displaystyle p(0|01)$
$\displaystyle=\textrm{Tr}\left[\Pi_{0}\left(\text{id}^{\mathsf{A}_{1}}\otimes\mathcal{E}_{1}^{\mathsf{A}_{2}}(\rho^{\prime})\right)\right].$

We can write $\rho^{\prime}=p\rho_{0}+(1-p)\rho_{1}$ where $\rho_{0}$ and
$\rho_{1}$ are projections of $\rho$ to the vacuum subspace $\mathcal{H}_{0}$
and the one-particle subspace $\mathcal{H}_{1}$ respectively. This is because
N-P operations always map $|\psi\rangle\langle\psi|$ to a block-diagonal state
(see Eq. (65) in the main text). Then

$\begin{cases}p\textrm{Tr}\left[\Pi_{0}\left(\text{id}^{\mathsf{A}_{1}}\otimes\mathcal{E}_{0}^{\mathsf{A}_{2}}(|00\rangle\langle
00|)\right)\right]+(1-p)\textrm{Tr}\left[\Pi_{0}\left(\text{id}^{\mathsf{A}_{1}}\otimes\mathcal{E}_{0}^{\mathsf{A}_{2}}(\rho_{1})\right)\right]=1,\\\\[5.0pt]
p\textrm{Tr}\left[\Pi_{0}\left(\text{id}^{\mathsf{A}_{1}}\otimes\mathcal{E}_{1}^{\mathsf{A}_{2}}(|00\rangle\langle
00|)\right)\right]+(1-p)\textrm{Tr}\left[\Pi_{0}\left(\text{id}^{\mathsf{A}_{1}}\otimes\mathcal{E}_{1}^{\mathsf{A}_{2}}(\rho_{1})\right)\right]=0.\end{cases}$
(110)

We then proceed to show that Eq. (110) always leads to a contradiction for any
$p\in[0,1]$.

If $p\in(0,1]$, then Eq. (110) implies that

$\displaystyle\textrm{Tr}\left[\Pi_{0}\left(\text{id}^{\mathsf{A}_{1}}\otimes\mathcal{E}_{0}^{\mathsf{A}_{2}}(|00\rangle\langle
00|)\right)\right]=1$

and

$\displaystyle\textrm{Tr}\left[\Pi_{0}\left(\text{id}^{\mathsf{A}_{1}}\otimes\mathcal{E}_{1}^{\mathsf{A}_{2}}(|00\rangle\langle
00|)\right)\right]=0.$

Since $\mathcal{E}_{0}^{\mathsf{A}_{2}}$ and
$\mathcal{E}_{1}^{\mathsf{A}_{2}}$ are both N-P operations,
$\text{id}^{\mathsf{A}_{1}}\otimes\mathcal{E}_{0}^{\mathsf{A}_{2}}(|00\rangle\langle
00|)=\text{id}^{\mathsf{A}_{1}}\otimes\mathcal{E}_{1}^{\mathsf{A}_{2}}(|00\rangle\langle
00|)=|00\rangle\langle 00|$. Therefore, these two equations cannot be true
simultaneously, and we have a contradiction.

Next, suppose that $p=0$. In this case,
$\rho^{\prime}=\mathcal{E}_{0}^{\mathsf{A}_{1}}\otimes\text{id}^{\mathsf{A}_{2}}(|\psi\rangle\langle\psi|)$
remains a one-particle state. Following a similar argument, we can see that
$\mathcal{E}_{1}^{\mathsf{A}_{1}}\otimes\text{id}^{\mathsf{A}_{2}}(|\psi\rangle\langle\psi|)$
and
$\text{id}^{\mathsf{A}_{1}}\otimes\mathcal{E}_{0,1}^{\mathsf{A}_{2}}(|\psi\rangle\langle\psi|)$
also have to be one-particle states. Therefore, all of the encoded states
$\sigma_{00}$, $\sigma_{01}$, $\sigma_{10}$, and $\sigma_{11}$ (recall
$\sigma_{a_{1}a_{2}}=\mathcal{E}_{a_{1}}^{\mathsf{A}_{1}}\otimes\mathcal{E}_{a_{2}}^{\mathsf{A}_{2}}(|\psi\rangle\langle\psi|)$)
are operators on the two-dimensional space $\mathcal{H}_{1}$. Additionally,
note that $p(0|a_{1}a_{2})=\delta_{0,a_{1}}\delta_{0,a_{2}}$ implies that the
encoder can perfectly distinguish $\sigma_{00}$ from
$\\{\sigma_{01},\sigma_{10},\sigma_{11}\\}$, i.e.,
$\sigma_{00}\perp\sigma_{01},\sigma_{10},\sigma_{11}$. Thus, it must be that
$\sigma_{01}=\sigma_{10}=\sigma_{11}$, which means that
$\mathcal{E}_{0}^{\mathsf{A}_{1}}=\mathcal{E}_{1}^{\mathsf{A}_{1}}$ and
$\mathcal{E}_{0}^{\mathsf{A}_{2}}=\mathcal{E}_{1}^{\mathsf{A}_{2}}$. However,
this will imply that all of the four encoded states are the same, that is,
$\sigma_{00}=\sigma_{01}=\sigma_{10}=\sigma_{11}$. We thus arrive at a
contradiction as well.

To conclude, we have shown that the MAC $\mathbf{p}$ is not in
$\mathcal{Q}_{2,1}([2]^{2};[2])$, and therefore
$\mathcal{Q}_{2,1}([2]^{2};[2])\neq\mathcal{C}_{2,2}([2]^{2};[2])$. ∎