Quantum Information and Computation - Nature
Quantum Information and Computation - Nature
Quantum Information and Computation - Nature
In information processing, as in physics, our classical world view provides an incomplete approximation to an underlying quantum
reality. Quantum effects like interference and entanglement play no direct role in conventional information processing, but they
can—in principle now, but probably eventually in practice—be harnessed to break codes, create unbreakable codes, and speed
up otherwise intractable computations.
Information and computation theory have undergone a spurt of classical information and quantum entanglement. Classical infor-
new growth, and a renewal of their historic connection to basic mation can be copied at will, but can only be transmitted forward in
physics, as they have expanded to treat the intact transmission and time, to a receiver in the sender’s forward light cone. Entanglement
processing of quantum states, and the interaction of such ‘quantum in contrast, cannot be copied, but can connect any two points in
information’ with traditional forms of information. We may space–time. Conventional data processing operations destroy
wonder why this did not happen earlier, as quantum principles entanglement, but quantum operations can create it and use it for
have long been accepted as fundamental to all of physics. Perhaps various purposes, such as speeding up certain classical computa-
the founders of information and computation theory, such as tions and assisting in the transmission of classical information or
Shannon, Turing and von Neumann, were too accustomed to intact quantum states. Part of the new quantum information theory
thinking of information processing in macroscopic terms, not yet is the qualitative and quantitative study of entanglement, and its
having before them the powerful examples of the genetic code and interactions with classical information.
ever-shrinking microelectronics. Be that as it may, information until Any means, such as an optical fibre, of delivering quantum
recently has largely been thought of in classical terms, with quantum systems more or less intact from one place to another, may be
mechanics playing a supporting role in the design of the equipment viewed as a quantum channel. Unlike classical channels, which are
to process it, and setting limits on the rate at which it could be sent well characterized by a single capacity, quantum channels have
through certain channels. Now we know that a fully quantum several distinct capacities, depending on what one is trying to use
theory of information and information processing offers, among them for, and what auxiliary resources are brought into play.
other benefits, a brand of cryptography whose security rests on New effects involving quantum information continue to be
fundamental physics, and a reasonable hope of constructing quan- discovered, not only in the traditional areas of computation,
tum computers that could dramatically speed up the solution of channel capacity, and cryptography, but in areas such as commu-
certain mathematical problems. These benefits depend on distinc- nication complexity and game theory.
tively quantum properties such as uncertainty, interference and
entanglement. Theory of quantum data and data processing
At a more fundamental level, it has become clear that an Quantum data. How, then, does quantum information, and the
information theory based on quantum principles extends and operations that can be performed on it, differ from conventional
completes classical information theory, just as complex numbers digital data and data-processing operations? A classical bit (such as a
extend and complete the reals. Besides quantum generalizations of memory element or a wire carrying a binary signal) is generally
classical notions such as sources, channels and codes, the new theory a macroscopic system, and is described by one or more con-
includes two complementary, quantifiable kinds of information— tinuous parameters such as voltages. Within this parameter space
Fault-tolerant computation By classical fault-tolerant gate arrays By quantum fault-tolerant gate arrays
Quantum computational speed-ups Factoring: exponential speed-up; search: quadratic speed-up; iteration,
parity: no speed-up; simulation of quantum systems: up to exponential
speed-up
...................................................................................................................................................................................................................................................................................................................................................................
Communication primitives Transmitting a classical bit Transmitting a classical bit; transmitting a qubit; sharing an EPR pair
Noiseless coding techniques Classical data compression Quantum data compression; entanglement concentration
Noisy-channel capacities Classical capacity C1 equals maximum mutual information Classical capacity C > C1 ; unassisted quantum capacity Q < C;
through a single channel use classically assisted quantum capacity Q2 > Q; entanglement-assisted
classical capacity CE > C
Communication complexity Bit communication cost of distributed computation Qubit cost, or entanglement-assisted bit cost, can be less
...................................................................................................................................................................................................................................................................................................................................................................
Secret cryptographic key agreement Known protocols insecure against quantum computer Secure against general quantum attack and unlimited computing
Two-party bit commitment Known protocols insecure against quantum computer Insecure against attack by a quantum computer
...................................................................................................................................................................................................................................................................................................................................................................
NATURE | VOL 404 | 16 MARCH 2000 | www.nature.com © 2000 Macmillan Magazines Ltd 247
review article
two well-separated regions are chosen by the designer to represent 0 Logical operations. Just as any classical computation can be
and 1, and signals are periodically restored toward these standard expressed as a sequence of one- and two-bit operations (for
regions to prevent them from drifting away due to environmental example, NOT and AND gates), any quantum computation can
influences, crosstalk, and finite manufacturing tolerances. An n-bit be expressed as a sequence of one- and two-qubit quantum gates,
memory can exist in any of 2n logical states, labelled 000…0 to that is, unitary operations acting on one or two qubits at a time1
111…1. Besides storing binary data, classical computers manipulate (compare with Fig. 1). The most general one-qubit gate is described
it; a sequence of boolean operations (for example, NOT and AND) by a 2 3 2 unitary matrix (ag bd) mapping |0i to aj0i þ bj1i and |1i to
acting on the bits one or two at a time is sufficient to realize any gj0i þ dj1i. One-qubit gates can easily be implemented physically,
deterministic transformation. for example, by quarter- and half-wave plates acting on polarized
A quantum bit or ‘qubit’ in contrast, is typically a microscopic photons, or by radio-frequency tipping pulses acting on nuclear
system, such as an atom or nuclear spin or photon. The boolean spins in a magnetic field.
states 0 and 1 are represented by a fixed pair of reliably distinguish- The standard two-qubit gate is the controlled-NOT or XOR gate,
able states of the qubit (for example, horizontal and vertical photon which flips its second (or ‘target’) input if its first (‘control’) input is
polarizations: j0i ¼ ↔, j1i ¼ ↕). A qubit can also exist in a con- |1i and does nothing if the first input is |0i. In other words it
tinuum of intermediate states or ‘superpositions’, represented interchanges |10i and |11i while leaving |00i and |01i unchanged.
mathematically as complex linear combinations of the basis states Unlike one-qubit gates, two-qubit gates are difficult to realize in the
|0i and |1i. For photons, these states correspond to other polariza- laboratory, because they require two separated quantum informa-
tions, for example ¼ Î 12 ðj0i þ j1iÞ, ¼ Î 12 ðj0i þ j1iÞ and tion carriers to be brought into strong and controlled interaction.
↔
by another, but no measurement can reliably distinguish ↔ from . would yield |w,wi, but this is not so. The unitarity of quantum
↔
A pair of qubits (for example, two photons in different locations) evolution requires that a superposition of input states evolve to a
is capable of existing in four boolean states, |00i, |01i, |10i and |11i, corresponding superposition of outputs. Thus the result of applying
as well as all possible superpositions of them. These include states UXOR to |w,0i must be aj0; 0i þ bj1; 1i, an entangled state in which
such as neither output qubit alone has a definite state. If one of the
q q entangled output qubits is lost (for example, discarded, or allowed
1
ðj00i þ j01iÞ ¼ j0i # 12ðj0i þ j1iÞ ¼ ↔ ð1Þ to escape into the environment), the other thenceforth behaves as if
↔
2
it had acquired a random classical value 0 (with probability |a|2) or
which is describable as a tensor product
p of states of the individual 1 (with probability |b|2). Unless the lost output is brought back into
photons, as well as states such as 12ðj00i þ j11iÞ which admit no play, all record of the original superposition |wi will have been lost.
such description. Such ‘entangled’ states correspond to a situation This behaviour is characteristic not only of the XOR gate but of
in which neither photon by itself has a definite state, even though unitary interactions generally: their typical effect is to map most
the pair together does. unentangled initial states of the interacting systems into entangled
More generally, where a string of n classical bits could exist in any final states, which from the viewpoint of either system alone causes
of 2n boolean states x ¼ 000…0 through 111…1, a string of n qubits an unpredictable disturbance.
can exist in any state of the form Environmental interactions. Since quantum physics underlies
11…1
classical, there should be a way to represent classical data and
W¼ ^ c jxi
x¼00…0
x ð2Þ
operations within the quantum formalism. If a classical bit is a
qubit having the value |0i or |1i, a classical wire should be a wire that
conducts |0i and |1i reliably, but not superpositions. This can be
where the cx are complex numbers such that Sx jcx j2 ¼ 1. In other implemented using the XOR gate as described above, with an initial
words, a quantum state of n qubits is represented by a complex |0i in the target position which is later discarded. In other words,
vector W of unit length in a space (‘Hilbert space’) of 2n dimensions, from the viewpoint of quantum information, classical communica-
one for each possible classical state. The exponentially large dimen- tion is an irreversible process in which the signal interacts en route
sionality of this space distinguishes quantum computers from with an environment in such a way that boolean signals pass
classical analogue computers, whose state is described by a through undisturbed, but other states suffer entanglement with
number of parameters that grows only linearly with the size of the the environment. If the environment is lost or discarded, the
system. This is because classical systems, whether digital or analo- surviving signal behaves as if it had been irreversibly forced to
gue, can be completely described by separately describing the state choose one of the boolean states. Not only a classical wire, but any
of each part. The vast majority of quantum states, by contrast, are classical data processing, can be realized similarly by quantum
entangled, and admit no such description. The ability to preserve processing supplemented by interaction with a quantum environ-
and manipulate entangled states is the distinguishing feature of ment that is later discarded.
quantum computers, responsible both for their power and for the Paradoxically, entangling interactions with the environment are
difficulty of building them. thought to be the main reason why the macroscopic world seems to
An isolated quantum system evolves in such a way as to preserve behave classically and not quantum-mechanically2. Macroscopically
superpositions and distinguishability; such evolution, called ‘uni- different states, for example, the different charge states representing
tary’, is the Hilbert-space analogue of rigid rotation in real space, 0 and 1 in a VLSI (very large scale integration) memory cell, interact
and is another important difference between quantum and analo- so strongly with their environment that information rapidly leaks
gue systems. Unitary evolution and superposition are the central out as to which state the cell is in. Therefore, even if it were possible
principles of quantum mechanics. to prepare the cell in a superposition of 0 and 1, the superposition
248 © 2000 Macmillan Magazines Ltd NATURE | VOL 404 | 16 MARCH 2000 | www.nature.com
review article
would rapidly evolve into a complex entangled state involving the be used to perform arbitrarily long classical computations reliably,
environment, which from the viewpoint of the memory cell would provided the error probability per gate is less than some constant
appear as a statistical mixture, rather than a superposition, of the threshold. Because of QFTC, it appears that experimentalists need
two classical values. The spontaneous decay of superpositions into ‘only’ build quantum hardware with a per-gate decoherence that is
mixtures is known as decoherence. below some finite threshold (variously estimated at 10−6 to 10−2,
Entanglement with the environment is thus a major obstacle to with a similar precision for individual gate rotations) in order for
quantum computation. To avoid having a quantum computation quantum computers to do arbitrarily complex computations.
decohere into a probabilistic classical computation (which could With this background we survey some of the main parallels and
just as well be done on a classical computer) it is necessary, while differences between quantum and classical information processing.
creating and maintaining entanglement among the computational Quantum speed-up of classical computation. This is potentially
degrees of freedom, to avoid entanglement between them and the the most important application of quantum data processing. By
environment. Until recently it appeared that the feasible number of using quantum gates and wires, with entangled states flowing
steps in a coherent quantum computation would necessarily be less through them in the intermediate stages of a computation, certain
than the ratio td/ts of decoherence time to switching time char- computations mapping classical inputs x to classical outputs f(x)
acteristic of the elementary quantum systems used in the hardware. can be done in far fewer steps than by any known sequence of
Even if all other problems in the design of a practical quantum classical gate operations. Most famously, a quantum computer can
computer could be overcome, currently attainable values of td/ts are factor large integers in time that is polynomial in the logarithm of
not high enough to make quantum computers competitive with the best classical time4,5, thereby threatening the security of crypto-
classical ones; also, the search for systems with ever-higher td/ts systems based on the presumed difficulty of factoring. This expo-
might ultimately be blocked by fundamental properties of available nential speed-up depends on the quantum computer’s ability to
atoms and nuclei. Apart from decoherence, it also appeared that vastly parallelize the performance of a fast Fourier transform, using
individual gate operations would have to be made more and more destructive interference among a number of parallel computation
precise the longer the computation. paths that increases exponentially with the number of physical
This pessimism has largely been dispelled by the discovery of qubits involved in the computation. Another class of problems for
quantum fault-tolerant computation3 (QFTC), the quantum ana- which quantum computers seem to provide exponential speed-up is
logue of von Neumann’s discovery that unreliable classical gates can the simulation of many-particle quantum systems6,7. In contrast to
these rather specialized problems, a much broader class of problems
can be speeded up quadratically, that is, solved in a time propor-
tional to the square root of the time that a classical computer would
a require. These include search and optimization problems (for
1 0 0 0
( 0
0
0
1
0
0
0
0
1
0
1
0
) U
example, given an algorithm for computing a function F, find an
input s where FðsÞ ¼ 0, or an input s where F(s) is a minimum)8,9.
For some other problems there is no quantum speed-up. These
U
include iterated function evaluation10,11 (for example, given an
U ( αγ βδ ) algorithm for computing F, compute the nth iterate
F ðnÞ ¼ FðFðF…ð:ÞÞ…ÞÞ for large n) and computing the parity of a
random set12,13.
Quantum information theory. This generalizes the classical
b c notions of source and channel, and the related techniques of
|1 =
source and channel coding, as well as introducing a new resource,
entanglement, which interacts with classical and quantum informa-
|0 =
= tion in a variety of ways that have no classical parallel.
As mentioned earlier, quantum channels have several distinct
+ |0 capacities, depending on what one is trying to use them for, and
=
2
( +( what auxiliary resources are brought into play. These include the
following:
Classical capacity, C, equal to the maximum rate at which classical
2
bits can be transmitted reliably through the channel;
d Quantum capacity, Q, the maximum rate at which intact qubits can
be transmitted reliably through the channel;
Q Classically-assisted quantum capacity, Q2, defined as the maximum
= U rate at which qubits can be transmitted reliably through the channel,
|0 with the help of unlimited two-way classical communication
|0
between sender and receiver; and
|0
Entanglement-assisted classical capacity, CE, defined as the max-
imum rate for sending classical bits through the channel, with the
help of unlimited prior entanglement between sender and receiver.
Figure 1 Quantum logical operations. a, Any unitary operation U on quantum data can be These capacities obey the relation Q < Q2 < C < C E for all known
synthesized from the two-qubit XOR or controlled-NOT gate, and one-qubit unitary channels, but otherwise appear to vary rather independently, and
operations U. b, The XOR acts as a classical cloner on boolean valued inputs, but if one are not easy to calculate from the quantum channel parameters,
attempts to clone intermediate values, the cloning fails and an entangled state (blue) again, unlike the single capacity of classical channels.
results instead. c, A classical wire (thick line) conducts 0 and 1 faithfully but not Quantum data compression and error correction. The two central
superpositions or entangled states. It may be defined as a quantum wire that interacts (via techniques of classical information theory, source and channel
an XOR) with an ancillary 0 qubit which is then discarded. d, The most general treatment, coding, have direct quantum analogues; a quantum source is an
or superoperator, Q that can be applied to quantum data is a unitary interaction with one entity that emits quantum states wi with probabilities pi, and a
or more 0 qubits, followed by discarding some of the qubits. Superoperators are typically channel is an entity, such as an optical fibre, that transmits quantum
irreversible. states more or less reliably from a sender to a receiver.
NATURE | VOL 404 | 16 MARCH 2000 | www.nature.com © 2000 Macmillan Magazines Ltd 249
review article
The von Neumann entropy of a quantum source, S ¼ for quantum channels, because it may depend on using a quantum
2 Trrlog2 r, where r ¼ Si pi jwi ihwi j, determines the minimum encoder to prepare inputs entangled over multiple uses of the
asymptotic number of qubits into which its signals can be com- channel, and/or a quantum decoder to perform coherent measure-
pressed by a quantum encoder and still be faithfully recovered by a ments on multiple channel outputs. Unlike any classical channel,
quantum decoder. This is the analogue of classical data compression some quantum channels are superadditive, in the sense that more
or source coding, by which redundant classical data is compressed classical information can be sent through n parallel uses of the
and faithfully regenerated, but quantum data compression14 differs channel than n times the amount that can be sent through one use of
in that it can be applied to non-orthogonal states (for example, the channel24–28.
equally probable horizontal and diagonal photons, as shown in Entanglement-assisted communication. Two forms of quantum
Fig. 2a) which would be spoiled if one tried to compress them information transmission that have no classical counterpart, but are
classically. Also, because the states are non-orthogonal, the encoder closely related to each other, are quantum teleportation29 (Fig. 3a)
cannot retain a copy of them, or indeed any memory of them, if they and quantum superdense coding30 (Fig. 3b). These involve an initial
are to be faithfully reconstructed at the receiving end. A quantum stage
pin
which a pair of particles in a maximally-entangled state such
encoder is like a discreet telegrapher, who transmits messages as 12ðj00i þ j11iÞ (often called an Einstein–Podolsky–Rosen or
without remembering them. EPR pair) is shared between two parties, followed by a second stage
Source coding removes redundancy, allowing data to be sent in which this shared entanglement is used to achieve, respectively,
more efficiently through a noiseless channel. Error-correction or transmission of a qubit via two classical bits, or transmission of two
channel coding, in contrast, introduces redundancy to enable data classical bits via one qubit. Quantum teleportation illustrates the
to withstand transmission through a noisy channel. The simplest fact that transmission of intact quantum states requires two quali-
classical error-correcting code is the triple repetition code 0 → 000, tatively different resources: a quantum resource that cannot be
1 → 111, which permits the encoded bit to be faithfully recovered cloned, and a directed resource that cannot travel faster than light.
after up to one transmission error in the three-bit codeword. In direct transmission of a qubit, these two functions are performed
Analogous error-correcting codes exist for quantum data, but by the same particle. In teleportation the former function is
they require more redundancy because they need to protect not provided by the shared EPR pair, the latter by the two classical
only boolean states, but also arbitrary superpositions of them15–20. bits. This situation may be summarized by saying that classical
Thus the simplest single-error-correcting quantum code (Fig. 2b) information theory involves one species of information, and one
encodes an arbitrary input qubit |wi into an entangled state of five kind of noiseless communication primitive (transmission of a bit),
qubits, in such a way that if any one is corrupted en route, the whereas quantum information theory involves two species (classical
decoder can funnel the effects of the error into the four ancillary qubits, information and entanglement), and three primitives (transmitting
while restoring the first qubit to its original state. Analogously to a bit, transmitting a qubit, and sharing an EPR pair) which are
classical capacity, the quantum capacity Q of a noisy channel can be related through superdense coding and teleportation.
defined as the limiting ratio of faithfully transmitted qubits per Superdense coding (Fig. 3b) is an example of entanglement-
noisy-channel use that is achievable by quantum error-correcting assisted classical communication, and shows that C E ¼ 2 for the
codes. This quantum capacity is usually less, and can never be noiseless qubit channel, while C ¼ Q ¼ 1. Surprisingly, the ratio
greater, than the same channel’s capacity C for transmitting classical
bits. The inequality Q < C holds for all channels because if a a
channel can faithfully transmit a general qubit, then it can certainly
transmit the particular qubits |0i and |1i.
The discovery of quantum error-correcting codes in 1995 came as
a great surprise, probably because people were used to thinking of U U –1
classical error correction in language unsuited to quantum generali-
zation. For example, triple repetition, if it is taken to mean making
three copies of the input qubit (w → w # w # w), flies in the face of
the well-known impossibility of exactly copying (‘cloning’) an
unknown quantum state. In retrospect, the natural quantum gen-
eralization of triple repetition can be seen instead to be the mapping
aj0i þ bj1i → aj000i þ bj111i, which does not violate any quan- b
tum principle and indeed suffices to correct single qubit errors in |ψ |ψ
any boolean input. As noted above, two more bits of redundancy are |0
needed to extend the protection to non-boolean inputs. Although |0
analogous in structure to classical discrete error-correcting codes, |0 U U –1
quantum error-correcting codes have the remarkable ability to |0
protect a continuum of inputs from a continuum of errors. For
example, in Fig. 2b, the input qubit might be a photon of any
polarization state, and the error (red) might be a rotation of one of
the five channel qubits’ polarizations by an arbitrary amount;
nevertheless, the error would be corrected. This is a beneficial side
effect of the linearity of quantum mechanics: if a quantum error- Figure 2 Quantum data compression and error correction. a, In quantum data
correcting code protects a sufficiently rich discrete set of inputs compression, inputs from a redundant source (here, an unknown sequence of horizontal
from a sufficiently rich discrete set of error processes, then it will and diagonal photons) are unitarily transformed into an entangled state (blue) in which
also protect any superposition of those inputs from any super- almost all the information has been concentrated into some of the photons, allowing the
position of those errors. Besides the simple capacities C and Q, others to be discarded. At the receiving end of the channel the discarded photons are
quantum channels have assisted capacities Q2 and CE mentioned replaced by standard (horizontal) photons and the unitary transformation is undone,
above, which will be discussed later. resulting in a close approximation to the original state. b, A quantum error-correcting code
The oldest branch of quantum information theory21–23 concerns with unitary encoder and decoder. An arbitrary input qubit |wi is entangled with four
the use of quantum channels to transmit classical information. Even standard |0i qubits in such a way that if any one of the five qubits is spoiled, the decoder
the seemingly pedestrian classical capacity C is not easy to calculate can still restore the original state exactly.
250 © 2000 Macmillan Magazines Ltd NATURE | VOL 404 | 16 MARCH 2000 | www.nature.com
review article
CE/C typically increases with increasing noise, and indeed can attain tative measures of entanglement, and to know whether all entangled
arbitrarily large values for channels so noisy that their quantum states (those not expressible as products of states of their parts, or
capacities Q and Q2 both vanish31. Thus, unlike most quantum probabilistic mixtures of such products) can be converted into EPR
effects, entanglement enhancement of a quantum channel’s classical pairs, and if so, how efficiently. In the case of bipartite pure states,
capacity does not disappear in the limit of large noise. In this respect entanglement is naturally measured by the state’s entropy of
it resembles the ability of bulk nuclear magnetic resonance systems entanglement, the von Neumann entropy of either subsystem
to carry out nontrivial quantum computations while remaining considered alone. For such states40–42 the entropy of entanglement
close to thermal equilibrium. E(W) is equal both to the state’s entanglement of formation—the
Superdense coding and teleportation have received much labora- number of EPR pairs asymptotically required to prepare one
tory attention recently. The first work was by the Innsbruck group32, instance of the state by classical communication and local opera-
which implemented a version of superdense coding in which three tions—and its distillable entanglement—the number of pure EPR
distinguishable states (rather than the theoretical maximum of pairs that can be asymptotically prepared from one instance of the
four) are created by manipulating one member of an EPR pair of state by classical communication and local operations.
polarization-entangled photons. Teleportation using these photon For mixed states, and states of three or more parties, the situation
states was more recently achieved by the same group33; by using is more complicated, and there are several non-equivalent kinds of
these techniques several other protocols involving entanglement, entanglement. Multipartite states, pure and mixed, have been
for example, the creation of three-particle entanglement, has studied43–45. Mixed states generally have a distillable entanglement
become possible. An experimentally different approach in which that is less than their entanglement of formation, reflecting the
another attribute of one of the EPR photons (such as its position) is irreversibility of the mixing process. An extreme form of this
teleported has been implemented in Rome34. This experiment is phenomenon is the existence of so-called ‘‘bound’’ entangled
easier in that it involves two rather than three photons. A very recent states46 —mixed states which are entangled, but from which no
experiment35 has followed more directly a version of a teleportation pure entanglement can be distilled.
scheme due to Vaidman36, in which continuous quantum degrees of Entanglement distillation is important not only for quantifying
freedom are teleported. This work demonstrates that an arbitrary entanglement but as a distinctively quantum kind of error correc-
quantum state of one optical mode can be teleported with good tion, complementary to the use of quantum error-correcting
fidelity; taking into account limitations on the intensity of the codes20,47,48. Suppose Alice and Bob can communicate classically,
mode, one finds that roughly a one-million-state quantum system is and in addition have access to a noisy quantum channel. Now Alice
involved, in contrast to the two-state systems used in the earlier wants to send an unknown qubit reliably to Bob. If the quantum
work. Finally, the operations necessary to teleport a nuclear spin channel is not too noisy, she can encode the input qubit into several
state have been performed using nuclear magnetic resonance37, qubits using a quantum error-correcting code as in Fig. 2b, send
although the range of teleportation is only the distance across a these through the noisy channel, and have Bob decode them.
single molecule. However for very noisy channels, such as a 50% depolarizing
Although entanglement by itself cannot be used to transmit a channel, this will not work, because such channels have zero
classical message, it can reduce the amount of classical commu- quantum capacity Q ¼ 0. In this case the best known strategy is
nication required to perform a distributed computation13,38,39. for Alice not to send the input qubit through the channel at all, but
Classically, ‘communication complexity’ refers to the amount of instead prepare a number of pure EPR pairs, and share them
communication needed to evaluate a function of several inputs in through the noisy channel with Bob (resulting in noisy EPR
remote locations. For example, if Alice and Bob each have appoint- pairs). Then, using their ability to communicate classically, Alice
ment calendars with n time slots, O(n) bits of communication are and Bob distill a smaller number of good EPR pairs from the larger
required to determine if there is a time when they are both free. If supply of noisy ones. Finally, Alice uses one of the good EPR pairs,
they are allowed to share prior entanglement, or if they are allowed and additional classical communication, to teleport the input qubit
to communicate using qubits rather than bits, the communication
p safely to Bob. The ability of entanglement distillation to salvage such
complexity of this problem is reduced from O(n) to Oð n log nÞ. noisy EPR pairs gives rise to a fact noted earlier, that for many
Quantifying and distilling entanglement. Because of its usefulness channels the classically-assisted quantum capacity Q2 exceeds the
in protocols such as teleportation, it is important to have quanti- direct quantum capacity Q. (However, this advantage depends on
two-way classical communication between Alice and Bob—if they
a
are limited to one-way communication, distillation is no more
efficient than quantum error-correcting codes.) As a function of
|ψ increasing noise, a typical quantum channel passes through two
Alice
thresholds; a noise level beyond which Q vanishes but Q2 and C
EPR remain positive; and a threshold beyond which Q2 vanishes but C
Bob
|ψ remains positive.
Quantum fault-tolerant computation. QFTC is both an expansion
of research in the theory of quantum information processing and a
b
practical necessity for implementing non-trivial quantum compu-
tation in the laboratory. Modern QFTC has been well reviewed (see
x x ref. 3 and references therein); some of the basic ideas are sketched in
y Bob y
Fig. 4. To avoid irrecoverable damage from a single error, an
EPR x appropriate quantum error-correcting code is used to spread the
Alice y logical state |wL i being stored or processed over several physical
qubits, carried by a bundle of parallel wires. Periodically the bundle
Figure 3 Quantum information transmission between a sender (Alice) and a receiver passes through a restorative gate array R, where it interacts with
(Bob). a, In quantum teleportation, prior sharing of an EPR pair, and transmission of a two- clean ancilla qubits from the environment, in order to correct the
bit classical message from Alice to Bob suffice to transmit an unknown quantum state errors by funnelling them into the ancillas, which are then dis-
even when no direct quantum channel from Alice to Bob is available. b, In quantum dense carded. Additional errors may occur during the restoration process
coding, prior sharing of an EPR pair, and transmission of a single qubit from Bob to Alice, itself, but if these are not too numerous they will be corrected by a
suffice to transmit an arbitrary two-bit classical message (x,y). subsequent restoration step (Fig. 4a). Such a regimen of active
NATURE | VOL 404 | 16 MARCH 2000 | www.nature.com © 2000 Macmillan Magazines Ltd 251
review article
restoration can be used to implement a fault-tolerant quantum allowed by the laws of quantum mechanics, and should also be able
memory, able to hold quantum states reliably for much longer than to cope with noise under the realistic assumption that it arises not
the natural decoherence times of the hardware of which the array is only from eavesdropping but also from noisy channels and detec-
built. Apart from the fact that it operates on quantum rather than tors. Finally, it should provide a way of calculating a safe rate of key
classical data, this is entirely analogous to devices such as the generation as a function of the noise level observed by Alice and
dynamic random access memory (DRAM) used in today’s compu- Bob. Recent proofs50,51 building on a long history of previous
ters, in which periodic signal restoration serves to delay the decay of security proofs against more limited attacks48,49,52,53, have largely
the stored data almost indefinitely. To perform quantum computa- met these criteria, the main remaining problems being to simplify
tion fault-tolerantly, it is also necessary, besides storing the data, to the proofs, improve the error thresholds, and to extend them to
perform gate operations on it without decoding it from its protected cover realistic sources, which do not emit exact single-photon states
form. For some gates, such as the XOR, this can be done in a or exact EPR pairs, and in extreme cases may even have been
straightforward fashion, by applying the gate operation successively sabotaged by Eve.
to wires in a bundle (Fig. 4b). Other gate operations, including some Given the success of quantum key distribution, there was high
necessary single-qubit rotations, must be implemented in a more hope that quantum techniques could help with another task, two-
complex fashion, involving preparation and testing of special party oblivious function evaluation, a better name for which might
entangled states of a set of ancilla qubits, which are then brought be ‘‘discreet decision-making’’. This is the task, which arises fre-
into interaction with the encoded data to perform the desired logical quently in commerce and diplomacy, of enabling two mutually
transformation3. distrustful parties to cooperate in evaluating a publicly agreed
The promise of quantum computation lies in the fact that, to function of private data held separately by each party, without
perform a t-step computation fault-tolerantly, the number of gates compromising the private data any more than it would have been
and wires need only be multiplied by a factor polynomial in log t. compromised had they assigned the job of evaluating the function
Therefore, for computations with a significant quantum speed-up, a to a trusted intermediary. Initially Alice knows data x and Bob
quantum computer would still vastly outperform any classical knows data y; when the protocol is finished, Alice and Bob should
computer on sufficiently large inputs. each also know f(x,y), but neither party should know any more
Quantum cryptography. This is the art of applying the unique about the other party’s private input than can logically be inferred
properties of quantum systems to cryptographic goals, that is, the from a knowledge of their own data and the common function value
protection of classical information from tampering or unauthorized f(x,y). Classical protocols for oblivious function evaluation exist,
disclosure in a multi-party setting where not all the parties trust one but, like classical key agreement protocols, they are not informa-
another. This adversarial element distinguishes it from the kinds of tionally secure and could be broken by a quantum computer. Hopes
quantum information processing considered earlier. for finding a quantum basis for absolutely secure oblivious function
One important quantum cryptographic task, quantum key dis- evaluation were dashed by the discovery that a fundamental build-
tribution has as its goal the sharing of a secret random bit string K, ing block of all known oblivious function evaluation protocols,
called a cryptographic key, between the two protagonists Alice and called bit commitment, is insecure in principle against quantum
Bob, who have at their disposal an insecure quantum channel and a attacks54,55. Bit commitment is the idealization of a protocol in
public classical channel. (Purely classical protocols for key agree- which Alice sends Bob a locked box containing a bit 0 or 1 of her
ment exist and are in widespread use, but these result in a key that is choosing, written on a piece of paper, then later, at a time of her
not informationally secure—an adversary with sufficient comput- choosing, sends him the key so that he can open the box and then
ing power could infer it from the public messages exchanged read the bit. Quantum bit commitment is insecure because of a
between Alice and Bob. In particular, the most widely used classical fundamental property of entangled states, namely that if two pure
key agreement protocols could be easily broken by a quantum states of the Alice–Bob system are indistinguishable to Bob, they
computer, if one were available.) In quantum key distribution, an must be interconvertible by a local action of Alice; thus there is in
eavesdropper (‘Eve’) is allowed to interact with the quantum principle no way of implementing a locked box containing a bit
information carriers (for example, photons) en route from Alice value that is both unmodifiable by Alice and unobservable by Bob.
to Bob—at the risk of disturbing them—and can also passively The similarities and differences between classical and quantum
listen to all classical communication between Alice and Bob, but she information are summarized in Table 1.
cannot alter or suppress the classical messages. Sometimes (for
example, if Eve jams or interacts strongly with the quantum signals) Experimental studies of quantum information
Alice and Bob will detect the excessive eavesdropping and abort the The continuing maturation of the theory of quantum information
protocol; but, for every eavesdropping strategy, Eve’s probability of and quantum computation has stimulated experimental work in a
remaining undetected and obtaining significant information on the great variety of disciplines, in optics and quantum optics, in single-
key should be negligible. atom and single-ion research, and in several areas of precision
The practical implementation of quantum key distribution is spectroscopy. We will touch on some of the progress along these
much farther advanced than other kinds of quantum information lines here. We will not mention here the very interesting prospects of
processing, owing to the fact that the standard quantum key using solid-state quantum technology—quantum dots, semicon-
distribution protocols require no two-qubit interactions, only ductor microcavities, ultrasmall Josephson junctions, and so
preparation and measurement of simple quantum states, along forth—to achieve quantum gate operation, which apparently lie
with classical communication and computations. Optical proto- several years further into the future.
types working over tens of kilometres of fibre, or even through a ‘Flying qubits’ will be needed to implement many of the quantum
kilometre of open air at night, have been built and tested. In processing protocols described above. Because of developments in
principle, however, a quantum key distribution protocol could quantum cryptography, high-quality flying qubits in the form of
involve quantum computations by Alice and Bob; and to be sure photons travelling on optical fibres are now produced routinely in
of its security, one ought to allow Eve the full power of a quantum several laboratories. An important innovation, introduced by the
computer, even though Alice and Bob do not need one for the Gisin group at the University of Geneva56, helps to make reliable
standard protocols. photon transmission through unreliable fibres a possibility. It
Various proofs of security of quantum key distribution protocols, involves the use of a Faraday mirror, which reflects any light that
especially the four-state ‘‘BB84’’ protocol of ref. 49, have been strikes it into an orthogonal polarization. In their scheme a strong
offered. A complete security proof should encompass all attacks coherent-state double pulse of light is sent from Bob to Alice on an
252 © 2000 Macmillan Magazines Ltd NATURE | VOL 404 | 16 MARCH 2000 | www.nature.com
review article
optical fibre; Alice attenuates it to one-photon intensity, sets the elementary functioning prototype. Optical quantum electrody-
relative phase of the two pulses to obtain one of four quantum states namics (QED) experiments have not succeeded in entangling the
of the photon, and finally Faraday-reflects this photon back to Bob. states of two ‘standing qubits’, but such entanglement has been
The Faraday reflection ensures that any distortions or variations of achieved in experiments in related areas, in microwave cavity QED
the propagating light mode due to birefringence (anisotropy of the (ref. 63) and in ion-trap studies64.
index of refraction) in the photon transmission from Bob to Alice Unfortunately, the controllable creation of entanglement with
are undone in the return transmission. With this invention a two-qubit quantum gates is only one of a formidable checklist of
remarkable interferometric stability is attained: the fringe visibility ingredients that a physical experiment must have if it is to realize a
of their 23-km transmission system used as an interferometer has quantum computer. There are at least four other milestones which
reached 99.98%, implying that the phase of the photon is reliable to must be achieved66: (1) The system should be extendible to a large
0.03 radians. This means that high-purity quantum states of light number of qubits. (2) It must be possible to place the qubits reliably
are being successfully transmitted in this system. in the ‘‘0’’ or cleared state at the outset. (3) The decoherence rate
Their ability to store and process qubits with ‘standing qubits’ can must, as explained above, be very low (that is, below some suitable
greatly augment the capabilities of ‘flying qubits’ for the processing threshold). (4) It must be possible to do single-quantum sensitivity
of quantum information. For example, the ability to do quantum measurements (if only one copy of the quantum computer is
computation in conjunction with quantum communication would available) or an accurate ensemble measurement in a qubit-specific
qualitatively enhance the ability to do quantum cryptography, fashion (if many copies of the quantum computer are available).
permitting the use of quantum repeater elements and opening up A full-scale experiment of any type to realize all of these criteria
new techniques for defeating eavesdropping, as well as permitting simultaneously is still a long way off. In the area of ion-trap research,
cryptography over indefinitely long distances57,58. With this in mind, concerted efforts are being undertaken by a number of experimental
workers have proposed a marriage of techniques from photon-fibre groups to realize the original Cirac and Zoller proposal67 for ion-
systems and trapped-atom (or ion) systems. In these schemes60,61, a trap quantum computing, which created great excitement and
‘standing qubit’ encoded in a state of the atom is mapped by an interest five years ago. The proposal of these authors was nothing
appropriate laser pulse59 into the same qubit state of the photon less than a scheme for realizing all of the requirements for quantum
state of a surrounding electromagnetic cavity, and can from there computation mentioned above: qubits are to be represented by the
become a ‘flying qubit’ by leaking out into a propagating mode in internal (spin) states of individual ions held in the electromagnetic
free space or in an optical fibre. The unexpected feature of this trap; extending the number of qubits is to be achieved by adding
procedure is the next step, in which the propagating photon then more atoms to the trap. The techniques of laser cooling would serve
impinges on a replica of the sending system. If the photon wave to put the system in the ‘‘0’’ state. Coupling to the environment in
packet has been tailored properly, this cavity–atom system can be the ion trap is low, and thus qubits with acceptable decoherence
made to recapture the photon into the atomic state by a suitable properties are known. The technique known as quantum-jump
time-reverse of the sending procedure. spectroscopy provides for the possibility of virtually single-quan-
Although extensions of the original two-bit gate demonstration tum measurements of almost 100% efficiency. The heart of the
in cavity quantum electrodynamics62 have brought us closer to this proposal is a detailed scheme for the realization of two-qubit
goal of marrying flying and standing qubits we do not yet have an quantum operations: their procedure involves a coupling of the
internal ion state with the quantum state of vibration of the ions in
the trap. Because these oscillations involve collective modes of all the
ions, entanglement of the internal ion states becomes possible.
a
Unfortunately, one feature of the Cirac–Zoller computer—cooling
to the ground state of motion of the trap—has proved to be very
|ψL |ψL difficult to achieve, and this essential step has only been accom-
plished reliably by one group for one65 or two64 ions.
R R While it is clear that the trap ideas are on a steady track of
|0 |0 progress, naturally workers in other fields hope that their techniques
|0 |0
|0 |0
will enable them to leapfrog the atomic physicists and get ahead in
|0 |0 the ‘quantum computer race’. The proponents of nuclear magnetic
resonance spectroscopy (NMR), as practised in organic chemistry,
have made a bold move in this direction. NMR spectroscopy has
many useful features for application to quantum computation: in a
well-understood limit of rapidly tumbling molecules in solution,
the hamiltonian of the nuclear spins of the molecule assumes a very
b simple form:
H¼ ^q j
i
i
i z þ ^J j j
i;j
i j
ij z z ð3Þ
R R
(Here jz is the angular momentum operator of the spins, q is the
Zeeman splitting, and J is the exchange interaction parameter.) This
depends only on the z-component of the nuclear spins (labelled i
and j here). A system with this hamiltonian is well adapted to
quantum computing68,69: as it commutes with all jiz operators, every
R R
computational basis state is an eigenstate. Thus, the state of the
system only changes when a resonance pulse is applied, so that the
dynamics of the system is entirely under external control. By
appropriate frequency and time selectivity, an external pulse can
Figure 4 Fault-tolerant computation. a, Fault-tolerant error-correction circuit with cold perform a very finely tailored operation, for example, flipping one
ancillas coming in and corrupted ones being discarded. b, Performing the XOR operation particular spin i if another specific spin j is up; this is the essence of
on encoded data without decoding it. the fundamental two-qubit XOR gate for quantum computing. In
NATURE | VOL 404 | 16 MARCH 2000 | www.nature.com © 2000 Macmillan Magazines Ltd 253
review article
addition, the pulse operations can be done much faster than the 7. Abrams, D. S. & Lloyd, S. Simulations of many-body Fermi systems on a universal quantum
computer. Phys. Rev. Lett. 79, 2586–2589 (1997).
decoherence time of 1–10 seconds in a well-chosen molecule. 8. Grover, L. K. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79,
Finally, in a situation in which many identical copies of the quantum 325–328 (1997).
computer are available (the many identical molecules in solution), 9. Boyer, M., Brassard, G., Hoyer, P. & Tapp, A. Tight bounds on quantum searching. Fortschr. Phys. 46,
493–506 (1998).
the readout of the final result can be accomplished by an ensemble
10. Ozhigov, Y. Quantum computers cannot speed up iterated applications of a black box. Preprint
measurement of the transverse magnetization, a standard operation quant-ph/9712051 at hhttp://xxx.lanl.govi (1997).
in NMR. 11. Terhal, B. M. Quantum Algorithms and Quantum Entanglement. Thesis, Univ. Amsterdam (1999).
After the initial proposals of refs 70 and 71, there has been a flood 12. Farhi, E., Goldstone, J., Gutmann, S. & Sipser, M. A limit on the speed of quantum computation in
determining parity. Phys. Rev. Lett. 81, 5442–5444 (1998).
of work on few-qubit systems, so numerous that we will just 13. Beals, R., Buhrman, H., Cleve, R., Mosca, M. & de Wolf, R. in Proceedings of the 39th Annual
enumerate the accomplishments in this area briefly here: the Symposium on the Foundations of Computer Science 352–361 (IEEE Computer Society Press, Los
action of two- and three-bit quantum gates has been demonstrated Alamitos, California, 1998).
in the protons in 2,3-dibromothiophene and in 1-chloro-2- 14. Jozsa, R. & Schumacher, B. A new proof of the quantum noiseless coding theorem. J. Mod. Opt. 41,
2343–2349 (1994).
nitrobenzene72, the Deutsch–Jozsa algorithm73 and the Grover 15. Shor, P. W. Scheme for reducing decoherence in quantum computer memory. Phys. Rev. A 52, 2493–
algorithm74 have been demonstrated using the H and 13C spins in 2496 (1995).
chloroform, the three H and C spins in trichlorethylene have been 16. Calderbank, A. R. & Shor, P. W. Good quantum error correcting codes exist. Phys. Rev. A 54, 1098–
1105 (1996).
used to simulate the synthesis of Greenberger–Horne–Zeilinger
17. Steane, A. Multiple particle interference and quantum error correction. Proc. R. Soc. Lond. A 452,
states75, to perform teleportation37 (see above), and to simulate the 2551–2577 (1996).
action of the three-qubit quantum error-correcting code76 (the three 18. Knill, E. & Laflamme, R. Theory of quantum error correcting codes. Phys. Rev. A 55, 900–911 (1997).
C spins in alanine were also used in this last study), protons in 19. Gottesman, D. A class of quantum error-correcting codes saturating the Hamming bound. Phys. Rev.
A 54, 1862-1868 (1996).
cytosine have been used to implement the original Deutsch 20. Bennett, C. H., DiVincenzo, D. P., Smolin, J. & Wootters, W. K. Mixed state entanglement and
algorithm77 as well as the quantum counting algorithm78, and 2,3- quantum error correction. Phys. Rev. A 54, 3824–3851 (1996).
dibromopropanoic acid has been used for some simple three-qubit 21. Helstrom, C. W. Quantum Detection and Estimation Theory (Academic, New York, 1976).
gate arrays79. 22. Kholevo, A. S. Bounds for the quantity of information transmitted by a quantum communication
channel. Problemy Peredachi Informatsii 9, 3–11 (1973); translated in Problems Inf. Transmiss. 9, 177–
The NMR practitioners are pressing on to implement more 183 (1973).
quantum information processing in molecules with larger numbers 23. Holevo, A. S. Problems in the mathematical theory of quantum communication channels. Rep. Math.
of spins. However, there are a couple of large obstacles to immedi- Phys. 12, 273–278 (1977).
24. Schumacher, B., Westmoreland, M. & Wootters, W. K. Limitation on the amount of accessible
ately going on to large-scale quantum computation; probably these
information in a quantum channel. Phys. Rev. Lett. 76, 3452–3455 (1997).
are not insuperable, but they may serve to make the progress of 25. Holevo, A. S. The capacity of the quantum channel with general signal states. IEEE Trans. Inf. Theory
NMR quantum computing no faster than that in atomic physics or 44, 269–273 (1998).
in other areas. One problem is just that the frequency-domain 26. Kholevo, A. S. Capacity of a quantum communications channel. Problemy Peredachi Informatsii 15,
3–11 (1979); translated in Problems Inf. Transmiss. 15, 247–253 (1979).
addressing which is used, in which each qubit has a distinct chemical 27. Sassaki, M., Kato, K., Izutsu, M. & Hirota, O. Quantum channels showing superadditivity in channel
shift qi, becomes difficult when the number of qubits grows large. A capacity. Phys. Rev. A 58, 146–158 (1998).
second problem (this will probably be the more immediate reason 28. Fuchs, C. A. Nonorthogonal quantum states maximize classical information capacity. Phys. Rev. Lett.
that the NMR technique will have to be radically modified to do 79, 1162–1165 (1997).
29. Bennett, C. H. et al. Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-
quantum computation at a scale much greater than about 10 qubits) Rosen channels. Phys. Rev. Lett. 70, 1895–1898 (1993).
has to do with state preparation: the spin states of the molecules in 30. Bennett, C. H. & Wiesner, S. J. Communication via one- and two-particle operators on Einstein-
the solution at room temperature are almost perfectly random, with Podolsky-Rosen states. Phys. Rev. Lett. 69, 2881–2884 (1992).
31. Bennett, C. H., Shor, P. W., Smolin, J. A. & Thapliyal, A. V. Entanglement enhanced classical capacity
a slight bias e for the zero qubit state (typically e, proportional to kBT
divided by the nuclear Zeeman energy, is of the order of 10−6). The
of noisy quantum channels. Phys. Rev. Lett. 83, 3081–3084 (1999).
32. Mattle, K., Weinfurter, H., Kwiat, P. G. & Zeilinger, A. Dense coding in experimental quantum
number of molecules in the solution starting in the correct state, communication. Phys. Rev. Lett. 76, 4656–4659 (1996).
rather than the completely random state, scales with e2−n, where n is 33. Bouwmeester, D. et al. Experimental quantum teleportation. Nature 390, 575–579 (1997).
34. Boschi, D., Branca, S., De Martini, F., Hardy, L. & Popescu, S. Experimental realization of teleporting
the number of spins in the molecule. The signal strength thus an unknown pure quantum state via dual classical and Einstein-Podolsky-Rosen channels. Phys. Rev.
becomes exponentially small in the number of qubits, and all Lett. 80, 1121–1124 (1998).
advantage gained from doing quantum computation is lost. This 35. Furusawa, A. et al. Unconditional quantum teleportation. Science 282; 706–709 (1998).
problem can be solved if e can be increased to nearly one; there are 36. Vaidman, L. Teleportation of quantum states. Phys. Rev. A 49, 1473–1476 (1994).
37. Nielsen, M. A., Knill, E. & Laflamme, R. Complete quantum teleportation using nuclear magnetic
innovative techniques in optical pumping which hold out the hope resonance. Nature 396, 52–55 (1998).
of doing this. While there is reason for optimism in these areas, we 38. Cleve, R. & Buhrman, H. J. Substituting quantum entanglement for communication. Phys. Rev. A 56,
think that it will require many years of concerted effort. 1201–1204 (1997).
We recall59 the incident at a quantum computation meeting in 39. Buhrman, H., Cleve, R. & Wigderson, A. in Proceedings of the 39th Annual ACM Symposium on the
Theory of Computing 63–68 (ACM Press, New York, 1998).
Torino in 1995, when Shor offered a bet that the first factoring of a 40. Bennett, C. H., Bernstein, H. J., Popescu, S. & Schumacher, B. Concentrating partial entanglement by
500-digit number would be accomplished by a quantum and not a local operators. Phys. Rev. A 53, 2046–2052 (1996).
classical computer. There were no takers on the other side, but some 41. Lo, H.-K. & Popescu, S. Concentrating entanglement by local actions—beyond mean values. Preprint
quant-ph/9707038 at hhttp://xxx.lanl.govi (1997).
commented that they would prefer to bet on a third possibility, that 42. Vidal, G. Entanglement monotones. Preprint quant-ph/9807077 at hhttp://xxx.lanl.govi (1998).
the Sun would burn up first. Although these sceptics have not been 43. Linden, N., Popescu, S. & Sudbury, A. Non-local properties of multi-partite density matrices. Phys.
entirely silenced, on balance we are more in agreement with Shor Rev. Lett. 83, 243–247 (1999).
than we were then. We think the odds in favour of the quantum 44. Thapliyal, A. V. On multipartite pure-state entanglement. Phys. Rev. A 59, 3336–3342 (1999).
45. Kempe, J. On multi-particle entanglement and its application to cryptography. Phys. Rev. A 60, 910–
computer have improved and will continue to increase slowly as 916 (1999).
more years of steady progress are made. M 46. Horodecki, M., Horodecki, P. & Horodecki, R. Mixed state entanglement and distillation: is there a
‘bound’ entanglement in nature? Phys. Rev. Lett. 80, 5239–5242 (1998).
47. Bennett, C. H. et al. Purification of noisy entanglement, and faithful teleportation via noisy channels.
1. Barenco, A. et al. Elementary gates for quantum computation. Phys. Rev. A 52, 3457–3467 (1995). Phys. Rev. Lett. 76, 722–725 (1996).
2. Zurek, W. Decoherence and the transition from quantum to classical. Phys. Today 44, 36–44 (1991). 48. Deutsch, D. et al. Quantum privacy amplification and the security of quantum cryptography over
3. Preskill, J. Reliable quantum computers. Proc. R. Soc. Lond. A 454, 385–410 (1998). noisy channels. Phys. Rev. Lett. 77, 2818–2821 (1996); 80; 2022 (1998) (errata).
4. Shor, P. W. in Proceedings of the 35th Annual Symposium on the Foundations of Computer Science 124– 49. Bennett, C. H. & Brassard, G. in Proceedings of the IEEE International Conference on Computers,
133 (IEEE Computer Society Press, Los Alamitos, California, 1994). Systems and Signal Processing, Bangalore, India 175–179 (IEEE, New York, 1984).
5. Ekert, A. & Jozsa, R. Shor’s quantum algorithm for factorising numbers. Rev. Mod. Phys. 68, 733–753 50. Mayers, D. Unconditional security in quantum cryptography. Preprint quant-ph/9802025 at hhttp://
(1996). xxx.lanl.govi (1998).
6. Wiesner, S. Simulations of many-body quantum systems by a quantum computer. Preprint quant-ph/ 51. Lo, H.-K. & Chau, H. F. Unconditional security of quantum key distribution over arbitrarily long
9603028 at hhttp://xxx.lanl.govi (1996). distances. Science 283, 2050–2056 (1999).
254 © 2000 Macmillan Magazines Ltd NATURE | VOL 404 | 16 MARCH 2000 | www.nature.com
review article
52. Griffiths, R. B. & Niu, C.-S. Optimal eavesdropping in quantum cryptography. II. Quantum circuit. 67. Cirac, J. I. & Zoller, P. Quantum computations with cold trapped ions. Phys. Rev. Lett. 74, 4091–4094
Phys. Rev. A 56, 1173–1176 (1997). (1995).
53. Biham, E., Boyer, M., Brassard, G., van de Graaf, J. & Mor, T. Security of quantum key distribution 68. Lloyd, S. A potentially realizable quantum computer. Science 261, 1569–1571 (1993).
against all collective attacks. Phys. Rev. Lett. 78, 2256–2259 (1997). 69. Lloyd, S. Envisioning a quantum supercomputer. Science 263, 695 (1994).
54. Mayers, D. Unconditionally secure quantum bit committment is impossible. Phys. Rev. Lett. 78, 3414– 70. Cory, D. G., Fahmy, A. F. & Havel, T. F. Ensemble quantum computing by nuclear magnetic resonance
3417 (1997). spectroscopy. Proc. Natl. Acad. Sci. USA 94, 1634–1639 (1997).
55. Lo, H.-K. & Chau, H. F. Is quantum bit committment really possible? Phys. Rev. Lett. 78, 3410–3413 71. Gershenfeld, N. A. & Chuang, I. L. Bulk spin resonance quantum computation. Science 275, 350–356
(1997). (1997).
56. Muller, A. et al. ‘Plug and Play’ systems for quantum cryptography. Appl. Phys. Lett. 70; 793–795 72. Cory, D. G., Price, M. D. & Havel, T. F. Nuclear magnetic resonance spectroscopy: an experimentally
(1997). accessible paradigm for quantum computing. Physica D 120, 82–101 (1998).
57. Briegel, H. J., Dür, W., Cirac, J. I. & Zoller, P. Quantum repeaters for communication. Phys. Rev. Lett. 73. Chuang, I. L., Vandersypen, L. M. K., Xinlan ZhouLeung, D. W. & Lloyd, S. Experimental realization
81, 5932–5935 (1998). of a quantum algorithm. Nature 393, 143–146 (1998).
58. Dür, W., Briegel, H. J., Cirac, J. I. & Zoller, P. Quantum repeaters based on entanglement purification. 74. Chuang, I. L., Gershenfeld, N. & Kubinec, M. Experimental implementation of fast quantum
Phys. Rev. A 59, 169–181 (1999). searching. Phys. Rev. Lett. 80, 3408–3411 (1998).
59. Bennett, C. H. & DiVincenzo, D. P. Quantum computing—towards an engineering era? Nature 377, 75. Laflamme, R., Knille, E., Zurek, W. H., Catasti, P. & Mariappan, S. V. S. NMR Greenberger Horne
389 (1995). Zeilinger states. Phil. Trans. R. Soc. Lond. A 356, 1941–1948 (1998).
60. van Enk, S. J., Cirac, J. I. & Zoller, P. Ideal quantum communication over noisy channels: a quantum 76. Cory, D. G. et al. Experimental quantum error correction. Phys. Rev. Lett. 81, 2152–2155 (1998).
optical implementation. Phys. Rev. Lett. 78, 4293–4296 (1997). 77. Jones, J. A. & Mosca, M. Implementation of a quantum algorithm on a nuclear magnetic resonance
61. van Enk, S. J., Kimble, H. J., Cirac, J. I. & Zoller, P. Quantum communication with dark photons. Phys. quantum computer. J. Chem. Phys. 109, 1648–1653 (1998).
Rev. A 59, 2659–2664 (1999). 78. Jones, J. A. & Mosca, M. Approximate quantum counting on an NMR ensemble quantum computer.
62. Mabuchi, H., Turchette, Q. A., Chapman, M. S. & Kimble, H. J. Real-time detection of individual Phys. Rev. Lett. 83, 1050–1053 (1999).
atoms falling through a high-finesse optical cavity. Opt. Lett. 21, 1393–1395 (1996). 79. Linden, N., Barjat, H. & Freeman, R. An implementation of the Deutsch Jozsa algorithm on a three
63. Haroche, S., Brune, M. & Raimond, J. M. Experiments with single atoms in a cavity: entanglement, qubit NMR quantum computer. Chem. Phys. Lett. 296, 61–67 (1998).
Schrodinger’s cats and decoherence. Phil. Trans. R. Soc. Lond. A 355, 2367–2380 (1997).
64. Turchette, Q. A. et al. Deterministic entanglement of two ions. Phys. Rev. Lett. 81; 3631–3634 (1998). Acknowledgements
65. Monroe, C., Meekhof, D. M., King, B. E., Itano, W. M. & Wineland, D. J. Demonstration of a
fundamental quantum logic gate. Phys. Rev. Lett. 75, 4714–4717 (1995).
This work was supported by the US Army Research office.
66. DiVincenzo, D. P. & Loss, D. Quantum information is physical. Superlatt. Microstruct. 23, 419–432 Correspondence and requests for materials should be addressed to C.H.B.
(1998). (e-mail: [email protected]).
NATURE | VOL 404 | 16 MARCH 2000 | www.nature.com © 2000 Macmillan Magazines Ltd 255