Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2312.00725 · Quantum

Algebra of Nonlocal Boxes and the Collapse of Communication Complexity

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

Published Jul 10, 2024• 4 citations
arXivHTMLPDF

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⊠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 PR boxes that collapse communication complexity for different types of noise models.

DOI
10.22331/q-2024-07-10-1402

Related papers

Nonlocality Distillation and Postquantum Theories with Trivial Communication Complexity

Nicolas Brunner, Paul Skrzypczyk

We first present a protocol for deterministically distilling nonlocality, building upon a recent result of Forster et al. [Phys. Rev. Lett. 102, 120401 (2009)10.1103/PhysRevLett.102.120401]. Our protocol, which is optimal for two-copy distillation, works efficiently for a specific class of postquantum nonlocal boxes, which we term correlated nonlocal boxes. In the asymptotic limit, all correlated nonlocal boxes are distilled to the maximally nonlocal box of Popescu and Rohrlich. Then, taking advantage of a result of Brassard et al. [Phys. Rev. Lett. 96, 250401 (2006)10.1103/PhysRevLett.96.250401] we show that all correlated nonlocal boxes make communication complexity trivial, and therefore appear very unlikely to exist in nature. Astonishingly, some of these nonlocal boxes are arbitrarily close to the set of classical correlations. This result therefore gives new insight to the problem of why quantum nonlocality is limited.

arXiv:0901.4070•Physical Review Letters•Apr 24, 2009•120 citations

Popescu-Rohrlich Correlations as a Unit of Nonlocality

Jonathan Barrett, Stefano Pironio

A set of nonlocal correlations that have come to be known as a Popescu-Rohrlich (PR) box suggest themselves as a natural unit of nonlocality, much as a singlet is a natural unit of entanglement. We present two results relevant to this idea. One is that a wide class of multipartite correlations can be simulated using local operations on PR boxes only. We show this with an explicit scheme, which has the interesting feature that the number of PR boxes required is related to the computational resources necessary to represent a function defining the multipartite box. The second result is that there are quantum multipartite correlations, arising from measurements on a cluster state, that cannot be simulated with n PR boxes, for any n.

arXiv:quant-ph/0506180•Physical Review Letters•Sep 29, 2005•181 citations

Functional boxes, communication complexity and information causality

Guoming Wang

We propose a class of nonlocal boxes named functional boxes which include a generalization of the Popescu-Rohrlich(PR) box as a special case. We show that every functional box corresponding to an additively inseparable function can make communication complexity trivial and thus seems unlikely to exist in nature. Then we relate general nonlocal boxes to these functional boxes, and derive several limits on them from the principle of information causality.

arXiv:1109.4988•Sep 23, 2011•8 citations

Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise

Noah Shutty, Mary K. Wootters, Patrick M. Hayden

It has long been known that the existence of certain superquantum nonlocal correlations would cause communication complexity to collapse. The absurdity of a world in which any function could be evaluated by two players with a constant amount of communication in turn provides a tantalizing way to distinguish quantum mechanics from incorrect theories of physics; the statement “communication complexity is nontrivial” has even been conjectured to be a concise information-theoretic axiom for characterizing quantum mechanics. We directly address the viability of that perspective with two results. First, we exhibit a nonlocal game such that communication complexity collapses in any physical theory whose maximal winning probability exceeds the quantum value. Second, we consider the venerable CHSH game that initiated this line of inquiry. In that case, the quantum value is about 0.85 but it is known that a winning probability of approximately 0.91 would collapse communication complexity. We show that the 0.91 result is the best possible using a large class of proof strategies, suggesting that the communication complexity axiom is insufficient for characterizing CHSH correlations. Both results build on new insights about reliable classical computation. The first exploits our formalization of an equivalence between amplification and reliable computation, while the second follows from a rigorous determination of the threshold for reliable computation with formulas of noise-free XOR gates and noisy AND gates.

arXiv:1809.09748•Annual Symposium on Foundations of Computer Science•Nov 1, 2020•8 citations

Quantifying the randomness of copies of noisy Popescu-Rohrlich correlations

Boris Bourdoncle, Stefano Pironio, Antonio Acín

In a no-signaling world, the outputs of a nonlocal box cannot be completely predetermined, a feature that is exploited in many quantum information protocols exploiting nonlocality, such as device-independent randomness generation and quantum key distribution. This relation between nonlocality and randomness can be formally quantified through the min-entropy, a measure of the unpredictability of the outputs that holds conditioned on the knowledge of any adversary that is limited only by the no-signaling principle. This quantity can easily be computed for the noisy Popescu-Rohrlich (PR) box, the paradigmatic example of nonlocality. In this paper, we consider the min-entropy associated to several copies of noisy PR boxes. In the case where $n$ noisy PR boxes are implemented using $n$ noncommunicating pairs of devices, it is known that each PR box behaves as an independent biased coin: the min-entropy per PR box is constant with the number of copies. We show that this does not hold in more general scenarios where several noisy PR boxes are implemented from a single pair of devices, either used sequentially $n$ times or producing $n$ outcome bits in a single run. In this case, the min-entropy per PR box is smaller than the min-entropy of a single PR box, and it decreases as the number of copies increases.

