{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,15]],"date-time":"2025-12-15T19:53:15Z","timestamp":1765828395222,"version":"3.40.5"},"reference-count":49,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T00:00:00Z","timestamp":1720569600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","award":["ALLRP 580876 - 22"],"award-info":[{"award-number":["ALLRP 580876 - 22"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004489","name":"MITACS","doi-asserted-by":"crossref","award":["FR113029"],"award-info":[{"award-number":["FR113029"]}],"id":[{"id":"10.13039\/501100004489","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ANR project ESQuisses","award":["ANR-20-CE47-0014-01"],"award-info":[{"award-number":["ANR-20-CE47-0014-01"]}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"crossref","award":["FA9550-20-1-0375"],"award-info":[{"award-number":["FA9550-20-1-0375"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100030708","name":"Artificial and Natural Intelligence Toulouse Institute","doi-asserted-by":"crossref","award":["ANR-3IA"],"award-info":[{"award-number":["ANR-3IA"]}],"id":[{"id":"10.13039\/100030708","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ANR project STARS","award":["ANR-20-CE40-0008"],"award-info":[{"award-number":["ANR-20-CE40-0008"]}]},{"name":"ANR project Q-COAST","award":["ANR-19-CE48-0003"],"award-info":[{"award-number":["ANR-19-CE48-0003"]}]},{"name":"ANR project \u201cQuantum Trajectories\u201d","award":["ANR-20-CE40-0024-01"],"award-info":[{"award-number":["ANR-20-CE40-0024-01"]}]},{"name":"ANR project \u201cInvestissements d\u2019Avenir\u201d","award":["ANR-11-LABX-0040"],"award-info":[{"award-number":["ANR-11-LABX-0040"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"Communication complexity quantifies how difficult it is for two distant computers to evaluate a functionf<\/mml:mi>(<\/mml:mo>X<\/mml:mi>,<\/mml:mo>Y<\/mml:mi>)<\/mml:mo><\/mml:math>, where the stringsX<\/mml:mi><\/mml:math>andY<\/mml:mi><\/mml:math>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 toc<\/mml:mi>o<\/mml:mi>l<\/mml:mi>l<\/mml:mi>a<\/mml:mi>p<\/mml:mi>s<\/mml:mi>e<\/mml:mi><\/mml:math>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<\/mml:mi>&#x22A0;<\/mml:mo>Q<\/mml:mi><\/mml:math>, 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 noisyPR<\/mml:mtext><\/mml:mrow><\/mml:math>boxes that collapse communication complexity for different types of noise models.<\/jats:p>","DOI":"10.22331\/q-2024-07-10-1402","type":"journal-article","created":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T14:25:56Z","timestamp":1720621556000},"page":"1402","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":2,"title":["Algebra of Nonlocal Boxes and the Collapse of Communication Complexity"],"prefix":"10.22331","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3861-0934","authenticated-orcid":false,"given":"Pierre","family":"Botteron","sequence":"first","affiliation":[{"name":"Institut de Math\u00e9matiques de Toulouse, Universit\u00e9 de Toulouse, France."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1911-0093","authenticated-orcid":false,"given":"Anne","family":"Broadbent","sequence":"additional","affiliation":[{"name":"Nexus for Quantum Technologies, University of Ottawa, Canada."},{"name":"Department of Mathematics and Statistics, University of Ottawa, Canada."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0085-0086","authenticated-orcid":false,"given":"Reda","family":"Chhaibi","sequence":"additional","affiliation":[{"name":"Institut de Math\u00e9matiques de Toulouse, Universit\u00e9 de Toulouse, France."},{"name":"Institut Universitaire de France (IUF), France."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3016-7795","authenticated-orcid":false,"given":"Ion","family":"Nechita","sequence":"additional","affiliation":[{"name":"Laboratoire de Physique Th\u00e9orique, Universit\u00e9 de Toulouse, CNRS, France."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cl\u00e9ment","family":"Pellegrini","sequence":"additional","affiliation":[{"name":"Institut de Math\u00e9matiques de Toulouse, Universit\u00e9 de Toulouse, France."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2024,7,10]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Jonathan Allcock, Nicolas Brunner, Noah Linden, Sandu Popescu, Paul Skrzypczyk, and Tam\u00e1s V\u00e9rtesi, ``Closed sets of nonlocal correlations'' Phys. Rev. A 80, 062107 (2009).","DOI":"10.1103\/PhysRevA.80.062107"},{"key":"1","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevA.80.040103"},{"key":"2","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevA.71.022101"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Jonathan Barrettand Stefano Pironio ``Popescu-Rohrlich Correlations as a Unit of Nonlocality'' Phys. Rev. Lett. 95, 140401 (2005).","DOI":"10.1103\/PhysRevLett.95.140401"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Mohammad Bavarianand Peter W. Shor ``Information Causality, Szemer\u00e9di-Trotter and Algebraic Variants of CHSH'' Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science 123\u2013132 (2015).","DOI":"10.1145\/2688073.2688112"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Salman Beigiand Amin Gohari ``Monotone Measures for Non-Local Correlations'' IEEE Transactions on Information Theory 61, 5185\u20135208 (2015).","DOI":"10.1109\/TIT.2015.2452253"},{"key":"6","unstructured":"Pierre Botteron ``Nonlocal Boxes and Communication Complexity'' thesis (2022) Under the supervision of Anne Broadbent, Ion Nechita and Cl\u00e9ment Pellegrini."},{"key":"7","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.132.070201"},{"key":"8","unstructured":"Pierre Botteronand R\u00e9da Chhaibi ``GitHub page'' [Accessed: November 2023]."},{"key":"9","doi-asserted-by":"publisher","unstructured":"Gilles Brassard, Harry Buhrman, Noah Linden, Andr\u00e9 Allan M\u00e9thot, Alain Tapp, and Falk Unger, ``Limit on Nonlocality in Any World in Which Communication Complexity Is Not Trivial'' Phys. Rev. Lett. 96, 250401 (2006).","DOI":"10.1103\/PhysRevLett.96.250401"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Samura\u00ed Brito, George Moreno, Ashutosh Rai, and Rafael Chaves, ``Nonlocality distillation and quantum voids'' Phys. Rev. A 100, 012102 (2019).","DOI":"10.1103\/PhysRevA.100.012102"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Nicolas Brunner, Daniel Cavalcanti, Alejo Salles, and Paul Skrzypczyk, ``Bound Nonlocality and Activation'' Phys. Rev. Lett. 106, 020402 (2011).","DOI":"10.1103\/PhysRevLett.106.020402"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Nicolas Brunnerand Paul Skrzypczyk ``Nonlocality Distillation and Postquantum Theories with Trivial Communication Complexity'' Physical Review Letters 102 (2009).","DOI":"10.1103\/physrevlett.102.160403"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Harry Buhrmanand Serge Massar ``Causality and Tsirelson's bounds'' Phys. Rev. A 72, 052103 (2005).","DOI":"10.1103\/PhysRevA.72.052103"},{"key":"14","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.22331\/q-2023-07-11-1054"},{"key":"15","doi-asserted-by":"publisher","unstructured":"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\u2013884 (1969).","DOI":"10.1103\/PhysRevLett.23.880"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1007\/3-540-49208-9_4"},{"key":"17","unstructured":"Wim van Dam ``Nonlocality $\\&$ Communication Complexity'' thesis (1999)."},{"key":"18","unstructured":"Dejan D. Dukaricand Stefan Wolf ``A Limit on Non-Locality Distillation'' (2008)."},{"key":"19","doi-asserted-by":"publisher","unstructured":"Fr\u00e9d\u00e9ric Dupuis, Nicolas Gisin, Avinatan Hasidim, Andr\u00e9 Allan M\u00e9thot, and Haran Pilpel, ``No nonlocal box is universal'' Journal of Mathematical Physics 48, 082107 (2007).","DOI":"10.1063\/1.2767538"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Helen Ebbeand Stefan Wolf ``Multi-User Non-Locality Amplification'' IEEE Transactions on Information Theory 60, 1159\u20131167 (2014).","DOI":"10.1109\/TIT.2013.2292515"},{"key":"21","unstructured":"Giorgos Eftaxias ``Theory-independent topics towards quantum mechanics: $\\psi$-ontology and nonlocality distillation'' thesis (2022)."},{"key":"22","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.130.100201"},{"key":"23","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevA.108.062212"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Manuel Forster, Severin Winkler, and Stefan Wolf, ``Distilling Nonlocality'' Phys. Rev. Lett. 102, 120401 (2009).","DOI":"10.1103\/PhysRevLett.102.120401"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Tobias Fritz, Ana Bel\u00e9n Sainz, Remigiusz Augusiak, Jonatan Bohr Brask, Rafael Chaves, Anthony Leverrier, and Antonio Ac\u00edn, ``Local orthogonality as a multipartite principle for quantum correlations'' Nature Communications 4, 2263 (2013).","DOI":"10.1038\/ncomms3263"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Peter Hoyerand Jibran Rashid ``Optimal protocols for nonlocality distillation'' Phys. Rev. A 82, 042118 (2010).","DOI":"10.1103\/PhysRevA.82.042118"},{"key":"27","doi-asserted-by":"crossref","unstructured":"Prabhav Jain, Mariami Gachechiladze, and Nikolai Miklin, ``Information causality as a tool for bounding the set of quantum correlations'' (2023).","DOI":"10.1103\/PhysRevLett.133.160201"},{"key":"28","unstructured":"Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen, ``MIP*=RE'' (2022)."},{"key":"29","doi-asserted-by":"publisher","unstructured":"Eyal Kushilevitzand Noam Nisan ``Communication Complexity'' Cambridge University Press (1996).","DOI":"10.1017\/CBO9780511574948"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Ben Lang, Tam\u00e1s V\u00e9rtesi, and Miguel Navascu\u00e9s, ``Closed sets of correlations: answers from the zoo'' Journal of Physics A: Mathematical and Theoretical 47, 424029 (2014).","DOI":"10.1088\/1751-8113\/47\/42\/424029"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Noah Linden, Sandu Popescu, Anthony J. Short, and Andreas Winter, ``Quantum Nonlocality and Beyond: Limits from Nonlocal Computation'' Phys. Rev. Lett. 99, 180502 (2007).","DOI":"10.1103\/PhysRevLett.99.180502"},{"key":"32","unstructured":"Lluis Masanes ``Necessary and sufficient condition for quantum-generated correlations'' (2003)."},{"key":"33","doi-asserted-by":"publisher","unstructured":"Ryuhei Mori ``Three-input majority function as the unique optimal function for the bias amplification using nonlocal boxes'' Phys. Rev. A 94, 052130 (2016).","DOI":"10.1103\/PhysRevA.94.052130"},{"key":"34","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.130.220201"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Miguel Navascu\u00e9s, Yelena Guryanova, Matty J. Hoban, and Antonio Ac\u00edn, ``Almost quantum correlations'' Nature Communications 6, 6288 (2015).","DOI":"10.1038\/ncomms7288"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Miguel Navascu\u00e9sand Harald Wunderlich ``A glance beyond the quantum model'' Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 466, 881\u2013890 (2009).","DOI":"10.1098\/rspa.2009.0453"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Jorge Nocedaland Stephen J. Wright ``Numerical Optimization'' Springer-Verlag (1999).","DOI":"10.1007\/b98874"},{"key":"38","unstructured":"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)."},{"key":"39","doi-asserted-by":"publisher","unstructured":"Marcin Paw\u0142owski, Tomasz Paterek, Dagomir Kaszlikowski, Valerio Scarani, Andreas Winter, and Marek \u017bukowski, ``Information causality as a physical principle'' Nature 461, 1101\u20131104 (2009).","DOI":"10.1038\/nature08400"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Sandu Popescuand Daniel Rohrlich ``Quantum nonlocality as an axiom'' Foundations of Physics 24, 379\u2013385 (1994).","DOI":"10.1007\/BF02058098"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Ashutosh Rai, Cristhiano Duarte, Samura\u00ed Brito, and Rafael Chaves, ``Geometry of the quantum set on no-signaling faces'' Phys. Rev. A 99, 032106 (2019).","DOI":"10.1103\/PhysRevA.99.032106"},{"key":"42","doi-asserted-by":"publisher","unstructured":"Anup Raoand Amir Yehudayoff ``Communication Complexity: and Applications'' Cambridge University Press (2020).","DOI":"10.1017\/9781108671644"},{"key":"43","unstructured":"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)."},{"key":"44","doi-asserted-by":"publisher","unstructured":"Anthony J. Short, Sandu Popescu, and Nicolas Gisin, ``Entanglement swapping for generalized nonlocal correlations'' Phys. Rev. A 73, 012101 (2006).","DOI":"10.1103\/PhysRevA.73.012101"},{"key":"45","doi-asserted-by":"publisher","unstructured":"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\u2013217 (2020).","DOI":"10.1109\/FOCS46700.2020.00028"},{"key":"46","doi-asserted-by":"publisher","unstructured":"Paul Skrzypczyk, Nicolas Brunner, and Sandu Popescu, ``Emergence of Quantum Correlations from Nonlocality Swapping'' Phys. Rev. Lett. 102, 110402 (2009).","DOI":"10.1103\/PhysRevLett.102.110402"},{"key":"47","doi-asserted-by":"publisher","unstructured":"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\u2013213 (1979).","DOI":"10.1145\/800135.804414"},{"key":"48","doi-asserted-by":"publisher","unstructured":"Yuqian Zhou, Yu Cai, Jean-Daniel Bancal, Fei Gao, and Valerio Scarani, ``Many-box locality'' Phys. Rev. A 96, 052108 (2017).","DOI":"10.1103\/PhysRevA.96.052108"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-07-10-1402\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,11,23]],"date-time":"2024-11-23T21:51:18Z","timestamp":1732398678000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-07-10-1402\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,10]]},"references-count":49,"URL":"https:\/\/doi.org\/10.22331\/q-2024-07-10-1402","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"type":"electronic","value":"2521-327X"}],"subject":[],"published":{"date-parts":[[2024,7,10]]},"article-number":"1402"}}