Tensor norms and the classical communication complexity of nonlocal quantum measurement

ABSTRACT

Nonlocality is at the heart of quantum information processing. In this paper we investigate the minimum amount of classical communication required to simulate a nonlocal quantum measurement. We derive general upper bounds, which in turn translate to systematic classical simulations of quantum communication protocols.As a concrete application, we prove that any quantum communication protocol with shared entanglement for computing a Boolean function can be simulated by a classical protocol whose cost does not depend on the amount of the shared entanglement. This implies that if the cost of communication is a constant, quantum and classical protocols, with shared entanglement and shared coins, respectively, compute the same class of functions.Furthermore, we describe a new class of efficient quantum communication protocols based on fast quantum algorithms. While some of them have efficient classical simulations by our method, others appear to be good candidates for separating quantum v.s. classical protocols, and quantum protocols with v.s. without shared entanglement.Yet another application is in the context of simulating quantum correlations using local hidden variable models augmented with classical communications. We give a constant cost, approximate simulation of quantum correlations when the number of correlated variables is a constant, while the dimension of the entanglement and the number of possible measurements can be arbitrary.Our upper bounds are expressed in terms of some tensor norms on the measurement operator. Those norms capture the nonlocality of bipartite operators in their own way and may be of independent interest and further applications.

REFERENCES