arXiv:1807.04674•Physical Review A•Oct 25, 2018•2 citations

Extending the Known Region of Nonlocal Boxes that Collapse Communication Complexity

Pierre Botteron, Anne Broadbent, Marc-Olivier Proulx

Nonsignaling boxes (NS) are theoretical resources defined by the principle of no-faster-than-light communication. They generalize quantum correlations and some of them are known to collapse communication complexity (CC). However, this collapse is strongly believed to be unachievable in nature, so its study provides intuition on which theories are unrealistic. In the present Letter, we find a better sufficient condition for a nonlocal box to collapse CC, thus extending the known collapsing region. In some slices of NS, we show this condition coincides with an area outside of an ellipse.

arXiv:2302.00488•Physical Review Letters•Feb 14, 2024•8 citations
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⊠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 PR boxes that collapse communication complexity for different types of noise models.
We first present a protocol for deterministically distilling nonlocality, building upon a recent result of Forster et al. [Phys. Rev. Lett. 102, 120401 (2009)10.1103/PhysRevLett.102.120401]. Our protocol, which is optimal for two-copy distillation, works efficiently for a specific class of postquantum nonlocal boxes, which we term correlated nonlocal boxes. In the asymptotic limit, all correlated nonlocal boxes are distilled to the maximally nonlocal box of Popescu and Rohrlich. Then, taking advantage of a result of Brassard et al. [Phys. Rev. Lett. 96, 250401 (2006)10.1103/PhysRevLett.96.250401] we show that all correlated nonlocal boxes make communication complexity trivial, and therefore appear very unlikely to exist in nature. Astonishingly, some of these nonlocal boxes are arbitrarily close to the set of classical correlations. This result therefore gives new insight to the problem of why quantum nonlocality is limited.
A set of nonlocal correlations that have come to be known as a Popescu-Rohrlich (PR) box suggest themselves as a natural unit of nonlocality, much as a singlet is a natural unit of entanglement. We present two results relevant to this idea. One is that a wide class of multipartite correlations can be simulated using local operations on PR boxes only. We show this with an explicit scheme, which has the interesting feature that the number of PR boxes required is related to the computational resources necessary to represent a function defining the multipartite box. The second result is that there are quantum multipartite correlations, arising from measurements on a cluster state, that cannot be simulated with n PR boxes, for any n.
It has long been known that the existence of certain superquantum nonlocal correlations would cause communication complexity to collapse. The absurdity of a world in which any function could be evaluated by two players with a constant amount of communication in turn provides a tantalizing way to distinguish quantum mechanics from incorrect theories of physics; the statement “communication complexity is nontrivial” has even been conjectured to be a concise information-theoretic axiom for characterizing quantum mechanics. We directly address the viability of that perspective with two results. First, we exhibit a nonlocal game such that communication complexity collapses in any physical theory whose maximal winning probability exceeds the quantum value. Second, we consider the venerable CHSH game that initiated this line of inquiry. In that case, the quantum value is about 0.85 but it is known that a winning probability of approximately 0.91 would collapse communication complexity. We show that the 0.91 result is the best possible using a large class of proof strategies, suggesting that the communication complexity axiom is insufficient for characterizing CHSH correlations. Both results build on new insights about reliable classical computation. The first exploits our formalization of an equivalence between amplification and reliable computation, while the second follows from a rigorous determination of the threshold for reliable computation with formulas of noise-free XOR gates and noisy AND gates.
In a no-signaling world, the outputs of a nonlocal box cannot be completely predetermined, a feature that is exploited in many quantum information protocols exploiting nonlocality, such as device-independent randomness generation and quantum key distribution. This relation between nonlocality and randomness can be formally quantified through the min-entropy, a measure of the unpredictability of the outputs that holds conditioned on the knowledge of any adversary that is limited only by the no-signaling principle. This quantity can easily be computed for the noisy Popescu-Rohrlich (PR) box, the paradigmatic example of nonlocality. In this paper, we consider the min-entropy associated to several copies of noisy PR boxes. In the case where nnn noisy PR boxes are implemented using nnn noncommunicating pairs of devices, it is known that each PR box behaves as an independent biased coin: the min-entropy per PR box is constant with the number of copies. We show that this does not hold in more general scenarios where several noisy PR boxes are implemented from a single pair of devices, either used sequentially nnn times or producing nnn outcome bits in a single run. In this case, the min-entropy per PR box is smaller than the min-entropy of a single PR box, and it decreases as the number of copies increases.
Nonsignaling boxes (NS) are theoretical resources defined by the principle of no-faster-than-light communication. They generalize quantum correlations and some of them are known to collapse communication complexity (CC). However, this collapse is strongly believed to be unachievable in nature, so its study provides intuition on which theories are unrealistic. In the present Letter, we find a better sufficient condition for a nonlocal box to collapse CC, thus extending the known collapsing region. In some slices of NS, we show this condition coincides with an area outside of an ellipse.