harnessingquanta

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

Simple Rules for a

Complex Quantum World
An exciting new fundamental discipline of research combines information science and quantum mechanics
By Michael A. Nielsen

Updated from the November 2002 issue

25

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

Over the past few decades, scientists have learned that simple rules can give rise to very rich behavior. A good example is chess. Imagine you’re an experienced chess player introduced to someone claiming to know the game. You play a few times and realize that although this person knows the rules of chess, he has no idea how to play well. He makes absurd moves, sacrificing his queen for a pawn and losing a rook for no reason at all. He does not truly understand chess: he is ignorant of the high-level principles and heuristics familiar to any knowledgeable player. These principles are collective or emergent properties of chess, features not immediately evident from the rules but arising from interactions among the pieces on the chessboard. Scientists’ current understanding of quantum mechanics is like that of a slowlearning student of chess. We’ve known the rules for more than 70 years, and we have a few clever moves that work in some special situations, but we’re only gradually learning the high-level principles that are needed to play a skillful overall game. The discovery of these principles is the goal of quantum information science, a fundamental field that is opening up in response to a new way of comprehending the world. Many articles about quantum information science focus on technological applications: research groups “teleport” quantum states from one location to another. Other physicists use quantum states to create cryptographic keys that are absolutely secure from eavesdropping. Information scientists devise algorithms for hypothetical quantum-mechanical computers, much faster than the best known algorithms for conventional, or classical, computers. These technologies are fascinating, but they obscure the fact that they are a by-product of investigations into deep new scientific questions. Applications such as quantum teleportation play a role similar to the steam engines and other machines that spurred the development of thermodynamics in the 18th and 19th centuries. Thermodynamics was motivated by profound, basic questions about how energy, heat and temperature are related, the transformations among these quantities in physical processes, and the key role of entropy. Similarly, quantum information scientists are fathoming the relation between classical and quantum units of information, the novel ways that quantum information can be processed, and the pivotal importance of a quantum feature called entanglement, which entails peculiar connections between different objects. Popular accounts often present entanglement as an all-or-nothing property in which quantum particles are either entangled or not. Quantum information science has revealed that entanglement is a quantifiable physical resource, like energy, that enables information-processing tasks: some systems have a little entanglement; others have a lot. The more entanglement available, the better suited a system is to quantum information processing. Furthermore, scientists have begun to develop powerful quantitative laws of entanglement (analogous to the laws of thermodynamics governing energy), which provide a set of high-level principles for understanding the behavior of entanglement and describing how we can use it to do information processing. Quantum information science is new enough that researchers are still coming to grips with its very nature, and they disagree about which questions lie at its heart. From my point of view, the central goal of quantum information science is to develop general principles, like the laws of entanglement, that will enable us to understand complexity in quantum systems.

Overview/Quantum Information
Information is not purely mathematical. Instead it always has a physical embodiment. In traditional information science the embodiment follows classical, or nonquantum, physics. The burgeoning field of quantum information science puts information in a quantum context. ■ The basic resource of classical information is the bit, which is always either a 0 or a 1. Quantum information comes in quantum bits, or qubits (pronounced “cue-bits”). Qubits can exist in superpositions, which simultaneously involve 0 and 1, and groups of qubits can be “entangled,” which gives them counterintuitive correlations. ■ Quantum computers processing qubits, particularly entangled qubits, can outperform classical computers. Entanglement behaves like a resource, similar to energy, that can be used to do quantum information processing. ■ The goal of quantum information science is to understand the general high-level principles that govern complex quantum systems such as quantum computers. These principles relate to the laws of quantum mechanics in the way that heuristics for skillful play at chess relate to the game’s basic rules.
■

Complexity and Quanta
NUMEROUS STUDIES

in complexity concentrate on systems, such as the weather or piles of sand, that are described by classical physics rather than quantum physics. That focus is natural because complex systems are usually macroscopTHE EDGE OF PHYSICS

26

SCIENTIFIC AMERICAN

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

SLIM FILMS (preceding pages)

THE FUNDAMENTAL QUESTION
MUCH OF INFORMATION SCIENCE, both classical and quantum,

