Eleanor Rieffel
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.
- 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.Google Scholar
- 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.Google Scholar
- BENNETT, C. H. 1992. Quantum cryptography using any two nonorthogonal states. Physical Review Letters 68, 3121-3124.Google Scholar
- BENNETT, C. H., BERNSTEIN, E., BRASSARD, G., AND VAZIRANI, U. V. 1997. Strengths and weaknesses of quantum computing. Society for Industrial and Applied Mathematics Journal on Computing 26, 5, 1510-1523. Preprint at Los Alamos Physics Preprint Archive, http://xxx.lanl.gov/abs/quant-ph/9701001. Google Scholar
- BENNETT, C. H. AND BRASSARD, G. 1987. Quantum public key distribution reinvented. SIGACT News (ACM Special Interest Group on Automata and Computability Theory) 18, 51-53. Google Scholar
- BENNETT, C. H., BRASSARD, G., AND EKERT, A. K. 1992. Quantum cryptography. Scientific American 267, 4 (Oct.), 50.Google Scholar
- BERNSTEIN, E. AND VAZIRANI, U. V. 1997. Quantum complexity theory. Society for Industrial and Applied Mathematics Journal on Computing 26, 5, 1411-1473. A preliminary version of this paper appeared in the Proceedings of the 25th Association for Computing Machinery Symposium on the Theory of Computing. Google Scholar
- BERTHIAUME. 1997. Quantum computation. In ALAN L. SELMAN, ED., Complexity Theory Retrospective, In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, (July 5, 1988), Vol. 2, 23- 51. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- BOUWMEESTER, D., PAN, J.-W., MATTLE, K., EIBL, M., WEINFURTER, H., AND ZEILINGER, A. 1997. Experimental quantum teleportation. Nature 390, 575.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- CIRAC, J. I. AND ZOLLER, P. 1995. Quantum computations with cold trapped ions. Physical Review Letters 74, 4091-4094.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- DIRAC, P. 1958. The Principles of Quantum Mechanics (4th ed.). Oxford University Press.Google Scholar
- 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.Google Scholar
- FEYNMAN, R. 1982. Simulating physics with computers. International Journal of Theoretical Physics 21, 6&7, 467-488.Google Scholar
- FEYNMAN, R. 1985. Quantum mechanical computers. Optics News 11, 11-20. Also in Foundations of Physics, 16(6), 507-531, 1986.Google Scholar
- FEYNMAN, R. 1996. In Feynman Lectures on Computation. A. J. HEY AND R. W. ALLEN EDS., Addison- Wesley. Google Scholar
- FEYNMAN, R. P., LEIGHTON, R. B., AND SANDS, M. 1965. Lectures on Physics, Vol. III. Addison- Wesley.Google Scholar
- GERSHENFELD, N. A. AND CHUANG, I. L. 1997. Bulk spin resonance quantum computing. Science 275, 350-356.Google Scholar
- GREENSTEIN, G. AND ZAJONC, A. G. 1997. The Quantum Challenge. Jones and Bartlett Publishers, Sudbury, Mass.Google Scholar
- GROVER, L. K. 1996. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (Philadelphia, Pennsylvania, 22-24 May 1996), pp. 212-219. Google Scholar
- GROVER, L. K. 1998. A framework for fast quantum mechanical algorithms. Proceedings of the 30th Annual ACM Symposium on the Theory of Computing, 53-62. Preprint at Los Alamos Physics Preprint Archive, http://xxx. lanl.gov/abs/quant-ph/9711043. Google Scholar
- HARDY, G. H. AND WRIGHT, E. M. 1979. An Introduction to the Theory of Numbers. Oxford University Press.Google Scholar
- 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. Google Scholar
- HOGG, T. 1998. Highly structured searches with quantum computers. Physical Review Letters 80, 2473-2473.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- HUNGERFORD, T. A. 1974. Algebra. Springer Verlag, New York, Heidelberg, Berlin.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- LENSTRA, A. AND LENSTRA, H. EDS. 1993. The Development of the Number Field Sieve, Vol. 1554 of Lecture Notes in Mathematics. Springer Verlag.Google Scholar
- LIBOFF, R. L. 1997. Introductory Quantum Mechanics (3rd ed.). Addison-Wesley, Reading, Mass.Google Scholar
- LO, H.-K. AND CHAU, H. F. 1999. Unconditional security of quantum key distribution over arbitrarily long distances. Science 283, 2050-2056.Google Scholar
- MAYERS, D. 1998. Unconditional Security in Quantum Cryptography. Preprint at Los Alamos Physics Preprint Archive, http://xxx.lanl. gov/abs/quant-ph/9802025.Google Scholar
- 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.Google Scholar
- SCHULMAN, L. J. AND VAZIRANI, U. 1998. Scalable NMR Quantum Computation. Los Alamos Physics Preprint Archive, http://xxx.lanl. gov/abs/quant-ph/9804060.Google Scholar
- 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.Google Scholar
- SHOR, P. W. 1997. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. Society for Industrial and Applied Mathematics Journal on Computing 26, 5, 1484-1509. Expanded version of Shor {1994}. Google Scholar
- SIMON, D. R. 1997. On the power of quantum computation. Society for Industrial and Applied Mathematics Journal on Computing 26, 5, 1474- 1483. A preliminary version of this paper appeared in the Proceedings of the 35th Annual Symposium on Foundations of Computer Science. Google Scholar
- STEANE, A. 1996. The Ion Trap Quantum Information Processor. Los Alamos Physics Preprint Archive, http://xxx.lanl.gov/abs/quant-ph/ 9608011.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- WATROUS, J. 1998. Relationships between quantum and classical space-bounded complexity classes. In 13th Annual IEEE Conference on Computational Complexity (June 1998), 210- 227. Google Scholar
- WILLIAMS, C. P. AND CLEARWATER, S. H. 1998. Explorations in Quantum Computing. Telos, Springer- Verlag. Google Scholar
- WOOTTERS, W. K. AND ZUREK, W. H. 1982. A single quantum cannot be cloned. Nature 299, 802.Google Scholar
- ZALKA, C. 1997. Grover's Quantum Searching Algorithm is Optimal. Los Alamos Physics Preprint Archive, http://xxx.lanl.gov/abs/ quant-ph/9711070.Google Scholar
Recommendations
Quantum computation and cryptography: an overview
The new Quantum Information Theory augurs powerful machines that obey the "entangled" logic of the subatomic world. Parallelism, entanglement, teleportation, no-cloning and quantum cryptography are typical peculiarities of this novel way of ...
Quantum computing via the Bethe ansatz
We recognize quantum circuit model of computation as factorisable scattering model and propose that a quantum computer is associated with a quantum many-body system solved by the Bethe ansatz. As an typical example to support our perspectives on quantum ...
Quantum computing and quantum simulation with group-II atoms
Recent experimental progress in controlling neutral group-II atoms for optical clocks, and in the production of degenerate gases with group-II atoms has given rise to novel opportunities to address challenges in quantum computing and quantum simulation. ...
Reviews
H. Van Dyke Parunak
A century ago, the discovery of quantum mechanics initiated a revolution in physics that challenged many deeply-held intuitions. Within the last 20 years, the application of quantum mechanics to computation has opened the door to a similar revolution in computer science. These new models of computation are of great interest both theoretically and practically. Practicing computer scientists will welcome the recent publication of several volumes on the subject that provide a variety of avenues to learning about this important new discipline. This review compares several of these volumes, and also a recent paper in ACM Computing Surveys on the subject, with the objective of helping readers select the most appropriate resource for their background and requirements. Table 1 summarizes the works reviewed, in four broad areas: background, applications, implementation, and pedagogy. Table 1: Subject Coverage Bouwmeester Hirvensalo Nielsen Reiffel Williams 98 Williams 00 Background Quantum Primer no Appendix yes yes no no Computation no Body yes no yes yes Mathematical Sophistication Medium High, Terse High, Full Medium Medium Low Applications Computation: Factoring (Shor) yes yes yes yes yes yes Hidden Subgroup no yes yes no no no Search (Grover) yes yes yes yes no yes Information: Cryptography yes no yes yes yes yes Teleportation yes no yes no yes yes Dense Coding yes no no yes no no Implementation Physical Implementations yes no yes no yes yes Error Correction and Purification yes no yes yes yes yes Pedagogy Exercises no yes yes no no no Software no no no no yes no Background : Quantum computing is an interdisciplinary study that requires a fair level of understanding of both quantum mechanics and the theory of computation. Each of these disciplines bristles with apparent paradoxes that challenge everyday intuitions, and different readers bring different levels of understanding. Physicists may have an excellent grasp of quantum mechanics but little knowledge of automata theory, while computer scientists will generally understand computation but not quantum mechanics. Because of the practical implications of quantum computing, some readers with an applications focus may need help with both disciplines, at a lower level of mathematical sophistication. Applications : Advocates of quantum computing have identified several applications for which quantum computers are superior to classical ones. It is customary to divide these into two groups. Quantum computation includes polynomial time factoring of large numbers and other forms of the hidden subgroup problem and quadratic speedup in search of unsorted databases. Quantum information theory enables secure exchange of keys and detection of eavesdropping in cryptography, the teleportation of quantum state, and schemes for passing two bits of information over a one-bit channel. Implementation : The main challenge in achieving these practical benefits is the difficulty of constructing a quantum computer. Quantum computation depends on manipulating a system in a superposition of quantum states without allowing it to interact to the outside world, which would cause the superposition to collapse. A number of physical schemes are being explored, and in addition, computational mechanisms exist that can make quantum computing more robust against occasional disruption. Pedagogy : Readers approaching the field as newcomers will welcome resources that can ease the learning process, such as exercises or demonstration software. Bouwmeester, Ekert, and Zeilinger offer a carefully edited volume that integrates contributions from 42 researchers into a coherent text. As the title suggests, they emphasize the physical techniques that are being explored to support quantum computation, and provide detailed descriptions of experimental set-ups and challenges. They begin their discussion with quantum information theory (including cryptographic applications, dense coding, and teleportation), and then move on to quantum computation, before providing a detailed discussion of implementation issues that occupies more than half of the volume. This book assumes mathematical maturity and a good grasp of quantum mechanics, including modern notational conventions such as the Dirac bra-ket notation. Hirvensalo’s monograph is a terse discussion at a highly mathematical level. The body of the text introduces the theory of computation but assumes a detailed knowledge of quantum mechanics and its mathematical background (including group theory and linear algebra) and other relevant mathematical tools (the Fourier transform; number theory; Shannon’s entropy), but detailed appendices occupying nearly half of the book provide thorough expositions of these as well. Hirvensalo emphasizes the hidden subgroup problem as an important generalization of Shor’s factoring algorithm, and explores the complexity bounds of quantum computers. He does not treat quantum information theory or the underlying physical implementation of quantum computers. Two of the six chapters and both appendices include exercises. The volume by Nielsen and Chuang is the most detailed and comprehensive among those reviewed. They provide excellent introductory sections on both quantum physics and computation, and exercises are carefully integrated with the text, accompanying each new concept to enable readers to test their comprehension before going further. They discuss both quantum computation (with a chapter on implementation issues) and (in great detail) quantum information theory, and offer appendices on probability theory, group theory, the Solovay Kitaev theorem, number theory, public key cryptography, and Lieb’s theorem. The level of presentation is mathematically rigorous but not terse, with numerous examples and intuition-building exposition. Reiffel and Polak offer a short exposition tailored for the computer scientist. They assume knowledge of computational theory but not of quantum mechanics, and discuss the major application areas, but not the physical techniques of implementation. Williams and Clearwater (1998) provide an accessible introduction to quantum computing at a less rigorous mathematical level than some of the other texts. They include a Mathematica notebook implementing a simulation of a Feynmann quantum computer, and use this simulator to illustrate the concepts that they develop. These concepts focus on information theory, cryptography, teleportation, and error correction, and mention Grover’s sorting algorithm only in passing (perhaps because the main publications on this technique appeared in 1996 and 1997, when this volume may have been substantially complete). The book devotes little time to discussing quantum mechanics as a discipline in its own right, but does offer a tutorial on the theory of computation. Williams and Clearwater (2000) is essentially a popularization of their 1998 volume, assuming little mathematical sophistication, but offering more details on Grover’s algorithm than the earlier presentation. Practicing computer scientists will want to acquaint themselves with the potential of quantum computers and the issues surrounding their development. These volumes and papers offer effective support for this process. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments