Simulating Quantum Correlations with Finite Communication

Abstract

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.

19 pages, 3 figures, preliminary version in IEEE FOCS 2007; to appear in SICOMP

References in corpus (9)

• The Communication Cost of Simulating Bell Correlations
• The cost of exactly simulating quantum entanglement with classical communication
• Quantum entanglement can be simulated without communication
• Simulating quantum correlations as a distributed sampling problem
• Classical simulation of quantum entanglement without local hidden variables
• Classical Teleportation of a Quantum Bit
• Violations of Bell inequalities as lower bounds on the communication cost of non-local correlations
• Bell Inequalities with Auxiliary Communication
• Simulation of bipartite qudit correlations

Cited by in corpus (4)

• Non-locality and Communication Complexity
• A generalized Grothendieck inequality and entanglement in XOR games
• The communication complexity of XOR games via summing operators
• Tripartite probability distributions and communication complexity