• 1: Scott Aaronson , Andris Ambainis, Quantum Search of Spatial Regions, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.200, October 11-14, 2003
• 2: Dorit Aharonov , Alexei Kitaev , Noam Nisan, Quantum circuits with mixed states, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.20-30, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276708]
• 3: Andris Ambainis , Leonard J. Schulman , Amnon Ta-Shma , Umesh Vazirani , Avi Wigderson, The Quantum Communication Complexity of Sampling, SIAM Journal on Computing, v.32 n.6, p.1570-1585, 2003 [doi>10.1137/S009753979935476]
• 4: A. Ambainis. Quantum query algorithms and lower bounds. In Proceedings of Foundations of the Formal Sciences III, September 2001.
• 5: Ziv Bar-Yossef , T. S. Jayram , Iordanis Kerenidis, Exponential separation of quantum and classical one-way communication complexity, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007379]
• 6: J. S. Bell. On the Einstein-Podolsky-Rosen paradox. Physics , 1:195, 1964.
• 7: C. H. Bennett and G. Brassard. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of IEEE international Conference on Computers, Systems and Signal Processing, Bangalore, India, page 175, New York, 1984. IEEE Press.
• 8: C. H. Bennett, A. W. Harrow, D. W. Leung, and J. A. Smolin. On the capacities of bipartite Hamiltonians and unitary gates, 2002.
• 9: Ethan Bernstein , Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, v.26 n.5, p.1411-1473, Oct. 1997 [doi>10.1137/S0097539796300921]
• 10: D. Bohm. The paradox of Einstein, Rosen, and Podolsky. In Quantum Theory and Measurement, pages 611--623. Prentice-Hall, 1951.
• 11: Harry Buhrman , Richard Cleve , Wim van Dam, Quantum Entanglement and Communication Complexity, SIAM Journal on Computing, v.30 n.6, p.1829-1841, 2001 [doi>10.1137/S0097539797324886]
• 12: H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Quantum fingerprinting. Phys. Rev. Lett., 87(16):167902, October 2001.
• 13: Harry Buhrman , Richard Cleve , Avi Wigderson, Quantum vs. classical communication and computation, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.63-68, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276713]
• 14: A. M. Childs, H. L. Haselgrove, and M. A. Nielsen. Lower bounds on the complexity of simulating quantum gates. Phys. Rev. A, 68:052311--052316, 2003.
• 15: A. M. Childs, D. W. Leung, F. Verstraete, and G. Vidal. Asymptotic entanglement capacity of the Ising and anisotropic Heisenberg interactions. Quantum Information and Computation, 3:97, 2003.
• 16: R. Cleve and H. Buhrman. Substituting quantum entanglement for communication. Phys. Rev. A, 56:1201, 1997.
• 17: Richard Cleve , Wim van Dam , Michael Nielsen , Alain Tapp, Quantum Entanglement and the Communication Complexity of the Inner Product Function, Selected papers from the First NASA International Conference on Quantum Computing and Quantum Communications, p.61-74, February 17-20, 1998
• 18: A. Defant and K. Floret. Tensor norms and operator ideals, volume 176 of North-Holland Mathematics Studies. North-Holland Publishing Co., Amsterdam, 1993.
• 19: A. Einstein, B. Podolsky, and N. Rosen. Can quantum-mechanical description of reality be considered complete? Phys. Rev., 47(10):777--780, May 1935.
• 20: Michel X. Goemans , David P. Williamson, .879-approximation algorithms for MAX CUT and MAX 2SAT, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.422-431, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195216]
• 21: Peter Høyer , Ronald de Wolf, Improved Quantum Communication Complexity Bounds for Disjointness and Equality, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, p.299-310, March 14-16, 2002
• 22: Alexei Kitaev , John Watrous, Parallelization, amplification, and exponential time simulation of quantum interactive proof systems, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.608-617, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335387]
• 23: A. Yu. Kitaev , A. H. Shen , M. N. Vyalyi, Classical and Quantum Computation, American Mathematical Society, Boston, MA, 2002
• 24: H. Klauck, Lower Bounds for Quantum Communication Complexity, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.288, October 14-17, 2001
• 25: Ilan Kremer , Noam Nisan , Dana Ron, On randomized one-round communication complexity, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.596-605, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225277]
• 26: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 27: H.-K. Lo and H. F. Chau. Unconditional security of quantum key distribution over arbitrarily long distances. Science, 283(5410):2050--2056, March 1999.
• 28: Dominic Mayers, Unconditional security in quantum cryptography, Journal of the ACM (JACM), v.48 n.3, p.351-406, May 2001 [doi>10.1145/382780.382781]
• 29: Ashwin Nayak , Julia Salzman, On communication over an entanglement-assisted quantum channel, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510007]
• 30: Ilan Newman, Private vs. common random bits in communication complexity, Information Processing Letters, v.39 n.2, p.67-71, July 31, 1991 [doi>10.1016/0020-0190(91)90157-D]
• 31: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 32: J. Preskill. Lecture notes for physics 229: Quantum information and computation.
• 33: Ran Raz, Exponential separation of quantum and classical communication complexity, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.358-367, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301343]
• 34: A. A. Razborov. Quantum communication complexity of symmetric predicates (Russian). Izvestiya of the Russian Academy of Science, Mathematics, 6, 2002. English translation available at http://genesis.mi.ras.ru/~razborov/qcc_eng.ps.
• 35: O. Rudolph. A separability criterion for density operators. J. Phys. A-Math. Gen., 33(21):3951--3955, June 2000.
• 36: O. Rudolph. Further results on the cross norm criterion for separability. Preprint available at quant-ph/0202143, February 2002.
• 37: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
• 38: Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing, v.26 n.5, p.1474-1483, Oct. 1997 [doi>10.1137/S0097539796298637]
• 39: W. Tittel, J. Brendel, H. Zbinden, and N. Gisin. Violation of Bell Inequalities by photons more than 10 km apart. Phys. Rev. Lett., 81(17):3563, Oct 1998.
• 40: B. Toner and D. Bacon. Communication cost of simulating Bell correlations. Phys Rev Lett., 91(18):187904, Oct 2003.
• 41: Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]
• 42: A. C.-C. Yao. Quantum circuit complexity. In 34th Annual Symposium on Foundations of Computer Science: November 3--5, 1993, Palo Alto, California: proceedings {papers}, pages 352--361. IEEE Computer Society Press, 1993.
• 43: Andrew Chi-Chih Yao, On the power of quantum fingerprinting, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780554]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Theory

Keywords:
bell inequality, classical simulation, communication complexity, fourier sampling problem, quantum entanglement, tensor norms