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:0904.1390 · Physical Review A

Lower bound on the communication cost of simulating bipartite quantum correlations

Tamás Vértesi, Erika Bene

Published Dec 8, 2009• 15 citations
arXivHTMLPDF

Abstract

Suppose Alice and Bob share a maximally entangled state of any finite dimension and each perform two-outcome measurements on the respective part of the state. It is known, due to the recent result of Regev and Toner, that if a classical model is augmented with two bits of communication, then all the quantum correlations arising from these measurements can be reproduced. Here, we show that two bits of communication are in fact necessary for the perfect simulation. In particular, we prove that a pair of maximally entangled four-dimensional quantum systems cannot be simulated by a classical model augmented by only one bit of communication.

DOI
10.1103/physreva.80.062316

Related papers

Simulating Quantum Correlations with Finite Communication

Oded Regev, Ben Toner

Assume Alice and Bob share some bipartite d-dimensional quantum state. A well-known result in quantum mechanics says that by performing two-outcome measurements, Alice and Bob can produce correlations that cannot be obtained locally, i.e., with shared randomness alone. We show that by using only two bits of communication, Alice and Bob can classically simulate any such correlations. All previous protocols for exact simulation required the communication to grow to infinity with the dimension d. Our protocol and analysis are based on a power series method, resembling Krivine's bound on Grothendieck's constant, and on the computation of volumes of spherical tetrahedra.

SIAM Journal on Computing•Dec 4, 2009•36 citations

Simulating Quantum Correlations with Finite Communication

Oded Regev, Ben Toner

Assume Alice and Bob share some bipartite d-dimensional quantum state. As is well known, by performing two-outcome measurements, Alice and Bob can produce correlations that cannot be obtained classically. We show that by using only two bits of communication, Alice and Bob can classically simulate any such correlations. All previous protocols for exact simulation required the communication to grow to infinity with the dimension d. Our protocol and analysis are based on a power series method, resembling Krivine's bound on Grothendieck's constant, and on the computation of volumes of spherical tetrahedra.

Annual Symposium on Foundations of Computer Science•Oct 1, 2007•2 citations

Simulating Quantum Correlations with Finite Communication

Oded Regev, Ben Toner

Assume Alice and Bob share some bipartite d-dimensional quantum state. As is well known, by performing two-outcome measurements, Alice and Bob can produce correlations that cannot be obtained classically. We show that by using only two bits of communication, Alice and Bob can classically simulate any such correlations. All previous protocols for exact simulation required the communication to grow to infinity with the dimension d. Our protocol and analysis are based on a power series method, resembling Krivine's bound on Grothendieck's constant, and on the computation of volumes of spherical tetrahedra.

Annual Symposium on Foundations of Computer Science•Oct 1, 2007•14 citations

The cost of classically simulating quantum communication is as high as it could be

Riccardo Castellano, Pavel Sekatski, Nicolas Brunner

A long-standing open question is to characterize the classical communication cost of simulating the correlations arising from measurements on finite-dimensional quantum systems. We consider this question in the prepare-and-measure scenario. First we construct a classical simulation model involving a finite average number of bits of one-way communication that simulates exactly the correlations arising from arbitrary $d$-dimensional quantum states and arbitrary measurements. Second, we show that no classical simulation protocol involving a finite average message dimension can exist for $d\geq 4$, hence strengthening a recent result of de Gois, Santos and Vieira. Our first result relies on a more general simulation theorem which can be applied to certain continuous variable (i.e. infinite-dimensional) quantum systems, and even beyond quantum theory, e.g. to generalized probabilistic theories. In particular, we show that multimode Gaussian states of bounded average energy and general Gaussian measurements admit an exact classical simulation with a finite expected number of bits. Overall, our results show that the classical simulation cost of quantum communication is essentially as high as it could be.

quant-pharXiv:2610.19060•Oct 15, 2026•0 citations

Simulating Quantum Correlations with Finite Communication

Oded Regev, Ben Toner

Assume Alice and Bob share some bipartite $d$-dimensional quantum state. A well-known result in quantum mechanics says that by performing two-outcome measurements, Alice and Bob can produce correlations that cannot be obtained locally, i.e., with shared randomness alone. We show that by using only two bits of communication, Alice and Bob can classically simulate any such correlations. All previous protocols for exact simulation required the communication to grow to infinity with the dimension $d$. Our protocol and analysis are based on a power series method, resembling Krivine's bound on Grothendieck's constant, and on the computation of volumes of spherical tetrahedra.

arXiv:0708.0827•Aug 7, 2007•12 citations

Quantum communication and Bell nonlocality require infinite classical communication to simulate

Carlos de Gois, Thyago S. R. Santos, Carlos Vieira

