290 Quantum computing
to 7 in decimals, the quantum computation does all eight calculations
simultaneously. Herein lies the great power of quantum computing.
The number of combinations of the input states increases exponen-
tially with the number of qubits; for a register of 100 qubits this means
a transformation of 2^100 ≡ 1030 inputs in parallel—an astronomical num-
ber. But how can the correct answer be picked out from the enormous
number of possible outputs? All the possibilities encoded in the multiple-
particle wavefunction Ψ′cannotbe turned into a list of the outputs for
a given input, as given by a classical computer. Indeed, a simple quan-
tum measurement just gives one of the outputs chosen randomly from
all the possibilities. However, quantum mechanics allows measurements
that give some information about all of the outputs, if we renounce the
possibility of getting information about any particular output—just as
the complementarity principle stops us knowing both the position and
momentum of a particle precisely. As a trivial example that gives the
flavour of this idea, but is in fact not strictly correct, consider the mea-
surement of the state of the last qubit in the output register—if all the
possible outputs are even numbers then this ion will be in| 0 〉.Sowe
can establish something about all the possibilities in a single quantum
computation, but this does not allow any more information to be ex-
tracted, i.e. if they are not all even we cannot find out which ones are
odd (nor which input states gave these outputs). Similar ideas apply for
more complicated quantum algorithms, e.g. finding the prime factors of
numbers. (The real nature of quantum computation can only properly
be appreciated by working through a quantum example, so the grossly
simplified case given here must not be pushed too far.)
The factorisation of large numbers is often quoted as a ‘killer appli-
cation’ of quantum computing, i.e. something that they can do which
cannot be done on existing computers (within a realistic time). It is ob-
viously easy to multiply two prime numbers together, e.g. 37×61 = 2257;
but it is much more difficult to go in the opposite direction, e.g. to find
the prime factors of 1271 (try it for yourself). For the larger numbers a
classical computer can easily do the multiplication, but the factorisation
of a number of order 10^100 would take an exceedingly long time even with
the fastest supercomputers and the most efficient classical algorithm to
search for the prime factors. It has been proved rigorously that quantum
algorithms exist to attack this type of problem—the algorithms act like
a filter only letting through the sought-after combination of qubits from
the input superposition state. The practical impossibility of factorising
large numbers on present-day computers forms the foundation of the(^8) The need for safe methods of encrypt- best methods of encryption. (^8) A quantum computer has the ability to
ing information has always been cru-
cial for the military, and nowadays it
is important for confidential electronic
transfer of data in business and to pro-
tect credit card numbers.
try many combinations in each computation and so quickly find the key.
The possibility of cracking the best currently-used codes has prompted
such hard-headed bodies as the government security agencies to investi-
gate quantum computing and fund research on ion traps. One wonders
what they think of the intrigue and mystery of quantum mechanics.