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/0209052 · Physical Review Letters

Combinatorics and Quantum Nonlocality

Harry Buhrman, Peter Høyer, Serge Massar, Hein Röhrig

Published Jul 25, 2003• 39 citations
arXivHTMLPDF

Abstract

We use techniques for lower bounds on communication to derive necessary conditions (in terms of detector efficiency or amount of superluminal communication) for being able to reproduce the quantum correlations occurring in Einstein-Podolsky-Rosen-type experiments with classical local hidden-variable theories. As an application, we consider n parties sharing a Greenberger-Horne-Zeilinger-type state and show that the amount of superluminal classical communication required to reproduce the correlations is at least n(log((2)n-3) bits and the maximum detector efficiency eta(*) for which the resulting correlations can still be reproduced by a local hidden-variable theory is upper bounded by eta(*)</=8/n and thus decreases with n.

DOI
10.1103/physrevlett.91.047903

Related papers

Multipartite nonlocal quantum correlations resistant to imperfections

Harry Buhrman, Peter Høyer, Hein Röhrig +1 more

We use techniques for lower bounds on communication to derive necessary conditions in terms of detector efficiency or amount of superluminal communication for being able to reproduce with classical local hidden-variable theories the quantum correlations occurring in Einstein-Podolsky-Rosen (EPR) experiments in the presence of noise. We apply our method to an example involving $n$ parties sharing a Greenberger-Horne-Zeilinger-type state on which they carry out local measurements. For this example, we show that for local hidden-variable theories to reproduce the quantum correlations, the amount of superluminal classical communication $c$ and the detector efficiency $\ensuremath{\eta}$ are constrained by $\ensuremath{\eta}{2}^{\ensuremath{-}c∕n}\ensuremath{\leqslant}O({n}^{\ensuremath{-}1∕6})$. This result holds even if the classical models are allowed to make an error with constant probability.

arXiv:quant-ph/0410139•Physical Review A•Jan 18, 2006•8 citations

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

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

Improved lower bound on superluminal quantum communication

Bruno Cocciaro, S. Faetti, Leone Fronzoni

As shown by Einstein, Podolsky, and Rosen (the EPR paradox) [A. Einstein, B. Podolsky, and N. Rosen, Phys. Rev. 47, 777 (1935)], quantum mechanics is a nonlocal theory contrarily to what happens for any other modern physical theory. Alternative local theories based on superluminal communications have been also proposed in the literature. So far, no evidence for these superluminal communications has been obtained and only lower bounds for the superluminal velocities have been established. In this paper we describe an improved experiment that increases by about two orders of magnitude the maximum detectable superluminal velocities. The locality, the freedom of choice, and the detection loopholes are not addressed here. No evidence for superluminal communications has been found and a higher lower bound for their velocities has been established.

arXiv:1802.00423•Physical Review A•May 23, 2018•10 citations

Quantifying Multipartite Nonlocality

Jean-Daniel Bancal, Cyril Branciard, Nicolas Gisin +1 more

The nonlocal correlations of multipartite entangled states can be reproduced by a classical model if sufficiently many parties join together or if sufficiently many parties broadcast their measurement inputs. The maximal number m of groups and the minimal number k of broadcasting parties that allow for the reproduction of a given set of correlations quantify their multipartite nonlocal content. We show how upper bounds on m and lower bounds on k can be computed from the violation of the Mermin-Svetlichny inequalities. While n-partite Greenberger-Horne-Zeilinger states violate these inequalities maximally, we find that W states violate them only by a very small amount.

arXiv:0903.2715•Physical Review Letters•Aug 26, 2009•98 citations

Bounding Two-Way Average Communication Cost of Simulating Quantum Correlations

Kai-Siang Chen, Gelo Noel M. Tabia, Bo-An Tsai +2 more

Bell nonlocal correlations cannot be reproduced by local hidden-variable models without communication, making classical communication cost a natural quantitative measure of nonlocality. Although finite communication always suffices to simulate any correlation in a fixed finite Bell scenario, determining the minimum amount needed to (exactly) simulate any given nonlocal correlation remains challenging, especially in the average-cost setting. Here, we derive lower bounds on input-average communication cost from nonlocal games, allowing variable-length, fully interactive two-way protocols. When applied to parallel games, these bounds yield explicit finite quantum correlations for which the exact simulation cost exceeds any prescribed finite input-average communication budget. For $n$ parallel Magic-Square-winning correlations, we prove a lower bound of $n\log_2(3/2)$ bits and give a one-way communication protocol that attains this rate asymptotically. For the quantum correlation maximally winning the $n$-copy of the Clauser--Horne--Shimony--Holt nonlocal game, we obtain an input-average lower bound of approximately $0.04627n$ bits for exact simulation. Finally, we formulate a hierarchy of lower bounds and complementary upper bounds using deterministic correlations up to chosen communication costs. Both recover the exact input-average cost at their final levels, and if the bounds agree at lower levels, their common value yields the exact input-average cost without needing to consider all communication strategies.

quant-pharXiv:2610.04648•Oct 6, 2026•0 citations
We use techniques for lower bounds on communication to derive necessary conditions (in terms of detector efficiency or amount of superluminal communication) for being able to reproduce the quantum correlations occurring in Einstein-Podolsky-Rosen-type experiments with classical local hidden-variable theories. As an application, we consider n parties sharing a Greenberger-Horne-Zeilinger-type state and show that the amount of superluminal classical communication required to reproduce the correlations is at least n(log((2)n-3) bits and the maximum detector efficiency eta() for which the resulting correlations can still be reproduced by a local hidden-variable theory is upper bounded by eta()</=8/n and thus decreases with n.
We use techniques for lower bounds on communication to derive necessary conditions in terms of detector efficiency or amount of superluminal communication for being able to reproduce with classical local hidden-variable theories the quantum correlations occurring in Einstein-Podolsky-Rosen (EPR) experiments in the presence of noise. We apply our method to an example involving nnn parties sharing a Greenberger-Horne-Zeilinger-type state on which they carry out local measurements. For this example, we show that for local hidden-variable theories to reproduce the quantum correlations, the amount of superluminal classical communication ccc and the detector efficiency $\ensuremath{\eta}$ are constrained by $\ensuremath{\eta}{2}^{\ensuremath{-}c∕n}\ensuremath{\leqslant}O({n}^{\ensuremath{-}1∕6})$. This result holds even if the classical models are allowed to make an error with constant probability.
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.
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.
As shown by Einstein, Podolsky, and Rosen (the EPR paradox) [A. Einstein, B. Podolsky, and N. Rosen, Phys. Rev. 47, 777 (1935)], quantum mechanics is a nonlocal theory contrarily to what happens for any other modern physical theory. Alternative local theories based on superluminal communications have been also proposed in the literature. So far, no evidence for these superluminal communications has been obtained and only lower bounds for the superluminal velocities have been established. In this paper we describe an improved experiment that increases by about two orders of magnitude the maximum detectable superluminal velocities. The locality, the freedom of choice, and the detection loopholes are not addressed here. No evidence for superluminal communications has been found and a higher lower bound for their velocities has been established.
The nonlocal correlations of multipartite entangled states can be reproduced by a classical model if sufficiently many parties join together or if sufficiently many parties broadcast their measurement inputs. The maximal number m of groups and the minimal number k of broadcasting parties that allow for the reproduction of a given set of correlations quantify their multipartite nonlocal content. We show how upper bounds on m and lower bounds on k can be computed from the violation of the Mermin-Svetlichny inequalities. While n-partite Greenberger-Horne-Zeilinger states violate these inequalities maximally, we find that W states violate them only by a very small amount.
Bell nonlocal correlations cannot be reproduced by local hidden-variable models without communication, making classical communication cost a natural quantitative measure of nonlocality. Although finite communication always suffices to simulate any correlation in a fixed finite Bell scenario, determining the minimum amount needed to (exactly) simulate any given nonlocal correlation remains challenging, especially in the average-cost setting. Here, we derive lower bounds on input-average communication cost from nonlocal games, allowing variable-length, fully interactive two-way protocols. When applied to parallel games, these bounds yield explicit finite quantum correlations for which the exact simulation cost exceeds any prescribed finite input-average communication budget. For nnn parallel Magic-Square-winning correlations, we prove a lower bound of nlog⁡2(3/2)n\log_2(3/2)nlog2​(3/2) bits and give a one-way communication protocol that attains this rate asymptotically. For the quantum correlation maximally winning the nnn-copy of the Clauser--Horne--Shimony--Holt nonlocal game, we obtain an input-average lower bound of approximately 0.04627n0.04627n0.04627n bits for exact simulation. Finally, we formulate a hierarchy of lower bounds and complementary upper bounds using deterministic correlations up to chosen communication costs. Both recover the exact input-average cost at their final levels, and if the bounds agree at lower levels, their common value yields the exact input-average cost without needing to consider all communication strategies.