Review of Mermin’s book
By now, maybe a half-dozen people have asked me what I thought of David Mermin’s new book Quantum Computer Science: An Introduction; many seemed surprised when I told them I hadn’t read it. Since I aim to please, I finally cracked open my review copy on a train this weekend, and am pleased to report that … yes, it’s quite good. Indeed, the biggest problem is just Mermin’s infamous insistence on spelling qubit “Qbit.” (At this point, one might as well decide to spell quark “Qork.” A language consists of shared, often highly-irrational conventions that cannot be changed unilaterally.)
Mermin’s book is, one might say, radically limited in scope. There’s nothing about physical implementation, not a mixed state or POVM in sight, not a word on the provable limitations of quantum computers, no mention of P, NP, or BQP, and pretty much nothing about any development after 1995. The sole aim is to cover the “quantum canon” — Hadamards and Toffolis, Shor and Grover, quantum error-correction, the BB84 key distribution protocol, etc. — while dispelling various misconceptions along the way. But at that limited task, Mermin — who’s an extremely gifted expositor — does a better job than almost anyone.
He certainly does a better job than I would have. I’ll admit that, when the Mike&Ike book came out seven years ago, I naïvely imagined that the “quantum textbook problem” (or more precisely, the good quantum textbook problem) had been solved. From now on, there would be a single place where everyone could go to learn the quantum canon. And because anyone could know all that twentieth-century material by reading a single book, I could readily assume that anyone who was interested did know it, and could take that as shared background knowledge (like, say, the existence of the Roman Empire) when discussing newer topics like quantum lower bounds, the adiabatic algorithm, or BQP/qpoly.
Of course I couldn’t have been more wrong. In the years since Mike&Ike came out, the total amount of confusion in the world about the |A〉|B〉|C〉’s of quantum computing (as well as the total number of books that try to address that confusion) has increased exponentially. And so it’s good to have a distinguished physicist like Mermin patiently telling readers the following:
“To understand how to build a quantum computer … you must indeed have many years of experience in quantum mechanics and its applications under your belt. But if you only want to know what such a device is capable in principle of doing once you have it, then there is no reason to get involved in the really difficult physics of the subject.” (page xiii)
“This means that all traces of the amplitudes αx characterizing the input state have vanished from the output state. The only role they have played in the measurement is to determine the probability of a particular output.” (page 25)
“Small alterations in the phases produce small alterations in the probabilities of getting that extremely precise digital information, but not the precision of the information itself, once it is acquired.” (page 85)
Personally, I find it hard to remember that anyone needs to be told these things — and even when I do tell them, they don’t believe me (probably because I’m waving my arms too wildly). They think I’m making it up. But Mermin dispels the common misconceptions with a calm air of gravity.
I’ll end with two quibbles.
First, while Mermin talks a great deal about quantum black-box algorithms, he never once mentions the crucial distinction between the “black-box” world — the world where one can prove unconditionally both that quantum computers can solve certain problems exponentially faster than classical computers, and that they can’t solve certain other problems any faster than classical ones — and the “non-black-box” world, where all such statements are necessarily conjectural. The one time he does touch on this distinction, he gets it wrong:
“The best known classical algorithms for finding the period r of such a function take a time that grows faster than any power of the number n of bits of r (exponentially with n1/3).” (page 63)
The best classical algorithm for period-finding provably takes time that grows exponentially with n/2. The best known classical algorithms for factoring take time that grows exponentially with n1/3. But the latter algorithms (necessarily) use deeper properties of the factoring problem than just its reducibility to period-finding.
I found this an uncharacteristic omission for Mermin — whose tendency is to examine whatever he brings up from all possible angles — though perhaps it can be understood in terms of a decision to avoid any mention of complexity theory.
The second quibble is that there are no exercises.
Follow
Comment #1 December 10th, 2007 at 2:12 pm
Does it use plain old complex numbers instead of that |A〉|B〉|C〉 crap? That’s my biggest complaint about the presentation of quantum mechanical stuff I’ve read, including your quantum computing since democritus lectures.
Comment #2 December 10th, 2007 at 2:36 pm
What about those of us who do care about physical implementations, and consequently, about the mathematics of POVMs, mixed states, measurement and control processes, etc. … does the Mike and Ike book have any serious competition?
Comment #3 December 10th, 2007 at 2:36 pm
That “crap” may make it harder for outsiders to break in, but in terms of formal manipulations, it simplifies many things.
Comment #4 December 10th, 2007 at 3:52 pm
I agree with Aaron (#3). As for myself, I can’t imagine trying to do my Quantum Mechanics II homework without Dirac notation. Sure, it is confusing at first– no two ways about that– but it helps so much as things get hairier.
Comment #5 December 10th, 2007 at 4:10 pm
@Bram
Well, you still have to use complex numbers to characterise your state. A single qubit has the state a |0> + b |1> with complex numbers a and b.
How would you prefer to denote a state such as |110> ?
\Psi_6 ?
@Scott
I’m currently working through the Nielsen-Chuang (Quantum Computation and Quantum Information) to get a broad overview, since there are no special lectures at our university on QC (at the moment).
Do you have any further recommendations? I’m a student of both physics and computer science with a profound background in theoretical computer science as well as in quantum mechanics.
It’s fun reading your blog!
Greetings,
Clemens
Comment #6 December 10th, 2007 at 4:29 pm
Clemens: A profound background in TCS and quantum mechanics? Wow! In that case, try the course lecture notes from Andris Ambainis (see also here), Umesh Vazirani, or Ashwin Nayak.
Comment #7 December 10th, 2007 at 4:40 pm
Bram: To echo what others said, I also disliked Dirac notation when I first saw it. But I eventually realized it’s indispensable — and not just for the obvious reason that without it you can’t communicate with anyone else in the field (which gets back to my earlier point, about language consisting of shared conventions one can’t just change unilaterally).
Look, how would you describe Shor’s algorithm without being able to write |r,xr mod N⟩ (i.e., if you couldn’t take an arbitrary tuple of information, enclose it in some kind of bracket, and call the result a direction in Hilbert space)? Would you define a vector “vr,x^r mod N“?
Comment #8 December 10th, 2007 at 4:43 pm
exponentially with n^{1/3}
Factorially, rather, but you surely already know that.
Comment #9 December 10th, 2007 at 5:06 pm
Dr. Aaronson, would you recommend this book for an undergrad physics/cs major seeking to get into the field? I’m trying to build some background before I graduate, and thus have already purchased Neilsen & Chuang (not that I understand most of it, but I’m trying). Anyway, thanks for maintaining the blog.
Comment #10 December 10th, 2007 at 5:07 pm
Eh, if O(n1/3)=Õ(n1/3) then exponential=factorial.
Comment #11 December 10th, 2007 at 5:16 pm
Chris: Sure, it won’t hurt to read it — just go back to Mike&Ike (or to online course lecture notes) when you want to dig deeper.
Comment #12 December 10th, 2007 at 5:35 pm
Of course the very best preparation for an undergraduate trying to get into the field is to do some original research, in whatever area you can find an advisor to help you out.
Comment #13 December 10th, 2007 at 9:24 pm
In reply to Sean (#12):
Of course! I wholeheartedly agree. Trouble is, my department doesn’t (yet) do anything with quantum comp, and so I’m going instead for REUs and SURFs and whatever else that I can find.
In particular, Dr. Aaronson, if you have anything coming up, I’d be quite happy to send along my credentials, my letters of recommendation, etc.
Thanks for all the help!
Comment #14 December 10th, 2007 at 9:43 pm
Chris,
I wholeheartedly recommend Mermin as a starting point.
Comment #15 December 10th, 2007 at 11:51 pm
Bram: Learn the |A> |B> |C> crap – it’s just notation for vectors.
Comment #16 December 11th, 2007 at 2:42 am
Hi Scott! Thanks for the review. The field has grown so much in the last decade that one could essentially write several textbooks on the subject. Quantum error-correction alone could take up an entire book. Now there’s a book waiting to be written!
Comment #17 December 11th, 2007 at 10:30 am
Many years ago I took a solid-state physics course from Mermin– He’s the only person I’ve ever encountered who stutters in complete sentences.
Comment #18 December 11th, 2007 at 2:32 pm
Many years ago I took a solid-state physics class that used an excellent textbook by Mermin. I also recall an entertaining article in “Physics Today” by Mermin about how he had coined a word (Boojum?) for some quantum phenomena or other and then had to concoct an elaborate backstory to get it by the editors of physics journals.
Comment #19 December 13th, 2007 at 4:15 am
How would you compare Mermin’s book to Hirvensalo’s — another quantum computing book which mostly aims at covering the basics ?
Comment #20 December 13th, 2007 at 12:23 pm
Sorry, haven’t read Hirvensalo’s.
Comment #21 December 17th, 2007 at 4:08 am
As a mathematics student who has tried a few times to learn something about quantum physics (and failed), I agree that the Dirac notation is confusing at first. (And the “at first” stage is all I’ve ever gotten to.) However, in my experience with other fields in mathematics, notation is frequently very confusing at first. However, once I learn it, it becomes a huge time saver, and simplifies many things. This has been my experience in logic, algorithmic complexity theory, and (especially) algebraic topology. My theory is that mathematicians and physicists are really smart, and don’t use pointlessly confusing notation.