- 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

Information and computation: Classical and quantum aspects

A. Galindo* and M. A. Martín-Delgado†

A. Galindo* and M. A. Martín-Delgado†

  • Departamento de Física Teórica I, Facultad de Ciencias Físicas, Universidad Complutense, 28040 Madrid, Spain

  • *Electronic address: agt@fis.ucm.es
  • †Electronic address: mardel@miranda.fis.ucm.es
PDF

Rev. Mod. Phys. 74, 347 – Published 8 May, 2002

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

Abstract

Quantum theory has found a new field of application in the realm of information and computation during recent years. This paper reviews how quantum physics allows information coding in classically unexpected and subtle nonlocal ways, as well as information processing with an efficiency largely surpassing that of the present and foreseeable classical computers. Some notable aspects of classical and quantum information theory will be addressed here. Quantum teleportation, dense coding, and quantum cryptography are discussed as examples of the impact of quanta on the transmission of information. Quantum logic gates and quantum algorithms are also discussed as instances of the improvement made possible in information processing by a quantum computer. Finally the authors provide some examples of current experimental realizations for quantum computers and future prospects.

View figure in article

References (283)

  1. Adleman, L., C. Pomerance, and R. Rumely, 1983, Ann. Math. 117, 173.
  2. Adleman, L.M., 1994, Science 266, 1021.
  3. Aharonov, D., 1998, in Annual Reviews of Computational Physics, edited by Dietrich Stauffer (World Scientific, Singapore), Vol. VI.
  4. Aspray, W., 1990, John von Neumann and the Origins of Modern Computing (MIT, Cambridge, MA)
  5. Atkins, D., M. Graff, A.K. Lenstra, and P.C. Leyland, 1995, in Advances in Cryptology—Asiacrypt’94: Proceedings of the 4th International Conference on the Theory and Applications of Cryptology, Lecture Notes in Computer Science No. 917(Springer, New York), p. 263.
  6. Averin, D.V., 1998, Solid State Commun. 105, 659.
  7. Barenco, A., 1995, Proc. R. Soc. London, Ser. A 449, 679.
  8. Barenco, A., C.H. Bennett, R. Cleve, D.P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J.A. Smolin, and H. Weinfurter, 1995, Phys. Rev. A 52, 3457.
  9. Barenco, A., A. Berthiaume, D. Deutsch, A. Ekert, R. Jozsa, and Ch. Macchiavello, 1997, SIAM J. Comput. 26, 1541.
  10. Barenco, A., D. Deutsch, A. Ekert, and R. Jozsa, 1995, Phys. Rev. Lett. 74, 4083.
  11. Bell, J.S., 1964, Physics (Long Island City, N.Y.) 1, 195.
  12. Bell, J.S., 1966, Rev. Mod. Phys. 38, 447.
  13. Bell, J.S., 1987, Speakable and Unspeakable in Quantum Mechanics (Cambridge University Press, Cambridge).
  14. Benioff, P.A., 1980, J. Stat. Phys. 22, 563.
  15. Benioff, P.A., 1981, J. Math. Phys. 22, 495.
  16. Benioff, P.A., 1982, Phys. Rev. Lett. 48, 1581.
  17. Bennett, C.H., 1973, IBM J. Res. Dev. 17, 525.
  18. Bennett, C.H., 1992a, Phys. Rev. Lett. 68, 3121.
  19. Bennett, C.H., 1992b, Science 257, 752.
  20. Bennett, C.H., 1995, Phys. Today 48 (10), 24.
  21. Bennett, C.H., 1998, Phys. Scr. T76, 210.
  22. Bennett, C.H., E. Berstein, G. Brassard, and U. Vazirani, 1997, SIAM J. Comput. 26, 1510.
  23. Bennett, C.H., F. Bessette, G. Brassard, L. Savail, and J. Smolin, 1992, J. Cryptology 5, 3.
  24. Bennett, C.H., and G. Brassard, 1984, in Proceedings of the International Conference on Computers, Systems & Signal Processing, Bangalore, India (Indian Institute of Science, Bangalore, India), p. 175.
  25. Bennett, C.H., G. Brassard, C. Crepeau, R. Jozsa, A. Peres, and W.K. Wootters, 1993, Phys. Rev. Lett. 70, 1895.
  26. Bennett, C.H., G. Brassard, and A. Ekert, 1992, Sci. Am. (Int. Ed.) (10), 50.
  27. Bennett, C.H., G. Brassard, and N.M. Mermin, 1992, Phys. Rev. Lett. 68, 557.
  28. Bennett, C.H., G. Brassard, S. Popescu, and B. Schumacher, 1996, Phys. Rev. Lett. 76, 722.
  29. Bennett, C.H., D.P. DiVincenzo, and J. Smolin, 1997, Phys. Rev. Lett. 78, 3217.
  30. Bennett, C.H., D.P. DiVincenzo, J. Smolin, and W.K. Wootters, 1996, Phys. Rev. A 54, 3824.
  31. Bennett, C.H., and P.W. Shor, 1998, IEEE Trans. Inf. Theory 44, 2724.
  32. Bennett, C.H., P.W. Shor, J.A. Smolin, and A.V. Thapliyal, 1999, Phys. Rev. Lett. 83, 3081.
  33. Bennett, C.H., and S.J. Wiesner, 1992, Phys. Rev. Lett. 69, 2881.
  34. Bergquist, J.C., R.G. Hulet, W.M. Itano, and D.J. Wineland, 1986, Phys. Rev. Lett. 57, 1699.
  35. Berman, G.P., D.K. Campbell, G.D. Doolen, G.V. López, and V.I. Tsifrinovich, 1997, Physica B 240, 61.
  36. Berman, G.P., D.K. Campbell, G.D. Doolen, and K.E. Nagaev, 2000, J. Phys. Condens. Mater. 12, 2945.
  37. Bernstein, E., and U. Vazirani, 1993, Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (Association for Computing Machinery, New York), p. 11.
  38. Berthiaume, A., and G. Brassard, 1992, Proceedings of the 7th IEEE Conference on Structure in Complexity Theory, Boston, MA (IEEE Computer Society, Los Alamitos, CA), p. 132.
  39. Berthiaume, A., D. Deutsch, and R. Jozsa, 1994, Third Workshop on Physics of Computation (IEEE Computer Society, Los Alamitos, CA), p. 60.
  40. Blake, I., C. Heegard, T. Høholdt, and V. Wei, 1998, IEEE Trans. Inf. Theory 44, 2596.
  41. Bohm, D., 1951, Quantum Theory (Prentice-Hall, Englewood Cliffs, NJ).
  42. Boneh, D., and R.J. Lipton, 1995, in Advances in Cryptology—CRYPTO’95, Proceedings of the 15th Annual International Cryptology Conference, edited by D. Coppersmith (Springer, Berlin), p. 424.
  43. Boschi, D., S. Branca, F. De Martini, L. Hardy, and S. Popescu, 1998, Phys. Rev. Lett. 80, 1121.
  44. Bouwmeester, D., A. Ekert, and A. Zeilinger, 2000, Eds., The Physics of Quantum Information (Springer, Berlin).
  45. Bouwmeester, D., J.-W. Pan, M. Daniell, H. Weinfurter, and A. Zeilinger, 1999, Phys. Rev. Lett. 82, 1345.
  46. Bouwmeester, D., J.-W. Pan, M. Daniell, H. Weinfurter, M. Zukowski, and A. Zeilinger, 1998, Nature (London) 394, 841.
  47. Bouwmeester, D., J.-W. Pan, K. Mattle, M. Eibl, H. Weinfurter, and A. Zeilinger, 1997, Nature (London) 390, 575.
  48. Bouwmeester, D., J.-W. Pan, H. Weinfurter, and A. Zeilinger, 2000, J. Mod. Opt. 47, 279.
  49. Boyer, M., G. Brassard, P. Hoyer, and A. Tapp, 1998, Fortschr. Phys. 46, 493.
  50. Brady, A.H., 1983, Math. Comput. 40, 647.
  51. Brassard, G., 1989, SIGACT News 20 (4), 78.
  52. Brassard, G., and P. Bratley, 1996, Fundamentals of Algorithmics (Prentice-Hall, Englewood Cliffs, NJ).
  53. Brassard, G., C. Crépeau, D. Mayers, and L. Salvail, 1997, e-print quant-ph/9712023.
  54. Brassard, G., P. Hoyer, and A. Tapp, 1998, in Proceedings of the 25th International Colloquium on Automata, Language, and Programming: ICALP, Lecture Notes in Computer Science No. 80(Springer, Berlin), Vol. 1443, p. 820.
  55. Braunstein, S.L., C.M. Caves, R. Jozsa, N. Linden, S. Popescu, and R. Schack, 1999, Phys. Rev. Lett. 83, 1054.
  56. Braunstein, S.L., C.A. Fuchs, and H.J. Kimble, 2000, J. Mod. Opt. 47, 267.
  57. Braunstein, S.L., and H.J. Kimble, 1998, Nature (London) 394, 840.
  58. Brylinski, J.-L., and R. Brylinski, 2002, Mathematics of Quantum Computation (CRC Press, Boca Raton, FL, in press).
  59. Burkard, G., H.-A. Engel, and D. Loss, 2000, Fortschr. Phys. 48, 9–11, 965. This is a special issue on “Experimental Proposals for Quantum Computation” edited by S.L. Braunshein and H.K. Lo.
  60. Buzek, V., and M. Hillery, 1996, Phys. Rev. A 54, 1844.
  61. Calderbank, A.R., and P.W. Shor, 1996, Phys. Rev. A 54, 1098.
  62. Chuang, I.L., 2000, Phys. Rev. Lett. 85, 2006.
  63. Chuang, I.L., N. Gershenfeld, and M. Kubinec, 1998, Phys. Rev. Lett. 80, 3408.
  64. Chuang, I.L., N. Gershenfeld, M. Kubinec, and D. Leung, 1998, Proc. R. Soc. London, Ser. A 454, 447.
  65. Church, A., 1936, Am. J. Math. 58, 345.
  66. Cirac, J.I., and P. Zoller, 1995, Phys. Rev. Lett. 74, 4091.
  67. Cirac, J.I., and P. Zoller, 2000, Nature (London) 404, 579.
  68. Cleve, R., 2000, in Collected Papers on Quantum Computation and Quantum Information Theory, edited by C. Macchiavello, G. M. Palma, and A. Zeilinger (World Scientific, Singapore), pp. 103–127.
  69. Cleve, R., A. Ekert, C. Macchiavello, and M. Mosca, 1998, Proc. R. Soc. London, Ser. A 454, 339.
  70. Cohen, H., 1993, A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics No. 138 (Springer-Verlag, Berlin).
  71. Cohen, H., and H.W. Lenstra, 1984, Math. Comput. 42, 297.
  72. Collins, D., K.W. Kim, W.C. Holton, H. Sierzputowska-Gracz, and E.O. Stejskal, 1999, e-print quant-ph/9910006.
  73. Collins, G.P., 1992, Phys. Today 45 (11), 21.
  74. Conway, J.H., and N.J.A. Sloane, 1999, Sphere Packings, Lattices and Groups, 3rd ed., Grundlehren der Mathematischen Wissenschaften No. 290 (Springer-Verlag, New York).
  75. Coppersmith, D., 1994, IBM Res. Rep. RC 19642.
  76. Cory, D.G., A.F. Fahmy, and T.F. Havel, 1996, in PhysComp96: Proceedings of the 4th Workshop on Physics and Computation, Boston, MA, 1996, edited by T. Toffoli, M. Biafore, and J. Leao (New England Complex Systems Institute, Cambridge, MA), p. 87.
  77. Cory, D.G., D.G. Fhamy, and T.F. Havel, 1997, Proc. Natl. Acad. Sci. U.S.A. 94, 1634.
  78. Cory, D.G., R. Laflamme, E. Knill, L. Viola, T.F. Havel, N. Boulant, G. Boutis, E. Fortunato, S. Lloyd, R. Martinez, C. Negrevergne, M. Pravia, Y. Sharf, G. Teklemariam, Y.S. Weinstein, and W.H. Zurek, 2000, Fortschr. Phys. 48, 875.
  79. Deutsch, D., 1985, Proc. R. Soc. London, Ser. A 400, 97.
  80. Deutsch, D., 1989, Proc. R. Soc. London, Ser. A 425, 73.
  81. Deutsch, D., 1993, talk given at the Rank Prize Funds Symposium on Quantum Communication and Cryptography, Broadway, UK.
  82. Deutsch, D., and R. Jozsa, 1992, Proc. R. Soc. London, Ser. A 439, 553.
  83. Diffie, W., 1992, in Contemporary Cryptology: The Science of Information Integrity, edited by G. Simmons (IEEE, Piscataway, NJ), p. 135.
  84. Diffie, W., and M.E. Hellman, 1976, IEEE Trans. Inf. Theory 22, 644.
  85. DiVincenzo, D., 1995, Phys. Rev. A 51, 1015.
  86. Dür, W., H.-J. Briegel, J.I. Cirac, and P. Zoller, 1999, Phys. Rev. A 59, 169.
  87. Dür, W., J.I. Cirac, and R. Tarrach, 1999, Phys. Rev. Lett. 83, 3562.
  88. Durr, Ch., and P. Hoyer, 1996, e-print quant-ph/9607014.
  89. Einstein, A., B. Podolsky, and N. Rosen, 1935, Phys. Rev. 47, 777.
  90. Eisert, J., M. Wilkens, and M. Lewenstein, 1999, Phys. Rev. Lett. 83, 3077.
  91. Ekert, A., 1991, Phys. Rev. Lett. 67, 661.
  92. Ekert, A., P. Hayden, and H. Inamori, 2000, e-print quant-ph/0011013.
  93. Ekert, A., and R. Jozsa, 1996, Rev. Mod. Phys. 68, 733.
  94. Ekert, A., and P. Knight, 1995, Am. J. Phys. 63, 415.
  95. Ekert, A., and C. Macchiavello, 1996, Phys. Rev. Lett. 77, 2585.
  96. Electronic Frontier Foundation, 1998, Cracking DES. Secrets of Encryption Research, Wiretap Politics & Chip Design. How federal agencies subvert privacy, foreword by W. Diffie (EFF, San Francisco, CA).
  97. Ellis, J.H., 1970, CESG (Communications-Electronics Security Group) Report, January.
  98. Ernst, R.R., G. Bodenhausen, and A. Wokaum, 1987, Principles of Nuclear Magnetic Resonance in One and Two Dimensions (Oxford University Press, New York).
  99. Fang, X., X. Zhu, M. Feng, X. Mao, and F. Du, 2000, Phys. Rev. A 61, 022307.
  100. Farhi, E., J. Goldstone, S. Gutmann, and M. Sipser, 1998, Phys. Rev. Lett. 81, 5442.
  101. Feynman, R.P., 1982, Int. J. Theor. Phys. 21, 467.
  102. Feynman, R.P., 1985, Optics News 11, 11.
  103. Feynman, R.P., 1996, in Feynman Lectures on Computation, edited by A. Hey and R. Allen (Addison-Wesley, Reading, MA).
  104. Flynn, M.J., 1966, Proc. IEEE 54, 1901.
  105. Flynn, M.J., 1972, IEEE Trans. Comput. 21, 948.
  106. Fredkin, E., and T. Toffoli, 1982, Int. J. Theor. Phys. 21, 219.
  107. Freeman, R., 1998, Spin Choreography (Oxford University Press, New York).
  108. Fulde, P., 1995, Electron Correlations in Molecules and Solids, Springer Series in Solid-State Sciences No. 100 (Springer-Verlag, Berlin).
  109. Furuzawa, A., J.L. Sørensen, S.L. Braunstein, C.A. Fuchs, H.J. Kimble, and E.S. Polzik, 1998, Science 282, 706.
  110. Galindo, A., and M.A. Martin-Delgado, 2000, Phys. Rev. A 62, 062303.
  111. Galindo, A., and P. Pascual, 1989, Problemas de Mecánica Cuántica (EUDEMA, Madrid).
  112. Galindo, A., and P. Pascual, 1990a, Quantum Mechanics I (Springer-Verlag, Berlin).
  113. Galindo, A., and P. Pascual, 1990b, Quantum Mechanics II (Springer-Verlag, Berlin).
  114. Gardner, M., 1977, Sci. Am. 237 (8), 120.
  115. Gauss, K. F., 1801, Disquisitiones Arithmeticae (G. Fleischer, Leipzig), English translation by A.A. Clark (Yale University, New Haven, 1966), revised English translation by W.C. Waterhouse (Springer-Verlag, New York, 1975).
  116. Gerber, J., 1983, Math. Comput. 41, 287.
  117. Gershenfeld, N.A., and I.L. Chuang, 1997, Science 275, 350.
  118. Gershenfeld, N.A., I.L. Chuang, and S. Lloyd, 1996, in PhysComp96: Proceedings of the Fourth Workshop on Physics and Computation, edited by T. Toffoli, M. Biafore, and J. Leão (New England Complex Systems Institute, Cambridge, MA), p. 136.
  119. Giedke, G., B. Kraus, M. Lewenstein, and J.I. Cirac, 2001, e-print quant-ph/0104050.
  120. Gisin, N., 1996, Phys. Lett. A 210, 151.
  121. Gisin, N., G. Ribordy, W. Tittel, and H. Zbinden, 2001, Rev. Mod. Phys. 74, 145.
  122. Goan, H.-S., and G.J. Milburn, 2000, unpblished.
  123. 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).
  124. Grover, L.K., 1996, Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, Philadelphia, PA (Association for Computing Machinery, New York), p. 212.
  125. Grover, L.K., 1997, Phys. Rev. Lett. 79, 325.
  126. Händler, W., 1982, in Parallel Processing Systems—An Advanced Course, edited by David J. Evans (Cambridge University Press, Cambridge, England), p. 1.
  127. Hellman, M.E., 1979, Sci. Am. 241 (8), 146.
  128. Herken, R., 1995, Ed., The Universal Turing Machine: A Half-Century Survey (Springer-Verlag, Vienna).
  129. Herring, C., and M. Flicker, 1964, Phys. Rev. 134, 362.
  130. Hillis, W.D., 1998, in Feynman and Computation, edited by Anthony J.G. Hey (Addison-Wesley, Reading, MA), p. 257.
  131. Hodges, A., 1992, Alan Turing: The Enigma (Vintage Random House, London).
  132. Hogg, T., 1998, Physica D 120, 102.
  133. Holevo, A.S., 1973, Probl. Peredachi Inf. 9, 3 [Probl. Inf. Transm. 9, 177].
  134. Horodecki, R., P. Horodecki, and M. Horodecki, 1996a, Phys. Lett. A 210, 377.
  135. Horodecki, R., P. Horodecki, and M. Horodecki, 1996b, Phys. Lett. A 223, 1.
  136. Horodecki, R., P. Horodecki, and M. Horodecki, 1998, Phys. Rev. Lett. 80, 5239.
  137. Horodecki, R., P. Horodecki, and M. Horodecki, 1999, Phys. Rev. Lett. 82, 1056.
  138. Hughes, R.J., 1998, Philos. Trans. R. Soc. London 356, 1713.
  139. Hughes, R.J., D.M. Alde, P. Dyer, G.G. Luther, G.L. Morgan, and M. Schauer, 1995, Contemp. Phys. 36, 149.
  140. Hughes, R.J., W.T. Buttler, P.G. Kwiat, S.K. Lamoreaux, G.L. Morgan, J.E. Nordholt, and C.G. Peterson, 1999, e-print quant-ph/9905009.
  141. Hughes, R.J., D.F.V. James, J.J. Gomez, M.S. Gulley, M.H. Holzscheiter, P.G. Kwiat, S.K. Lamoreaux, C.G. Peterson, V.D. Sandberg, M.M. Schauer, C.M. Simmons, C.E. Thorburn, D. Tupa, P.Z. Wang, and A.G. White, 1998, Fortschr. Phys. 46, 329.
  142. Hughes, R.J., D.F.V. James, E.H. Knill, R. Laflamme, and A.G. Petschek, 1996, Phys. Rev. Lett. 77, 3240.
  143. Hughes, R.J., G. Luther, G. Morgan, G. Peterson, and C. Simmons, 1996, Lect. Notes Comput. Sci. 1109, 329.
  144. Hughes, R.J., G.L. Morgan, and C.G. Peterson, 2000, J. Mod. Opt. 47, 533.
  145. Hughes, R.J., and J.E. Nordholt, 1999, Phys. World 12 (15), 31.
  146. Hughston, L.P., R. Jozsa, and W.K. Wootters, 1993, Phys. Lett. A 183, 14.
  147. Hwang, K., and F.A. Briggs, 1985, Computer Architecture and Parallel Processing (McGraw-Hill International, New York).
  148. Jennewein, T., C. Simon, G. Weihs, H. Weinfurter, and A. Zeilinger, 2000, Phys. Rev. Lett. 84, 4729.
  149. Jones, J.A., 2001, Prog. Nucl. Magn. Reson. Spectrosc. 38, 325.
  150. Jones, J.A., R.H. Hansen, and M. Mosca, 1998, J. Magn. Reson. 135, 353.
  151. Jones, J.A., and M. Mosca, 1998, J. Chem. Phys. 109, 1648.
  152. Jones, J.A., M. Mosca, and R.H. Hansen, 1998, Nature (London) 392, 344.
  153. Jones, J.A., V. Vedral, A. Ekert, and G. Castagnoli, 2000, Nature (London) 403, 869.
  154. Jozsa, R., 1994, J. Mod. Opt. 41, 2315.
  155. Jozsa, R., 1998, Proc. R. Soc. London Ser. A 454, 323.
  156. Jozsa, R., 1999, e-print quant-ph/9901021.
  157. Jozsa, R., D.S. Abrams, J.P. Dowling, and C.P. Williams, 2000, Phys. Rev. Lett. 85, 2010.
  158. Jozsa, R., and B. Schumacher, 1994, J. Mod. Opt. 41, 2343.
  159. Kahn, D., 1967, The Codebreakers, the Story of Secret Writing (MacMillan, New York).
  160. Kane, B.E., 1998, Nature (London) 393, 133.
  161. Kane, B.E., 2000, Fortschr. Phys. 48, 1023.
  162. Kitaev, A.Yu., 1995, L. D. Landau Institute for Theoretical Physics, Moscow report; e-print quant-ph/9511026.
  163. Kitaev, A.Y., 1997, Russ. Math. Surveys 52, 1191.
  164. Knill, E., 1995, e-print quant-ph/9508006.
  165. Knill, E., I. Chuang, and R. Laflamme, 1998, Phys. Rev. A 57, 3348.
  166. Knill, E., R. Laflamme, R. Martinez, and C.-H. Tseng, 2000, Nature (London) 404, 368.
  167. Knuth, D.E., 1975, The Art of Computer Programming, Vol. 3: Sorting and Searching (Addison-Wesley, Reading, MA).
  168. Knuth, D.E., 1981, The Art of Computer Programming 2: Seminumerical Algorithms, 2nd ed. (Addison-Wesley, Reading, MA).
  169. Koblitz, N., 1994, A Course in Number Theory and Cryptography, 2nd ed. (Springer-Verlag, Berlin).
  170. Kwiat, P., S. Barraza-López, A. Stefanov, and N. Gisin, 2001, Nature (London) 409, 1014.
  171. Kwiat, P., K. Mattle, H. Weinfurter, A. Zeilinger, A.V. Sergienko, and Y. Shih, 1995, Phys. Rev. Lett. 75, 4337.
  172. Landauer, R., 1961, IBM J. Res. Dev. 5, 183.
  173. Landauer, R., 1991, Phys. Today 44 (5), 23.
  174. Landauer, R., 1996, Phys. Lett. A 217, 188.
  175. Landauer, R., 1997, in Proceedings of the Drexel-4 Symposium on Quantum Nonintegrability-Quantum-Classical Correspondence, Philadelphia, PA, 1994, edited by D.H. Feng and B.-L. Hu (International Press, Boston).
  176. Lecerf, Y., 1963, C. R. Acad. Fran. Sci. 257, 2597.
  177. Lenstra, H.W., 1987, Ann. Math. 126, 649.
  178. Lenstra, A., and H.W. Lenstra, 1993, Eds., The Development of the Number Field Sieve, Lecture Notes in Math. No. 1554 (Springer-Verlag, Berlin).
  179. Levitin, L.B., 1969, Proceedings of the 4th All-Union Conf. Information and Coding Theory, Tashkent, 1969, p. 111 (in Russian).
  180. Levitin, A., 1999, in Proceedings of SIGCSE’99, pp. 179–183.
  181. Lewenstein, M., D. Bruss, J.I. Cirac, B. Kraus, M. Kus, J. Samsonowicz, A. Sanpera, and R. Tarrach, 2000, J. Mod. Opt. 47, 2841.
  182. Li, M., and P. Vitányi, 1997, An Introduction to Kolmogorov Complexity and Its Applications, 2nd ed. (Springer-Verlag, New York).
  183. Lin, S., and T. Rado, 1965, J. ACM 12 (2), 196.
  184. Lloyd, S., 1995, Phys. Rev. Lett. 75, 346.
  185. Lo, H-K., and H. F. Chau, 1999, Science 283, 2050.
  186. Loss, D., and D.P. DiVincenzo, 1998, Phys. Rev. A 57, 120.
  187. Macwilliams, F.J., and N.J.A. Sloane, 1977, The Theory of Error-Correcting Codes (North-Holland, Amsterdam).
  188. Makhlin, Y., G. Schön, and A. Shnirman, 2001, Rev. Mod. Phys. 73, 357.
  189. Manin, Yu., 1980, Vychislimoe i Nevychislimoe [Computable and Uncomputable] (Sovetskoye Radio, Moscow).
  190. Marand, Ch., and P.D. Townsend, 1995, Opt. Lett. 20, 1695.
  191. Marxen, H., 1997, Usenet newsgroup comp.theory, October 5.
  192. Marxen, H., and J. Buntrock, 1990, Bull. Eur. Assoc. Theor. Comput. Sci. 40, 247.
  193. Mattle, K., H. Weinfurter, P.G. Kwiat, and A. Zeilinger, 1996, Phys. Rev. Lett. 76, 4656.
  194. Mayers, D., 1996, in PhysComp96: Proceedings of the Fourth Workshop on Physics and Computation, Boston, edited by T. Toffoli, M. Biafore, and J. Leão (New England Complex Systems Institute, Cambridge, MA), p. 226.
  195. Mayers, D., 1997, Phys. Rev. Lett. 78, 3414.
  196. Mayers, D., 1998, e-print quant-ph/9802025.
  197. Meyer, D.A., 1999, Phys. Rev. Lett. 82, 1052.
  198. Miller, G.L., 1976, J. Comput. Syst. Sci. 13, 300.
  199. Minsky, M., 1967, Computation: Finite and Infinite Machines (Prentice-Hall, Englewood Cliffs, NJ).
  200. Molmer, K., and A. Sorensen, 1999, Phys. Rev. Lett. 82, 1835.
  201. Monroe, C., D.M. Meekhof, B.E. King, W.M. Itano, and D.J. Wineland, 1995, Phys. Rev. Lett. 75, 4714.
  202. Moore, G., 1965, unpublished.
  203. Mosca, M., and A. Ekert, 1999, in Quantum Computing and Quantum Communications, edited by C.P. Williams (Springer, Berlin), p. 174.
  204. Muller, A., J. Breguet, and N. Gisin, 1993, Europhys. Lett. 23, 383.
  205. Muller, A., H. Zbinden, and N. Gisin, 1996, Europhys. Lett. 33, 335.
  206. Nagourney, W., J. Sandberg, and H. Dehmelt, 1986, Phys. Rev. Lett. 56, 2797.
  207. Nielsen, M.A., 1999, Phys. Rev. Lett. 83, 436.
  208. Nielsen, M.A., and I.L. Chuang, 2000, Quantum Computation and Quantum Information (Cambridge University Press, Cambridge).
  209. Nielsen, M.A., E. Knill, and R. Laflamme, 1998, Nature (London) 396, 52.
  210. Palma, G.M., K.A. Suominen, and A.K. Ekert, 1996, Proc. R. Soc. London, Ser. A 452, 567.
  211. Pan, J-W., D. Bouwmeester, H. Weinfurter, and A. Zeilinger, 1998, Phys. Rev. Lett. 80, 3891.
  212. Papadimitriou, Ch. H., 1994, Computational Complexity (Addison-Wesley, Reading, MA).
  213. Peres, A., 1996, Phys. Rev. Lett. 77, 1413.
  214. Pippengger, N., and M. Fisher, 1979, J. ACM 26, 361.
  215. Planck, M., 1900, Verh. Dtsch. Phys. Ges. 2, 237.
  216. Pomerance, C., 1982, in Computational Methods in Number Theory, edited by H.W. Lenstra, Jr., and R. Tidjeman (Mathematisch Centrum, Amsterdam), p. 89.
  217. Pomerance, C., 1996, Not. Am. Math. Soc. 43, 1473.
  218. Preskill, J., 1997, Talk, 15 January 1997, www.theory. caltech.edu/∼preskill
  219. Preskill, J., 1998, lecture notes, www.theory.caltech.edu/∼preskill/ph229
  220. Press, W.H., S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery, 1992, Numerical Recipes in C, 2nd ed. (Cambridge University Press, Cambridge).
  221. Price, M-D., S.S. Somaroo, C.-H. Tseng, J.C. Gore, A.F. Fahmy, T.F. Havel, and D.G. Cory, 1999, J. Magn. Reson., Ser. A 140, 371.
  222. Rabi, I.I., 1937, Phys. Rev. 51, 652.
  223. Rabin, M.O., 1980, J. Number Theory 12, 128.
  224. Rado, T., 1962, Bell Syst. Tech. J. 61, 877.
  225. Reck, M., A. Zeilinger, H.J. Bernstein, and P. Bertani, 1994, Phys. Rev. Lett. 73, 58.
  226. Rieffel, E., and W. Polack, 2000, ACM Comput. Surv. 32, 300.
  227. Rivest, R.L., A. Shamir, and L. Adleman, 1978, Commun. ACM 21, 120.
  228. Roman, S., 1992, Coding and Information Theory (Springer-Verlag, New York).
  229. Rozenberg, G., and A. Salomaa, 1994, Cornerstones of Undecidability (Prentice Hall, Englewood Cliffs, NJ).
  230. Rungta, P., W.J. Munro, K. Nemoto, P. Deuar, G.J. Milburn, and C.M. Caves, 2001, in Directions in Quantum Optics: A Collection of Papers Dedicated to the Memory of Dan Walls, edited by H.J. Carmichael, R.J. Glauber, and M.O. Scully (Springer, Berlin), pp. 149–164.
  231. Sachdev, S., 1999, Quantum Phase Transitions (Cambridge University Press, New York).
  232. 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.
  233. Salomaa, A., 1989, Computation and Automata, Encyclopedia of Mathematics and Its Applications No. 25 (Cambridge University Press, Cambridge).
  234. Salomaa, A., 1996, Public-Key Cryptography, 2nd enlarged ed. (Springer-Verlag, Berlin).
  235. Sauter, Th., W. Neuhauser, R. Blatt, and P.E. Toschek, 1986, Phys. Rev. Lett. 57, 1696.
  236. Savage, J., 1972, J. ACM 19, 660.
  237. Schmidt, E., 1906, Math. Ann. 63, 433.
  238. Schnorr, C., 1976, Acta Inf. 7, 95.
  239. Schumacher, B., 1995, Phys. Rev. A 51, 2738.
  240. Shallit, J., 1998, University of Waterloo report.
  241. Shannon, C.E., 1948, Bell Syst. Tech. J. 27, 379; ibid.27, 623 (1948).
  242. Shannon, C.E., 1949, Bell Syst. Tech. J. 28, 656.
  243. Shor, P.W., 1994, Proceedings of the 35th Annual Symposium on the Foundations of Computer Science (IEEE Computer Society Press, Los Alamitos, CA, 1994), p. 124; e-print quant-ph/l9508027.
  244. Shor, P.W., 1995, Phys. Rev. A 52, R2493.
  245. Shor, P., 2000, e-print quant-ph/0005003.
  246. Shor, P.W., and J.A. Sloane, 1998, J. Algebr. Combinatorics 7, 157.
  247. Simon, D.R., 1994, Proceedings of the 35th Annual IEEE Symposium on the Foundations of Computer Science (IEEE Computer Society, Los Alamitos, CA), extended abstract p. 116. Full version, in SIAM J. Comput. 26, 1474(1997).
  248. Slichter, C.P., 1990, Principles of Magnetic Resonance (Springer-Verlag, New York).
  249. Solovay, R., 1995, unpublished.
  250. Steane, A.M., 1996a, Phys. Rev. Lett. 77, 793.
  251. Steane, A.M., 1996b, Proc. R. Soc. London, Ser. A 452, 2551.
  252. Steane, A.M., 1998, Rep. Prog. Phys. 61, 117.
  253. Stichtenoth, H., 1993, Algebraic Function Fields and Codes (Springer Verlag, Heidelberg).
  254. Stinson, D.R., 1995, Cryptography: Theory and Practice (CRC Press, Boca Raton, FL).
  255. Thirring, W., 1983, A Course in Mathematical Physics 4: Quantum Mechanics of Large Systems (Springer-Verlag, New York).
  256. Toffoli, T., 1981, Math. Syst. Theory 14, 13.
  257. Turing, A., 1936, Proc. London Math. Soc. 42, 230; ibid.43, 544(E) (1936).
  258. Turing, A., 1946, unpublished, reprinted in A.M. Turing’s ACE Report of 1946 and Other Papers, edited by B.E. Carpenter and R.W. Doran (MIT, Los Angeles, CA, 1986).
  259. Turing, A.M., 1948, “Intelligent Machinery.” National Physical Laboratory Report, reprinted 1969 in Machine Intelligence 5, edited by B. Meltzer and D. Michie (Edinburgh University Press, Edinburgh).
  260. Turing, A., 1950, Mind 49, 433.
  261. Unruh, W.G., 1995, Phys. Rev. A 51, 992.
  262. Vaidman, L., 1998, Talk at the Conference: Mysteries, Puzzles and Paradoxes in Quantum Mechanics, Gargano, Italy; e-print quant-ph/9810089.
  263. van der Lubbe, J.C.A., 1998, Basic Methods of Cryptography (Cambridge University Press, Cambridge).
  264. Vandersypen, L.M.K., C.S. Yannoni, M.H. Sherwood, and I.L. Chuang, 1999, Phys. Rev. Lett. 83, 3085.
  265. Vedral, V., A. Barenco, and A. Ekert, 1996, Phys. Rev. A 54, 147.
  266. Vedral, V., and M.B. Plenio, 1998, Phys. Rev. A 57, 1619.
  267. Vernam, G.S., 1926, J. Am. Inst. Electr. Eng. 45, 109.
  268. Vidal, G., 1999, Phys. Rev. Lett. 83, 1046.
  269. von Neumann, J., 1945, First Draft of a Report on the EDVAC (June 1945), reprinted with corrections in Ann. Hist. Comput. 15, 25(1993).
  270. von Neumann, J., 1946, The Principles of Large-Scale Computing Machines, reprinted in the Ann. Hist. Comput. 3, 263(1981).
  271. Weinstein, Y.S., S. Lloyd, and D.G. Cory, 1999, e-print quant-ph/9906059.
  272. Welsh, D., 1995, Codes and Cryptography (Oxford University Press, Oxford).
  273. Werner, R. F., 1989, Phys. Rev. A 40, 4277.
  274. Wheeler, J.A., 1990, in Complexity, Entropy and the Physics of Information, edited by W.H. Zurek (Addison-Wesley, Redwood City, CA).
  275. White, S.R., 1992, Phys. Rev. Lett. 69, 2863.
  276. White, S.R., 1993, Phys. Rev. B 48, 10345.
  277. Wiesner, S., 1983, SIGACT News 15 (1), 78.
  278. Wineland, D.J., C. Monroe, W.M. Itano, D. Leibfried, B.E. King, and D.M. Meekhof, 1998, J. Res. Natl. Inst. Stand. Technol. 3, 259.
  279. Wootters, W.K., and W.H. Zurek, 1982, Nature (London) 299, 802.
  280. Yan, S.Y., 2000, Number Theory for Computing (Springer-Verlag, Berlin).
  281. Yao, A., 1993, Proceedings of the 34th IEEE Symposium on the Foundations of Computer Science (IEEE Computer Society, Los Alamitos, CA), p. 352.
  282. Zalka, Ch., 1999, Phys. Rev. A 60, 2746.
  283. Zeilinger, A., 1999, Found. Phys. 29, 631.

Outline

Information

Rev. Mod. Phys. 74, 347– Published 8 May, 2002

    © 2002 American Physical Society

    Sign In to Your Journals Account

    Filter

    Filter

    Article Lookup

    Enter a citation