can be summed up by analyzing variants of a basic question: “What quantity of an information resource is needed to perform a specific information-processing task?” For example: “How many computational steps are needed to find

the prime factors of a 300-digit number?” The best classical algorithm known would take about 5 × 1024 steps, or about 150,000 years at terahertz speed. By taking advantage of innumerable quantum states, a quantum factoring algorithm would take only 5 × 1010 steps, or less than a second at terahertz speed.

Classical computer

300-digit number

2:30:00 P.M. Year: 2012 Quantum computer

2:30:01 P.M. Year: 2012

2:30:00 P.M. Year: 154,267

ic, containing many constituent parts, and most systems lose their quantum nature as their size is increased. This quantumto-classical transition occurs because large quantum systems generally interact strongly with their environment, causing a process of decoherence, which destroys the system’s quantum properties [see “100 Years of Quantum Mysteries,” by Max Tegmark and John A. Wheeler; Scientific American, February 2001]. As an example of decoherence, think of Erwin Schrödinger’s famous cat inside a box. In principle, the cat ends up in a weird quantum state, somewhere between dead and alive; it makes no sense to describe it as either one or the other. In a real experiment, however, the cat interacts with the box by exchange of light, heat and sound, and the box similarly interacts with the rest of the world. In nanoseconds, these processes destroy the delicate quantum states inside the box and replace them with states describable, to a good approximation, by the laws of classical physics. The cat inside really is either www.sciam.com BRYAN CHRISTIE DESIGN

alive or dead, not in some mysterious nonclassical state that combines the two. The key to seeing truly quantum behavior in a complex system is to isolate the system extremely well from the rest of the world, preventing decoherence and preserving fragile quantum states. This isolation is relatively easy to achieve with small systems, such as atoms suspended in a magnetic trap in a vacuum, but is much more difficult with the larger ones in which complex behavior may be found. Accidental laboratory discoveries of remarkable phenomena such as superconductivity and the quantum Hall effect are examples in which physicists have achieved large, well-isolated quantum systems. These phenomena demonstrate that the simple rules of quantum mechanics can give rise to emergent principles governing complex behaviors.

Resources and Tasks
WE ATTEMPT TO

understand the highlevel principles that govern in those rare instances when the quantum and the

complex meet by abstracting, adapting and extending tools from classical information theory. In 2001 Benjamin W. Schumacher of Kenyon College proposed that the essential elements of information science, both classical and quantum, can be summarized as a three-step procedure: 1. Identify a physical resource. A familiar classical example is a string of bits. Although bits are often thought of as abstract entities— 0’s and 1’s— all information is inevitably encoded in real physical objects, and thus a string of bits should be regarded as a physical resource. 2. Identify an information-processing task that can be performed using the physical resource of step 1. A classical example is the two-part task of compressing the output from an information source (for example, the text in a book) into a bit string and then decompressing it— that is, recovering the original information from the compressed bit string. 3. Identify a criterion for successful completion of the task of step 2. In our example, the criterion could be that the
THE EDGE OF PHYSICS

27

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

QUBITS EXPLAINED
A BIT can have one of two states: 0 or 1. A bit can be represented by a transistor switch set to “off” or “on” or abstractly by an arrow pointing up or down.
N 23º 34′ 41.4422...″ E 32º 48′ 10.3476...″

A QUBIT, the quantum

version of a bit, has many more possible states. The states can be represented by an arrow pointing to a location on a sphere. The north pole is equivalent to 1, the south pole to 0. The other locations are quantum superpositions of 0 and 1.

N=

S=

A QUBIT MIGHT SEEM TO CONTAIN an infinite amount of information because its coordinates can encode an infinite sequence of digits. But the information in a qubit must be extracted by a measurement. When the qubit is measured, quantum mechanics requires that the result is always an ordinary bit— a 0 or a 1. The probability of each outcome depends on the qubit’s “latitude.”

