# Quantum error correction

Quantum error correction

Quantum error correction is used in quantum computing to protect quantum information from errors due to decoherence and other quantum noise. Quantum error correction is essential if one is to achieve fault-tolerant quantum computation that can deal not only with noise on stored quantum information, but also with faulty quantum gates, faulty quantum preparation, and faulty measurements.

Classical error correction employs redundancy. The simplest way is to store the information multiple times, and—if these copies are later found to disagree—just take a majority vote; e.g. Suppose we copy a bit three times. Suppose further that a noisy error corrupts the three-bit state so that one bit is equal to zero but the other two are equal to one. We also assume that noisy errors are independent and occur with some probability p. It is most likely that the error is a single-bit error and the transmitted message is three ones. It is possible that a double-bit error occurs and the transmitted message is equal to three zeros, but this outcome is less likely than the above outcome.

Copying quantum information is not possible due to the no-cloning theorem. This theorem seems to present an obstacle to formulating a theory of quantum error correction. But it is possible to "spread" the information of one qubit onto a highly-entangled state of several ("physical") qubits. Peter Shor first discovered this method of formulating a "quantum error correcting code" by storing the information of one qubit onto a highly-entangled state of nine qubits. A quantum error correcting code protects quantum information against errors of a limited form.

Classical error correcting codes use a "syndrome measurement" to diagnose which error corrupts an encoded state. We then reverse an error by applying a corrective operation based on the syndrome. Quantum error correction also employs syndrome measurements. We perform a multi-qubit measurement that does not disturb the quantum information in the encoded state but retrieves information about the error. A syndrome measurement can determine whether a qubit has been corrupted, and if so, which one. What is more, the outcome of this operation (the "syndrome") tells us not only which physical qubit was affected, but also, in which of several possible ways it was affected. The latter is counter-intuitive at first sight: Since noise is arbitrary, how can the effect of noise be one of only few distinct possibilities? In most codes, the effect is either a bit flip, or a sign (of the phase) flip, or both (corresponding to the Pauli matrices "X", "Z", and "Y"). The reason is that the measurement of the syndrome has the projective effect of a quantum measurement. So even if the error due to the noise was arbitrary, it can be expressed as a superposition of basis operations—the "error basis" (which is here given by the Pauli matrices and the identity). The syndrome measurement "forces" the qubit to "decide" for a certain specific "Pauli error" to "have happened", and the syndrome tells us which, so that we can let the same Pauli operator act again on the corrupted qubit to revert the effect of the error.

The syndrome measurement tells us as much as possible about the error that has happened, but "nothing" at all about the "value" that is stored in the logical qubit—as otherwise the measurement would destroy any quantum superposition of this logical qubit with other qubits in the quantum computer.

The bit flip code

The repetition code works in a classical channel, because Cbits are easy to measure and to repeat. However, in a quantum channel, it is longer more possible, due to the no-cloning theorem, which forbids the creation of identical copies of an arbitrary unknown quantum state. So a single Qbit can not be repeated three times as in the previous example, as any measurement of the Qbit will change its wave function. Nevertheless, in a quantum computer, there is another method, which is called the three Qbits bit flip code. It uses entanglement and syndrome measurements, and can perform the similar results to the repetition code. If there is a Qbit $|psi angle = alpha_0|0 angle + alpha_1|1 angle$. The first step of the three Qbit bit flip code is to entangle the Qbit with two other Qbits using two CNOT gates with input $|0 angle$ [cite journal
author = Michael A. Nielsen and Isaac L. Chuang
title = Quantum Computation and Quantum Information
journal = Cambridge University Press
date = 2000
] .

