From: Eugen Leitl (eugen@leitl.org)
Date: Wed Oct 23 2002 - 15:00:22 MDT
-- -- Eugen* Leitl leitl ______________________________________________________________ ICBMTO: N48 04'14.8'' E11 36'41.2'' http://eugen.leitl.org 83E5CA02: EDE4 7193 0833 A96B 07A7 1A88 AA58 0E89 83E5 CA02 ---------- Forwarded message ---------- Date: Wed, 23 Oct 2002 11:13:24 -0400 From: Sabine Atkins <sabine@posthuman.com> Reply-To: transhumantech@yahoogroups.com To: transhumantech <transhumantech@yahoogroups.com> Subject: [>Htech] Scientific American: Rules for a Complex Quantum World October 15, 2002 Rules for a Complex Quantum World An exciting new fundamental discipline of research combines information science and quantum mechanics By Michael A. Nielsen 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 slow-learning 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 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 [see www.sciam.com for past Scientific American articles related to these developments]. 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, researchers 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. This article presents my personal view that 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. 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 macroscopic, containing many constituent parts, and most systems lose their quantum nature as their size is increased. This quantum-to-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 Schroedinger'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 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 high-level principles that govern in those rare instances when the quantum and the complex meet by abstracting, adapting and extending tools from classical information theory. Last year 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 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]. 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 Schroedinger. 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 details 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]. 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 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 chi), 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 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. Schroedinger 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]. 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 quantum systems behave in ways impossible in any classical world. 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 impossible 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 As with individual 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 second half of the 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, researchers 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]. 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 entanglement 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 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 larger 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]. 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. 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]. 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 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. Quantum error correction might improve the precision of the world's best clocks. The situation looked bleak in the mid-1990s, when prominent physicists such as the late Rolf Landauer of IBM wrote skeptical articles pointing out that quantum error correction would be necessary for 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. Michael A. Nielsen is an 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. © 1996-2002 Scientific American, Inc. All rights reserved. Reproduction in whole or in part without permission is prohibited. <http://www.sciam.com/article.cfm?chanID=sa006&articleID=0005C8BF-1B88-1D9B-815A809EC5880000-- Sabine Atkins, http://www.posthuman.com/ ------------------------ Yahoo! Groups Sponsor ---------------------~--> Home Selling? Try Us! http://us.click.yahoo.com/QrPZMC/iTmEAA/jd3IAA/PMYolB/TM ---------------------------------------------------------------------~-> -----BEGIN TRANSHUMANTECH SIGNATURE----- Post message: transhumantech@yahoogroups.com Subscribe: transhumantech-subscribe@yahoogroups.com Unsubscribe: transhumantech-unsubscribe@yahoogroups.com List owner: transhumantech-owner@yahoogroups.com List home: http://www.yahoogroups.com/group/transhumantech/ -----END TRANSHUMANTECH SIGNATURE----- Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
This archive was generated by hypermail 2.1.5 : Sat Nov 02 2002 - 09:17:44 MST