output from the decompression stage perfectly matches the input to the compression stage. The fundamental question of information science is then “What is the minimal quantity of the physical resource (1) we need to perform the information-processing task (2) in compliance with the success criterion (3)?” Although this question does not quite capture all of information science, it provides a powerful lens through which to view much research in the field [see box on preceding page]. The data-compression example corresponds to a basic question of classical information science— namely, what is the minimum number of bits needed to store the information produced by some source? This problem was solved by Claude E. Shannon in his famous 1948 papers founding information theory. In so doing, Shannon quantified the information content produced by an information source, defining it to be the minimum number of bits needed to reliably store the output of the source. His mathematical expression for the information content

is now known as the Shannon entropy. Shannon’s entropy arises as the answer to a simple, fundamental question about classical information processing. It is perhaps not surprising, then, that studying the properties of the Shannon entropy has proved fruitful in analyzing processes far more complex than data compression. For example, it plays a central role in calculating how much information can be transmitted reliably through a noisy communications channel and even in understanding phenomena such as gambling and the behavior of the stock market. A general theme in information science is that questions about elementary processes lead to unifying concepts that stimulate insight into more complex processes. In quantum information science, all three elements of Schumacher’s list take on new richness. What novel physical resources are available in quantum mechanics? What information-processing tasks can we hope to perform? What are appropriate criteria for success? The resources now include superposition states,

like the idealized alive and dead cat of Schrödinger. The processes can involve manipulations of entanglement (mysterious quantum correlations) between widely separated objects. The criteria of success become more subtle than in the classical case, because to extract the result of a quantum information-processing task we must observe, or measure, the system— which almost inevitably changes it, destroying the special superposition states that are unique to quantum physics.

Qubits
QUANTUM INFORMATION

science begins by generalizing the fundamental resource of classical information— bits— to quantum bits, or qubits. Just as bits are ideal objects abstracted from the principles of classical physics, qubits are ideal quantum objects abstracted from the principles of quantum mechanics. Bits can be represented by magnetic regions on disks, voltages in circuitry, or graphite marks made by a pencil on paper. The functioning of these classical physical states as bits does not depend on the deTHE EDGE OF PHYSICS

28

SCIENTIFIC AMERICAN

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

BRYAN CHRISTIE DESIGN

tails of how they are realized. Similarly, the properties of a qubit are independent of its specific physical representation as the spin of an atomic nucleus, say, or the polarization of a photon of light. A bit is described by its state, 0 or 1. Likewise, a qubit is described by its quantum state. Two possible quantum states for a qubit correspond to the 0 and 1 of a classical bit. In quantum mechanics, however, any object that has two different states necessarily has a range of other possible states, called superpositions, which entail both states to varying degrees. The allowed states of a qubit are precisely all those states that must be available, in principle, to a classical bit that is transplanted into a quantum world. Qubit states correspond to points on the surface of a sphere, with the 0 and 1 being the south and north poles [see box on opposite page]. The continuum of states between 0 and 1 fosters many of the extraordinary properties of quantum information. How much classical information can we store in a qubit? One line of reasoning suggests the amount is infinite: To specify a quantum state we need to specify the latitude and longitude of the corresponding point on the sphere, and in principle each may be given to arbitrary precision. These numbers can encode a long string of bits. For example, 011101101... could be encoded as a state with latitude 01 degrees, 11 minutes and 01.101... seconds. This reasoning, though plausible, is incorrect. One can encode an infinite amount of classical information in a single qubit, but one can never retrieve that information from the qubit. The simplest attempt to read the qubit’s state, a standard direct measurement of it, will give a result of either 0 or 1, south pole or north pole, with the probability of each outcome determined by the latitude of the original state. You could have chosen a different measurement, perhaps using the “Melbourne–Azores Islands” axis instead of north-south, but again only one bit of information would have been extracted, albeit one governed by probabilities with a different dependence on the state’s latitude and longitude. Whichever measurement you choose erases all the information in the qubit except for the www.sciam.com single bit that the measurement uncovers. The principles of quantum mechanics prevent us from ever extracting more than a single bit of information, no matter how cleverly we encode the qubit or how ingeniously we measure it afterward. This surprising result was proved in 1973 by Alexander S. Holevo of the Steklov Mathematical Institute in Moscow, following a 1964 conjecture by J. P. Gordon of AT&T Bell Laboratories. It is as though the qubit contains hidden information that we can manipulate but not access directly. A better viewpoint, however, is to regard this hidden information as being a unit of quantum information rather than an infinite number of inaccessible classical bits. Notice how this example follows Schumacher’s paradigm for information science. Gordon and Holevo asked how many qubits (the physical resource) are required to store a given amount of classical information (the task) in such a way

