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:1109.4988

Functional boxes, communication complexity and information causality

Guoming Wang

Published Sep 23, 2011• 8 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1109.4988

Related papers

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

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

Popescu-Rohrlich box fraction of nonobjective information and distinguishing quantum theory

Chellasamy Jebarathinam

It is demonstrated that identifying information-theoretic limitations of quantum Bell nonlocality alone cannot completely distinguish quantum theory from generalized nonsignaling theories. To this end, an information-theoretic concept of certifying nonobjective information by the Popescu-Rohrlich box fraction is employed. Furthermore, in the aforementioned demonstration, a partial answer to the question of what distinguishes quantum theory from generalized nonsignaling theories emerges beyond the one provided by the principle of information causality alone. This is accomplished by demonstrating that postquantum models identified by the information causality are isolated by the emergence of the Popescu-Rohrlich box fraction of nonobjective information in Bell-local boxes of a nonsignaling model, over the other nonsignaling models.

arXiv:2507.21051•Jul 28, 2025•0 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

Communication complexity bounds from information causality

Nikolai Miklin, Prabhav Jain, Mariami Gachechiladze

Communication complexity, which quantifies the minimum communication required for distributed computation, offers a natural setting for investigating the capabilities and limitations of quantum mechanics in information processing. We introduce an information-theoretic approach to study one-way communication complexity based solely on the axioms of mutual information. Within this framework, we derive an extended statement of the information causality principle, which recovers known lower bounds on the communication complexities for a range of functions in a simplified manner and leads to new results. We further prove that the extended information causality principle is at least as strong as the principle of non-trivial communication complexity in bounding the strength of quantum correlations attainable in Bell experiments. Our study establishes a new route for exploring the fundamental limits of quantum technologies from an information-theoretic viewpoint.

quant-pharXiv:2602.10206•Feb 12, 2026•6 citations

Limit on Nonlocality in Any World in Which Communication Complexity Is Not Trivial

Gilles Brassard, Harry Buhrman, Noah Linden +3 more

Bell proved that quantum entanglement enables two spacelike separated parties to exhibit classically impossible correlations. Even though these correlations are stronger than anything classically achievable, they cannot be harnessed to make instantaneous (faster than light) communication possible. Yet, Popescu and Rohrlich have shown that even stronger correlations can be defined, under which instantaneous communication remains impossible. This raises the question: Why are the correlations achievable by quantum mechanics not maximal among those that preserve causality? We give a partial answer to this question by showing that slightly stronger correlations would result in a world in which communication complexity becomes trivial.

arXiv:quant-ph/0508042•Physical Review Letters•Jun 27, 2006•409 citations
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.
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.
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 demonstrated that identifying information-theoretic limitations of quantum Bell nonlocality alone cannot completely distinguish quantum theory from generalized nonsignaling theories. To this end, an information-theoretic concept of certifying nonobjective information by the Popescu-Rohrlich box fraction is employed. Furthermore, in the aforementioned demonstration, a partial answer to the question of what distinguishes quantum theory from generalized nonsignaling theories emerges beyond the one provided by the principle of information causality alone. This is accomplished by demonstrating that postquantum models identified by the information causality are isolated by the emergence of the Popescu-Rohrlich box fraction of nonobjective information in Bell-local boxes of a nonsignaling model, over the other nonsignaling 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.
Communication complexity, which quantifies the minimum communication required for distributed computation, offers a natural setting for investigating the capabilities and limitations of quantum mechanics in information processing. We introduce an information-theoretic approach to study one-way communication complexity based solely on the axioms of mutual information. Within this framework, we derive an extended statement of the information causality principle, which recovers known lower bounds on the communication complexities for a range of functions in a simplified manner and leads to new results. We further prove that the extended information causality principle is at least as strong as the principle of non-trivial communication complexity in bounding the strength of quantum correlations attainable in Bell experiments. Our study establishes a new route for exploring the fundamental limits of quantum technologies from an information-theoretic viewpoint.
Bell proved that quantum entanglement enables two spacelike separated parties to exhibit classically impossible correlations. Even though these correlations are stronger than anything classically achievable, they cannot be harnessed to make instantaneous (faster than light) communication possible. Yet, Popescu and Rohrlich have shown that even stronger correlations can be defined, under which instantaneous communication remains impossible. This raises the question: Why are the correlations achievable by quantum mechanics not maximal among those that preserve causality? We give a partial answer to this question by showing that slightly stronger correlations would result in a world in which communication complexity becomes trivial.