Published December 4, 2009
| Published
Journal Article
Open
Simulating Quantum Correlations with Finite Communication
- Creators
- Regev, Oded
- Toner, Ben
Chicago
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.
Additional Information
© 2009 Society for Industrial and Applied Mathematics. Received by the editors May 12, 2008; accepted for publication (in revised form) August 17, 2009; published electronically December 4, 2009. This author's research was supported by an Alon Fellowship, by the Binational Science Foundation, by the Israel Science Foundation, by the EU project QAP funded by the IST directorate as contract 015848, and by a European Research Council (ERC) starting grant. Part of this work was completed while the author was at CWI (Amsterdam) and Caltech. This author's research was supported by NSF grants PHY-0456720 and CCF-0524828, by ARO grant W911NF-05-1-0294, by the Dutch BSIK/BRICKS project, by EU project QAP, and by NWO VICI project 639-023-302. Part of this work was done while we were visiting the Institut Henri Poincar´e as part of the program "Quantum information, computation and complexity," and we would like to thank the organizers for their efforts. We thank Aram Harrow for discussions about lower bounds, Falk Unger for assistance with the proof of Lemma 3.1, and Peter Harremo¨es for discussions about Schoenberg's theorem.Attached Files
Published - Regev2009p10151Siam_J_Comput.pdf
Files
Regev2009p10151Siam_J_Comput.pdf
Files
(329.2 kB)
Name | Size | Download all |
---|---|---|
md5:e274fa6eaf98c0d569b94a0087fd03e1
|
329.2 kB | Preview Download |
Additional details
- Eprint ID
- 18727
- Resolver ID
- CaltechAUTHORS:20100618-081821751
- Alon Fellowship
- Binational Science Foundation
- Israel Science Foundation
- European Union (EU)
- IST directorate
- 015848
- European Research Council (ERC)
- NSF
- PHY-0456720
- NSF
- CCF-0524828
- Army Research Office (ARO)
- W911NF-05-1-0294
- Dutch BSIK/BRICKS
- NWO VICI
- 639-023-302
- Created
-
2010-07-09Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field