that the information can be reliably recovered (the criterion for success). Furthermore, to answer this question, they introduced a mathematical concept, now known as the Holevo chi (represented by the Greek letter χ), that has since been used to simplify the analysis of more complex phenomena, similar to the simplifications enabled by Shannon’s entropy. For example, Michal Horodecki of the University of Gdansk in Poland has shown that the Holevo chi can be used to analyze the problem of compressing quantum states produced by a quantum information source, which is analogous to the classical data compression considered by Shannon.

Entangled States
SINGLE QUBITS

are interesting, but more fascinating behavior arises when several qubits are brought together. A key feature of quantum information science is the understanding that groups of two or

HERE THERE BE QUANTUM TYGERS
QUANTUM INFORMATION SCIENTISTS are still mapping out the broad topography of

their nascent field. Some simpler processes, such as teleportation and quantum cryptography, are well understood. In contrast, complex phenomena such as quantum error correction and Peter W. Shor’s factorization algorithm are surrounded by large tracts of terra incognita. One effort to bridge the gaps between the simple and the complex is work on a comprehensive theory of entanglement, analogous to the theory of energy embodied in thermodynamics.

TELEPORTATION SUPERDENSE CODING CRYPTOGRAPHY THEORY OF ENTANGLEMENT
QU

QUANTUM ERROR-CORRECTING CODES

FOURIER TRAN SF TUM O AN

RM

SHOR’S FACTORING ALGORITHM DISCRETE LOGARITHM ALGORITHM

BRYAN CHRISTIE DESIGN

GROVER’S SEARCHING ALGORITHM DATA COMPRESSION INCREASING COMPLEXITY

THE EDGE OF PHYSICS

29

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

DISENTANGLING ENTANGLEMENT
IF DICE COULD BE “entangled” in the manner of quantum particles, each entangled pair would give the same outcome, even if rolled light-years apart or at very different times.

Bob

Alice

The Standard E-Bit
WHEN TWO QUBITS are entangled, they no

Weighing Entanglement
INCOMPLETELY ENTANGLED PAIRS carry less than one e-bit. If Alice and Bob share two partially entangled pairs, they can try to “distill” the entanglement onto a single pair. If distillation produces a maximally entangled pair, then Alice and Bob know their pairs originally carried a total of at least one e-bit of entanglement. BEFORE Bob Alice Bob AFTER Alice

longer have individual quantum states. Instead a relation between the qubits is defined. For example, in one type of maximally entangled pair, the qubits give opposite results when measured. If one gives 0, the other returns 1, and vice versa. A maximally entangled pair carries one “e-bit” of entanglement.
Bob

Incompletely entangled pair

Maximally entangled pair

By using distillation (and the inverse process, entanglement dilution), one constructs a virtual set of scales for weighing the entanglement of various states against the standard e-bit.

2

Alice BEFORE

⁄ 3 e-bit

Quantum Teleportation
IF ALICE AND BOB share one e-bit, they can teleport one qubit. The shared e-bit is “used up,” in that they no longer share it after teleporting.

Bob

Alice

Bob

AFTER Alice

Qubit to be teleported

b

c

30

SCIENTIFIC AMERICAN

THE EDGE OF PHYSICS

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

BRYAN CHRISTIE DESIGN

If Bob teleports a member (b) of an entangled pair to Alice, that particle’s entanglement with its original partner (c) is transferred to Alice’s particle (a). Alice and Bob cannot use teleportation, however, to increase their stock of shared e-bits.

Qubit to be teleported

a