The result will be: $|psi\text{'} angle= alpha_0 |000 angle + alpha_1|111 angle.$This is just a tensor product of three Qbits, and different from cloning a state.

Now these Qbits will be sent through separate similarly constructed channels. For example, in the channel the first Qbit were be flipped, and the result would be $|psi\text{'}_r angle=alpha_0|100 angle + alpha_1|011 angle$. To diagnose bit flips in any of the three possible Qbits, syndrome diagnosis is needed, which includes four projection operators:

$P_0=|000 anglelangle000|+|111 anglelangle111|$

$P_1=|100 anglelangle100|+|011 anglelangle011|$

$P_2=|010 anglelangle010|+|101 anglelangle101|$

$P_3=|001 anglelangle001|+|110 anglelangle110|$

It can be obtained:

$langlepsi\text{'}_r|P_0|psi\text{'}_r angle = 0$

$langlepsi\text{'}_r|P_1|psi\text{'}_r angle = 1$

$langlepsi\text{'}_r|P_2|psi\text{'}_r angle = 0$

$langlepsi\text{'}_r|P_3|psi\text{'}_r angle = 0$

So it will be known that the error syndrome correspondsing to $P_1$.This three Qbits bit flip code can correct one error, if one bit-flip-error happend in the channel. It is like the function of a three bits repetition code in classical computer.

The sign flip code

Flipped bits are the only kind of error in classical computer, but there is another possibility of an error with quantum computers, the sign flip. Through the transmission in a channel the relative sign between $|0 angle$ and $|1 angle$ can become inverted. For instance, a Qbit in the state $|- angle=\left(|0 angle-|1 angle\right)/sqrt\left\{2\right\}$ may have its sign flip to $|+ angle=\left(|0 angle+|1 angle\right)/sqrt\left\{2\right\}.$

The original state of the Qbit

$|psi angle = alpha_0|+ angle+alpha_1|- angle$

will be changed into the state

$|psi\text{'} angle = alpha_0|+++ angle+alpha_1|--- angle.$

The correction for sign flip is similar to that of flipped bits.

The Shor code

The error correction code over channels may be either bit flip or sign flip. And it is also possible to combine both codes in one code. The Shor code is just the method, which can correct arbitrary Qbit errors.

The 1st, 4th and 7th Qbits are for the sign flip code, while the three group of Qbits (1,2,3), (4,5,6), and (7,8,9) are designed for the bit flip code. With the Shor code a Qbit state $|psi angle=alpha_0|0 angle+alpha_1|1 angle$ will be transformed into the product of 9 Qbits $|psi\text{'} angle=alpha_0|0_S angle+alpha_1|1_S angle$, where

$|0_S angle=\left(|000000000 angle+|000000111 angle+|000111000 angle+|000111111 angle+|111000000 angle+|111000111 angle+|111111000 angle+|111111111 angle\right)/sqrt\left\{8\right\}$

$|1_S angle=\left(|000000000 angle-|000000111 angle-|000111000 angle+|000111111 angle-|111000000 angle+|111000111 angle+|111111000 angle-|111111111 angle\right)/sqrt\left\{8\right\}$

If a bit flip error happens to a Qbit, the syndrome analysis will be performed on each set of states (1,2,3), (4,5,6), and (7,8,9), then correct the error.

If the three bit flip group (1,2,3), (4,5,6), and (7,8,9) are considered as three inputs, then the Shor code circuit can be reduced as a sign flip code. This means Shor code can also repair sign flip error for a single Qbit [cite journal
last = W.Shor
first = Peter
title = Scheme for reducing decoherence in quantum computer memory
journal = AT&T Bell Laboratories
accessdate = 1995
] .

The Shor code also can correct for any arbitrary errors (both bit flip and sign flip) to a single Qbit. If an arbitrary error is an arbitrary unitary transform U, which will act on an Qbit

$U|psi angle=|psi_e angle.$

$|psi angle$ is the original state of the single Qbit, which is being affected. U can be described in the form

$U=C_0I+C_1sigma_x+C_2sigma_y+C_3sigma_z$

where $C_0$,$C_1$,$C_2$, and $C_3$ are complex coefficients, I is the identity, and the Pauli matrices are given by

The Pauli matrices are a set of 2x2 complex Hermitian and unitary matrices.If U is equal to I, this means the state is unchanged. If $U=sigma_x$, there is a bit flip error happend in channel, if $U=sigma_z$, a sign flip must be happend, and both a bit flip and a sign flip according to $U=isigma_y$. Then the error correction system will correct error as above. But the Shor code is only works in the case that there no more than 1-Qbit error.

Models

Over time, researchers have come up with several codes:

* Peter Shor's 9-qubit-code, a.k.a. the Shor code, encodes 1 logical qubit in 9 physical qubits and can correct for arbitrary errors in a single qubit.
* Andrew Steane found a code which does the same with 7 instead of 9 qubits, see Steane code.
* Raymond Laflamme found a class of 5-qubit codes which do the same, which also have the property of being fault-tolerant.
* A generalisation of this concept are the CSS codes, named for their inventors: A. R. Calderbank, Peter Shor and Andrew Steane. According to the quantum Hamming bound, encoding a single logical qubit and providing for arbitrary error correction in a single qubit requires a minimum of 5 physical qubits.
* A more general class of codes (encompassing the former) are the stabilizer codes discovered by Daniel Gottesman ( [http://arxiv.org/abs/quant-ph/9604038] ), and by A. R. Calderbank, Eric Rains, Peter Shor, and N. J. A. Sloane ( [http://arxiv.org/abs/quant-ph/9605005] , [http://arxiv.org/abs/quant-ph/9608006] ); these are also called additive codes.
* A newer idea is Alexei Kitaev's topological quantum codes and the more general idea of a topological quantum computer.

That these codes allow indeed for quantum computations of arbitrary length is the content of the "threshold theorem", found by Michael Ben-Or and Dorit Aharonov, which asserts that you can correct for all errors if you concatenate quantum codes such as the CSS codes—i.e. re-encode each logical qubit by the same code again, and so on, on logarithmically many levels—"provided" the error rate of individual quantum gates is below a certain threshold; as otherwise, the attempts to measure the syndrome and correct the errors would introduce more new errors than they correct for.

As of late 2004, estimates for this threshold indicate that it could be as high as 1-3% [http://www.arxiv.org/abs/quant-ph/0410199] , provided that there are sufficiently many qubits available.

Notes

* [http://www.arxiv.org/abs/quant-ph/0410199 Prospects]
* [http://www.newscientisttech.com/article.ns?id=dn9301&feedId=online-news_rss20 Error-check breakthrough in quantum computing]

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Quantum mind — theories are based on the premise that quantum mechanics is necessary to fully understand the mind and brain, particularly concerning an explanation of consciousness. This approach is considered a minority opinion in science, although it does… …   Wikipedia

• Quantum information science — concerns information science that depends on quantum effects in physics. It includes theoretical issues in computational models as well as more experimental topics in quantum physics including what can and cannot be done with quantum information …   Wikipedia

• Quantum computer — A quantum computer is a device for computation that makes direct use of distinctively quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. In a classical (or conventional) computer, information is… …   Wikipedia

• Quantum information — For the journal with this title, see Historical Social Research. In quantum mechanics, quantum information is physical information that is held in the state of a quantum system. The most popular unit of quantum information is the qubit, a two… …   Wikipedia

• Quantum channel — In quantum information theory, a quantum channel is a communication channel which can transmit quantum information, as well as classical information. An example of quantum information is the state of a qubit. An example of classical information… …   Wikipedia

• Quantum finite automata — In quantum computing, quantum finite automata or QFA are a quantum analog of probabilistic automata. They are related to quantum computers in a similar fashion as finite automata are related to Turing machines. Several types of automata may be… …   Wikipedia

• Quantum threshold theorem — In quantum computing, the Threshold Theorem (also called the Quantum Fault Tolerance Theorem) states that a quantum computer with noise can quickly and accurately simulate an ideal quantum computer, provided the level of noise is below a certain… …   Wikipedia

• Quantum virtual machine — A Quantum Virtual Machine (QVM) is a virtual machine which emulates a quantum computer. It provides a structure for a quantum register (the memory of a quantum computer) and operations for the manipulation of a quantum register.ee also*libquantum …   Wikipedia

• Quantum circuit — In quantum information theory, a quantum circuit is a model for quantum computation in which a computation is a sequence of reversible transformations on a quantum mechanical analog of an n bit register. This analogous structure is referred to as …   Wikipedia

• Timeline of quantum computing — Timeline of quantum computers1970s* 1970 Stephen Wiesner invents conjugate coding.* 1973 Alexander Holevo publishes a paper showing that n qubits cannot carry more than n classical bits of information (a result known as Holevo s theorem or Holevo …   Wikipedia