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:quant-ph/0210114 · Physical Review Letters

Bell’s Inequalities and Quantum Communication Complexity

Časlav Brukner, Marek Żukowski, Jian-Wei Pan, Anton Zeilinger

Published Mar 22, 2004• 265 citations
arXivHTMLPDF

Abstract

We prove that for every Bell's inequality, including those which are not yet known, there always exists a communication complexity problem, for which a protocol assisted by states which violate the inequality is more efficient than any classical protocol. Violation of Bell's inequalities is the necessary and sufficient condition for quantum protocol to beat the classical ones.

DOI
10.1103/physrevlett.92.127901

Related papers

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•17 citations

Quantum communication complexity advantage implies violation of a Bell inequality

Harry Buhrman, Łukasz Czekaj, Andrzej Grudka +5 more

Significance For many communication complexity problems the quantum strategies, distinguished by using Bell nonlocal correlations, provide exponential advantage over the best possible classical strategies. Conversely, for any Bell nonlocal correlations there exists a communication complexity problem that is solved more efficiently using the former. Despite many efforts, there were only two problems for which one could certify that any strategy that outperforms the classical one must harbor Bell nonlocal correlations. We prove that any large advantage over the best known classical strategy makes use of Bell nonlocal correlations. Thus, we provide the missing link to the fundamental equivalence between Bell nonlocality and quantum advantage.

arXiv:1502.01058•Proceedings of the National Academy of Sciences•Mar 8, 2016•56 citations

Quantum Communication Complexity Protocol with Two Entangled Qutrits

Časlav Brukner, Marek Żukowski, Anton Zeilinger

We formulate a two-party communication complexity problem and present its quantum solution that exploits the entanglement between two qutrits. We prove that for a broad class of protocols the entangled state can enhance the efficiency of solving the problem in the quantum protocol over any classical one if and only if the state violates Bell's inequality for two qutrits.

arXiv:quant-ph/0205080•Physical Review Letters•Oct 18, 2002•189 citations

Robust Bell inequalities from communication complexity

Sophie Laplante, Mathieu Laurière, Alexandre Nolin +2 more

The question of how large Bell inequality violations can be, for quantum distributions, has been the object of much work in the past several years. We say that a Bell inequality is normalized if its absolute value does not exceed 1 for any classical (i.e. local) distribution. Upper and (almost) tight lower bounds have been given for the quantum violation of these Bell inequalities in terms of number of outputs of the distribution, number of inputs, and the dimension of the shared quantum states. In this work, we revisit normalized Bell inequalities together with another family: inefficiency-resistant Bell inequalities. To be inefficiency-resistant, the Bell value must not exceed 1 for any local distribution, including those that can abort. This makes the Bell inequality resistant to the detection loophole, while a normalized Bell inequality is resistant to general local noise. Both these families of Bell inequalities are closely related to communication complexity lower bounds. We show how to derive large violations from any gap between classical and quantum communication complexity, provided the lower bound on classical communication is proven using these lower bound techniques. This leads to inefficiency-resistant violations that can be exponential in the size of the inputs. Finally, we study resistance to noise and inefficiency for these Bell inequalities.

arXiv:1606.09514•Quantum•Jun 7, 2018•12 citations

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•40 citations
We prove that for every Bell's inequality, including those which are not yet known, there always exists a communication complexity problem, for which a protocol assisted by states which violate the inequality is more efficient than any classical protocol. Violation of Bell's inequalities is the necessary and sufficient condition for quantum protocol to beat the classical ones.
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.
Significance For many communication complexity problems the quantum strategies, distinguished by using Bell nonlocal correlations, provide exponential advantage over the best possible classical strategies. Conversely, for any Bell nonlocal correlations there exists a communication complexity problem that is solved more efficiently using the former. Despite many efforts, there were only two problems for which one could certify that any strategy that outperforms the classical one must harbor Bell nonlocal correlations. We prove that any large advantage over the best known classical strategy makes use of Bell nonlocal correlations. Thus, we provide the missing link to the fundamental equivalence between Bell nonlocality and quantum advantage.
The question of how large Bell inequality violations can be, for quantum distributions, has been the object of much work in the past several years. We say that a Bell inequality is normalized if its absolute value does not exceed 1 for any classical (i.e. local) distribution. Upper and (almost) tight lower bounds have been given for the quantum violation of these Bell inequalities in terms of number of outputs of the distribution, number of inputs, and the dimension of the shared quantum states. In this work, we revisit normalized Bell inequalities together with another family: inefficiency-resistant Bell inequalities. To be inefficiency-resistant, the Bell value must not exceed 1 for any local distribution, including those that can abort. This makes the Bell inequality resistant to the detection loophole, while a normalized Bell inequality is resistant to general local noise. Both these families of Bell inequalities are closely related to communication complexity lower bounds. We show how to derive large violations from any gap between classical and quantum communication complexity, provided the lower bound on classical communication is proven using these lower bound techniques. This leads to inefficiency-resistant violations that can be exponential in the size of the inputs. Finally, we study resistance to noise and inefficiency for these Bell inequalities.
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.