American Scientist

QUANTUM COMPUTER SCIENCE: An Introduction. N. David Mermin. xvi + 220 pp. Cambridge University Press, 2007. $45.

What business does a physicist have writing a textbook on the theory of quantum computation aimed at computer scientists? In the preface to Quantum Computer Science, David Mermin reassuringly states that his book addresses "computer scientists, electrical engineers, or mathematicians who may know little or nothing about quantum physics (or any other kind of physics)," suggesting that it takes an insider to help the outsiders. Much can be said in favor of this viewpoint: Quantum physics is subtle and counterintuitive, and it is comforting to be in the hands of one of the world's best educators on all things quantum mechanical. (For those readers who do not know Mermin: He is a professor emeritus at Cornell University who is much loved by fellow physicists for his engaging columns and popular books about the foundations of quantum mechanics and other aspects of modern physics.) But then there is also the other point of view: How well can an outsider explain computer science to those who are more on the inside? Not entirely satisfactorily, it appears.

Quantum Computer Science is a gentle and clearly written textbook that introduces the theory of quantum information processing, or quantum computation for short, in a way that does not rely on any university-grade prior knowledge, except for some basic understanding of linear algebra. These minimal prerequisites make it an ideal introductory book for self-study or for a course attended by students from different departments. Indeed, Mermin developed this text from his notes for a course in quantum computation that he has given six times to "undergraduates, graduates students and faculty, in computer science, electrical engineering, mathematics, physics and applied physics," so we can safely consider this course book to be battle-tested.

Of its 220 pages, about 100 are devoted to introducing the quantum circuit model, Shor's algorithm for period finding and factoring, and Grover's search algorithm; about 40 to quantum error correction; and about 20 to various "few qubit" protocols such as teleportation and quantum cryptography. The remainder of the book, more than a quarter of it, is occupied by appendices that give additional background. The text, the mathematics and the (many, many) circuit diagrams are impeccably laid out; the tone is enthusiastic without resorting to hyperbole; and the writing is clear and a joy to read (leaving aside Mermin's odd insistence on writing Qbit where pretty much everybody else uses qubit to refer to a quantum bit). Indeed, the reader is well taken care of in this book.

What is eminently missing is a discussion of how to physically implement any of these algorithms or protocols, which indeed is a whole field by itself. Even the obligatory double-slit experiment or Mach-Zender interferometer is absent from the introduction, which must be a first in books on quantum computing. It no doubt shows Mermin's experience in thinking about the foundations of quantum mechanics that he feels comfortable talking about quantum computing in such an abstract way—an experience that has prepared him well for conveying the essential ideas behind quantum computing, without getting sidetracked by hundreds of years of experimental physics.

Instead, Mermin uses the introduction to carefully explain that the power of quantum computing should not be thought of as a straightforward corollary of the miracle of "quantum parallelism" with its exponentially sized superposition of states and computations, but rather as a more subtle consequence of the superposition principle and its constraints combined with the effects of interference between the probability amplitudes of the states. He is keen to remind us that it is an illusion to think that we have access to all the information used to describe a system of quantum bits and that we should be careful not to expect unreasonable benefits from storing information quantum mechanically. Although no proper textbook would disagree with that assertion, it is the strength of this book that it makes the point as explicitly and convincingly as it does.

Also missing is any reference to Turing machines, computational complexity theory or lower bounds. This decision, if it was one, is less fortunate. The excitement about quantum computing among computer scientists does not stem from the mere fact that we have found some efficient algorithms and novel ways of doing cryptography; new algorithms and cryptographic protocols are invented on a regular basis, and only a few of them will get noticed outside a small community of researchers. What does make quantum computing a revolution in theoretical computer science is the fact that it gives a whole new model of computation—only the third one after the deterministic and probabilistic models, and seemingly the first one that violates the strong Church-Turing principle, which states that any process that can be implemented on a physical device can be simulated efficiently on a Turing machine (the violation being that Shor's algorithm gives strong evidence that a quantum computer would be impossible to simulate efficiently on a classical computer).

Quantum Computer Science does not share this excitement about the field; it presents quantum computing more as a collection of quantum tricks. Readers with some knowledge of computational complexity will find no answers to obvious questions, such as what Shor's factoring algorithm implies for the hardness of simulating quantum systems, or whether Grover's search algorithm can be improved to solve NP-complete search problems efficiently on a quantum computer.

This last omission is an especially dangerous one. A significant part of the research in quantum computation is devoted to proving that even quantum computers cannot solve certain problems beyond certain bounds. Such "lower bounds" provide powerful no-go theorems telling us that quantum computers, like classical computers, have their limits. In conjunction with Grover's discovery of a quantum algorithm that searches a function over N items in √N steps, it is also known that such a quadratic speedup is the best possible, ruling out once and forever the hope for generic exponential speedups for similar problems. To not bring this to the attention of readers learning about Grover's algorithm for the first time seems downright irresponsible. (Think of all the time wasted by ambitious students who, after reading this book, will try to find a log N algorithm for searching.)

Despite such omissions, Quantum Computer Science will be hard to beat for theoretically oriented self-learning, because its selection of topics will keep the attention of readers from beginning to end. Those interested in the experimental side of quantum computing should look elsewhere, however. An Introduction to Quantum Computing, by Phillip Kaye, Raymond Laflamme and Michele Mosca (Oxford University Press, 2007) is more complete than Mermin's textbook, but it is also more detailed and more technical. This makes Quantum Computer Science one of the two best books currently available for an introductory course on the theory of quantum computing. Readers who have a quantum computer scientist (who might or might not "know little or nothing about quantum physics") available to field follow-up questions will get the most benefit.

Wim van Dam is an assistant professor in the departments of computer science and physics at the University of California, Santa Barbara.