Algebra of Nonlocal Boxes and the Collapse of Communication Complexity
arXiv:2312.00725 · doi:10.22331/q-2024-07-10-1402
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" , 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 PR boxes that collapse communication complexity for different types of noise models.
arXiv comment32 + 3 pages, 13 figures
References in corpus (30)
- Information Causality as a Physical Principle
- Non-local correlations as an information theoretic resource
- A limit on nonlocality in any world in which communication complexity is not trivial
- A glance beyond the quantum model
- Local orthogonality as a multipartite principle for quantum correlations
- Almost quantum correlations
- No quantum advantage for nonlocal computation
- Popescu-Rohrlich correlations as a unit of nonlocality
- Non-locality distillation and post-quantum theories with trivial communication complexity
- Recovering part of the quantum boundary from information causality
- Distilling Non-Locality
- Closed sets of non-local correlations
- Emergence of Quantum Correlations from Non-Locality Swapping
- Causality and Cirel'son bounds
- Bound non-locality and activation
- Optimal Protocols for Nonlocality Distillation
- Closed sets of correlations: answers from the zoo
- Monotone Measures for Non-Local Correlations
- Geometry of the quantum set on no-signaling faces
- No nonlocal box is universal
- Quantum correlations on the no-signaling boundary: self-testing and more
- Advantages of multi-copy nonlocality distillation and its application to minimizing communication complexity
- Distilling Nonlocality in Quantum Correlations
- Nonlocality Distillation and Quantum Voids
- Many-box locality
- Extending the Known Region of Nonlocal Boxes that Collapse Communication Complexity
- Information causality as a tool for bounding the set of quantum correlations
- Multi-User Non-Locality Amplification
- Three-input Majority Function as the Unique Optimal Function for the Bias Amplification using Nonlocal Boxes
- Multi-system measurements in generalized probabilistic theories and their role in information processing