*Explorations in Quantum Computing*. 1998, with Colin P. Williams2000, with Colin P. Williams*Ultimate Zero and One*.

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.