ScienceWeek

COMPUTER SCIENCE: ON REVERSIBLE COMPUTATION

The following points are made by Seth Lloyd (Nature 2004 430:971):

1) Most of the good things in life -- including life itself --arise from the gradual degradation of the useful into the useless, of order into disorder, known in physical terms as an increase in entropy. Still, wouldn't it be nice sometimes to slow down or even momentarily stop this inevitable dissipation of resources? After all, the second law of thermodynamics does not require that entropy always increase: it leaves open the possibility that entropy can remain constant. There are some processes that are effectively reversible: no energy is dissipated, and entropy remains constant, or almost so. Chemical reactions are reversible if run sufficiently slowly; they can dissipate arbitrarily small amounts of energy per step. Coherent quantum-mechanical processes such as tunnelling and superconductivity are reversible and can operate without dissipation. And so can computation, in principle.

1) More than 40 years ago, Rolf Landauer realized that there was a fundamental connection between computation and the second law of thermodynamics. Just like physical processes, logical processes can be either reversible or irreversible. A logic operation is reversible if its inputs can be inferred from its outputs. For example, the NOT operation that takes 0 to 1 and vice versa is reversible because if Y = NOT X, then knowing that Y is 0 allows one to deduce that X is 1. By contrast, the ERASE operation, which always gives the output 0 regardless of its input, is irreversible: the output gives no knowledge of the input.

2) Landauer pointed out a strong connection between logical irreversibility and physical irreversibility. First, logically reversible operations such as NOT can be implemented using physically reversible operations. For example, if a proton spinning clockwise around some axis is taken to register YES, and one spinning anticlockwise registers NO, then application of a magnetic field causes the proton to flip from YES to NO and back again, all without dissipation or increase in entropy. The flipping spin implements a NOT operation in a physically reversible way. Second, a logically irreversible operation such as ERASE requires physical irreversibility. A bit in your computer's memory is registered by the charge in a tiny capacitor: when you erase the bit by restoring the capacitor to an uncharged state, then half the time the energy in the capacitor is dissipated as heat.

3) Conventional computations are built up of both reversible and irreversible logical operations, so at first the idea that logical irreversibility requires physical irreversibility (which is known as "Landauer's principle") seemed to imply that computation requires dissipation. But then Charles Bennett and, independently, Ed Fredkin realized that most logically irreversible operations can be embedded in slightly more complicated reversible operations. As a consequence, computation can in principle be implemented using reversible physical processes such as slow chemical reactions or coherent quantum processes. The one logically irreversible process that cannot be embedded in a more complicated reversible process is erasure: when you erase the last copy of a bit from your computer, entropy must increase elsewhere.(1)

References:

1) Leff, H. S. & Rex, A. F. (eds) Maxwell's Demon 2: Entropy, Classical and Quantum Information, Computing, 2nd edition (Institute of Physics, Bristol, 2003)

Nature http://www.nature.com/nature

--------------------------------

Related Material:

QUANTUM COMPUTING: IONS, PHOTONS, AND COMMUNICATION LINKS

The following points are made by Eugene Polzik (Nature 2004 428:129):

1) The initial proposal(1) for a quantum computer by Ignacio Cirac and Peter Zoller in 1995 has since been followed up by a train of theoretical and experimental breakthroughs, which last year arrived at the demonstration of elementary quantum logic gates using trapped ions(2,3). Recently, Blinov et al(4) reported the first observation of entanglement between a trapped ion and light -- a significant step towards building a quantum network.

2) Entanglement is a quantum correlation between various parts of a system and is required for processing quantum information. The quantum logic gates(2,3) involving trapped ions were built with short-range entanglement, over only a few micrometers, created by electrical interaction between the ions. Such short-range interaction is not suitable for linking distant nodes of a quantum computer, let alone a large-scale network of such computers. Quantum networks should be linked with light, which is the best long-distance carrier of information, be it classical or quantum.

3) In a classical computer, bits of information are physically implemented as charges on tiny capacitors, and can take two distinct values, usually denoted 0 and 1. Quantum mechanics, however, allows for a superposition of states. This superposition, called a quantum bit or "qubit", dramatically enhances computing and communication capabilities. More specifically, in the work of Blinov et al(4), a qubit formed by a trapped ion can exist in a superposition of two different orientations of its magnetic momentum, say "up" and "down", or +1 and -1. The trick by which Blinov et al(4) entangled an ion and a photon was to bring the ion into this superposition of states through the emission of the photon.

4) According to the conservation of angular momentum, if the ion is created in a spin-down state, the emitted photon is circularly polarized (a property of its electric-field vector) in the right-hand direction. Similarly, if the ion is created in a spin-up state, the emitted photon has left-hand circular polarization. Most importantly, if the ion ends up in an unknown superposition of spin-up and spin-down states, the emitted photon has a complementary superposition state. This is the essence of entanglement of two qubits.

5) Such an entangled state has been generated before, most often between two photons, but also for two ions(2,3), two atoms(5) or an atom and a microwave photon in a cavity(5). In fact, entanglement between atoms and light has been hinted at in a variety of experiments: for example, in the quantum correlations in light emitted by atomic ensembles; in work on spin squeezing and the entanglement of atomic ensembles; and in early experiments on Bell inequalities, in which two photons were emitted by a single atom.

