author : Scott H. Clearwater

This overview of the current state of quantum computing is blurbed as being for non-specialists -- but it does helps to know a fair bit about quantum mechanics and computational complexity theory. Nonetheless, it is an excellent introduction to this weird counter-intuitive subject.

The authors explain how quantum mechanics gives a different kind of computational power, with superimposed states and entangled states having very different properties from classical zero or one states. Quantum computers can do (some) calculations exponentially faster than can their classical counterparts, such as factoring large numbers, by being able to explore many computations in parallel.

Quantum computers aren't magic, and they are not all-powerful. For example, observing a quantum state "collapses the wavefunction" and destroys the crucial entangled state, changing the nature of any remaining computation -- so a quantum computation can be observed only at the end when it produces its result, not during the computation. (And only one result can be observed, so doing an exponential number of calculations in parallel does not give an exponential number of results -- one has to arrange the computation carefully so the the answer observed is the one that is wanted.) One kind of activity that a quantum computer might do is calculate a proof of a theorem. Classically, intermediate computational states represent intermediate steps in the proof; and long computer proofs, such as that of the Four Colour Theorem, have been criticised for being too huge for any person to read and understand them. A quantum proof is worse: it is not just too tedious, but physically impossible, to view the intermediate steps!

Quantum computers can also do things that classical computers cannot, such as generate genuine random (stochastic) numbers (as opposed to algorithmic pseudo-random numbers), communicate information so that eavesdroppers can be reliably detected, "teleport" information so that it never actually exists in any place other than at the sender and receiver, and, maybe most mind-bogglingly of all, do computations without even being switched on! I would have liked a little more explanation about the why and the how, to help my physical intuition along, maybe in terms of the Many Worlds interpretation of QM, which is the one favoured by one of the subject's founders. The authors, however, are proponents of the "shut up and calculate" school -- which is all very well when you already know what you want to calculate, but not much help when you are grappling with which equations to set up in the first place. But they certainly do explain the what of all these bizarre concepts lucidly, and with clear and helpful example calculations.