|
 |
Modern methods of encrypting computer data rely on the problems we encounter
in trying to find all of the factors of a large number which is the
product of two primes. To take a simple (but non-trivial) example, the number
1729 has three prime factors which are in arithmetic progression, making
it one of an interesting subset of the Carmichael numbers, but even finding
the small factors of such a simple number can take a human quite a while.
Computers can do it faster, but if you ask a computer to factorise a 1000-digit
number, that would take the fastest existing supercomputer about 10 billion
times the age of the universe. But hope for the code-breakers may be on the
way, sooner or later.
The trick is to develop a quantum computer, which
nobody has done yet. Rut when the first quantum computer is unveiled, the
algorithms will be there to help program it, including an algorithm which
would factorise the 1000-digit number in about half an hour!
Described in the 16 March issue of Physical Review Letters, this algorithm
could dramatically speed up chores like searching through reams of data,
especially in scheduling problems where teachers and students have to be
fitted into a timetable with no clashes. The limitation in doing this on
an ordinary computer is that each item must be in binary form, coded as a
single bit which is either on or off, 1 or 0.
A ''bit'' in a quantum computer can have more than one state at a time,
represented by the quantum characteristics of a particle like an electron
or photon. This means that a string of quantum bits can hold all possible
schedules at the same time. when the quantum states of the particles are
measured, this forces the system to choose one of the possible configurations,
one of the schedules. Each schedule has a probability of being chosen. and
this can be set to depend on havina the smallest number of conflicts. The
algorithm is the work of Tad Hogg of the Xerox Palo Alto Research Center
in California. Even if quantum computers are years away from being built,
studying quantum algorithms clarifies the nature of problems by probing their
structures ever more deeply - and it may just turn out to be useful to those
who design the new forms of computer, sometime in the 21st century.
©WebsterWorld Pty Ltd/contributors 2002