6) The real breakthrough achieved by Blinov et al.4 is that, for the first time, entanglement has been observed between a stationary computational qubit (a trapped ion) and a "flying" communication qubit (an optical photon). The emitted photon can carry a unique piece of information about the state of the ion over a long distance. Another advantage of the system is that trapped ions have exceptionally long lifetimes in entangled states. Although in this experiment the lifetime of demonstrated entanglement did not exceed a microsecond, it can potentially be increased by many orders of magnitude.

References (abridged):

1. Cirac, J. I. & Zoller, P. Phys. Rev. Lett. 74, 4091-4094 (1995)

2. Liebfried, D. et al. Nature 422, 412-415 (2003)

3. Schmidt-Kaler, F. et al. Nature 422, 408-411 (2003)

4. Blinov, B. B., Moehring, D. L., Duan, L. -M. & Monroe, C. Nature 428, 153-157 (2004)

5. Rauschenbeutel, A. et al. Science 288, 2024-2028 (2000)

Nature http://www.nature.com/nature

--------------------------------

Related Material:

SHOR'S ALGORITHM AND QUANTUM COMPUTATION

The following points are made by John L. Casti (citation below):

1) In 1982, the quantum physicist Richard Feynman (1918-1988) published an article titled, "Simulating Physics with Computers". In this speculative piece, Feynman suggested harnessing the weird ambivalence of quantum-mechanical superposition of states of particles like electrons to compute at a pace that would far exceed the fastest possible conventional computer.

2) The phenomenon upon which a quantum computer rests is the ability of a quantum system, say an atom or a single photon, to be in more than one quantum state at the same time, that is, a superposition of states. So, for instance, the spin of a photon can be in both the up and down states simultaneously. If we represent these two states by 0 and 1, respectively, then calculations on the superposition act on both values at once. Thus, a quantum computer containing (n) photons or atoms in superposed states could do a calculation on 2^(n) numbers simultaneously -- a degree of parallelism that is inconceivable for everyday, classical computers.

3) There are a couple of drawbacks to this rosy picture, however. The first is that the process of quantum-mechanical measurement limits (via the Heisenberg Uncertainty Principle) the amount of information that can be extracted from a quantum computer. The second is that quantum superpositions are delicate, fragile things; any contact with the environment sets off the process of decoherence, which collapses the superposition to just one of the many possible states the quantum object can occupy. This collapse, of course, eliminates entirely the advantage of using a quantum, rather than classical, computer.

4) A good question to ask is, Why bother trying to build such a gadget as a quantum computer? Until rather recently, there was no convincing evidence to support the idea that a quantum machine could compute anything that could not be done equally well with a classical computer. But in 1992, Peter Shor of AT&T Bell Laboratories published a quantum-mechanical algorithm for factoring large numbers into their prime components that showed the superiority of using quantum computers over their classical counterparts. Factoring large numbers is a task of not only theoretical, but practical, importance in cryptography, which resulted in Shor's work getting a lot of attention. In all known classical factoring algorithms, the amount of time needed to find the prime factors of a number grows as an exponential function of the size of the number (this factor is approximately exp(L^(1/3)), where L is the length of the number in question). Shor's quantum algorithm requires a time proportional to L^(2), a polynomial growth in L. This is a dramatic reduction over the classical methods when L becomes large. So dramatic, in fact, that it transforms factoring from a computationally "hard" to a computationally "easy" problem.

5) The question surrounding the feasibility of Shor's method in practice (leaving aside the not entirely simple question of actually constructing a quantum machine) is whether the exponentially fast collapse of the superposition of states when exposed to the environment would swamp the exponential increase in computing speed for the factorization scheme. Careful estimates by Shor, Woijcech Zurek, and others have shown that quantum computation can still be useful in factoring as long as a sufficiently low decoherence rate can be maintained. Basically, these results rely on Shor's discovery of quantum analogs of the error-correcting codes used in conventional computers. The standard schemes for error correction cannot be used in the quantum case because they involve actually reading the state of the computer as the computation unfolds and creating redundant states to get any erroneous calculation back on track. The difficulty in the quantum situation is that information disappears in a quantum system as soon as you look at it.

6) The trick to creating an error-correcting scheme for the quantum computer is to encode the state of a single quantum bit as a combination of states in a multiple-bit system. In other words, Shor spreads the information in a single bit across nine such bits. In this way, the original quantum information is preserved even if an error occurs in one of these nine bits. Seth Lloyd of MIT, one of the pioneers in the quantum-computation game, states that the existence of such error-correcting codes came as "quite a surprise. Before Shor came up with this idea, nobody thought it was possible." One problem, however, noted by Lloyd, is that error correction, being a computation all its own, runs the same risk of making mistakes as in the original computation. At the moment, nobody has any good idea of how to address this "second-order" difficulty in quantum computation.

Adapted from: John L. Casti: Paradigms Regained: A Further Exploration of the Mysteries of Modern Science. Perennial 2000, p.254. The author is a professor of mathematics at the Technical University of Vienna (AT).

ScienceWeek http://scienceweek.com