Quantum Computing for the Classically Minded

(April 24, 2001)

Abstract:

Theoretical studies over the last decade suggest that computers based in the quantum mechanical domain have the potential to dramatically out perform more conventional (i.e., classical) models of computation. For example, Shor developed a quantum algorithm that factors an n-bit integer in polynomial time. (The best known classical algorithm requires O(exp(n^(1/3) (log n)^(2/3))) operations.) This talk will introduce some fundamental concepts of quantum computing, including qubits, quantum circuits, and maybe even the quantum Fourier transform, a component of Shor's algorithm.

References and Links:

Michael A. Nielson and Issac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press (2000), ISBN 0-521-63503-9
Richard P. Feynman, Feynman Lectures on Computation, Perseus Books, ISBN 0738202967.
Artur Ekert and Richard Jozsa, ``Quantum computation and Shor's factoring algorithm,'' Review of Modern Physics, vol. 68, n.3 (1996), pp. 733-753.
Neil Gershenfeld, The Physics of Information Technology, Cambridge University Press, 2000.
Peter W. Shor, ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,'' SIAM Journal of Computation, vol. 26, n.5 (1997), pp. 1484-1509.
Claude Cohen-Tannoudji, et al., Quantum Mechanics, vols 1 & 2, Wiley and Sons, (1992). (Likely the best advanced textbook on quantum theory, albeit an expensive paperback!)
P.J.E. Peebles, Quantum Mechanics, Princeton University Press, 1992. (A clear and concise introduction to the essentials.)
David Bohm, Quantum Theory Dover Books, (1989). (A classic and affordable.)
John von Neumann, Mathematical Foundations of Quantum Mechanics, Princeton University Press, (1986).
Research Centers for Quantum Computing:
- Centre for Quantum Computation, University of Oxford.
- Quantum Information and Information Physics at IBM Research Yorktown.
- Quantum Information at IBM Almaden.
- Quantum Computer Technology, University of Queensland
- Laboratory for Theoretical and Quantum Computing, University ofMontreal.
- Quantum Computing page maintained at Xerox PARC.
- Quantum Information and Comptuation (QUIC): a DARPA project that involves Caltech, MIT, and USC.
- Quantum Computing Initiative at Nasa's Jet Propulsion Laboratory
- Quantum Information at Los Alamos National Laboratory.
More articles and abstracts
- Webopedia.com's entry on Quantum Computing (includes additional links).
- Neil Gershenfeld and Isaac L. Chuang, ``Quantum computing with molecules,'' Scientific American, (1998)
- Corey S. Powell's news article ``Subatomic logic'' Scientific Amierican, (1996)
- Andrew Streane ``Quantum Computing,'' LANL abstract and postscript version of a review article published in Reports on Progress in Physics, 1997.
- Claude Crepeau's collections of papers on quantum computing, and on quantum cryptography .
- Computerworld.com article entitled ``Government hikes spending on quantum computing''

Return to Robert Snapp's Home Page or to the Department of Computer Science Home Page
(Last modified on April 26, 2001.)