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
| ||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
| ||Dense Coding||yes||no||no||yes||no||no
| ||Error Correction and Purification||yes||no||yes||yes||yes||yes
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 with 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
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.
Nielsen and Chuang
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
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)
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)
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. Thes e volumes and papers offer effective support for this process.