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:2106.06552 · npj Quantum Information

Entanglement-based quantum communication complexity beyond Bell nonlocality

Joseph Ho, George Moreno, Samuraí Brito, Francesco Graffitti, Christopher L. Morrison, Ranieri Nery, Alexander Pickston, Massimiliano Proietti, Rafael Rabelo, Alessandro Fedrizzi, Rafael Chaves

Published Feb 3, 2022• 29 citations
arXivHTMLPDF

Abstract

Abstract Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks, such as parallel computation and circuit optimisation. Crucially, the communication overhead introduced by the allotment process should be minimised—a key motivation behind the communication complexity problem (CCP). Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. Furthermore, the connection between quantum CCPs and non-locality provides an information-theoretic insight into fundamental quantum mechanics. Here we connect quantum CCPs with a generalised non-locality framework—beyond Bell’s paradigmatic theorem—by incorporating the underlying causal structure, which governs the distributed task, into a so-called non-local hidden-variable model. We prove that a new class of communication complexity tasks can be associated with Bell-like inequalities, whose violation is both necessary and sufficient for a quantum gain. We experimentally implement a multipartite CCP akin to the guess-your-neighbour-input scenario, and demonstrate a quantum advantage when multipartite Greenberger-Horne-Zeilinger (GHZ) states are shared among three users.

DOI
10.1038/s41534-022-00520-8

Related papers

High-Dimensional Quantum Communication Complexity beyond Strategies Based on Bell’s Theorem

Daniel Martínez, Armin Tavakoli, Maurício Casanova +3 more

Quantum resources can improve communication complexity problems (CCPs) beyond their classical constraints. One quantum approach is to share entanglement and create correlations violating a Bell inequality, which can then assist classical communication. A second approach is to resort solely to the preparation, transmission, and measurement of a single quantum system, in other words, quantum communication. Here, we show the advantages of the latter over the former in high-dimensional Hilbert space. We focus on a family of CCPs, based on facet Bell inequalities, study the advantage of high-dimensional quantum communication, and realize such quantum communication strategies using up to ten-dimensional systems. The experiment demonstrates, for growing dimension, an increasing advantage over quantum strategies based on Bell inequality violation. For sufficiently high dimensions, quantum communication also surpasses the limitations of the postquantum Bell correlations obeying only locality in the macroscopic limit. We find that the advantages are tied to the use of measurements that are not rank-one projective, and provide an experimental semi-device-independent falsification of such measurements in Hilbert space dimension six.

arXiv:1807.04622•Physical Review Letters•Oct 12, 2018•41 citations

Does violation of a Bell inequality always imply quantum advantage in a communication complexity problem?

Armin Tavakoli, Marek Żukowski, Časlav Brukner

Quantum correlations which violate a Bell inequality are presumed to power better-than-classical protocols for solving communication complexity problems (CCPs). How general is this statement? We show that violations of correlation-type Bell inequalities allow advantages in CCPs, when communication protocols are tailored to emulate the Bell no-signaling constraint (by not communicating measurement settings). Abandonment of this restriction on classical models allows us to disprove the main result of, inter alia, \cite{BZ02}; we show that quantum correlations obtained from these communication strategies assisted by a small quantum violation of the CGLMP Bell inequalities do not imply advantages in any CCP in the input/output scenario considered in the reference. More generally, we show that there exists quantum correlations, with nontrivial local marginal probabilities, which violate the I3322 Bell inequality, but do not enable a quantum advantange in any CCP, regardless of the communication strategy employed in the quantum protocol, for a scenario with a fixed number of inputs and outputs

arXiv:1907.01322•Quantum•Sep 7, 2020•20 citations

Higher-dimensional communication complexity problems: Classical protocols versus quantum ones based on Bell's theorem or prepare-transmit-measure schemes

Armin Tavakoli, Marek Żukowski

Communication complexity problems (CCPs) are tasks in which separated parties attempt to compute a function whose inputs are distributed among the parties. Their communication is limited so that not all inputs can be sent. We show that broad classes of Bell inequalities can be mapped to CCPs and that a quantum violation of a Bell inequality is a necessary and sufficient condition for an enhancement of the related CCP beyond its classical limitation. However, one can implement CCPs by transmitting a quantum system, encoding no more information than is allowed in the CCP, and extracting information by performing measurements. We show that for a large class of Bell inequalities, the improvement of the CCP associated with a quantum violation of a Bell inequality can be no greater than the improvement obtained from quantum prepare-transmit-measure strategies.

arXiv:1611.00977•Physical Review A•Apr 4, 2017•18 citations

Quantum nonlocality, cryptography and complexity

Anne Broadbent

Quantum computing is the study of what we can and cannot do with quantum computers: computers operating based on the laws of quantum mechanics. This thesis is a collection of seven papers, dealing with three aspects of quantum computing: non-locality, cryptography and complexity. Nonlocality. Quantum nonlocality refers to the fact that, using a resource called quantum entanglement, two participants who are physically separated and unable to communicate can exhibit correlations that cannot be produced without entanglement. This gives rise to nonlocal games, which are multi-player cooperative games for which quantum players (who share entanglement) have an advantage over classical players (who share only classical information). A pseudo-telepathy game is a special case of a nonlocal game for which quantum players have a perfect winning strategy. The first paper in this thesis, On the power of non-local boxes, is a study of quantum correlations (which are non-signalling, i.e. they do not allow faster-than-light communication), as well as superquantum correlations (which are also non-signalling, but stronger than those predicted by quantum mechanics). We consider the simulation of pseudo-telepathy winning strategies with the nonlocal box (which can be seen as the most basic superquantum correlation), revealing that nonlocality and entanglement are different resources. Before our work, it was common to equate these two notions. The second paper, Classical, quantum and non-signalling resources in bipartite games, shows that the problem of deciding if a fixed game has a perfect classical winning strategy is NP-complete, while deciding if a perfect strategy exists with superquantum correlations is in P. We also establish links with the Bell-Kochen-Specker theorem, orthogonality graphs and two-prover interactive proofs. Quantum nonlocality is a phenomenon that we can, in theory, witness in the laboratory. Many experiments have been performed, but none so far have simultaneously closed all experimental loopholes. There is currently a substantial scientific effort to achieve the perfect laboratory experiment. Yet not all experimental setups are created equally: the third and fourth paper of this thesis, Entanglement swapping, light cones and elements of reality and On the logical structure of Bell theorems, show that recent proposals have classical explanations, and thus do nothing to aid in our comprehension of the quantum world. This work is scientifically valuable, since it tells us that we should not invest in the proposed lines of research. Classical and quantum cryptography. The groundbreaking work of Peter Shor in 1995 established that quantum computers can efficiently factor large integers, thus rendering most modern cryptographic systems insecure. But what quantum computers break, they also fix: Bennett and Brassard had already given in 1984 a protocol for key distribution whose security is based only on the laws of quantum mechanics. In a world with quantum computers, it seems like the only way to ensure perfect security in cryptographic tasks is to do away with computational assumptions (such as the apparent difficulty of factoring): this is the realm of information-theoretic security. In the fifth paper of this thesis, Information-theoretic security without an honest majority we give protocols to accomplish a series of six private distributed tasks (in particular, vote and anonymous message transmission), while ensuring information-theoretic security. Then, in Anonymous quantum communication, we give a protocol which, within a group, allows a sender to transfer a quantum message to a receiver ofhis choosing. The protocol ensures information-theoretic anonymity for the sender and the receiver as well as information-theoretic privacy for the message. Complexity in the measurement-based model. Finally, in Parallelizing quantum circuits, we study the depth complexity of quantum circuits, giving an automated technique for the parrallelization of quantum circuits. The development of parallel (low-depth) quantum circuits seems almost essential if we wish to implement quantum algorithms in the near future with available technology. Quantum information is usually unstable, hence we can only operate on it for a very short period of time. Parallel circuits maximize the use of this fragile quantum information. Our method is based on the recent paradigm for quantum computing called the measurement-based model. Key words: quantum information processing, pseudo-telepathy, nonlocal boxes, Bell's theorem, multi-party computation, information-theoretic security, anonymity, quantum depth complexity, measurement-based quantum computing, measurement calculus.

