Quantum
Computation
By David Deutsch and Artur Ekert
from the March 1998 issue of Physics World
A new way of harnessing
nature
Many milestones in the history of technology have involved the
discovery of new ways of harnessing nature --- exploiting various physical
resources such as materials, forces, and sources of energy. In the
twentieth century information was added to this list when the invention of
computers allowed complex information processing to be performed outside
human brains. The history of computer technology has itself involved a
sequence of changes from one type of physical realisation to another ---
from gears to relays to valves to transistors, integrated circuits and so
on. Today’s advanced lithographic techniques can etch logic gates and
wires less than a micron across onto the surfaces of silicon chips. Soon
they will yield even smaller components, until we reach the point where
logic gates are so small that they consist of only a few atoms each.
On the scale of human perception and above, classical (non-quantum)
laws of physics are good phenomenological approximations, but on the
atomic scale the laws of quantum mechanics become dominant, and they have
quite a different character. If computers are to continue to become faster
(and therefore smaller), new, quantum technology must replace or
supplement what we have now, but it turns out that such technology can
offer much more than smaller and faster microprocessors. It can support
entirely new modes of computation, with new quantum algorithms that do not
have classical analogues. And more: the quantum theory of computation
plays an even more fundamental role in the scheme of things than its
classical predecessor did, so that anyone who seeks a fundamental
understanding of either physics or information processing must incorporate
its new insights into their world view.
From bits to qubits
What makes quantum computers so different from their classical
counterparts? Let us take a closer look at the basic unit of information:
the bit. From a physical point of view a bit is a two-state system: it can
be prepared in one of two distinguishable states representing two logical
values --- no or yes, false or true, or simply 0 or 1. For example, in
digital computers, the voltage between the plates of a capacitor can
represent a bit of information: a charge on the capacitor denotes 1 and
the absence of charge denotes 0. One bit of information can be also
encoded using, for instance, two different polarisations of light or two
different electronic states of an atom. Now, quantum mechanics tells us
that if a bit can exist in either of two distinguishable states, it can
also exist in coherent superpositions of them. These are further states,
which in general have no classical analogues, in which the atom represents
both values, 0 and 1, simultaneously. To get used to the idea that a
physical quantity can have two values at once, it is helpful to consider
the experiment in Fig. 1a.
 |
Fig.1a. A half-silvered mirror reflects half the
light that impinges upon it. But a single photon doesn’t split: when
we send a photon at such a mirror it is detected, with equal
probability, either at detector A or B. This does not, however, mean
that the photon leaves the mirror in either the horizontal (H) or
the vertical (V) direction at random. In fact the photon takes both
paths at once! This can be demonstrated with the help of a slightly
more complicated experiment shown in Fig.
1b. |
A half—silvered mirror is one that reflects half the light that
impinges upon it, while allowing the remaining half to pass
throughunaffected. Let us aim a single photon at such a mirror, as in
Fig.1a. What happens? One thing we know is that the photon doesn’t split
in two: we can place photodetectors wherever we like in the apparatus,
fire in a photon, and verify that if any of the photodetectors registers a
hit, none of the others do. In particular, if we place a photodetector
behind the mirror in each of the two possible exit beams, the photon is
detected with equal probability at either detector. So does the photon
leave the first mirror in one of the two possible directions, at random?
It does not! It may seem obvious that at the very least, the photon is
either in the transmitted beam H or in the reflected beam V
during any one run of this experiment. But that is not so either. In fact
the photon takes both paths at once, as can be demonstrated with the help
of the apparatus shown in Fig. 1b. Two normal mirrors are placed as so
that both paths intersect at a second half—silvered mirror. With this
setup we can observe the astonishing, purely quantum phenomenon of
single-particle interference.
 |
