Books : reviews

Colin P. Williams, Scott H. Clearwater.
Explorations in Quantum Computing.
Springer. 1998

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.

Colin P. Williams, Scott H. Clearwater.
Ultimate Zero and One: computing at the quantum frontier.
Copernicus/Springer. 2000

rating : 2.5 : great stuff
review : 10 February 2000

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.