An introduction to quantum computing for non-physicists

ABSTRACT

Richard Feynman's observation that certain quantum mechanical effects cannot be simulated efficiently on a computer led to speculation that computation in general could be done more efficiently if it used these quantum effects. This speculation proved justified when Peter Shor described a polynomial time quantum algorithm for factoring intergers.In quantum systems, the computational space increases exponentially with the size of the system, which enables exponential parallelism. This parallelism could lead to exponentially faster quantum algorithms than possible classically. The catch is that accessing the results, which requires measurement, proves tricky and requires new nontraditional programming techniques.The aim of this paper is to guide computer scientists through the barriers that separate quantum computing from conventional computing. We introduce basic principles of quantum mechanics to explain where the power of quantum computers comes from and why it is difficult to harness. We describe quantum cryptography, teleportation, and dense coding. Various approaches to exploiting the power of quantum parallelism are explained. We conclude with a discussion of quantum error correction.

REFERENCES

• 1: ABRAMS, D. S. AND LLOYD, S. 1998. Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #p problems. Los Alamos Physics Preprint Archive, http://xxx.lanl. gov/abs/quant-ph/9801041.
• 2: BARENCO, A., BENNETT, C. H., CLEVE, R., DIVINCENZO, D. P., MARGOLUS, N. H., SHOR, P. W., SLEATOR, T. , SMOLIN, J. A., AND WEINFURTER, H. 1995. Elementary gates for quantum computation. Physical Review A 52, 5, 3457-3467. Preprint at Los Alamos Physics Preprint Archive, http:// xxx.lanl.gov/abs/quant-ph/9503016 and at http://vesta.physics.ucla.edu/cgi-bin/ uncompress ps cgi?torgats1.ps.
• 3: BENNETT, C. H. 1992. Quantum cryptography using any two nonorthogonal states. Physical Review Letters 68, 3121-3124.
• 4: Charles H. Bennett , Ethan Bernstein , Gilles Brassard , Umesh Vazirani, Strengths and Weaknesses of Quantum Computing, SIAM Journal on Computing, v.26 n.5, p.1510-1523, Oct. 1997 [doi>10.1137/S0097539796300933]
• 5: Charles H. Bennett , Gilles Brassard, Quantum public key distribution reinvented, ACM SIGACT News, v.18 n.4, p.51-53, Summer 1987 [doi>10.1145/36068.36070]
• 6: BENNETT, C. H., BRASSARD, G., AND EKERT, A. K. 1992. Quantum cryptography. Scientific American 267, 4 (Oct.), 50.
• 7: Ethan Bernstein , Umesh Vazirani, Quantum complexity theory, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.11-20, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167097]
• 8: André Berthiaume, Quantum computation, Complexity theory retrospective II, Springer-Verlag New York, Inc., New York, NY, 1998
• 9: BIRON, D., BIHAM, O., BIHAM, E., GRASSEL, M., AND LI- DAR, D. A. 1998. Generalized grover search algorithm for arbitrary initial amplitude distribution. Los Alamos Physics Preprint Archive, http://xxx.lanl.gov/abs/quant-ph/9801066.
• 10: BOSCHI, D., BRANCA, S., MARTINI, F. D., HARDY, L., AND POPESCU, S. 1998. Experimental realization of teleporting an unknown pure quantum state via dual classical and einstein-podolski-rosen channels. Physical Review Letters 80, 1121-1125.
• 11: BOUWMEESTER, D., PAN, J.-W., MATTLE, K., EIBL, M., WEINFURTER, H., AND ZEILINGER, A. 1997. Experimental quantum teleportation. Nature 390, 575.
• 12: BOYER, M., BRASSARD, G., H~YER, P., AND TAPP, A. 1996. Tight bounds on quantum search. In Proceedings of the Workshop on Physics of Computation: PhysComp '96 (Los Alamitos, CA, 1996), 36-43. Institute of Electrical and Electronic Engineers Computer Society Press. Preprint at Los Alamos Physics Preprint Archive, http://xxx.lanl. gov/abs/quant-ph/9605034.
• 13: BRASSARD, G., H&OslashYER, P., AND TAPP, A. 1998. Quantum counting. Preprint at Los Alamos Physics Preprint Archive, http://xxx.lanl. gov/abs/quant-ph/9805082.
• 14: CERF, N. J., GROVER, L. K., AND WILLIAMS, C. P. 1998. Nested quantum search and np-complete problems. Preprint at Los Alamos Physics Preprint Archive, http://xxx.lanl.gov/abs/ quant-ph/9806078.
• 15: CIRAC, J. I. AND ZOLLER, P. 1995. Quantum computations with cold trapped ions. Physical Review Letters 74, 4091-4094.
• 16: CORY, D. G., MASS, W., PRICE, M., KNILL, E., LAFLAMME, R., ZUREK, W. H., HAVEL, T. F., AND SOMAROO, S. S. 1998. Experimental quantum error correction. Preprint at Los Alamos Physics Preprint Archive, http://xxx.lanl.gov/abs/ quant-ph/9802018.
• 17: DEUTSCH, D. 1985. Quantum theory, the Church- Turing principle and the universal quantum computer. Proceedings of the Royal Society of London Series A A400, 97-117.
• 18: DEUTSCH, D. AND JOZSA, R. 1992. Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London Series A A439, 553-558.
• 19: DIRAC, P. 1958. The Principles of Quantum Mechanics (4th ed.). Oxford University Press.
• 20: EKERT, A. K., RARITY, J., TAPSTER, P., AND PALMA, G. 1992. Practical quantum cryptography based on two-photon interferometry. Physical Review Letters 69, 1293-1295.
• 21: FEYNMAN, R. 1982. Simulating physics with computers. International Journal of Theoretical Physics 21, 6&7, 467-488.
• 22: FEYNMAN, R. 1985. Quantum mechanical computers. Optics News 11, 11-20. Also in Foundations of Physics, 16(6), 507-531, 1986.
• 23: Richard Phillips Feynman , Anthony J. Hey , Robin W. Allen, Feynman Lectures on Computation, Perseus Books, Cambridge, MA, 2000
• 24: FEYNMAN, R. P., LEIGHTON, R. B., AND SANDS, M. 1965. Lectures on Physics, Vol. III. Addison- Wesley.
• 25: GERSHENFELD, N. A. AND CHUANG, I. L. 1997. Bulk spin resonance quantum computing. Science 275, 350-356.
• 26: GREENSTEIN, G. AND ZAJONC, A. G. 1997. The Quantum Challenge. Jones and Bartlett Publishers, Sudbury, Mass.
• 27: Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.212-219, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237866]
• 28: Lov K. Grover, A framework for fast quantum mechanical algorithms, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.53-62, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276712]
• 29: HARDY, G. H. AND WRIGHT, E. M. 1979. An Introduction to the Theory of Numbers. Oxford University Press.
• 30: HOGG, T. 1996. Quantum computing and phase transitions in combinatorial search. Journal of Artificial Intelligence Research 4, 91- 128. Preprint at Los Alamos Physics Preprint Archive, http://xxx.lanl.gov/abs/quant-ph/ 9508012.
• 31: HOGG, T. 1998. Highly structured searches with quantum computers. Physical Review Letters 80, 2473-2473.
• 32: HUGHES, R. J., BUTTLER, W. T., KWIAT, P. G., LAMOREAUX, S. K., MORGAN, G. L., NORDHOLT, J. E., AND PETERSON, C. G. 1999. Practical Quantum Cryptography for Secure Free-Space Communications. Preprint at Los Alamos Physics Preprint Archive, http://xxx.lanl.gov/abs/ quant-ph/9905009.
• 33: HUGHES, R. J., BUTTLER, W. T., KWIAT, P. G., LUTHER, G. G., MORGAN, G. L., NORDHOLT, J. E., PETERSON, C. G., AND SIMMONS, C. M. 1997. Secure communications using quantum cryptography. In S. P. HOTALING AND A. R. PIRICH EDS., Photonic Quantum Computing, Vol. 3076, 2-11.
• 34: HUNGERFORD, T. A. 1974. Algebra. Springer Verlag, New York, Heidelberg, Berlin.
• 35: JONES, J. A. AND MOSCA, M. 1998. Implementation of a quantum algorithm on a nuclear magnetic resonance quantum computer. Journal of Chemical Physics 109, 5, 1648-1653. Preprint at Los Alamos Physics Preprint Archive, http://xxx.lanl.gov/abs/quant-ph/9801027.
• 36: LAFLAMME, R., KNILL, E., ZUREK, W., CATASTI, P., AND MARIAPPAN, S. 1997. NMR GHZ. Los Alamos Physics Preprint Archive, http://xxx.lanl. gov/abs/quant-ph/9709025.
• 37: LENSTRA, A. AND LENSTRA, H. EDS. 1993. The Development of the Number Field Sieve, Vol. 1554 of Lecture Notes in Mathematics. Springer Verlag.
• 38: LIBOFF, R. L. 1997. Introductory Quantum Mechanics (3rd ed.). Addison-Wesley, Reading, Mass.
• 39: LO, H.-K. AND CHAU, H. F. 1999. Unconditional security of quantum key distribution over arbitrarily long distances. Science 283, 2050-2056.
• 40: MAYERS, D. 1998. Unconditional Security in Quantum Cryptography. Preprint at Los Alamos Physics Preprint Archive, http://xxx.lanl. gov/abs/quant-ph/9802025.
• 41: NIELSEN, M. A., KNILL, E., AND LAFLAMME, R. 1998. Complete Quantum Teleportation using Nuclear Magnetic Resonance. Preprint at Los Alamos Physics Preprint Archive, http://xxx.lanl. gov/abs/quant-ph/9811020.
• 42: SCHULMAN, L. J. AND VAZIRANI, U. 1998. Scalable NMR Quantum Computation. Los Alamos Physics Preprint Archive, http://xxx.lanl. gov/abs/quant-ph/9804060.
• 43: SHOR, P. W. 1994. Algorithms for quantum computation: Discrete log and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (Nov.), 124-134. Institute of Electrical and Electronic Engineers Computer Society Press. ftp://netlib.att.com/netlib/ att/math/shor/quantum.algorithms.ps.Z.
• 44: 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]
• 45: 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]
• 46: STEANE, A. 1996. The Ion Trap Quantum Information Processor. Los Alamos Physics Preprint Archive, http://xxx.lanl.gov/abs/quant-ph/ 9608011.
• 47: STEANE, A. 1998. Quantum computing. Reports on Progress in Physics 61, 2, 117-173. Preprint at Los Alamos Physics Preprint Archive, http:// xxx.lanl.gov/abs/quant-ph/9708022.
• 48: TERHAL, B. M. AND SMOLIN, J. A. 1997. Single Quantum Querying of a Database. Los Alamos Physics Preprint Archive, http://xxx.lanl.gov/abs/ quant-ph/9705041.
• 49: VANDERSYPEN, L. M. K., YANNONI, C. Y., SHERWOOD, M. H., AND CHUANG, I. L. 1999. Realization of Effective Pure States for Bulk Quantum Computation. Preprint at Los Alamos Physics Preprint Archive, http://xxx.lanl.gov/abs/ quant-ph/9905041.
• 50: VEDRAL, V., BARENCO, A., AND EKERT, A. K. 1996. Quantum Networks for Elementary Arithmetic Operations. Physical Review A. Preprint at Los Alamos Physics Preprint Archive, http://xxx. lanl.gov/abs/quant-ph/9511018.
• 51: J. Watrous, Relationships Between Quantum and Classical Space-Bounded Complexity Classes, Proceedings of the Thirteenth Annual IEEE Conference on Computational Complexity, p.210, June 15-18, 1998
• 52: Colin P. Williams , Scott H. Clearwater, Explorations in quantum computing, TELOS, Santa Clara, CA, 1997
• 53: WOOTTERS, W. K. AND ZUREK, W. H. 1982. A single quantum cannot be cloned. Nature 299, 802.
• 54: ZALKA, C. 1997. Grover's Quantum Searching Algorithm is Optimal. Los Alamos Physics Preprint Archive, http://xxx.lanl.gov/abs/ quant-ph/9711070.

INDEX TERMS

Primary Classification:
  A. General Literature
  A.1 INTRODUCTORY AND SURVEY

Additional Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Physics

General Terms:
Algorithms, Security, Theory

Keywords:
complexity, parallelism, quantum computing