ScienceWeek

INFORMATION SCIENCE: ON QUANTUM ERROR CORRECTION

The following points are made by Andrew Steane (Nature 2004 432:560):

1) Quantum error correction is a central concept of quantum information science and is almost the only thing a quantum computer would need to do if it is to work properly. It has been implemented, in its most simple form, in a laboratory experiment reported by Chiaverini et al[1].

2) It is surprising indeed that irreversible changes in quantum systems can be corrected. A correcting machine should first gather information from the faulty system, but for a quantum system this would cause the unavoidable disturbance associated with observation. One needs to engineer an observation in such a way as to disturb the error, not the stored information, and to learn what the error is after the influence of our observation. Chiaverini et al[1] have done exactly that.

3) Traditionally, "Alice" is the protagonist in any quantum information story. Imagine that Alice wishes to preserve an atom's quantum state in the presence of noise. The state can be thought of as a spin, or rotation, about an axis oriented in three dimensions. (This is a short-hand for a pair of hyperfine levels in the electronic ground state of a 9Be+ ion.) We assume that Alice does not know what state her atom is in, because if she did she could circumvent the whole problem by recording the state. Such cases are of no use for quantum computing.

4) Alice cannot examine the atom, because this would disturb its state. She cannot generate copies of it (that is, prepare further atoms in the same state) because no method to do that is physically possible (the "no-cloning" theorem, which if broken would lead to various contradictions involving non-local correlations). However, Alice can cause her atom to interact with two others so that the group of three is now in a state described by its own quantum parameters. These parameters are related to the quantum parameters of Alice's atom, and when the three-atom group is perturbed by an error, the function of error-correction is to manipulate the group until the quantum parameters of Alice's atom are restored.[2,3]

References:

1. Chiaverini, J. et al. Nature 432, 602-605 (2004)

2. Cory, D. G. et al. Phys. Rev. Lett. 81, 2152-2155 (1998)

3. Knill, E. et al. Phys. Rev. Lett. 86, 5811-5814 (2001)

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

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

Related Material:

COMPUTER SCIENCE: ON ERROR-CORRECTION IN MESSAGE TRANSFER

The following points are made by Marc Mezard (Science 2003 301:1685):

1) Complex behaviors can emerge in systems in which many "atoms" -- such as real atoms, economic agents, logical variables, or neurons -- locally exchange messages. Recent independent studies of such systems in different subject areas have shown that message passing is extremely powerful as an algorithmic framework, as well as a conceptual one. Three archetypal problems illustrate this utility: error correction in information theory, satisfiability in discrete optimization, and spin glasses in statistical physics.

2) Error correction is important for the transmission of information. To transmit a signal -- for example, a string of 0's and 1's -- through a noisy channel, one first encodes the signal by adding some redundant bits to it. These bits enable the decoding of the received string even if it has been degraded by errors during transmission.

3) In the 1940s, Claude Shannon (1916-2001) predicted that, for a given degree of redundancy, there exist error-correcting codes that can correct all distortions induced by a channel below a threshold noise level. However, practical codes coming close to Shannon's prediction have only recently been found. The main difficulty was to find fast decoding procedures. A clever message-passing procedure called "belief propagation" (BP) (a name borrowed from computer science studies of inference problems) recently allowed these problems to be overcome.

4) In low-density parity check codes, redundancy is added through a number of parity checks. These checks are constraints such that, for instance, the sum of bits B1, B2, B3, and B5 is even. If the received string does not satisfy this constraint, at least one of these four bits has been corrupted. With several such checks one can identify the bits of the received string that have been corrupted during transmission. The more noisy the channel, the more checks are required.

5) This decoding process can be very slow, because an N-bit message can be garbled in 2N ways. This is where the BP algorithm comes to the rescue. It works by exchanging messages along a graph in which the vertices, or nodes, are bits and parity checks. The edges of the graph connect each check to the bits that it involves.

Science http://www.sciencemag.org

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

Related Material:

ON CLAUDE SHANNON (1916-2001)

The following points are made by M. Mitchell Waldrop (Technol. Rev. 2001 August):

1) The entire science of information theory grew out of one electrifying paper that Shannon published in 1948, when he was a 32-year-old researcher at Bell Laboratories. Shannon demonstrated how the once vague notion of information could be defined and quantified with absolute precision. He demonstrated the essential unity of all information media, pointing out that text, telephone signals, radio waves, pictures, film, and every other mode of communication could be encoded in the universal language of binary digits, or "bits" -- a term that first appeared in that Shannon 1948 paper.

2) Shannon proposed the idea that once information becomes digital, it can be transmitted without error. This was a great conceptual leap that led directly to modern information-storage technologies, and Shannon is thus considered to have provided a blueprint for the digital age.

3) After graduating from the University of Michigan in 1936, Shannon went directly to the Massachusetts Institute of Technology to take up a work-study position he had seen advertised on a postcard tacked to a campus bulletin board. The arrangement was that Shannon was to spend half his time pursuing a master's degree in electrical engineering and the other half working as a laboratory assistant to computer pioneer Vannevar Bush. Shannon was soon given responsibility for the Differential Analyzer, at that time the most powerful computing machine in existence. When Shannon died in February 2001, he was completely debilitated with Alzheimer's disease, the symptoms of which first appeared around 1985. He was a professor of physics at the Massachusetts Institute of Technology from 1958 to 1978.

Technology Review http://www.techreview.com

ScienceWeek http://scienceweek.com