- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Reviews of Modern Physics

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Nonlocality and communication complexity

Harry Buhrman, Richard Cleve, Serge Massar, and Ronald de Wolf

Harry Buhrman

  • Centrum Wiskunde & Informatica, Science Park 123, 1098 XG Amsterdam, The Netherlands

Richard Cleve

  • Institute for Quantum Computing and School of Computer Science, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, Canada N2L 3G1 and Perimeter Institute for Theoretical Physics, 31 Caroline Street North, Waterloo, Ontario, Canada N2L 2Y5

Serge Massar

  • Laboratoire d’Information Quantique, CP 225, Université Libre de Bruxelles, Boulevard du Triomphe, B-1050 Bruxelles, Belgium

Ronald de Wolf

  • Centrum Wiskunde & Informatica, Science Park 123, 1098 XG Amsterdam, The Netherlands

PDF

Rev. Mod. Phys. 82, 665 – Published 11 March, 2010

DOI: https://doi.org/10.1103/RevModPhys.82.665

Abstract

Quantum information processing is the emerging field that defines and realizes computing devices that make use of quantum mechanical principles such as the superposition principle, entanglement, and interference. Until recently the common notion of computing was based on classical mechanics and did not take into account all the possibilities that physically realizable computing devices offer in principle. The field gained momentum after Shor developed an efficient algorithm for factoring numbers, demonstrating the potential computing powers that quantum computing devices can unleash. In this review the information counterpart of computing is studied. It was realized early on by Holevo that quantum bits, the quantum mechanical counterpart of classical bits, cannot be used for efficient transformation of information in the sense that arbitrary k-bit messages cannot be compressed into messages of k−1 qubits. The abstract form of the distributed computing setting is called communication complexity. It studies the amount of information, in terms of bits or in our case qubits, that two spatially separated computing devices need to exchange in order to perform some computational task. Surprisingly, quantum mechanics can be used to obtain dramatic advantages for such tasks. The area of quantum communication complexity is reviewed and it is shown how it connects the foundational physics questions regarding nonlocality with those of communication complexity studied in theoretical computer science. The first examples exhibiting the advantage of the use of qubits in distributed information-processing tasks were based on nonlocality tests. However, by now the field has produced strong and interesting quantum protocols and algorithms of its own that demonstrate that entanglement, although it cannot be used to replace communication, can be used to reduce the communication exponentially. In turn, these new advances yield a new outlook on the foundations of physics and could even yield new proposals for experiments that test the foundations of physics.

View figure in article

Article Text