Entangled quantum systems behave in ways impossible in any classical world. more quantum objects can have states that are entangled. These entangled states have properties fundamentally unlike anything in classical physics and are coming to be thought of as an essentially new type of physical resource that can be used to perform interesting tasks. Schrödinger was so impressed by entanglement that in a seminal 1935 paper (the same year that he introduced his cat to the world) he called it “not one but rather the characteristic trait of quantum mechanics, the one that enforces its entire departure from classical lines of thought.” The members of an entangled collection of objects do not have their own individual quantum states. Only the group as a whole has a well-defined state [see box on opposite page]. This phenomenon is much more peculiar than a superposition state of a single particle. Such a particle does have a well-defined quantum state even though that state may superpose different classical states. Entangled objects behave as if they were connected with one another no matter how far apart they are— distance does not attenuate entanglement in the slightest. If something is entangled with other objects, a measurement of it simultaneously provides information about its partners. It is easy to be misled into thinking that one could use entanglement to send signals faster than the speed of light, in violation of Einstein’s special relativity, but the probabilistic nature of quantum mechanics stymies such efforts. Despite its strangeness, for a long time entanglement was regarded as a curiosity and was mostly ignored by physicists. This changed in the 1960s, when John S. Bell of CERN, the European laboratory for particle physics near Geneva, predicted that entangled quantum states allow crucial experimental tests that distinguish between quantum mechanics and classical physics. Bell predicted, and experimenters have confirmed, that entangled quantum systems exhibit behavior that is impossiwww.sciam.com

ble in a classical world— impossible even if one could change the laws of physics to try to emulate the quantum predictions within a classical framework of any sort! Entanglement represents such an essentially novel feature of our world that even experts find it very difficult to think about. Although one can use the mathematics of quantum theory to reason about entanglement, as soon as one falls back on analogies, there is a great danger that the classical basis of our analogies will mislead us. In the early 1990s the idea that entanglement falls wholly outside the scope of classical physics prompted researchers to ask whether entanglement might be useful as a resource for solving information-processing problems in new ways. The answer was yes. The flood of examples began in 1991, when Artur K. Ekert of the University of Cambridge showed how to use entanglement to distribute cryptographic keys impervious to eavesdropping. In 1992 Charles H. Bennett of IBM and Stephen Wiesner of Tel Aviv University showed that entanglement can assist the sending of classical information from one location to another (a process called superdense coding, in which two bits are transferred on a particle that seems to have room to carry only one). In 1993 an international team of six collaborators explained how to teleport a quantum state from one location to another using entanglement. An explosion of further applications followed.

Weighing Entanglement
A S W I T H I N D I V I D U A L qubits, which can be represented by many different physical objects, entanglement also has properties independent of its physical representation. For practical purposes, it may be more convenient to work with one system or another, but in principle it does not matter. For example, one could perform quantum cryptography with an entangled photon pair or an entangled pair of atomic nuclei or even a

photon and a nucleus entangled together. Representation independence suggests a thought-provoking analogy between entanglement and energy. Energy obeys the laws of thermodynamics regardless of whether it is chemical energy, nuclear energy or any other form. Could a general theory of entanglement be developed along similar lines to the laws of thermodynamics? This hope was greatly bolstered in the late 1990s, when researchers showed that different forms of entanglement are qualitatively equivalent—the entanglement of one state could be transferred to another, similar to energy flowing from, say, a battery charger to a battery. Building on these qualitative relations, investigators have begun introducing quantitative measures of entanglement. These developments are ongoing, and researchers have not yet agreed as to the best way of quantifying entanglement. The most successful scheme thus far is based on the notion of a standard unit of entanglement, akin to a standard unit of mass or energy [see box on opposite page]. This approach works analogously to measuring masses by using a balance. The mass of an object is defined by how many copies of the standard mass are needed to balance it on a set of scales. Quantum information scientists have developed a theoretical “entanglement balance” to compare the entanglement in two different states. The amount of entanglement in a state is defined by seeing how many copies of some fixed standard unit of entanglement are needed to balance it. Notice that this method of quantifying entanglement is another example of the fundamental question of information science. We have identified a physical resource (copies of our entangled state) and a task with a criterion for success. We define our measure of entanglement by asking how much of our physical resource we need to do our task successfully. The quantitative measures of entanTHE EDGE OF PHYSICS

