Quantum Computing: A Gentle Introduction

Quantum Computing: A Gentle Introduction, Eleanor Rieffel and Wolfgang Polak, MIT Press, Cambridge, MA, 2011. $45.00 (372 pp.). ISBN 978-0-262-01506-6

How do you describe a masterpiece in a page or less? This is the pleasant problem I am facing in writing a review of Quantum Computing: A Gentle Introduction by Eleanor Rieffel and Wolfgang Polak. I shall start by spending a few words on the topic.

The birth narrative of quantum computing is well known: Richard Feynman and others had some prophetic intuitions, David Deutsch and others tried the first formal approaches, and in 1994 Peter Shor demonstrated its potential by providing an efficient algorithm for integer factorization. At that point, the narrative usually goes badly astray. For instance, an algorithm proposed by Lov Grover in 1997 is typically brought to bear to solve an everyday problem that it cannot solve. I have even witnessed undergraduate research projects based on the underlying misunderstanding. Moreover, there is a general misconception that the power of quantum computing comes from “quantum parallelism,” understood as “everything is computed at the same time thanks to superposition.” That is simply the wrong explanation, given that quantum speed-up happens for only a few algorithms and provably does not happen for others. The truth is: Grover’s algorithm can only be appreciated by someone who has considerable technical background and researchers have not yet pinned down why quantum computing works.

If you want to learn quantum computing in more detail, do some small projects on it. Or in preparation for doing research in the field, find a good textbook. I have in my office two texts, written by reputable experts, that provide an interesting sample of the strengths and weaknesses of such treatises. Reviewed in PHYSICS TODAY (March 2008, page 54 ), David Mermin’s Quantum Computer Science: An Introduction (Cambridge University Press, 2007) is light and inspiring: It contains some mathematics, but the value really comes from the pleasure of following the approach of a great thinker in quantum science. The other book, also reviewed in PHYSICS TODAY (February 2008, page 61 ) was written by Phillip Kaye, Raymond Laflamme, and Michele Mosca. Their book, An Introduction to Quantum Computing (Oxford University Press, 2007), is a good reference for those already working in the field, but it seems to me a bit too rushed for beginners.

In contrast to those authors, Rieffel and Polak are trained in classical computer science and have not been active researchers in quantum computing. Although my experience is that most of the textbooks written from the outskirts of a field are insignificant, the few good ones from that vantage point are exactly what is needed. That is true for Michel Le Bellac’s delicious A Short Introduction to Quantum Information and Quantum Computation (Cambridge University Press, 2006), which was reviewed in PHYSICS TODAY (May 2007, page 64 ); it is also true for Rieffel and Polak’s book.

The authors choose to present quantum computing through the circuit model. The material is laid out in an orderly way, with a clear pedagogical plan. The collection of exercises is a treasure. I detected another rare quality: I could open any chapter and follow its content without having to turn to previous chapters for notions and notation. The book touches on other approaches to quantum computing—for example, measurement-based and adiabatic quantum computing—and related topics such as information theory, quantum cryptography, and even Bell’s inequalities. It also provides further references.

I particularly appreciated the passages devoted to critical appraisals of key concepts. Consider, for instance, Grover’s algorithm. All the books mentioned above explain it correctly, by stressing that, loosely speaking, it helps to find the needle in the haystack only if someone has attached one qubit to each piece of hay and flipped the qubit attached to the needle. In describing the algorithm, Quantum Computing offers a section (9.6) that discusses the possible misunderstandings. The authors’ remarks will be precious for the beginner, who may not appreciate the weight of the text in a first reading. Similar pearls are chapter 6, devoted to the design of classical circuits; section 7.6, on the danger of the quantum parallelism notion mentioned earlier; and section 13.9, on the role of entanglement in the power of quantum computing, a topic still poorly understood and certainly less obvious than one might expect.

And now, I‘ve just about reached my word limit. But I have space to repeat the key one: masterpiece. I need not say more.