Fig.1b. Single-particle interference. A photon
which enters the interferometer always strikes detector A and never
detector B. Any explanation which assumes that the photon takes
exactly one path through the interferometer --- either H or V ---
leads to the conclusion that detectors A and B should on average
each fire on half the occasions when the experiment is performed.
But experiment shows
otherwise. |
Suppose that a particular photon followed
the horizontal path marked H in Fig.1b. after striking the mirror. Then
(by comparison with Fig.1a) we should find that the two detectors
registered hits with equal probability. Exactly the same would be observed
if the photon were on the vertical path V. Hence if it were really the
case that the photon takes exactly one path through the apparatus --- no
matter which one --- detectors A and B would on average each fire on half
the occasions when the experiment is performed. However, that is not what
happens. It turns out that in the arrangement shown, the photon always
strikes detector A and never detector B.
The inescapable conclusion is that the photon must, in some sense, have
travelled both routes at once --- for if either of the two paths is
blocked by an absorbing screen, it immediately becomes equally probable
that A or B is struck. In other words, blocking off either of the paths
illuminates B; with both paths open, the photon somehow receives
information that prevents it from reaching B, information that travels
along the other path at the speed of light, bouncing off the mirror,
exactly as a photon would. This property of quantum interference --- that
there appear to be invisible counterparts affecting the motion of
particles that we detect --- applies not only to photons but to all
particles and all physical systems. Thus quantum theory describes an
enormously larger reality than the universe we observe around us. It turns
out that this reality has the approximate structure of multiple variants
of that universe, co-existing and affecting each other only through
interference phenomena --- but for the purposes of this article, all we
need of this ‘parallel universes’ ontology is the fact that what we see as
a single particle is actually only one tiny aspect of a tremendously
complex entity, the rest of which we cannot detect directly. Quantum
computation is all about making the invisible aspects of the particle ---
its counterparts in other universes --- work for us.
 |
