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/0407133

Efficient classical-communication-assisted local simulation of n-qubit GHZ correlations

Tracey E. Tessier, Ivan Deutsch, Carlton M. Caves

Published Jul 16, 2004• 1 citation
arXivHTMLPDF

Abstract

We present a local hidden-variable model supplemented by classical communication that reproduces the quantum-mechanical predictions for measurements of all products of Pauli operators on an n-qubit GHZ state (or "cat state"). The simulation is efficient since the required amount of communication scales linearly with the number of qubits, even though there are Bell-type inequalities for these states for which the amount of violation grows exponentially with n. The structure of our model yields insight into the Gottesman-Knill theorem by demonstrating that, at least in this limited case, the correlations in the set of nonlocal hidden variables represented by the stabilizer generators are captured by an appropriate set of local hidden variables augmented by n-2 bits of classical communication.

DOI
10.48550/arxiv.quant-ph/0407133

Related papers

Optimal classical-communication-assisted local model of n -qubit Greenberger-Horne-Zeilinger correlations

Tracey E. Tessier, Carlton M. Caves, Ivan Deutsch +2 more

We present a model, motivated by the criterion of reality put forward by Einstein, Podolsky, and Rosen and supplemented by classical communication, which correctly reproduces the quantum-mechanical predictions for measurements of all products of Pauli operators on an $n$-qubit GHZ state (or ``cat state''). The $n\ensuremath{-}2\phantom{\rule{0.3em}{0ex}}\text{bits}$ employed by our model are shown to be optimal for the allowed set of measurements, demonstrating that the required communication overhead scales linearly with $n$. We formulate a connection between the generation of the local values utilized by our model and the stabilizer formalism, which leads us to conjecture that a generalization of this method will shed light on the content of the Gottesman-Knill theorem.

arXiv:quant-ph/0503047•Physical Review A•Sep 6, 2005•16 citations

Classical simulation of quantum entanglement without local hidden variables

Serge Massar, Dave Bacon, Nicolas J. Cerf +1 more

Recent work has extended Bell's theorem by quantifying the amount of communication required to simulate entangled quantum systems with classical information. The general scenario is that a bipartite measurement is given from a set of possibilities and the goal is to find a classical scheme that reproduces exactly the correlations that arise when an actual quantum system is measured. Previous results have shown that, using local hidden variables, a finite amount of communication suffices to simulate the correlations for a Bell state. We extend this in a number of ways. First, we show that, when the communication is merely required to be finite on average, Bell states can be simulated without any local hidden variables. More generally, we show that arbitrary positive operator valued measurements on systems of n Bell states can be simulated with ${O(n2}^{n})$ bits of communication on average (again, without local hidden variables). On the other hand, when the communication is required to be absolutely bounded, we show that a finite number of bits of local hidden variables is insufficient to simulate a Bell state. This latter result is based on an analysis of the nondeterministic communication complexity of the NOT-EQUAL function, which is constant in the quantum model and logarithmic in the classical model.

arXiv:quant-ph/0009088•Physical Review A•Apr 16, 2001•82 citations

Communication Cost of Simulating Bell Correlations

Ben Toner, Dave Bacon

What classical resources are required to simulate quantum correlations? For the simplest and most important case of local projective measurements on an entangled Bell pair state, we show that exact simulation is possible using local hidden variables augmented by just one bit of classical communication. Certain quantum teleportation experiments, which teleport a single qubit, therefore admit a local hidden variables model.

arXiv:quant-ph/0304076•Physical Review Letters•Oct 31, 2003•339 citations

Cost of Exactly Simulating Quantum Entanglement with Classical Communication

Gilles Brassard A, Richard Cleve, Alain Tapp

We investigate the amount of communication that must augment classical local hidden variable models in order to simulate the behavior of entangled quantum systems. We consider the scenario where a bipartite measurement is given from a set of possibilities and the goal is to obtain exactly the same correlations that arise when the actual quantum system is measured. We show that, in the case of a single pair of qubits in a Bell state, a constant number of bits of communication is always sufficient---regardless of the number of measurements under consideration. We also show that, in the case of a system of $n$ Bell states, a constant times ${2}^{n}$ bits of communication is necessary.

arXiv:quant-ph/9901035•Physical Review Letters•Aug 30, 1999•245 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•2 citations

Combinatorics and Quantum Nonlocality

Harry Buhrman, Peter Høyer, Serge Massar +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 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.

arXiv:quant-ph/0209052•Physical Review Letters•Jul 25, 2003•38 citations
We present a local hidden-variable model supplemented by classical communication that reproduces the quantum-mechanical predictions for measurements of all products of Pauli operators on an n-qubit GHZ state (or "cat state"). The simulation is efficient since the required amount of communication scales linearly with the number of qubits, even though there are Bell-type inequalities for these states for which the amount of violation grows exponentially with n. The structure of our model yields insight into the Gottesman-Knill theorem by demonstrating that, at least in this limited case, the correlations in the set of nonlocal hidden variables represented by the stabilizer generators are captured by an appropriate set of local hidden variables augmented by n-2 bits of classical communication.
We present a model, motivated by the criterion of reality put forward by Einstein, Podolsky, and Rosen and supplemented by classical communication, which correctly reproduces the quantum-mechanical predictions for measurements of all products of Pauli operators on an nnn-qubit GHZ state (or ``cat state''). The $n\ensuremath{-}2\phantom{\rule{0.3em}{0ex}}\text{bits}$ employed by our model are shown to be optimal for the allowed set of measurements, demonstrating that the required communication overhead scales linearly with nnn. We formulate a connection between the generation of the local values utilized by our model and the stabilizer formalism, which leads us to conjecture that a generalization of this method will shed light on the content of the Gottesman-Knill theorem.
Recent work has extended Bell's theorem by quantifying the amount of communication required to simulate entangled quantum systems with classical information. The general scenario is that a bipartite measurement is given from a set of possibilities and the goal is to find a classical scheme that reproduces exactly the correlations that arise when an actual quantum system is measured. Previous results have shown that, using local hidden variables, a finite amount of communication suffices to simulate the correlations for a Bell state. We extend this in a number of ways. First, we show that, when the communication is merely required to be finite on average, Bell states can be simulated without any local hidden variables. More generally, we show that arbitrary positive operator valued measurements on systems of n Bell states can be simulated with O(n2n){O(n2}^{n})O(n2n) bits of communication on average (again, without local hidden variables). On the other hand, when the communication is required to be absolutely bounded, we show that a finite number of bits of local hidden variables is insufficient to simulate a Bell state. This latter result is based on an analysis of the nondeterministic communication complexity of the NOT-EQUAL function, which is constant in the quantum model and logarithmic in the classical model.
We investigate the amount of communication that must augment classical local hidden variable models in order to simulate the behavior of entangled quantum systems. We consider the scenario where a bipartite measurement is given from a set of possibilities and the goal is to obtain exactly the same correlations that arise when the actual quantum system is measured. We show that, in the case of a single pair of qubits in a Bell state, a constant number of bits of communication is always sufficient---regardless of the number of measurements under consideration. We also show that, in the case of a system of nnn Bell states, a constant times 2n{2}^{n}2n bits of communication is necessary.
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 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.