A quantum system of any fixed dimension can be prepared in a continuum of states, yet it cannot be used to transmit an unlimited amount of classical information. Similarly, the correlations observed between measurement outcomes on separate parts of a shared quantum system can be stronger than classical correlations, but they cannot transmit information. These fundamental limitations suggest that the statistics observed from quantum communication and quantum correlations may admit a simulation using a finite amount of classical communication. This expectation is confirmed in the smallest nontrivial quantum dimension, with two classical bits being necessary and sufficient to exactly simulate qubit communication and all correlations between qubits. Despite significant efforts during the previous decades, this remained the only solved case. Here we resolve both problems for every quantum dimension. The solution reveals an unexpected qualitative transition starting at dimension four: no finite amount of classical communication can exactly simulate ququart communication nor all quantum correlations of two entangled ququarts, even with unlimited shared randomness. One might have expected this transition, if it existed, to appear already for qutrits. Instead, we construct an explicit protocol that exactly simulates qutrit communication using $357$ classical bits, and consequently, all correlations of two entangled qutrits.

quant-pharXiv:2609.04182•Sep 4, 2026•0 citations
Suppose Alice and Bob share a maximally entangled state of any finite dimension and each perform two-outcome measurements on the respective part of the state. It is known, due to the recent result of Regev and Toner, that if a classical model is augmented with two bits of communication, then all the quantum correlations arising from these measurements can be reproduced. Here, we show that two bits of communication are in fact necessary for the perfect simulation. In particular, we prove that a pair of maximally entangled four-dimensional quantum systems cannot be simulated by a classical model augmented by only one bit of communication.
Assume Alice and Bob share some bipartite d-dimensional quantum state. A well-known result in quantum mechanics says that by performing two-outcome measurements, Alice and Bob can produce correlations that cannot be obtained locally, i.e., with shared randomness alone. We show that by using only two bits of communication, Alice and Bob can classically simulate any such correlations. All previous protocols for exact simulation required the communication to grow to infinity with the dimension d. Our protocol and analysis are based on a power series method, resembling Krivine's bound on Grothendieck's constant, and on the computation of volumes of spherical tetrahedra.
Assume Alice and Bob share some bipartite d-dimensional quantum state. As is well known, by performing two-outcome measurements, Alice and Bob can produce correlations that cannot be obtained classically. We show that by using only two bits of communication, Alice and Bob can classically simulate any such correlations. All previous protocols for exact simulation required the communication to grow to infinity with the dimension d. Our protocol and analysis are based on a power series method, resembling Krivine's bound on Grothendieck's constant, and on the computation of volumes of spherical tetrahedra.
Assume Alice and Bob share some bipartite d-dimensional quantum state. As is well known, by performing two-outcome measurements, Alice and Bob can produce correlations that cannot be obtained classically. We show that by using only two bits of communication, Alice and Bob can classically simulate any such correlations. All previous protocols for exact simulation required the communication to grow to infinity with the dimension d. Our protocol and analysis are based on a power series method, resembling Krivine's bound on Grothendieck's constant, and on the computation of volumes of spherical tetrahedra.
A long-standing open question is to characterize the classical communication cost of simulating the correlations arising from measurements on finite-dimensional quantum systems. We consider this question in the prepare-and-measure scenario. First we construct a classical simulation model involving a finite average number of bits of one-way communication that simulates exactly the correlations arising from arbitrary ddd-dimensional quantum states and arbitrary measurements. Second, we show that no classical simulation protocol involving a finite average message dimension can exist for d≥4d\geq 4d≥4, hence strengthening a recent result of de Gois, Santos and Vieira. Our first result relies on a more general simulation theorem which can be applied to certain continuous variable (i.e. infinite-dimensional) quantum systems, and even beyond quantum theory, e.g. to generalized probabilistic theories. In particular, we show that multimode Gaussian states of bounded average energy and general Gaussian measurements admit an exact classical simulation with a finite expected number of bits. Overall, our results show that the classical simulation cost of quantum communication is essentially as high as it could be.
Assume Alice and Bob share some bipartite ddd-dimensional quantum state. A well-known result in quantum mechanics says that by performing two-outcome measurements, Alice and Bob can produce correlations that cannot be obtained locally, i.e., with shared randomness alone. We show that by using only two bits of communication, Alice and Bob can classically simulate any such correlations. All previous protocols for exact simulation required the communication to grow to infinity with the dimension ddd. Our protocol and analysis are based on a power series method, resembling Krivine's bound on Grothendieck's constant, and on the computation of volumes of spherical tetrahedra.
A quantum system of any fixed dimension can be prepared in a continuum of states, yet it cannot be used to transmit an unlimited amount of classical information. Similarly, the correlations observed between measurement outcomes on separate parts of a shared quantum system can be stronger than classical correlations, but they cannot transmit information. These fundamental limitations suggest that the statistics observed from quantum communication and quantum correlations may admit a simulation using a finite amount of classical communication. This expectation is confirmed in the smallest nontrivial quantum dimension, with two classical bits being necessary and sufficient to exactly simulate qubit communication and all correlations between qubits. Despite significant efforts during the previous decades, this remained the only solved case. Here we resolve both problems for every quantum dimension. The solution reveals an unexpected qualitative transition starting at dimension four: no finite amount of classical communication can exactly simulate ququart communication nor all quantum correlations of two entangled ququarts, even with unlimited shared randomness. One might have expected this transition, if it existed, to appear already for qutrits. Instead, we construct an explicit protocol that exactly simulates qutrit communication using 357357357 classical bits, and consequently, all correlations of two entangled qutrits.