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

By the year 2020, the basic memory components of a computer will be the size of individual atoms.
At such scales, the current theory of computation will become invalid.
A new field called “quantum computing” is emerging that is reinventing
the foundations of computer science and information theory
in a way that is consistent with quantum physics—the
most accurate model of reality that is currently known.
Remarkably, this new theory predicts that quantum computers
can perform certain tasks breathtakingly faster than classical computers,
and, better yet, can accomplish mind-boggling feats such as teleporting information,
breaking supposedly “unbreakable” codes, generating true random numbers,
and communicating with messages that betray the presence of eavesdropping.

*Explorations in Quantum Computing* explains these burgeoning developments in simple terms,
and describes the key technological hurdles that must be overcome
in order to make quantum computers a reality.
This book draws upon the very latest research and uses executable software simulations
to help explain the material and allow the reader to experiment with the ideas behind quantum computers.
This is the ideal text for anyone wishing to learn more about the next,
perhaps “ultimate,” computer revolution.

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.