杏吧原创

Minds, Machines and the Multiverse: The Quest for the Quantum Computer by
Julian Brown, Simon & Schuster, $27, ISBN 0684814811

DO you have 10 billion years to spare? Yes? Then you鈥檒l have to the time to
wait for a solution to the travelling salesman problem. He wants to visit
several cities in the shortest possible trip. If his route takes in only a few
cities, he can calculate the length of the journey for every itinerary and
simply pick the shortest. Unfortunately, the number of choices blossoms
amazingly quickly each time he adds a city to his list. With 24 cities to sell,
he has the choice of more than 10²³ routes. A computer cracking through a
million routes a second will take roughly the age of the Universe to solve this
puzzle.

Surprisingly, many tasks that look simple are similarly impossible for
conventional computers to solve but a revolutionary solution may be on its way.
Julian Brown鈥檚 Minds, Machines and the Multiverse explains how a
quantum computer can beat this system hands down by processing quantum bits
(qbits) of information using particles such as atoms, nuclei or photons instead
of electronic circuits. The information is held in the quantum states of the
particles鈥攖he direction of their spin, for example. Now, the peculiarities
of the quantum world give each qbit an extraordinary new possibility that
ordinary bits don鈥檛 have: as long as we don鈥檛 measure the qbit, it can be 1 or 0
or a 鈥渟uperposition鈥� of both at once. Once we have looked, of course, the
character of the particle is fixed.

Herein lies the power of the quantum computer: using superpositions in the
inputs, it can calculate all the corresponding outputs at once rather than
plodding through them one after another. This is not particularly helpful for
some classes of problems because a superposition of all the answers in the
output register yields only one of them when we measure the register. But
suppose we just want to know whether the answers are all the same. In that case
the computer can compare them without needing to know explicitly what they
are.

So how does this help our travelling salesman? A register of roughly 80 qbits
can simultaneously represent all his different routes. The computer can then
simultaneously work out the lengths of all the trips and discover the
shortest.

Code breakers are going to have fun with the quantum computer too. Another
important problem, not quite as difficult as the travelling salesman, but still
too hard for classical computers, is to factorise a large number N. If
the number of digits is small the computer can just try dividing until it is
successful or reaches 鈭歂 but for a large number, say with 23 decimal digits, we
are again stuck because we have too many possibilities to try. When you send a
private e-mail, telephone or Internet message it is encoded using a system
relying on this fact. Indeed, the military and financial security of the world
hinges on the difficulty of factorising large numbers.

But how can a quantum register hold many numbers simultaneously? What
constitutes a measurement and where do the other possibilities go when a
measurement is made? Oxford physicist David Deutsch (who introduces the book)
suggests that whenever quantum possibilities are removed by a measurement, they
do not disappear but simply move into other universes, causing a vast
proliferation of worlds he calls the Multiverse. Although Brown discusses these
fascinating questions of interpretation, mercifully he sticks to his central
theme most of the time: what is a quantum computer鈥攁nd why it is a concept
of stunning intellectual importance.

Brown does, I think, give too little space to what might just be quantum
computing鈥檚 undoing. It is immensely difficult to prevent the quantum state of a
many-qbit register from collapsing because of its interaction with the
surroundings. This is called decoherence. Brown seems to dismiss this as a mere
technical detail. Still, this should not deter anyone who would like to know
more about quantum computers from buying the book. It is a fascinating and
entertaining read from start to finish, spanning a huge tract of new scientific
thought in quantum physics, mathematics and philosophy.