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

Tripartite probability distributions and communication complexity

Carlos Palazuelos, David Pérez-Garcı́a, Ignacio Villanueva

Published Jun 28, 2010• 0 citations
arXivHTMLPDF

Abstract

We show that every tripartite quantum correlation generated with a Schmidt state (in particular every correlation generated with the GHZ state) can be simulated with the sending of two bits of classical communication from Alice to Bob and Charlie plus the sending of two bits of classical communication from Bob to Charlie. This extends recent results which showed that the maximal violation of Bell inequalities attainable by these correlations is uniformly bounded. For simplicity, we state and prove the result for three parties, but the generalization to the case of $n$ parties follows easily. We also show that every $n$-partite probability distribution generated with local resources plus $c$-bits of local communication can violate a Bell inequality by at most a factor of $2^c$.

DOI
10.48550/arxiv.1006.5318

Related papers

Violations of Bell inequalities as lower bounds on the communication cost of nonlocal correlations

Stefano Pironio

To reproduce in a local hidden variables theory correlations that violate Bell inequalities, communication must occur between the parties. We show that the amount of violation of a Bell inequality imposes a lower bound on the average communication needed to produce these correlations. Moreover, for every probability distribution there exists an optimal inequality for which the degree of violation gives the minimal average communication. As an example, to produce using classical resources the correlations that maximally violate the Clauser-Horne-Shimony-Holt inequality, $\sqrt{2}\ensuremath{-}1\ensuremath{\simeq}0.4142$ bits of communication are necessary and sufficient. For Bell tests performed on two entangled states of dimension $d>~3$ where each party has the choice between two measurements, our results suggest that more communication is needed to simulate outcomes obtained from certain nonmaximally entangled states than maximally entangled ones.

arXiv:quant-ph/0304176•Physical Review A•Dec 4, 2003•70 citations

Exact Classical Simulation of the GHZ Distribution

Gilles Brassard A, Luc Devroye, Claude Gravel

John Bell has shown that the correlations entailed by quantum mechanics cannot be reproduced by a classical process involving non-communicating parties. But can they be simulated with the help of bounded communication? This problem has been studied for more than twenty years and it is now well understood in the case of bipartite entanglement. However, the issue was still widely open for multipartite entanglement, even for the simplest case, which is the tripartite Greenberger-Horne-Zeilinger (GHZ) state. We give an exact simulation of arbitrary independent von Neumann measurements on general n-partite GHZ states. Our protocol requires O(n^2) bits of expected communication between the parties, and O(n*log(n)) expected time is sufficient to carry it out in parallel. Furthermore, we need only an expectation of O(n) independent unbiased random bits, with no need for the generation of continuous real random variables nor prior shared random variables. In the case of equatorial measurements, we improve earlier results with a protocol that needs only O(n*log(n)) bits of communication and O(log^2(n)) parallel time. At the cost of a slight increase in the number of bits communicated, these tasks can be accomplished with a constant expected number of rounds.

Leibniz international proceedings in informatics•Jan 1, 2014•0 citations

Exact Classical Simulation of the Quantum-Mechanical GHZ Distribution

Gilles Brassard A, Luc Devroye, Claude Gravel

John Bell has shown that the correlations entailed by quantum mechanics cannot be reproduced by a classical process involving non-communicating parties. But can they be simulated with the help of bounded communication? This problem has been studied for more than two decades, and it is now well understood in the case of bipartite entanglement. However, the issue was still widely open for multipartite entanglement, even for the simplest case, which is the tripartite Greenberger- Horne-Zeilinger (GHZ) state. We give an exact simulation of arbitrary independent von Neumann measurements on general n-partite GHZ states. Our protocol requires O(n2) bits of expected communication between the parties, and O(n log n) expected time is sufficient to carry it out in parallel. Furthermore, we need only an expectation of O(n) independent unbiased random bits, with no need for the generation of continuous real random variables nor prior shared random variables. In the case of equatorial measurements, we improve on the prior art with a protocol that needs only O(n log n) bits of communication and O(log2n) parallel time. At the cost of a slight increase in the number of bits communicated, these tasks can be accomplished with a constant expected number of rounds.

arXiv:1303.5942•IEEE Transactions on Information Theory•Dec 1, 2015•7 citations

Exact simulation for the GHZ distribution

Luc Devroye, Claude Gravel

John Bell has shown that the correlations entailed by quantum mechanics cannot be reproduced by a classical process involving non-communicating parties. But can they be simulated with the help of bounded communication? This problem has been studied for more than two decades and it is now well understood in the case of bipartite entanglement. However, the issue was still widely open for multipartite entanglement, even for the simplest case, which is the tripartite Greenberger-Horne-Zeilinger (GHZ) state. We give an exact simulation of arbitrary independent von Neumann measurements on general n-partite GHZ states. Our protocol requires O(n^2) bits of expected communication between the parties, and O(n log n) expected time is sufficient to carry it out in parallel. Furthermore, we need only an expectation of O(n) independent unbiased random bits, with no need for the generation of continuous real random variables nor prior shared random variables. In the case of equatorial measurements, we improve on the prior art with a protocol that needs only O(n log n) bits of communication and O(log^2 n) parallel time. At the cost of a slight increase in the number of bits communicated, these tasks can be accomplished with a constant expected number of rounds.

