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:2302.00488 · Physical Review Letters

Extending the Known Region of Nonlocal Boxes that Collapse Communication Complexity

Pierre Botteron, Anne Broadbent, Marc-Olivier Proulx

Published Feb 14, 2024• 8 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevlett.132.070201

Related papers

Algebra of Nonlocal Boxes and the Collapse of Communication Complexity

Pierre Botteron, Anne Broadbent, Reda Chhaibi +2 more

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.

arXiv:2312.00725•Quantum•Jul 10, 2024•4 citations

Nonlocal correlations as an information-theoretic resource

Jonathan Barrett, Noah Linden, Serge Massar +3 more

It is well known that measurements performed on spatially separated entangled quantum systems can give rise to correlations that are nonlocal, in the sense that a Bell inequality is violated. They cannot, however, be used for superluminal signaling. It is also known that it is possible to write down sets of ``superquantum'' correlations that are more nonlocal than is allowed by quantum mechanics, yet are still nonsignaling. Viewed as an information-theoretic resource, superquantum correlations are very powerful at reducing the amount of communication needed for distributed computational tasks. An intriguing question is why quantum mechanics does not allow these more powerful correlations. We aim to shed light on the range of quantum possibilities by placing them within a wider context. With this in mind, we investigate the set of correlations that are constrained only by the no-signaling principle. These correlations form a polytope, which contains the quantum correlations as a (proper) subset. We determine the vertices of the no-signaling polytope in the case that two observers each choose from two possible measurements with $d$ outcomes. We then consider how interconversions between different sorts of correlations may be achieved. Finally, we consider some multipartite examples.

arXiv:quant-ph/0404097•Physical Review A•Feb 2, 2005•627 citations

Finite-time collapse process and non-local correlations are incompatible with non-signaling theories

George Moreno, Alejandro Fonseca, Márcio M. Cunha

We propose a hidden variable analysis of collapse dynamics in which the state's reduction process may take a finite time $δt$. A full characterization of the model is given for the case of black boxes. By introducing nonlocal perfect correlations to a two black-boxes scenario, it is shown that in order to avoid faster than light communication, the reduction time associated to the system must be strictly null. Furthermore we prove that the result above holds even when there is a time window between the choice of both part's inputs. Our results represent a new evidence of the instantaneous nature of the wave function collapse process which could have implications in foundations of quantum mechanics and information science.

arXiv:1809.00383•Sep 2, 2018•0 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

Information-based measure of nonlocality

A. Montina, Stefan Wolf

Quantum nonlocality concerns correlations among spatially separated systems that cannot be explained classically without communication among the parties. Thus, a natural measure of nonlocal correlations is provided by the minimal amount of communication required for classically simulating them. In this paper, we present a method to compute the minimal communication cost of parallel simulations, which we call nonlocal capacity, for any general nonsignaling correlations. This measure turns out to have an important role in communication complexity and can be used to discriminate between local and nonlocal correlations, as an alternative to the violation of Bell's inequalities.

arXiv:1312.6290•New Journal of Physics•Jan 20, 2016•13 citations

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
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.
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.
It is well known that measurements performed on spatially separated entangled quantum systems can give rise to correlations that are nonlocal, in the sense that a Bell inequality is violated. They cannot, however, be used for superluminal signaling. It is also known that it is possible to write down sets of ``superquantum'' correlations that are more nonlocal than is allowed by quantum mechanics, yet are still nonsignaling. Viewed as an information-theoretic resource, superquantum correlations are very powerful at reducing the amount of communication needed for distributed computational tasks. An intriguing question is why quantum mechanics does not allow these more powerful correlations. We aim to shed light on the range of quantum possibilities by placing them within a wider context. With this in mind, we investigate the set of correlations that are constrained only by the no-signaling principle. These correlations form a polytope, which contains the quantum correlations as a (proper) subset. We determine the vertices of the no-signaling polytope in the case that two observers each choose from two possible measurements with ddd outcomes. We then consider how interconversions between different sorts of correlations may be achieved. Finally, we consider some multipartite examples.
We propose a hidden variable analysis of collapse dynamics in which the state's reduction process may take a finite time δtδtδt. A full characterization of the model is given for the case of black boxes. By introducing nonlocal perfect correlations to a two black-boxes scenario, it is shown that in order to avoid faster than light communication, the reduction time associated to the system must be strictly null. Furthermore we prove that the result above holds even when there is a time window between the choice of both part's inputs. Our results represent a new evidence of the instantaneous nature of the wave function collapse process which could have implications in foundations of quantum mechanics and information science.
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.
Quantum nonlocality concerns correlations among spatially separated systems that cannot be explained classically without communication among the parties. Thus, a natural measure of nonlocal correlations is provided by the minimal amount of communication required for classically simulating them. In this paper, we present a method to compute the minimal communication cost of parallel simulations, which we call nonlocal capacity, for any general nonsignaling correlations. This measure turns out to have an important role in communication complexity and can be used to discriminate between local and nonlocal correlations, as an alternative to the violation of Bell's inequalities.
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.