Fig.2. A sliver of glass inserted into one
of the two paths in the interferometer can redirect photons from one
detector to another. All photons that enter the top interferometer
strike detector A.. In the bottom interferometer, the interference
is modified by the presence of the sliver of glass on the vertical
path, and as a result all photons end up in detector B. Thus
something that has happened on only one of the paths has, with
certainty, changed the final outcome of the experiment. This effect
is especially useful in quantum
computation. |
One effect that is especially useful in quantum computation can
be demonstrated if we delay the photon on one of the paths H or V. This
can be done by inserting a sliver of glass into that path, as illustrated
in Fig.2. Since the interference between the photon and its invisible
counterpart depends on their exact arrival times, we can, for instance,
choose the thickness of the glass, and hence the delay time, in such a way
that the photon will certainly (i.e. in all universes) emerge at detector
B instead of detector A. Thus something that has happened on only one of
the paths (and hence in only one of the universes) has affected both of
them. We shall return to this point below.
Just as the photon can be in a coherent superposition of being on the
path H and on the path V, any quantum bit, or qubit, can be
prepared in a superposition of its two logical states 0 and 1. That is the
sense in which a qubit can store both 0 and 1 simultaneously, in arbitrary
proportions. But note that just as the photon, if measured, will be
detected on only one of the two paths, so if the qubit is measured, only
one of the two numbers it holds will be detected, at random: not a very
useful property in itself.
But now let us push the idea of superpositions of numbers a little
further. Consider a register composed of three physical bits. A classical
3-bit register can store exactly one of eight different numbers i.e the
register can be in one of the eight possible configurations 000, 001, 010,
..., 111, representing the numbers 0 to 7. But a quantum register composed
of three qubits can simultaneously store up to eight numbers in a quantum
superposition. It is quite remarkable that eight different numbers can be
physically present in the same register; but it should be no more
surprising than the numbers 0 and 1 both being present in the same qubit.
If we add more qubits to the register its capacity for storing quantum
information increases exponentially: four qubits can store 16 different
numbers at once, and in general L qubits can store up to 2L
numbers at once. A 250-qubit register --- essentially made of 250 atoms,
say --- would be capable of holding more numbers simultaneously than there
are atoms in the known universe. (If anything, this understates the
amount of quantum information that they hold, for in general, the elements
of a superposition are present in continuously variable proportions, each
with its own phase angle as well.) Even so, if we measure the register’s
contents, we will see only one of those numbers. However, now we can start
doing some non-trivial quantum computation, for once the register is
prepared in a superposition of many different numbers, we can perform
mathematical operations on all of them at once. For example, if the qubits
are atoms then suitably tuned laser pulses affect their electronic states
and evolve initial superpositions of encoded numbers into different
superpositions. During such an evolution each number in the superposition
is affected, so we are performing a massive parallel computation. Thus a
quantum computer can in a single computational step perform the same
mathematical operation on, say, 2L different input numbers, and
the result will be a superposition of all the corresponding outputs. In
order to accomplish the same task any classical computer has to repeat the
computation 2L times, or has to use 2L different
processors working in parallel. In this way a quantum computer offers an
enormous gain in the use of computational resources such as time and
memory --- though only in certain types of computation.
Quantum
algorithms
What types? As we have said, ordinary information storage is not one of
them, for although the computer now holds all the outcomes of
2L computations, the laws of physics only allow us to see one
of them. However, just as the single answer ‘A’ in the experiment of Fig.2
depends on information that travelled along each of two paths, quantum
interference now allows us to obtain a single, final result that depends
logically on all 2L of the intermediate results. This is how a
remarkable quantum algorithm recently discovered by Lov Grover of
AT&T’s Bell Laboratories in New Jersey achieves the mind-boggling feat
of searching an unsorted list of N items in only square root N or so steps
[1]. Consider, for example, searching for a specific telephone number in a
directory containing a million entries, stored in the computer’s memory in
alphabetical order of names. It is easily proved (and obvious) that no
classical algorithm can improve on the brute-force method of simply
iscanning the entries one by one until the given number is found, which
will, on average, require 500,000 memory accesses. A quantum computer can
examine all the entries simultaneously, in the time of a single access.
However, if it is merely programmed to print out the result at that point,
there is no improvement over the classical algorithm: only one of the
million computational paths (i.e. one in a million universes) would have
checked the entry we are looking for, so there would be a probability of
only one in a million that we would obtain that information if we measured
the computer’s state. But if we leave that quantum information in the
computer, unmeasured, a further quantum operation can cause that
information to affect other paths, just as in the simple interference
experiment described above. In this way the information about the desired
entry is spread, through quantum interference, to more universes. It turns
out that if this interference generating operation is repeated about 1000
times, (in general, square root of N times) the information about which
entry contains the desired number will be accessible to measurement with
probability 0.5 --- i.e. it will have spread to more than half the
universes. Therefore repeating the entire algorithm a few more times will
find the desired entry with a probability overwhelmingly close to 1. In
addition to finding the entry with a given property, variations on
Grover’s algorithm can also find the largest or smallest value in a list,
or the modal value, and so on, so it is a very versatile searching tool.
However, in practice, searching a physical database is unlikely to become
a major application of Grover’s algorithm --- at least so long as
classical memory remains cheaper than quantum memory. For since the
operation of transferring a database from classical to quantum memory
(bits to qubits) would itself require O(N) steps, Grover’s algorithm would
improve search times by at best a constant factor, which could also be
achieved by classical parallel processing. Where Grover’s algorithm would
really come into its own is in algorithmic searches --- that is, searches
of lists that are not stored in memory but are themselves generated on the
fly by a computer program.
For instance, a chess-playing quantum computer could use it to
investigate a trillion possible continuations from a given position in
roughly the number of steps that a classical computer (using blind
‘brute-force’ searching) would need to investigate a mere million. Despite
the greater scope for ‘tree-pruning’ in classical chess-playing
algorithms, this is likely to provide a very significant improvement. As
Gilles Brassard of the Universitéde Montréal has recently pointed out,
another important application of Grover’s algorithm will be in
cryptanalysis, to attack classical cryptographic schemes such as DES (the
Data Encryption Standard)[2]. Cracking DES essentially requires a search
among 256 =7 x1016 possible keys. If these can be
checked at a rate of, say, one million keys per second, a classical
computer would need over a thousand years to discover the correct key
while a quantum computer using Grover’s algorithm would do it in less than
four minutes. By some strange coincidence, several of the superior
features of quantum computers have applications in cryptography. One of
them is Grover’s algorithm. Another is the quantum algorithm discovered in
1994 by Peter Shor, also of AT&T’s Bell Laboratories in New Jersey,
for factorising large integers efficiently [3]. Here the difference in
performance between the quantum and classical algorithms is even more
spectacular.
Mathematicians believe (firmly, though they have not actually proved
it) that in order to factorise a number with N decimal digits, any
classical computer needs a number of steps that grows exponentially with
N: that is to say, adding one extra digit to the number to be factorised
generally multiplies the time required by a fixed factor. Thus, as we
increase the number of digits, the task rapidly becomes intractable. The
largest number that has been factorised as a mathematical challenge, i.e.
a number whose factors were secretly chosen by mathematicians in order to
present a challenge to other mathematicians, had 129 digits. No one can
even conceive of how one might factorise, say, thousand-digit numbers by
classical means; the computation would take many times as long the
estimated age of the universe. In contrast, quantum computers could factor
thousand-digit numbers in a fraction of a second --- and the execution
time would grow only as the cube of the number of digits.
Now, the intractability of factorisation underpins the security of what
are currently the most trusted methods of encryption, in particular of the
RSA (Rivest, Shamir and Adleman) system, which is often used to protect
electronic bank accounts (Public key cryptography was originally
discovered by Ellis and Cocks of the British Government Communication
Headquarters GCHQ). Once a quantum factorisation engine (a special-purpose
quantum computer for factorising large numbers) is built, all such
cryptographic systems will become insecure. Indeed, in one sense they are
already insecure: any RSA-encrypted message that is recorded today will
become readable moments after the first quantum factorisation engine is
switched on, and therefore RSA cannot be used for securely transmitting
any information that will still need to be secret on that happy day.
Admittedly, that day is probably decades away, but can anyone
prove, or give any reliable assurance, that it is? Confidence in
the slowness of technological progress is all that the security of the RSA
system now rests on. What quantum computation takes away with one hand, it
returns, at least partially, with the other. One of the simplest types of
quantum computation—a type which is now routinely carried out in the
laboratory and may soon be a commercial proposition --- is quantum
cryptography [4]. The reason why it is already feasible is that it
requires only one qubit and one quantum computational step at a time. It
provides perfect security because unlike all classical cryptography
(except the one-time pad) it relies on the laws of physics rather than on
ensuring that successful eavesdropping would require excessive
computational effort. Note, however, that existing systems have limited
range.
The potential power of quantum phenomena to perform computations was
first adumbrated in a talk given by Richard Feynman at the First
Conference on the Physics of Computation held at MIT in 1981 [5]. He
observed that it appeared to be impossible in general to simulate a
evolution of a quantum system on a classical computer in an efficient way.
The computer simulation of quantum evolution typically involves an
exponential slowdown in time, compared with the natural evolution,
essentially because the amount of classical information required to
describe the evolving quantum state is exponentially larger than that
required to describe the corresponding classical system with a similar
accuracy. (To predict interference effects, one has to describe all the
system’s exponentially many counterparts in parallel universes.) However,
instead of viewing this intractability as an obstacle, Feynman regarded it
as an opportunity. He pointed out that if it requires that much
computation to work out what will happen in a multi-particle interference
experiment, then the very act of setting up such an experiment and
measuring the outcome is equivalent to performing a complex
computation.
Quantum computation has already been used, in simple cases, to predict
the behaviour of quantum systems. At some point in the foreseeable future,
they will take on a new and irreplaceable role in the structure of
science, for the ability of science to make predictions will then depend
on quantum computation. The foundations of the quantum theory of
computation (which must now be regarded as the theory of computation ---
Turing’s classical theory being only an approximation) were laid down in
1985 when David Deutsch of the University of Oxford published a crucial
theoretical paper in which he described a universal quantum computer [6].
Since then, the hunt has been on for interesting things for quantum
computers to do, and at the same time, for the scientific and
technological advances that could allow us to build quantum computers.
Building quantum
computers
In principle we know how to build a quantum computer; we start with
simple quantum logic gates and connect them up into quantum networks
[7].
A quantum logic gate, like a classical gate, is a very simple computing
device that performs one elementary quantum operation, usually on two
qubits, in a given time. Of course, quantum logic gates differ from their
classical counterparts in that they can create, and perform operations, on
quantum superpositions.
However as the number of quantum gates in a network increases, we
quickly run into some serious practical problems. The more interacting
qubits are involved, the harder it tends to be to engineer the interaction
that would display the quantum interference. Apart from the technical
difficulties of working at single-atom and single-photon scales, one of
the most important problems is that of preventing the surrounding
environment from being affected by the interactions that generate quantum
superpositions. The more components there are, the more likely it is that
quantum information will spread outside the quantum computer and be lost
into the environment, thus spoiling the computation. This process is
called decoherence. Thus our task is to engineer sub-microscopic
systems in which qubits affect each other but not the environment.
Some physicists are pessimistic about the prospects of substantial
further progress in quantum computer technology. They believe that
decoherence will in practice never be reduced to the point where more than
a few consecutive quantum computational steps can be performed. (This,
incidentally, would already allow for some very useful devices--- see the
table below.) Other, more optimistic researchers believe that practical
quantum computers will appear in a matter of years rather than decades. We
tend towards the optimistic end of the scale, partly because theory tells
us that there is now no fundamental obstacle in the way, partly
because of the astonishing talents and problem-solving abilities of the
experimental physicists now working on this project, and partly because
optimism makes things happen.
However, the problems will not be solved in one fell swoop. The current
challenge is not to build a fully-fledged universal quantum computer right
away, but rather to move from the experiments in which we merely observe
quantum phenomena to experiments in which we can control those phenomena
in the necessary ways. Simple quantum logic gates involving two qubits are
being realised in laboratories in Europe and U.S.A. The next decade should
bring control over several qubits and, without any doubt, we shall already
begin to benefit from our new way of harnessing nature. It is known, for
instance, that simple quantum networks can offer better frequency
standards [8]. Some possible milestones in the development of quantum
computer technology are shown in the table below.
Milestones in the development of quantum computer
technology
|
Type of hardware |
Number of qubits needed |
Number of steps before decoherence |
Status |
|
Quantum Cryptography |
1 |
1 |
Already implemented |
|
Entanglement-based quantum cryptography |
2 |
1 |
Demonstrated in lab |
|
Quantum controlled-NOT gate |
2 |
1 |
Demonstrated in lab |
|
Composition of quantum gates |
2 |
2 |
Demonstrated in lab |
|
Deutsch's algorithm |
2 |
3 |
Demonstrated in NMR quantum computer |
|
Channel capacity doubling |
2 |
2 |
Imminent |
|
Teleportation |
3 |
2 |
Achieved intermittently |
|
Entanglement swapping |
4 |
1 |
Achieved intermittently |
|
Repeating station for quantum cryptography |
A few |
A few |
Theory not yet complete |
|
Quantum simulations |
A few |
A few |
Simple cases demonstrated |
|
Grover;s algorithms with toy data |
3+ |
6+ |
Foreseeable |
|
Ultra-precise frequency standards |
A few |
A few |
Foreseeable |
|
Entanglement purification |
A few |
A few |
|
|
Shor's algorithms with toy data |
16+ |
Hundreds+ |
|
|
Quantum factoring engine |
Hundreds |
Hundreds |
|
|
Universal quantum computer |
Thousands |
Thousands+ |
|
(the table was compiled in March 1998)
Deeper
implications
When the physics of computation was first investigated systematically
in the 1970s, the main fear was that quantum-mechanical effects might
place fundamental bounds on the accuracy with which physical objects could
realise the properties of bits, logic gates, the composition of
operations, and so on, which appear in the abstract and
mathematicallysophisticated theory of computation. Thus it was feared that
the power and elegance of that theory, its deep concepts such as
computational universality, its deep results such as Turing’s halting
theorem, and the more modern theory of complexity, might all be mere
figments of pure mathematics, not really relevant to anything in
nature.
Those fears have not only been proved groundless by the research we
have been describing, but also, in each case, the underlying aspiration
has been wonderfully vindicated to an extent that no one even dreamed of
just twenty years ago. As we have explained, quantum mechanics, far from
placing limits on what classical computations can be performed in nature,
permits them all, and in addition provides whole new modes of computation,
including algorithms that perform tasks (such as perfectly secure
public-key cryptography) that no classical computer can perform at all. As
far as the elegance of the theory goes, researchers in the field have now
become accustomed to the fact that the real theory of computation hangs
together better, and fits in far more naturally with fundamental theories
in other fields, than its classical approximation could ever have been
expected to. Even at the simplest level, the very word ‘quantum’ means the
same as the word ‘bit’ --- an elementary chunk --- and this reflects the
fact that fully classical physical systems, being subject to the generic
instability known as ‘chaos’, would not support digital computation at all
(so even Turing machines, the theoretical prototype of all classical
computers, were secretly quantum-mechanical all along!). The Church-Turing
hypothesis in the classical theory (that all ‘natural’ models of
computation are essentially equivalent to each other), was never proved.
Its analogue in the quantum theory of computation (the Turing Principle,
that the universal quantum computer can simulate the behaviour of any
finite physical system) was straightforwardly proved in Deutsch’s 1985
paper. A stronger result (also conjectured but never proved in the
classical case), namely that such simulations can always be performed in a
time that is at most a polynomial function of the time taken for the
physical evolution, has since been proved in the quantum case.
Among the many ramifications of quantum computation for apparently
distant fields of study are its implications for both the philosophy and
the practice of mathematical proof. Performing any computation that
provides a definite output is tantamount to proving that the
observed output is one of the possible results of the given computation.
Since we can describe the computer’s operations mathematically, we can
always translate such a proof into the proof of some mathematical theorem.
This was the case classically too, but in the absence of interference
effects it is always possible to note down the steps of the computation,
and thereby produce a proof that satisfies the classical definition: ‘a
sequence of propositions each of which is either an axiom or follows from
earlier propositions in the sequence by the standards rules of inference’.
Now we must leave that definition behind. Henceforward, a proof must be
regarded as a process --- the computation itself, not a record of all its
steps --- for we must accept that in future, quantum computers will prove
theorems by methods that neither a human brain nor any other arbiter will
ever be able to check step-by-step, since if the ‘sequence of
propositions’ corresponding to such a proof were printed out, the paper
would fill the observable universe many times over.
Concluding
remarks
Experimental and theoretical research in quantum computation is now
attracting increasing attention from both academic researchers and
industry worldwide. The idea that nature can be controlled and manipulated
at the quantum level is a powerful stimulus to the imagination of
physicists and engineers. There is almost daily progress in developing
ever more promising technologies for realising quantum computation and new
quantum algorithms with various advantages over their classical
counterparts. There is potential here for truly revolutionary
innovation.
Further
reading
The newly established Centre for
Quantum Computation at the University of Oxford has several WWW pages
and links devoted to quantum computation and cryptography. Some of the
deeper implications of quantum computing are discussed at length in The
Fabric of Reality by David Deutsch (Allen Lane, The Penguin Press,
1997). The discovery of public key cryptography by GCHQ is described on
the CESG web pages.
Bibliography
[1] Grover, L. K. "A Fast Quantum Mechanical Algorithm for Database
Search" Proceedings of the 28th Annual ACM Symposium on the Theory of
Computing, Philadelphia, (1996) pp. 212-219.
[2] Brassard, G., Science vol. 275, p. 627 (1997).
[3] Shor, P. "Algorithms for quantum computation: discrete logarithms
and factoring" Proceedings 35th Annual Symposium on Foundations of
Computer Science, Santa Fe, NM, USA, 20-22 Nov. 1994, IEEE Comput. Soc.
Press (1994) pp. 124-134.
[4]. Wiesner, S. "Conjugate Coding" SIGACT News, Vol. 15, 1983, pp.
78-88; Brassard, G. and Bennett, C.H., Proceedings of the IEEE
International Conference on Computer Systems and Signal Processing, 1984,
p. 175 Ekert, A. "Quantum Cryptography Based on Bell's Theorem" Physical
Review Letters, Vol. 67 1991 pp. 661-663.
[5] Feynman, R. P. "Simulating Physics with Computers" International
Journal of Theoretical Physics, Vol. 21 (1982) pp. 467-488.
[6] Deutsch, D. "Quantum Theory, the Church-Turing Principle, and the
Universal Quantum Computer" Proc. Roy. Soc. Lond. A400 (1985) pp.
97-117.
[7] Deutsch, D. "Quantum computational networks" Proceedings of the
Royal Society of London, Series A (8 Sept.1989) vol.425, no.1868, pp.
73-90.
[8] Huelga, S.F., Macchiavello, C., Pellizzari, T., Ekert, A.K.,
Plenio, M.B., and Cirac, J.I., Physical Review Letters (1998), vol. 79,
3865.
Updated for web publication by Wim van Dam (June 1999)