•Mar 24, 2013•1 citation

Quantifying quantum nonlocality

Ben Toner

Quantum mechanics is nonlocal, meaning it cannot be described by any classical local hidden variable model. In this thesis we study two aspects of quantum nonlocality. Part I addresses the question of what classical resources are required to simulate nonlocal quantum correlations. We start by constructing new local models for noisy entangled quantum states. These constructions exploit the connection between nonlocality and Grothendieck's inequality, first noticed by Tsirelson. Next, we consider local models augmented by a limited amount of classical communication. After generalizing Bell inequalities to this setting, we show that (i) one bit of communication is sufficient to simulate the correlations of projective measurements on a maximally entangled state of two qubits, and (ii) five bits of communication are sufficient to simulate the joint correlation of two-outcome measurements on any bipartite quantum state. The latter result can be interpreted as a stronger (constrained) version of Grothendieck's inequality. In part II, we investigate the monogamy of nonlocal correlations. In a setting where three parties, A, B, and C, share an entangled quantum state of arbitrary dimension, we: (i) bound the trade-off between AB's and AC's violation of the CHSH inequality, obtaining an intriguing generalization of Tsirelson's bound, and (ii) demonstrate that forcing B and C to be classically correlated prevents A and B from violating certain Bell inequalities. We study not only correlations that arise within quantum theory, but also arbitrary correlations that do not allow signaling between separate groups of parties. These results are based on new techniques for obtaining Tsirelson bounds, or bounds on the quantum value of a Bell inequality, and have applications to interactive proof systems and cryptography.

•Aug 12, 2013•2 citations

Unbounded Violation of Tripartite Bell Inequalities

David Pérez-Garcı́a, Michael M. Wolf, Carlos Palazuelos +2 more

We prove that there are tripartite quantum states (constructed from random unitaries) that can lead to arbitrarily large violations of Bell inequalities for dichotomic observables. As a consequence these states can withstand an arbitrary amount of white noise before they admit a description within a local hidden variable model. This is in sharp contrast with the bipartite case, where all violations are bounded by Grothendieck’s constant. We will discuss the possibility of determining the Hilbert space dimension from the obtained violation and comment on implications for communication complexity theory. Moreover, we show that the violation obtained from generalized Greenberger-Horne-Zeilinger (GHZ) states is always bounded so that, in contrast to many other contexts, GHZ states do not lead to extremal quantum correlations in this case. In order to derive all these physical consequences, we will have to obtain new mathematical results in the theories of operator spaces and tensor norms. In particular, we will prove the existence of bounded but not completely bounded trilinear forms from commutative C*-algebras. Finally, we will relate the existence of diagonal states leading to unbounded violations with a long-standing open problem in the context of Banach algebras.