•Jan 1, 2008•0 citations

Scalable and noise-robust communication advantage of multipartite quantum entanglement

Ananya Chakraborty, Ram Krishna Patra, Kunika Agarwal +4 more

Distributed computing, involving multiple servers collaborating on designated computations, faces a critical challenge in optimizing interserver communication---an issue central to the study of communication complexity. Quantum resources offer advantages over classical methods in addressing this challenge. In this work, we investigate a distributed computing scenario with multiple senders and a single receiver, establishing a scalable advantage of multipartite quantum entanglement in mitigating communication complexity. Specifically, we demonstrate that when the receiver and the senders share a multiqubit Greenberger-Horne-Zeilinger (GHZ) state---a quintessential form of genuine multipartite entanglement---certain global functions of the distributed inputs can be computed with only one bit of classical communication from each sender. In contrast, without entanglement, two bits of communication are required from all but one sender. Consequently, quantum entanglement reduces communication overhead by $n\ensuremath{-}1$ bits for $n$ senders, allowing for arbitrary scaling with an increasing number of senders. We also show that the entanglement-based protocol exhibits significant robustness under white noise, thereby establishing the potential for experimental realization of this quantum advantage.

arXiv:2409.13223•Physical Review A•Mar 20, 2025•8 citations

Unbounded Bell violations for quantum genuine multipartite non-locality

Abderramán Amr, Carlos Palazuelos, Julio I. de Vicente

Abstract The violations of Bell inequalities by measurements on quantum states give rise to the phenomenon of quantum non-locality and express the advantage of using quantum resources over classical ones for certain information-theoretic tasks. The relative degree of quantum violations has been well studied in the bipartite scenario and in the multipartite scenario with respect to fully local behaviours. However, the multipartite setting entails a more complex classification in which different notions on non-locality can be established. In particular, genuine multipartite non-local distributions apprehend truly multipartite effects, given that these behaviours cannot be reproduced by bilocal models that allow correlations among strict subsets of the parties beyond a local common cause. We show here that, while in the so-called correlation scenario the relative violation of bilocal Bell inequalities by quantum resources is bounded, i.e. it does not grow arbitrarily with the number of inputs, it turns out to be unbounded in the general case. We identify Bell functionals that take the form of non-local games for which the ratio of the quantum and bilocal values grows unboundedly as a function of the number of inputs and outputs.