References (139)

  1. Aaronson, S., and A. Ambainis, 2003, Proceedings of the 44th IEEE FOCS (IEEE, Los Alamitos, CA), pp. 200–209.
  2. Acin, A., N. Brunner, N. Gisin, S. Massar, S. Pironio, and V. Scarani, 2007, Phys. Rev. Lett. 98, 230501.
  3. Acín, A., N. Gisin, and B. Toner, 2006, Phys. Rev. A 73, 062105.
  4. Ambainis, A., 1996, Algorithmica 16, 298.
  5. Aravind, P. K., 2004, Am. J. Phys. 72, 1303.
  6. Aspect, A., J. Dalibard, and G. Roger, 1982, Phys. Rev. Lett. 49, 1804.
  7. Aspect, A., P. Grangier, and G. Roger, 1981, Phys. Rev. Lett. 47, 460.
  8. Aspect, A., P. Grangier, and G. Roger, 1982, Phys. Rev. Lett. 49, 91.
  9. Barrett, J., 2002, Phys. Rev. A 65, 042302.
  10. Barrett, J., L. Hardy, and A. Kent, 2005, Phys. Rev. Lett. 95, 010503.
  11. Barrett, J., N. Linden, S. Massar, S. Pironio, S. Popescu, and D. Roberts, 2005, Phys. Rev. A 71, 022101.
  12. Bar-Yossef, Z., T. S. Jayram, and I. Kerenidis, 2004, Proceedings of the 36th ACM STOC (ACM, New York), pp. 128–137.
  13. Bell, J. S., 1965, Physics (N.Y.) 1, 195.
  14. Bennett, C., G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. Wootters, 1993, Phys. Rev. Lett. 70, 1895.
  15. Bennett, C., and S. Wiesner, 1992, Phys. Rev. Lett. 69, 2881.
  16. Bennett, C. H., H. J. Bernstein, S. Popescu, and B. Schumacher, 1996, Phys. Rev. A 53, 2046.
  17. Bennett, C. H., and G. Brassard, 1984, Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing (IEEE, Los Alamitos, CA), pp. 175–179.
  18. Bennett, C. H., G. Brassard, S. Popescu, B. Schumacher, J. A. Smolin, and W. K. Wootters, 1996, Phys. Rev. Lett. 76, 722.
  19. Bhatia, R., 1997, Matrix Analysis, Graduate Texts in Mathematics Vol. 169 (Springer-Verlag, New York).
  20. Brassard, G., 2003, Found. Phys. 33, 1593.
  21. Brassard, G., A. Broadbent, and A. Tapp, 2005, Found. Phys. 35, 1877.
  22. Brassard, G., H. Buhrman, N. Linden, A. A. Méthot, A. Tapp, and F. Unger, 2006, Phys. Rev. Lett. 96, 250401.
  23. Brassard, G., R. Cleve, and A. Tapp, 1999, Phys. Rev. Lett. 83, 1874.
  24. Brassard, G., P. Høyer, M. Mosca, and A. Tapp, 2002, Quantum Computation and Quantum Information: A Millennium Volume, AMS Contemporary Mathematics Series Vol. 305 (AMS, Providence, RI), pp. 53–74.
  25. Briët, J., H. Buhrman, and B. Toner, 2009, e-print arXiv:0901.2009.
  26. Brukner, Č., M. Żukowski, J.-W. Pan, and A. Zeilinger, 2004, Phys. Rev. Lett. 92, 127901.
  27. Brunner, N., N. Gisin, S. Popescu, and V. Scarani, 2008, Phys. Rev. A 78, 052111.
  28. Brunner, N., N. Gisin, and V. Scarani, 2005, New J. Phys. 7, 88.
  29. Brunner, N., N. Gisin, V. Scarani, and C. Simon, 2007, Phys. Rev. Lett. 98, 220403.
  30. Brunner, N., S. Pironio, A. Acin, N. Gisin, A. Méthot, and V. Scarani, 2008, Phys. Rev. Lett. 100, 210503.
  31. Brunner, N., and P. Skrzypczyk, 2009, Phys. Rev. Lett. 102, 160403.
  32. Buhrman, H., R. Cleve, and W. van Dam, 2001, SIAM J. Comput. 30, 1829.
  33. Buhrman, H., R. Cleve, J. Watrous, and R. de Wolf, 2001, Phys. Rev. Lett. 87, 167902.
  34. Buhrman, H., R. Cleve, and A. Wigderson, 1998, Proceedings of the 30th ACM STOC (ACM, New York), pp. 63–68.
  35. Buhrman, H., P. Høyer, S. Massar, and H. Röhrig, 2006, Phys. Rev. A 73, 012321.
  36. Buhrman, H., P. Høyer, S. Massar, and H. Röhrig, 2003, Phys. Rev. Lett. 91, 047903.
  37. Buhrman, H., W. van Dam, P. Høyer, and A. Tapp, 1999, Phys. Rev. A 60, 2737.
  38. Cabello, A., 2001a, Phys. Rev. Lett. 87, 010403.
  39. Cabello, A., 2001b, Phys. Rev. Lett. 86, 1911.
  40. Cabello, A., 2005, Phys. Rev. Lett. 95, 210401.
  41. Cabello, A., and J.-A. Larsson, 2007, Phys. Rev. Lett. 98, 220402.
  42. Cabello, A., and A. J. López-Tarrida, 2005, Phys. Rev. A 71, 020301(R).
  43. Cerf, N. J., N. Gisin, S. Massar, and S. Popescu, 2005, Phys. Rev. Lett. 94, 220403.
  44. Cirel’son, B. S. T., 1980, Lett. Math. Phys. 4, 93.
  45. Clauser, J. F., M. A. Horne, A. Shimony, and R. A. Holt, 1969, Phys. Rev. Lett. 23, 880.
  46. Cleve, R., and H. Buhrman, 1997, Phys. Rev. A 56, 1201.
  47. Cleve, R., P. Høyer, B. Toner, and J. Watrous, 2004, Proceedings of the 19th IEEE Complexity (IEEE, Los Alamitos, CA), pp. 236–249.
  48. Cleve, R., W. van Dam, M. Nielsen, and A. Tapp, 1998, Proceedings of the First NASA QCQC Conference, Lecture Notes in Computer Science Vol. 1509 (Springer, Berlin), pp. 61–74.
  49. Collins, D., and N. Gisin, 2004, J. Phys. A 37, 1775.
  50. Collins, D., N. Gisin, N. Linden, S. Massar, and S. Popescu, 2002, Phys. Rev. Lett. 88, 040404.
  51. de Beaudrap, J. N., 2004, Phys. Rev. A 69, 022307.
  52. Degorre, J., S. Laplante, and J. Roland, 2005, Phys. Rev. A 72, 062314.
  53. Degorre, J., S. Laplante, and J. Roland, 2007, Phys. Rev. A 75, 012309.
  54. Deutsch, D., and R. Jozsa, 1992, Proc. R. Soc. London, Ser. A 439, 553.
  55. Du, J., P. Zou, X. Peng, D. K. Oi, L. C. Kwek, and A. Ekert, 2006, Phys. Rev. A 74, 042319.
  56. Ehlich, H., and K. Zeller, 1964, Math. Z. 86, 41.
  57. Einstein, A., B. Podolsky, and N. Rosen, 1935, Phys. Rev. 47, 777.
  58. Forster, M., S. Winkler, and S. Wolf, 2009, Phys. Rev. Lett. 102, 120401.
  59. Frankl, P., and V. Rödl, 1987, Trans. Am. Math. Soc. 300, 259.
  60. Freedman, S. J., and J. F. Clauser, 1972, Phys. Rev. Lett. 28, 938.
  61. Galvão, E. F., 2001, Phys. Rev. A 65, 012318.
  62. Gavinsky, D., 2008a, Proceedings of the 40th ACM STOC (ACM, New York), pp. 95–102.
  63. Gavinsky, D., 2008b, e-print arXiv:0901.0956.
  64. Gavinsky, D., J. Kempe, and R. de Wolf, 2006, Proceedings of the 21st IEEE Complexity (IEEE, Los Alamitos, CA), pp. 288–298.
  65. Gavinsky, D., J. Kempe, I. Kerenidis, R. Raz, and R. de Wolf, 2008, SIAM J. Comput. 38, 1695.
  66. Gavinsky, D., J. Kempe, O. Regev, and R. de Wolf, 2006, Proceedings of the 38th ACM STOC (ACM, New York), pp. 594–603.
  67. Gavinsky, D., O. Regev, and R. de Wolf, 2008, Chicago J. Theor. Comput. Sci. 2008, 7.
  68. Gisin, N., and B. Gisin, 1999, Phys. Lett. A 260, 323.
  69. Greenberger, D. M., M. Horne, and A. Zeilinger, 1989, in Bell’s Theorem, Quantum Theory, and Conceptions of the Universe, edited by M. Kafatos (Kluwer, Dordrecht), pp. 69–72.
  70. Gross, D., S. T. Flammia, and J. Eisert, 2009, Phys. Rev. Lett. 102, 190501.
  71. Grover, L. K., 1996, Proceedings of the 28th ACM STOC (ACM, New York), pp. 212–219.
  72. Holevo, A. S., 1973, Probl. Peredachi Inf. 9, 3 [Probl. Inf. Transm. 9, 177 (1973)].
  73. Horn, R. T., S. A. Babichev, K.-P. Marzlin, A. I. Lvovsky, and B. C. Sanders, 2005, Phys. Rev. Lett. 95, 150502.
  74. Hromkovič, J., 1997, Communication Complexity and Parallel Computing (Springer-Verlag, New York).
  75. Kalyanasundaram, B., and G. Schnitger, 1992, SIAM J. Discrete Math. 5, 545, earlier version in Structures’87.
  76. Khalfi, L. A., and B. S. Tsirelson, 1985, in Symposium on the Foundations of Modern Physics, edited by P. Lahti and P. Mittelstaedt (World Scientific, Singapore), pp. 441–460.
  77. Klauck, H., R. Špalek, and R. de Wolf, 2007, SIAM J. Comput. 36, 1472, earlier version in FOCS’03.
  78. Knuth, D. E., 2003, Selected Papers on Discrete Mathematics, CSLI Lecture Notes Vol. 106 (Stanford University, Stanford).
  79. Kremer, I., 1995, MS thesis (Hebrew University).
  80. Kushilevitz, E., and N. Nisan, 1997, Communication Complexity (Cambridge University Press, Cambridge).
  81. Linial, N., and A. Shraibman, 2007, Proceedings of the 39th ACM STOC (ACM, New York), pp. 699–708.
  82. Marcikic, I., H. de Riedmatten, W. Tittel, H. Zbinden, M. Legré, and N. Gisin, 2004, Phys. Rev. Lett. 93, 180502.
  83. Masanes, L., A. Acin, and N. Gisin, 2006, Phys. Rev. A 73, 012112.
  84. Massar, S., 2002, Phys. Rev. A 65, 032121.
  85. Massar, S., 2005, Phys. Rev. A 71, 012310.
  86. Massar, S., D. Bacon, N. J. Cerf, and R. Cleve, 2001, Phys. Rev. A 63, 052305.
  87. Massar, S., S. Pironio, J. Roland, and B. Gisin, 2002, Phys. Rev. A 66, 052112.
  88. Matsukevich, D. N., P. Maunz, D. L. Moehring, S. Olmschenk, and C. Monroe, 2008, Phys. Rev. Lett. 100, 150404.
  89. Maudlin, T., 1992, in PSA Proceedings of the 1992 Biennial Meeting of the Philosophy of Science Association, edited by D. Hull, M. Forbes, and K. Okruhlik (Philosophy of Science Association, East Lansing, MI), Vol. 1, pp. 404–417.
  90. Mermin, N. D., 1990a, Phys. Rev. Lett. 65, 3373.
  91. Mermin, N. D., 1990b, Phys. Today 43 (6), 9.
  92. Mermin, N. D., 1993, Rev. Mod. Phys. 65, 803.
  93. Moehring, D. L., M. J. Madsen, B. B. Blinov, and C. Monroe, 2004, Phys. Rev. Lett. 93, 090410.
  94. Navascues, M., S. Pironio, and A. Acin, 2007, Phys. Rev. Lett. 98, 010401.
  95. Nayak, A., 1999, Proceedings of the 40th IEEE FOCS (IEEE, Los Alamitos, CA), pp. 369–376.
  96. Nayak, A., and J. Salzman, 2002, Proceedings of the 34th ACM STOC (ACM, New York), pp. 698–704.
  97. Newman, I., 1991, Inf. Process. Lett. 39, 67.
  98. Newman, I., and M. Szegedy, 1996, Proceedings of the 28th ACM STOC (ACM, New York), pp. 561–570.
  99. Nielsen, M. A., and I. L. Chuang, 2000, Quantum Computation and Quantum Information (Cambridge University Press, Cambridge).
  100. Pan, J.-W., D. Bouwmeester, M. Daniell, H. Weinfurter, and A. Zeilinger, 2000, Nature (London) 403, 515.
  101. Paturi, R., 1992, Proceedings of the 24th ACM STOC (ACM, New York), pp. 468–474.
  102. Pearle, P. M., 1970, Phys. Rev. D 2, 1418.
  103. Perez-Garcia, D., M. Wolf, C. Palazuelos, I. Villanueva, and M. Junge, 2008, Commun. Math. Phys. 279, 455.
  104. Popescu, S., and D. Rohrlich, 1994, Found. Phys. 24, 379.
  105. Rauschenbeutel, A., G. Nogues, S. Osnaghi, P. Bertet, M. Brune, J.-M. Raimond, and S. Haroche, 2000, Science 288, 2024.
  106. Raz, R., 1999, Proceedings of the 31st ACM STOC (ACM, New York), pp. 358–367.
  107. Razborov, A., 1992, Theor. Comput. Sci. 106, 385.
  108. Razborov, A., 2003, Izv. Russ. Acad. Sci., Math. 67, 145.
  109. Regev, O., and B. Toner, 2007, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07) (IEEE, Los Alamitos, CA), pp. 384–394.
  110. Rivlin, T. J., and E. W. Cheney, 1966, SIAM J. Numer. Anal. 3, 311.
  111. Rowe, M. A., D. Kielpinski, V. Meyer, C. Sackett, W. M. Itano, C. Monroe, and D. J. Wineland, 2001, Nature (London) 409, 791.
  112. Sackett, C. A., D. Kielpinski, B. E. King, C. Langer, V. Meyer, C. J. Myatt, M. Rowe, Q. A. Turchette, W. M. Itano, D. J. Wineland, and C. Monroe, 2000, Nature (London) 404, 256.
  113. Scholz, V. B., and R. F. Werner, 2008, e-print arXiv:0812.4305.
  114. Schrödinger, E., 1935, Proc. Cambridge Philos. Soc. 31, 555.
  115. Schrödinger, E., 1936, Proc. Cambridge Philos. Soc. 32, 446.
  116. Schumacher, B., 1995, Phys. Rev. A 51, 2738.
  117. Shannon, C. E., 1948, Bell Syst. Tech. J. 27, 379.
  118. Sherstov, A., 2008, Proceedings of the 40th ACM STOC (ACM, New York), pp. 85–94.
  119. Shor, P. W., 1997, SIAM J. Comput. 26, 1484, earlier version in FOCS’94.
  120. Steiner, M., 2000, Phys. Lett. A 270, 239.
  121. Thew, R. T., A. Acín, H. Zbinden, and N. Gisin, 2004, Phys. Rev. Lett. 93, 010503.
  122. Tittel, W., J. Brendel, H. Zbinden, and N. Gisin, 1998, Phys. Rev. Lett. 81, 3563.
  123. Toner, B. F., and D. Bacon, 2003, Phys. Rev. Lett. 91, 187904.
  124. Trojek, P., C. Schmid, M. Bourennane, C. Brukner, M. Żukowski, and H. Weinfurter, 2005, Phys. Rev. A 75, 050305(R).
  125. Tsirelson, B. S., 1987, J. Sov. Math. 36, 557.
  126. van Dam, W., 2000, Ph.D. thesis (University of Oxford).
  127. van Dam, W., 2005, e-print arXiv:quant-ph/0501159.
  128. van Dam, W., R. D. Gill, and P. D. Grünwald, 2005, IEEE Trans. Inf. Theory 51, 2812.
  129. Vaziri, A., G. Weihs, and A. Zeilinger, 2002, Phys. Rev. Lett. 89, 240401.
  130. Vértesi, T., and K. F. Pál, 2009, Phys. Rev. A 79, 042106.
  131. Wehner, S., M. Christandl, and A. Doherty, 2008, Phys. Rev. A 78, 062112.
  132. Weihs, G., T. Jennewein, C. Simon, H. Weinfurter, and A. Zeilinger, 1998, Phys. Rev. Lett. 81, 5039.
  133. Werner, R. F., 1989, Phys. Rev. A 40, 4277.
  134. Werner, R. F., and M. M. Wolf, 2001, Quantum Inf. Comput. 1 (3), 1.
  135. Yao, A. C.-C., 1979, Proceedings of the 11th ACM STOC (ACM, New York), pp. 209–213.
  136. Yao, A. C.-C., 1993, Proceedings of the 34th IEEE FOCS (IEEE, Los Alamitos, CA), pp. 352–360.
  137. Yao, A. C.-C., 2003, Proceedings of the 35th ACM STOC (ACM, New York), pp. 77–81.
  138. Zhang, J., X.-H. Bao, T.-Y. Chen, T. Yang, A. Cabello, and J.-W. Pan, 2007, Phys. Rev. A 75, 022302.
  139. Zhao, Z., T. Yang, Y.-A. Chen, A.-N. Zhang, M. Żukowski, and J.-W. Pan, 2003, Phys. Rev. Lett. 91, 180401.

Outline

Information

Rev. Mod. Phys. 82, 665– Published 11 March, 2010

    © 2010 American Physical Society

    Sign In to Your Journals Account

    Filter

    Filter

    Article Lookup

    Enter a citation