Algebra of Nonlocal Boxes and the Collapse of Communication Complexity

Pierre Botteron; Anne Broadbent; Reda Chhaibi; Ion Nechita; Clément Pellegrini

doi:10.22331/q-2024-07-10-1402

Algebra of Nonlocal Boxes and the Collapse of Communication Complexity

Pierre Botteron¹, Anne Broadbent^2,3, Reda Chhaibi^1,4, Ion Nechita⁵, and Clément Pellegrini¹

¹Institut de Mathématiques de Toulouse, Université de Toulouse, France.
²Nexus for Quantum Technologies, University of Ottawa, Canada.
³Department of Mathematics and Statistics, University of Ottawa, Canada.
⁴Institut Universitaire de France (IUF), France.
⁵Laboratoire de Physique Théorique, Université de Toulouse, CNRS, France.

Published:	2024-07-10, volume 8, page 1402
Eprint:	arXiv:2312.00725v3
Doi:	https://doi.org/10.22331/q-2024-07-10-1402
Citation:	Quantum 8, 1402 (2024).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Communication complexity quantifies how difficult it is for two distant computers to evaluate a function $f(X,Y)$, where the strings $X$ and $Y$ are distributed to the first and second computer respectively, under the constraint of exchanging as few bits as possible. Surprisingly, some nonlocal boxes, which are resources shared by the two computers, are so powerful that they allow to $collapse$ communication complexity, in the sense that any Boolean function f can be correctly estimated with the exchange of only one bit of communication. The Popescu-Rohrlich (PR) box is an example of such a collapsing resource, but a comprehensive description of the set of collapsing nonlocal boxes remains elusive.

In this work, we carry out an algebraic study of the structure of wirings connecting nonlocal boxes, thus defining the notion of the "product of boxes" $P\boxtimes Q$, and we show related associativity and commutativity results. This gives rise to the notion of the "orbit of a box", unveiling surprising geometrical properties about the alignment and parallelism of distilled boxes. The power of this new framework is that it allows us to prove previously-reported numerical observations concerning the best way to wire consecutive boxes, and to numerically and analytically recover recently-identified noisy $\texttt{PR}$ boxes that collapse communication complexity for different types of noise models.

Featured image: Distilling non-signalling boxes with a wiring, and deducing that they collapse communication complexity.

Popular summary

In working towards a comprehensive information-based description of Quantum Mechanics, it is convenient to study a more general theory called the Non-Signalling Theory, which is less restrictive, with the only constraint of satisfying the no-faster-than-light principle. A famous example of an element in this theory is the Popescu-Rohrlich box (PR box), which maximally violates the Clauser-Horne-Shimony-Holt inequality, but is so "powerful" that it violates the principle of No-Collapse of Communication Complexity. Based on this observation, a natural question arises, still open to this day: what are all non-signalling boxes that induce a collapse of communication complexity? An explicit answer to this question may allow to rule out the set of quantum correlations as the only set satisfying the non-signalling principle, the no-collapse of communication complexity, and some other information-based principles. This is why we introduce new algebraic perspectives on correlation distillation to show the collapse of communication complexity. More precisely, given two non-signalling boxes $P$ and $Q$, it is possible to plug the outputs of $P$ into the inputs $Q$ with a wiring $W$, thus creating a new box that we write $P\boxtimes_W Q$. This defines a product of boxes, for which we characterize the associativity and commutativity, and we feature surprising alignment and parallelism properties when we apply recursively many times this product. Importantly, this algebraic framework allows us to prove previously-reported numerical observations concerning the best way to wire consecutive boxes, and to numerically and analytically recover recently-identified noisy PR boxes that collapse communication complexity for different types of noise models. The importance of our results is emphasized by considering the many known impossibility results.

► BibTeX data