arXiv:quant-ph/0702189•Communications in Mathematical Physics•Feb 11, 2008•141 citations
We show that every tripartite quantum correlation generated with a Schmidt state (in particular every correlation generated with the GHZ state) can be simulated with the sending of two bits of classical communication from Alice to Bob and Charlie plus the sending of two bits of classical communication from Bob to Charlie. This extends recent results which showed that the maximal violation of Bell inequalities attainable by these correlations is uniformly bounded. For simplicity, we state and prove the result for three parties, but the generalization to the case of nnn parties follows easily. We also show that every nnn-partite probability distribution generated with local resources plus ccc-bits of local communication can violate a Bell inequality by at most a factor of 2c2^c2c.
To reproduce in a local hidden variables theory correlations that violate Bell inequalities, communication must occur between the parties. We show that the amount of violation of a Bell inequality imposes a lower bound on the average communication needed to produce these correlations. Moreover, for every probability distribution there exists an optimal inequality for which the degree of violation gives the minimal average communication. As an example, to produce using classical resources the correlations that maximally violate the Clauser-Horne-Shimony-Holt inequality, $\sqrt{2}\ensuremath{-}1\ensuremath{\simeq}0.4142$ bits of communication are necessary and sufficient. For Bell tests performed on two entangled states of dimension d> 3d>~3d> 3 where each party has the choice between two measurements, our results suggest that more communication is needed to simulate outcomes obtained from certain nonmaximally entangled states than maximally entangled ones.
John Bell has shown that the correlations entailed by quantum mechanics cannot be reproduced by a classical process involving non-communicating parties. But can they be simulated with the help of bounded communication? This problem has been studied for more than twenty years and it is now well understood in the case of bipartite entanglement. However, the issue was still widely open for multipartite entanglement, even for the simplest case, which is the tripartite Greenberger-Horne-Zeilinger (GHZ) state. We give an exact simulation of arbitrary independent von Neumann measurements on general n-partite GHZ states. Our protocol requires O(n^2) bits of expected communication between the parties, and O(n*log(n)) expected time is sufficient to carry it out in parallel. Furthermore, we need only an expectation of O(n) independent unbiased random bits, with no need for the generation of continuous real random variables nor prior shared random variables. In the case of equatorial measurements, we improve earlier results with a protocol that needs only O(n*log(n)) bits of communication and O(log^2(n)) parallel time. At the cost of a slight increase in the number of bits communicated, these tasks can be accomplished with a constant expected number of rounds.
John Bell has shown that the correlations entailed by quantum mechanics cannot be reproduced by a classical process involving non-communicating parties. But can they be simulated with the help of bounded communication? This problem has been studied for more than two decades, and it is now well understood in the case of bipartite entanglement. However, the issue was still widely open for multipartite entanglement, even for the simplest case, which is the tripartite Greenberger- Horne-Zeilinger (GHZ) state. We give an exact simulation of arbitrary independent von Neumann measurements on general n-partite GHZ states. Our protocol requires O(n2) bits of expected communication between the parties, and O(n log n) expected time is sufficient to carry it out in parallel. Furthermore, we need only an expectation of O(n) independent unbiased random bits, with no need for the generation of continuous real random variables nor prior shared random variables. In the case of equatorial measurements, we improve on the prior art with a protocol that needs only O(n log n) bits of communication and O(log2n) parallel time. At the cost of a slight increase in the number of bits communicated, these tasks can be accomplished with a constant expected number of rounds.
John Bell has shown that the correlations entailed by quantum mechanics cannot be reproduced by a classical process involving non-communicating parties. But can they be simulated with the help of bounded communication? This problem has been studied for more than two decades and it is now well understood in the case of bipartite entanglement. However, the issue was still widely open for multipartite entanglement, even for the simplest case, which is the tripartite Greenberger-Horne-Zeilinger (GHZ) state. We give an exact simulation of arbitrary independent von Neumann measurements on general n-partite GHZ states. Our protocol requires O(n^2) bits of expected communication between the parties, and O(n log n) expected time is sufficient to carry it out in parallel. Furthermore, we need only an expectation of O(n) independent unbiased random bits, with no need for the generation of continuous real random variables nor prior shared random variables. In the case of equatorial measurements, we improve on the prior art with a protocol that needs only O(n log n) bits of communication and O(log^2 n) parallel time. At the cost of a slight increase in the number of bits communicated, these tasks can be accomplished with a constant expected number of rounds.
Quantum mechanics is nonlocal, meaning it cannot be described by any classical local hidden variable model. In this thesis we study two aspects of quantum nonlocality. Part I addresses the question of what classical resources are required to simulate nonlocal quantum correlations. We start by constructing new local models for noisy entangled quantum states. These constructions exploit the connection between nonlocality and Grothendieck's inequality, first noticed by Tsirelson. Next, we consider local models augmented by a limited amount of classical communication. After generalizing Bell inequalities to this setting, we show that (i) one bit of communication is sufficient to simulate the correlations of projective measurements on a maximally entangled state of two qubits, and (ii) five bits of communication are sufficient to simulate the joint correlation of two-outcome measurements on any bipartite quantum state. The latter result can be interpreted as a stronger (constrained) version of Grothendieck's inequality. In part II, we investigate the monogamy of nonlocal correlations. In a setting where three parties, A, B, and C, share an entangled quantum state of arbitrary dimension, we: (i) bound the trade-off between AB's and AC's violation of the CHSH inequality, obtaining an intriguing generalization of Tsirelson's bound, and (ii) demonstrate that forcing B and C to be classically correlated prevents A and B from violating certain Bell inequalities. We study not only correlations that arise within quantum theory, but also arbitrary correlations that do not allow signaling between separate groups of parties. These results are based on new techniques for obtaining Tsirelson bounds, or bounds on the quantum value of a Bell inequality, and have applications to interactive proof systems and cryptography.
We prove that there are tripartite quantum states (constructed from random unitaries) that can lead to arbitrarily large violations of Bell inequalities for dichotomic observables. As a consequence these states can withstand an arbitrary amount of white noise before they admit a description within a local hidden variable model. This is in sharp contrast with the bipartite case, where all violations are bounded by Grothendieck’s constant. We will discuss the possibility of determining the Hilbert space dimension from the obtained violation and comment on implications for communication complexity theory. Moreover, we show that the violation obtained from generalized Greenberger-Horne-Zeilinger (GHZ) states is always bounded so that, in contrast to many other contexts, GHZ states do not lead to extremal quantum correlations in this case. In order to derive all these physical consequences, we will have to obtain new mathematical results in the theories of operator spaces and tensor norms. In particular, we will prove the existence of bounded but not completely bounded trilinear forms from commutative C*-algebras. Finally, we will relate the existence of diagonal states leading to unbounded violations with a long-standing open problem in the context of Banach algebras.