31

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

DEALING WITH ERRORS
Classical Repetition Code Error Correction for Qubits
THIS SIMPLE CLASSICAL scheme for reducing errors encodes each bit as a triplet of identical bits. If noise flips one bit, the error can be corrected by fixing the minority bit of a triplet. THE REPETITION STRATEGY IS IMPOSSIBLE for qubits for two reasons. First, qubits in unknown states cannot be perfectly cloned (a). Even if duplicates are produced (for example, by running multiple copies of the computation), a simple measurement will not reveal errors (b).

a

b

Encoding

Noise

ONE QUANTUM ERROR-CORRECTING CODE works by entangling each data qubit with two preset 0 qubits. These three qubits are in turn entangled with six others. Joint measurements on pairs of qubits will reveal whether one of these nine qubits suffers an error and, if so, how to correct it without disrupting the qubits’ individual states.

Data qubit Error correction

Entangled qubits

Preset 0 qubits

Preset 0 qubits

Entangled qubits

glement developed by following this program are proving enormously useful as unifying concepts in the description of a wide range of phenomena. Entanglement measures improve how researchers can analyze tasks such as quantum teleportation and algorithms on quantum-mechanical computers. The analogy with energy helps again: to understand processes such as chemical reactions or the operation of an engine, we study the flow of energy between different parts of the system
MICHAEL A. NIELSEN is associate professor in the department of physics at the University of Queensland in Brisbane, Australia. Born in Brisbane, he received his Ph.D. in physics as a Fulbright Scholar at the University of New Mexico in 1998. He is the author, with Isaac L. Chuang of the Massachusetts Institute of Technology, of the first comprehensive graduate-level textbook on quantum information science, Quantum Computation and Quantum Information.
SCIENTIFIC AMERICAN

and determine how the energy must be constrained at various locations and times. In a similar way, we can analyze the flow of entanglement from one subsystem to another required to perform a quantum information-processing task and so obtain constraints on the resources needed to perform the task. The development of the theory of entanglement is an example of a bottom-up approach— starting from simple questions about balancing entanglement, we gradually gain insight into more complex phenomena. In contrast, in a few cases, people have divined extremely complex phenomena through a great leap of insight, allowing quantum information science to proceed from the top down. The most celebrated example is an algorithm for quickly finding the prime factors of a composite integer on a quantum computer, formulated in 1994 by Peter W. Shor of AT&T Bell Labs. On a classical computer, the best algorithms known take exponentially more resources to factor larg-

er numbers. A 500-digit number needs 100 million times as many computational steps as a 250-digit number. The cost of Shor’s algorithm rises only polynomially— a 500-digit number takes only eight times as many steps as a 250-digit number. Shor’s algorithm is a further example of the basic paradigm (how much computational time is needed to find the factors of an n-bit integer?), but the algorithm appears isolated from most other results of quantum information science [see box on page 29]. At first glance, it looks like merely a clever programming trick with little fundamental significance. That appearance is deceptive; researchers have shown that Shor’s algorithm can be interpreted as an instance of a procedure for determining the energy levels of a quantum system, a process that is more obviously fundamental. As time goes on and we fill in more of the map, it should become easier to grasp the principles underlying Shor’s and other quantum algorithms and, one hopes, to develop new algorithms.
THE EDGE OF PHYSICS

THE AUTHOR

32

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

BRYAN CHRISTIE DESIGN