arXiv:2002.12614•Journal of Physics A Mathematical and Theoretical•May 7, 2020•1 citation
Abstract Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks, such as parallel computation and circuit optimisation. Crucially, the communication overhead introduced by the allotment process should be minimised—a key motivation behind the communication complexity problem (CCP). Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. Furthermore, the connection between quantum CCPs and non-locality provides an information-theoretic insight into fundamental quantum mechanics. Here we connect quantum CCPs with a generalised non-locality framework—beyond Bell’s paradigmatic theorem—by incorporating the underlying causal structure, which governs the distributed task, into a so-called non-local hidden-variable model. We prove that a new class of communication complexity tasks can be associated with Bell-like inequalities, whose violation is both necessary and sufficient for a quantum gain. We experimentally implement a multipartite CCP akin to the guess-your-neighbour-input scenario, and demonstrate a quantum advantage when multipartite Greenberger-Horne-Zeilinger (GHZ) states are shared among three users.
Quantum resources can improve communication complexity problems (CCPs) beyond their classical constraints. One quantum approach is to share entanglement and create correlations violating a Bell inequality, which can then assist classical communication. A second approach is to resort solely to the preparation, transmission, and measurement of a single quantum system, in other words, quantum communication. Here, we show the advantages of the latter over the former in high-dimensional Hilbert space. We focus on a family of CCPs, based on facet Bell inequalities, study the advantage of high-dimensional quantum communication, and realize such quantum communication strategies using up to ten-dimensional systems. The experiment demonstrates, for growing dimension, an increasing advantage over quantum strategies based on Bell inequality violation. For sufficiently high dimensions, quantum communication also surpasses the limitations of the postquantum Bell correlations obeying only locality in the macroscopic limit. We find that the advantages are tied to the use of measurements that are not rank-one projective, and provide an experimental semi-device-independent falsification of such measurements in Hilbert space dimension six.
Quantum correlations which violate a Bell inequality are presumed to power better-than-classical protocols for solving communication complexity problems (CCPs). How general is this statement? We show that violations of correlation-type Bell inequalities allow advantages in CCPs, when communication protocols are tailored to emulate the Bell no-signaling constraint (by not communicating measurement settings). Abandonment of this restriction on classical models allows us to disprove the main result of, inter alia, \cite{BZ02}; we show that quantum correlations obtained from these communication strategies assisted by a small quantum violation of the CGLMP Bell inequalities do not imply advantages in any CCP in the input/output scenario considered in the reference. More generally, we show that there exists quantum correlations, with nontrivial local marginal probabilities, which violate the I3322 Bell inequality, but do not enable a quantum advantange in any CCP, regardless of the communication strategy employed in the quantum protocol, for a scenario with a fixed number of inputs and outputs
Communication complexity problems (CCPs) are tasks in which separated parties attempt to compute a function whose inputs are distributed among the parties. Their communication is limited so that not all inputs can be sent. We show that broad classes of Bell inequalities can be mapped to CCPs and that a quantum violation of a Bell inequality is a necessary and sufficient condition for an enhancement of the related CCP beyond its classical limitation. However, one can implement CCPs by transmitting a quantum system, encoding no more information than is allowed in the CCP, and extracting information by performing measurements. We show that for a large class of Bell inequalities, the improvement of the CCP associated with a quantum violation of a Bell inequality can be no greater than the improvement obtained from quantum prepare-transmit-measure strategies.
Quantum computing is the study of what we can and cannot do with quantum computers: computers operating based on the laws of quantum mechanics. This thesis is a collection of seven papers, dealing with three aspects of quantum computing: non-locality, cryptography and complexity. Nonlocality. Quantum nonlocality refers to the fact that, using a resource called quantum entanglement, two participants who are physically separated and unable to communicate can exhibit correlations that cannot be produced without entanglement. This gives rise to nonlocal games, which are multi-player cooperative games for which quantum players (who share entanglement) have an advantage over classical players (who share only classical information). A pseudo-telepathy game is a special case of a nonlocal game for which quantum players have a perfect winning strategy. The first paper in this thesis, On the power of non-local boxes, is a study of quantum correlations (which are non-signalling, i.e. they do not allow faster-than-light communication), as well as superquantum correlations (which are also non-signalling, but stronger than those predicted by quantum mechanics). We consider the simulation of pseudo-telepathy winning strategies with the nonlocal box (which can be seen as the most basic superquantum correlation), revealing that nonlocality and entanglement are different resources. Before our work, it was common to equate these two notions. The second paper, Classical, quantum and non-signalling resources in bipartite games, shows that the problem of deciding if a fixed game has a perfect classical winning strategy is NP-complete, while deciding if a perfect strategy exists with superquantum correlations is in P. We also establish links with the Bell-Kochen-Specker theorem, orthogonality graphs and two-prover interactive proofs. Quantum nonlocality is a phenomenon that we can, in theory, witness in the laboratory. Many experiments have been performed, but none so far have simultaneously closed all experimental loopholes. There is currently a substantial scientific effort to achieve the perfect laboratory experiment. Yet not all experimental setups are created equally: the third and fourth paper of this thesis, Entanglement swapping, light cones and elements of reality and On the logical structure of Bell theorems, show that recent proposals have classical explanations, and thus do nothing to aid in our comprehension of the quantum world. This work is scientifically valuable, since it tells us that we should not invest in the proposed lines of research. Classical and quantum cryptography. The groundbreaking work of Peter Shor in 1995 established that quantum computers can efficiently factor large integers, thus rendering most modern cryptographic systems insecure. But what quantum computers break, they also fix: Bennett and Brassard had already given in 1984 a protocol for key distribution whose security is based only on the laws of quantum mechanics. In a world with quantum computers, it seems like the only way to ensure perfect security in cryptographic tasks is to do away with computational assumptions (such as the apparent difficulty of factoring): this is the realm of information-theoretic security. In the fifth paper of this thesis, Information-theoretic security without an honest majority we give protocols to accomplish a series of six private distributed tasks (in particular, vote and anonymous message transmission), while ensuring information-theoretic security. Then, in Anonymous quantum communication, we give a protocol which, within a group, allows a sender to transfer a quantum message to a receiver ofhis choosing. The protocol ensures information-theoretic anonymity for the sender and the receiver as well as information-theoretic privacy for the message. Complexity in the measurement-based model. Finally, in Parallelizing quantum circuits, we study the depth complexity of quantum circuits, giving an automated technique for the parrallelization of quantum circuits. The development of parallel (low-depth) quantum circuits seems almost essential if we wish to implement quantum algorithms in the near future with available technology. Quantum information is usually unstable, hence we can only operate on it for a very short period of time. Parallel circuits maximize the use of this fragile quantum information. Our method is based on the recent paradigm for quantum computing called the measurement-based model. Key words: quantum information processing, pseudo-telepathy, nonlocal boxes, Bell's theorem, multi-party computation, information-theoretic security, anonymity, quantum depth complexity, measurement-based quantum computing, measurement calculus.
Distributed computing, involving multiple servers collaborating on designated computations, faces a critical challenge in optimizing interserver communication---an issue central to the study of communication complexity. Quantum resources offer advantages over classical methods in addressing this challenge. In this work, we investigate a distributed computing scenario with multiple senders and a single receiver, establishing a scalable advantage of multipartite quantum entanglement in mitigating communication complexity. Specifically, we demonstrate that when the receiver and the senders share a multiqubit Greenberger-Horne-Zeilinger (GHZ) state---a quintessential form of genuine multipartite entanglement---certain global functions of the distributed inputs can be computed with only one bit of classical communication from each sender. In contrast, without entanglement, two bits of communication are required from all but one sender. Consequently, quantum entanglement reduces communication overhead by $n\ensuremath{-}1$ bits for nnn senders, allowing for arbitrary scaling with an increasing number of senders. We also show that the entanglement-based protocol exhibits significant robustness under white noise, thereby establishing the potential for experimental realization of this quantum advantage.
Abstract The violations of Bell inequalities by measurements on quantum states give rise to the phenomenon of quantum non-locality and express the advantage of using quantum resources over classical ones for certain information-theoretic tasks. The relative degree of quantum violations has been well studied in the bipartite scenario and in the multipartite scenario with respect to fully local behaviours. However, the multipartite setting entails a more complex classification in which different notions on non-locality can be established. In particular, genuine multipartite non-local distributions apprehend truly multipartite effects, given that these behaviours cannot be reproduced by bilocal models that allow correlations among strict subsets of the parties beyond a local common cause. We show here that, while in the so-called correlation scenario the relative violation of bilocal Bell inequalities by quantum resources is bounded, i.e. it does not grow arbitrarily with the number of inputs, it turns out to be unbounded in the general case. We identify Bell functionals that take the form of non-local games for which the ratio of the quantum and bilocal values grows unboundedly as a function of the number of inputs and outputs.