@article{Botteron2024algebraofnonlocal,
  doi = {10.22331/q-2024-07-10-1402},
  url = {https://doi.org/10.22331/q-2024-07-10-1402},
  title = {Algebra of {N}onlocal {B}oxes and the {C}ollapse of {C}ommunication {C}omplexity},
  author = {Botteron, Pierre and Broadbent, Anne and Chhaibi, Reda and Nechita, Ion and Pellegrini, Cl{\'{e}}ment},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1402},
  month = jul,
  year = {2024}
}

► References

[1] Jonathan Allcock, Nicolas Brunner, Noah Linden, Sandu Popescu, Paul Skrzypczyk, and Tamás Vértesi, ``Closed sets of nonlocal correlations'' Phys. Rev. A 80, 062107 (2009).
https://doi.org/10.1103/PhysRevA.80.062107

[2] Jonathan Allcock, Nicolas Brunner, Marcin Pawlowski, and Valerio Scarani, ``Recovering part of the boundary between quantum and nonquantum correlations from information causality'' Phys. Rev. A 80, 040103 (2009).
https://doi.org/10.1103/PhysRevA.80.040103

[3] Jonathan Barrett, Noah Linden, Serge Massar, Stefano Pironio, Sandu Popescu, and David Roberts, ``Nonlocal correlations as an information-theoretic resource'' Phys. Rev. A 71, 022101 (2005).
https://doi.org/10.1103/PhysRevA.71.022101

[4] Jonathan Barrettand Stefano Pironio ``Popescu-Rohrlich Correlations as a Unit of Nonlocality'' Phys. Rev. Lett. 95, 140401 (2005).
https://doi.org/10.1103/PhysRevLett.95.140401

[5] Mohammad Bavarianand Peter W. Shor ``Information Causality, Szemerédi-Trotter and Algebraic Variants of CHSH'' Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science 123–132 (2015).
https://doi.org/10.1145/2688073.2688112

[6] Salman Beigiand Amin Gohari ``Monotone Measures for Non-Local Correlations'' IEEE Transactions on Information Theory 61, 5185–5208 (2015).
https://doi.org/10.1109/TIT.2015.2452253

[7] Pierre Botteron ``Nonlocal Boxes and Communication Complexity'' thesis (2022) Under the supervision of Anne Broadbent, Ion Nechita and Clément Pellegrini.
https://pierre-botteron.github.io/Articles/2022-06-MSc-Thesis.pdf

[8] Pierre Botteron, Anne Broadbent, and Marc-Olivier Proulx, ``Extending the Known Region of Nonlocal Boxes that Collapse Communication Complexity'' Phys. Rev. Lett. 132, 070201 (2024).
https://doi.org/10.1103/PhysRevLett.132.070201

[9] Pierre Botteronand Réda Chhaibi ``GitHub page'' [Accessed: November 2023].
https://github.com/Pierre-Botteron/Algebra-of-Boxes-code

[10] Gilles Brassard, Harry Buhrman, Noah Linden, André Allan Méthot, Alain Tapp, and Falk Unger, ``Limit on Nonlocality in Any World in Which Communication Complexity Is Not Trivial'' Phys. Rev. Lett. 96, 250401 (2006).
https://doi.org/10.1103/PhysRevLett.96.250401

[11] Samuraí Brito, George Moreno, Ashutosh Rai, and Rafael Chaves, ``Nonlocality distillation and quantum voids'' Phys. Rev. A 100, 012102 (2019).
https://doi.org/10.1103/PhysRevA.100.012102

[12] Nicolas Brunner, Daniel Cavalcanti, Alejo Salles, and Paul Skrzypczyk, ``Bound Nonlocality and Activation'' Phys. Rev. Lett. 106, 020402 (2011).
https://doi.org/10.1103/PhysRevLett.106.020402

[13] Nicolas Brunnerand Paul Skrzypczyk ``Nonlocality Distillation and Postquantum Theories with Trivial Communication Complexity'' Physical Review Letters 102 (2009).
https://doi.org/10.1103/physrevlett.102.160403

[14] Harry Buhrmanand Serge Massar ``Causality and Tsirelson's bounds'' Phys. Rev. A 72, 052103 (2005).
https://doi.org/10.1103/PhysRevA.72.052103

[15] Kai-Siang Chen, Gelo Noel M. Tabia, Chellasamy Jebarathinam, Shiladitya Mal, Jun-Yi Wu, and Yeong-Cherng Liang, ``Quantum correlations on the no-signaling boundary: self-testing and more'' Quantum 7, 1054 (2023).
https://doi.org/10.22331/q-2023-07-11-1054

[16] John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt, ``Proposed Experiment to Test Local Hidden-Variable Theories'' Phys. Rev. Lett. 23, 880–884 (1969).
https://doi.org/10.1103/PhysRevLett.23.880

[17] Richard Cleve, Wim van Dam, Michael Nielsen, and Alain Tapp, ``Quantum Entanglement and the Communication Complexity of the Inner Product Function'' Springer Berlin Heidelberg (1999).
https://doi.org/10.1007/3-540-49208-9_4

[18] Wim van Dam ``Nonlocality $\&$ Communication Complexity'' thesis (1999).
https://sites.cs.ucsb.edu/~vandam/oxford_thesis.pdf

[19] Dejan D. Dukaricand Stefan Wolf ``A Limit on Non-Locality Distillation'' (2008).
arXiv:0808.3317

[20] Frédéric Dupuis, Nicolas Gisin, Avinatan Hasidim, André Allan Méthot, and Haran Pilpel, ``No nonlocal box is universal'' Journal of Mathematical Physics 48, 082107 (2007).
https://doi.org/10.1063/1.2767538

[21] Helen Ebbeand Stefan Wolf ``Multi-User Non-Locality Amplification'' IEEE Transactions on Information Theory 60, 1159–1167 (2014).
https://doi.org/10.1109/TIT.2013.2292515

[22] Giorgos Eftaxias ``Theory-independent topics towards quantum mechanics: $\psi$-ontology and nonlocality distillation'' thesis (2022).

[23] Giorgos Eftaxias, Mirjam Weilenmann, and Roger Colbeck, ``Advantages of Multicopy Nonlocality Distillation and Its Application to Minimizing Communication Complexity'' Phys. Rev. Lett. 130, 100201 (2023).
https://doi.org/10.1103/PhysRevLett.130.100201

[24] Giorgos Eftaxias, Mirjam Weilenmann, and Roger Colbeck, ``Multisystem measurements in generalized probabilistic theories and their role in information processing'' Phys. Rev. A 108, 062212 (2023).
https://doi.org/10.1103/PhysRevA.108.062212

[25] Manuel Forster, Severin Winkler, and Stefan Wolf, ``Distilling Nonlocality'' Phys. Rev. Lett. 102, 120401 (2009).
https://doi.org/10.1103/PhysRevLett.102.120401

[26] Tobias Fritz, Ana Belén Sainz, Remigiusz Augusiak, Jonatan Bohr Brask, Rafael Chaves, Anthony Leverrier, and Antonio Acín, ``Local orthogonality as a multipartite principle for quantum correlations'' Nature Communications 4, 2263 (2013).
https://doi.org/10.1038/ncomms3263

[27] Peter Hoyerand Jibran Rashid ``Optimal protocols for nonlocality distillation'' Phys. Rev. A 82, 042118 (2010).
https://doi.org/10.1103/PhysRevA.82.042118

[28] Prabhav Jain, Mariami Gachechiladze, and Nikolai Miklin, ``Information causality as a tool for bounding the set of quantum correlations'' (2023).
arXiv:2308.02478

[29] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen, ``MIP*=RE'' (2022).
arXiv:2001.04383

[30] Eyal Kushilevitzand Noam Nisan ``Communication Complexity'' Cambridge University Press (1996).
https://doi.org/10.1017/CBO9780511574948

[31] Ben Lang, Tamás Vértesi, and Miguel Navascués, ``Closed sets of correlations: answers from the zoo'' Journal of Physics A: Mathematical and Theoretical 47, 424029 (2014).
https://doi.org/10.1088/1751-8113/47/42/424029

[32] Noah Linden, Sandu Popescu, Anthony J. Short, and Andreas Winter, ``Quantum Nonlocality and Beyond: Limits from Nonlocal Computation'' Phys. Rev. Lett. 99, 180502 (2007).
https://doi.org/10.1103/PhysRevLett.99.180502

[33] Lluis Masanes ``Necessary and sufficient condition for quantum-generated correlations'' (2003).

[34] Ryuhei Mori ``Three-input majority function as the unique optimal function for the bias amplification using nonlocal boxes'' Phys. Rev. A 94, 052130 (2016).
https://doi.org/10.1103/PhysRevA.94.052130

[35] Sahil Gopalkrishna Naik, Govind Lal Sidhardh, Samrat Sen, Arup Roy, Ashutosh Rai, and Manik Banik, ``Distilling Nonlocality in Quantum Correlations'' Phys. Rev. Lett. 130, 220201 (2023).
https://doi.org/10.1103/PhysRevLett.130.220201

[36] Miguel Navascués, Yelena Guryanova, Matty J. Hoban, and Antonio Acín, ``Almost quantum correlations'' Nature Communications 6, 6288 (2015).
https://doi.org/10.1038/ncomms7288

[37] Miguel Navascuésand Harald Wunderlich ``A glance beyond the quantum model'' Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 466, 881–890 (2009).
https://doi.org/10.1098/rspa.2009.0453

[38] Jorge Nocedaland Stephen J. Wright ``Numerical Optimization'' Springer-Verlag (1999).
https://doi.org/10.1007/b98874

[39] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer, ``Automatic differentiation in PyTorch'' OpenReview (2017).
https://openreview.net/forum?id=BJJsrmfCZ

[40] Marcin Pawłowski, Tomasz Paterek, Dagomir Kaszlikowski, Valerio Scarani, Andreas Winter, and Marek Żukowski, ``Information causality as a physical principle'' Nature 461, 1101–1104 (2009).
https://doi.org/10.1038/nature08400

[41] Sandu Popescuand Daniel Rohrlich ``Quantum nonlocality as an axiom'' Foundations of Physics 24, 379–385 (1994).
https://doi.org/10.1007/BF02058098

[42] Ashutosh Rai, Cristhiano Duarte, Samuraí Brito, and Rafael Chaves, ``Geometry of the quantum set on no-signaling faces'' Phys. Rev. A 99, 032106 (2019).
https://doi.org/10.1103/PhysRevA.99.032106

[43] Anup Raoand Amir Yehudayoff ``Communication Complexity: and Applications'' Cambridge University Press (2020).
https://doi.org/10.1017/9781108671644

[44] Denis Rosset, Amin Baumeler, Jean-Daniel Bancal, Nicolas Gisin, Anthony Martin, Marc-Olivier Renou, and Elie Wolfe, ``Algebraic and geometric properties of local transformations'' (2020).
arXiv:2004.09405

[45] Anthony J. Short, Sandu Popescu, and Nicolas Gisin, ``Entanglement swapping for generalized nonlocal correlations'' Phys. Rev. A 73, 012101 (2006).
https://doi.org/10.1103/PhysRevA.73.012101

[46] Noah Shutty, Mary Wootters, and Patrick Hayden, ``Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise'' 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) 206–217 (2020).
https://doi.org/10.1109/FOCS46700.2020.00028

[47] Paul Skrzypczyk, Nicolas Brunner, and Sandu Popescu, ``Emergence of Quantum Correlations from Nonlocality Swapping'' Phys. Rev. Lett. 102, 110402 (2009).
https://doi.org/10.1103/PhysRevLett.102.110402

[48] Andrew Chi-Chih Yao ``Some Complexity Questions Related to Distributive Computing (Preliminary Report)'' Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing 209–213 (1979).
https://doi.org/10.1145/800135.804414

[49] Yuqian Zhou, Yu Cai, Jean-Daniel Bancal, Fei Gao, and Valerio Scarani, ``Many-box locality'' Phys. Rev. A 96, 052108 (2017).
https://doi.org/10.1103/PhysRevA.96.052108

Cited by

[1] Syed Affan Aslam, Areej Ilyas, and Jibran Rashid, 2025 International Conference on Quantum Communications, Networking, and Computing (QCNC) 521 (2025) ISBN:979-8-3315-3159-1.

[2] Syed Affan Aslam, Areej Ilyas, and Jibran Rashid, "Suboptimality of parity for distilling correlations with nontrivial marginals", Physical Review A 112 6, 062426 (2025).

[3] Pierre Botteron and Moritz Weber, "Communication Complexity of Graph Isomorphism, Coloring, and Distance Games", arXiv:2406.02199, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-10 16:07:44) and SAO/NASA ADS (last updated successfully 2026-08-10 16:07:46). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.