Simulating quantum correlations with finite communication

Oded Regev, Ben Toner

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)1562-1580
Number of pages19
JournalSIAM Journal on Computing
Issue number4
StatePublished - 2010


  • Communication complexity
  • Quantum entanglement

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Simulating quantum correlations with finite communication'. Together they form a unique fingerprint.

Cite this