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:1907.01322 · Quantum

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

Armin Tavakoli, Marek Żukowski, Časlav Brukner

Published Sep 7, 2020• 20 citations
arXivHTMLPDF

Abstract

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

DOI
10.22331/q-2020-09-07-316

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

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•67 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

Universal scheme for violation of local realism from quantum advantage in one-way communication complexity

Łukasz Czekaj, Andrzej Grudka, Michał Horodecki +2 more

We consider relations between communication complexity problems and detecting correlations (violating local realism) with no local hidden variable model. We show first universal equivalence between characteristics of protocols used in that type of problems and non-signaling correlations. We construct non linear bipartite Bell type inequalities and strong nonlocality test with binary observables by providing general method of Bell inequalities construction and showing that existence of gap between quantum and classical complexity leads to violation of these inequalities. We obtain, first to our knowledge, explicit Bell inequality with binary observables and exponential violation.

arXiv:1308.5404•Aug 25, 2013•1 citation

Bell’s Inequalities and Quantum Communication Complexity

Časlav Brukner, Marek Żukowski, Jian-Wei Pan +1 more

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.

arXiv:quant-ph/0210114•Physical Review Letters•Mar 22, 2004•274 citations

Entanglement-based quantum communication complexity beyond Bell nonlocality

Joseph Ho, George Moreno, Samuraí Brito +8 more

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.

arXiv:2106.06552•npj Quantum Information•Feb 3, 2022•29 citations
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
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.
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.
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.
We consider relations between communication complexity problems and detecting correlations (violating local realism) with no local hidden variable model. We show first universal equivalence between characteristics of protocols used in that type of problems and non-signaling correlations. We construct non linear bipartite Bell type inequalities and strong nonlocality test with binary observables by providing general method of Bell inequalities construction and showing that existence of gap between quantum and classical complexity leads to violation of these inequalities. We obtain, first to our knowledge, explicit Bell inequality with binary observables and exponential violation.
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.