Quantum error correction might improve the precision of the world’s best clocks.
One final application, quantum error correction, provides the best evidence to date that quantum information science is a useful framework for studying the world. Quantum states are delicate, easily destroyed by stray interactions, or noise, so schemes to counteract these disturbances are essential. Classical computation and communications have a well-developed assortment of error-correcting codes to protect information against the depredations of noise. A simple example is the repetition code [see box on opposite page]. This scheme represents the bit 0 as a string of three bits, 000, and the bit 1 as a string of three bits, 111. If the noise is relatively weak, it may sometimes flip one of the bits in a triplet, changing, for instance, 000 to 010, but it will flip two bits in a triplet far less often. Whenever we encounter 010 (or 100 or 001), we can be almost certain the correct value is 000, or 0. More complex generalizations of this idea provide very good error-correcting codes to protect classical information. quantum computation but that the standard classical techniques could not be used in the quantum world. The field owes a great debt to Landauer’s skepticism for pointing out problems of this type that had to be overcome [see “Riding the Back of Electrons,” by Gary Stix; Profile, Scientific American, September 1998]. Happily, clever ideas developed independently by Shor and Andrew M. Steane of the University of Oxford in 1995 showed how to do quantum error correction without ever learning the states of the qubits or needing to clone them. As with the triplet code, each value is represented by a set of qubits. These qubits are passed through a circuit (the quantum analogue of logic gates) that will successfully fix an error in any one of the qubits without actually “reading” what all the individual states are. It is as if one ran the triplet 010 through a circuit that could spot that the middle bit was different and flip it, all without determining the identity of any of the three bits. Quantum error-correcting codes are a triumph of science. Something that brilliant people thought could not be done— protecting quantum states against the effects of noise— was accomplished using a combination of concepts from information science and basic quantum mechanics. These techniques have now received preliminary confirmation in experiments conducted at Los Alamos National Laboratory, IBM and the Massachusetts Institute of Technology, and more extensive experiments are planned. Quantum error correction has also stimulated many exciting new ideas. For example, the world’s best clocks are currently limited by quantum-mechanical noise; researchers are asking whether the precision of those clocks can be improved by using quantum error correction. Another idea, proposed by Alexei Kitaev of the California Institute of Technology, is that some physical systems might possess a type of natural noise tolerance. Those systems would in effect use quantum error correction without human intervention and might show extraordinary inherent resilience against decoherence. We have explored how quantum information science progresses from fundamental questions to build up an understanding of more complex systems. What does the future hold? By following Schumacher’s program, we will surely obtain novel insights into the information-processing capabilities of the universe. Perhaps the methods of quantum information science will even yield insights into systems not traditionally thought of as information-processing systems. For instance, condensed matter exhibits complex phenomena such as high-temperature superconductivity and the fractional quantum Hall effect. Quantum properties such as entanglement are involved, but their role is currently unclear. By applying what we have learned from quantum information science, we may greatly enhance our skills in the ongoing chess match with the complex quantum universe.

Quantum Error Correction
INITIALLY IT APPEARED

to be impossible to develop codes for quantum error correction because quantum mechanics forbids us from learning with certainty the unknown state of a quantum object—the obstacle, again, of trying to extract more than one bit from a qubit. The simple classical triplet code therefore fails because one cannot examine each copy of a qubit and see that one copy must be discarded without ruining each and every copy in the process. Worse still, making the copies in the first place is nontrivial: quantum mechanics forbids taking an unknown qubit and reliably making a duplicate, a result known as the no-cloning theorem. The situation looked bleak in the mid1990s, when prominent physicists such as the late Rolf Landauer of IBM wrote skeptical articles pointing out that quantum error correction would be necessary for

MORE TO E XPLORE
Quantum Theory and Measurement. Edited by John A. Wheeler and Wojciech H. Zurek. Contains reprints of landmark papers, including a translation of Erwin Schrödinger’s 1935 “cat paradox” paper. Princeton University Press, 1983. The Fabric of Reality. David Deutsch. Penguin Books, 1998. The Bit and the Pendulum. Tom Siegfried. John Wiley & Sons, 2000. Quantum Computation and Quantum Information. Michael A. Nielsen and Isaac L. Chuang. Cambridge University Press, 2000. The Center for Quantum Computation’s Web site: www.qubit.org John Preskill’s lecture notes are available at www.theory.caltech.edu/people/preskill/ph229/ See www.sciam.com for Scientific American articles related to quantum information science. THE EDGE OF PHYSICS

www.sciam.com

33

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.