======================================================================
= Quantum error correction =
======================================================================
Introduction
======================================================================
Quantum error correction (QEC) 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. If we 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 classical
bits are easy to measure and to repeat. This stops being the case for
a quantum channel in which, due to the no-cloning theorem, it is no
longer possible to repeat a single qubit three times. To overcome
this, a different method, such as the so-called 'three-qubit bit flip
code', has to be used. This technique uses entanglement and syndrome
measurements and is comparable in performance with the repetition
code.
Consider the situation in which we want to transmit the state of a
single qubit \vert\psi\rangle through a noisy channel \mathcal E. Let
us moreover assume that this channel either flips the state of the
qubit, with probability p, or leaves it unchanged. The action of
\mathcal E on a general input \rho can therefore be written as
\mathcal E(\rho) = (1-p) \rho + p\ X\rho X.
Let |\psi\rangle = \alpha_0|0\rangle + \alpha_1|1\rangle be the
quantum state to be transmitted. With no error correcting protocol in
place, the transmitted state will be correctly transmitted with
probability 1-p. We can however improve on this number by 'encoding'
the state into a greater number of qubits, in such a way that errors
in the corresponding 'logical qubits' can be detected and corrected.
In the case of the simple three-qubit repetition code, the encoding
consists in the mappings
\vert0\rangle\rightarrow\vert0_L\rangle\equiv\vert000\rangle and
\vert1\rangle\rightarrow\vert1_L\rangle\equiv\vert111\rangle. The
input state \vert\psi\rangle is encoded into the state
\vert\psi'\rangle = \alpha_0 \vert000\rangle + \alpha_1
\vert111\rangle. This mapping can be realized for example using two
CNOT gates, entangling the system with two ancillary qubits
initialized in the state \vert0\rangle.
The encoded state \vert\psi'\rangle is what is now passed through the
noisy channel.
The channel acts on \vert\psi'\rangle by flipping some subset
(possibly empty) of its qubits. No qubit is flipped with probability
(1-p)^3, a single qubit is flipped with probability 3p(1-p)^2, two
qubits are flipped with probability 3p^2(1-p), and all three qubits
are flipped with probability p^3. Note that a further assumption about
the channel is made here: we assume that \mathcal E acts equally and
independently on each of the three qubits in which the state is now
encoded. The problem is now how to detect and correct such errors,
'without at the same time corrupting the transmitted state'.
Let us assume for simplicity that p is small enough that the
probability of more than a single qubit being flipped is negligible.
One can then detect whether a qubit was flipped, 'without also
querying for the values being transmitted', by asking whether one of
the qubits differs from the others. This amounts to performing a
measurement with four different outcomes, corresponding to the
following four projective measurements:Comparison of output 'minimum'
fidelities, with (blue) and without (red) error correcting via the
three qubit bit flip code. Notice how, for p\le 1/2, the error
correction scheme improves the fidelity.\begin{align}
P_0 &=|000\rangle\langle000|+|111\rangle\langle111|, \\
P_1 &=|100\rangle\langle100|+|011\rangle\langle011|, \\
P_2 &=|010\rangle\langle010|+|101\rangle\langle101|, \\
P_3 &=|001\rangle\langle001|+|110\rangle\langle110|.
\end{align}This can be achieved for example by measuring Z_1 Z_2 and
then Z_2 Z_3. This reveals which qubits are different from which
others, without at the same time giving information about the state of
the qubits themselves. If the outcome corresponding to P_0 is
obtained, no correction is applied, while if the outcome corresponding
to P_i is observed, then the Pauli X gate is applied to the i-th
qubit. Formally, this correcting procedure corresponds to the
application of the following map to the output of the channel:
\mathcal E_{\operatorname{corr}}(\rho)=P_0\rho P_0 + \sum_{i=1}^3 X_i
P_i \rho\, P_i X_i.Note that, while this procedure perfectly corrects
the output when zero or one flips are introduced by the channel, if
more than one qubit is flipped then the output is not properly
corrected. For example, if the first and second qubits are flipped,
then the syndrome measurement gives the outcome P_3, and the third
qubit is flipped, instead of the first two. To assess the performance
of this error correcting scheme for a general input we can study the
fidelity F(\psi') between the input \vert\psi'\rangle and the output
\rho_{\operatorname{out}}\equiv\mathcal
E_{\operatorname{corr}}(\mathcal
E(\vert\psi'\rangle\langle\psi'\vert)). Being the output state
\rho_{\operatorname{out}} correct when no more than one qubit is
flipped, which happens with probability (1-p)^3 + 3p(1-p)^2, we can
write it as [(1-p)^3+3p(1-p)^2]\,\vert\psi'\rangle\langle\psi'\vert +
(...), where the dots denote components of \rho_{\operatorname{out}}
resulting from errors not properly corrected by the protocol. It
follows that
F(\psi')=\sqrt{\langle\psi'\vert\rho_{\operatorname{out}}\vert\psi'\rangle}\ge
\sqrt{(1-p)^3 + 3p(1-p)^2}=\sqrt{1-3p^2+2p^3}.This fidelity is to be
compared with the corresponding fidelity obtained when no error
correcting protocol is used, which was shown before to equal
\sqrt{1-p}. A little algebra then shows that the fidelity 'after'
error correction is greater than the one without for p<1/2. Note
that this is consistent with the working assumption that was made
while deriving the protocol (of p being small enough).
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\rangle and |1\rangle can become inverted. For instance, a
qubit in the state |-\rangle=(|0\rangle-|1\rangle)/\sqrt{2} may have
its sign flip to |+\rangle=(|0\rangle+|1\rangle)/\sqrt{2}.
The original state of the qubit
|\psi\rangle = \alpha_0|+\rangle+\alpha_1|-\rangle
will be changed into the state
|\psi'\rangle = \alpha_0|{+}{+}{+}\rangle+\alpha_1|{-}{-}{-}\rangle.
In the Hadamard basis, bit flips become sign flips and sign flips
become bit flips. Let E_\text{phase} be a quantum channel that can
cause at most one phase flip. Then the bit flip code from above can
recover |\psi\rangle by transforming into the Hadamard basis before
and after transmission through E_\text{phase}.
The Shor code
======================================================================
The error channel may induce either a bit flip, a sign flip, or both.
It is possible to correct for both types of errors using one code, and
the Shor code does just that. In fact, the Shor code corrects
arbitrary single-qubit errors.
Let E be a quantum channel that can arbitrarily corrupt a single
qubit. The 1st, 4th and 7th qubits are for the sign flip code, while
the three group of qubits (1,2,3), (4,5,6), and (7,8,9) are designed
for the bit flip code. With the Shor code, a qubit state
|\psi\rangle=\alpha_0|0\rangle+\alpha_1|1\rangle will be transformed
into the product of 9 qubits
|\psi'\rangle=\alpha_0|0_S\rangle+\alpha_1|1_S\rangle, where
: |0_S\rangle=\frac{1}{2\sqrt{2}}(|000\rangle + |111\rangle) \otimes
(|000\rangle + |111\rangle
) \otimes (|000\rangle + |111\rangle)
: |1_S\rangle=\frac{1}{2\sqrt{2}}(|000\rangle - |111\rangle) \otimes
(|000\rangle - |111\rangle) \otimes (|000\rangle - |111\rangle)
If a bit flip error happens to a qubit, 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 that the Shor code can also repair
sign flip error for a single qubit.
The Shor code also can correct for any arbitrary errors (both bit flip
and sign flip) to a single qubit. If an error is modeled by a unitary
transform U, which will act on a qubit |\psi\rangle, then U can be
described in the form
: U=c_0I+c_1\sigma_x+c_2\sigma_y+c_3\sigma_z
where c_0,c_1,c_2, and c_3 are complex constants, I is the identity,
and the Pauli matrices are given by
: \sigma_x=\biggl( \begin{matrix}
0&1\\1&0
\end{matrix} \biggr);
: \sigma_y=\biggl( \begin{matrix}
0&-i\\i&0
\end{matrix} \biggr);
: \sigma_z=\biggl( \begin{matrix}
1&0\\0&-1
\end{matrix} \biggr)
If U is equal to I, then no error occurs. If U=\sigma_x, a bit flip
error occurs. If U=\sigma_z, a sign flip error occurs. If U=i\sigma_y
then both a bit flip error and a sign flip error occur. Due to
linearity, it follows that the Shor code can correct arbitrary 1-qubit
errors.
Bosonic codes
======================================================================
Several proposals have been made for storing error-correctable quantum
information in bosonic modes. Unlike a two-level system, a quantum
harmonic oscillator has infinitely many energy levels in a single
physical system. For example, the cat code was followed shortly after
by Gottesman-Kitaev-Preskill (GKP) states, and more recently by the
binomial code. The insight offered by these codes is to take advantage
of this redundancy within a single system, rather than to duplicate
many two-level qubits.
Written in the Fock basis, the simplest binomial encoding is
|0_L\rangle=\frac{|0\rangle+|4\rangle}{\sqrt{2}},\quad
|1_L\rangle=|2\rangle,
where the subscript L indicates a "logically encoded" state. Then if
the dominant error mechanism of the system is the stochastic
application of the bosonic lowering operator \hat{a}, the
corresponding error states are |3\rangle and |1\rangle, respectively.
Since the codewords involve only even photon number, and the error
states involve only odd photon number, errors can be detected by
measuring the photon number parity of the system. Measuring the odd
parity will allow correction by application of the raising operator
\hat{a}^{\dagger} without knowledge of the specific logical state of
the qubit. (However, the binomial code is not robust to two-photon
loss.)
General codes
======================================================================
In general, a 'quantum code' for a quantum channel \mathcal{E} is a
subspace \mathcal{C} \subseteq \mathcal{H}, where \mathcal{H} is the
state Hilbert space, such that there exists another quantum channel
\mathcal{R} with
(\mathcal{R} \circ \mathcal{E})(\rho) = \rho \quad \forall \rho =
P_{\mathcal{C}}\rho P_{\mathcal{C}},
where P_{\mathcal{C}} is the orthogonal projection onto \mathcal{C}.
Here \mathcal{R} is known as the 'correction operation'.
A 'non-degenerate code' is one for which different elements of the set
of correctable errors produce linearly independent results when
applied to elements of the code. If distinct of the set of correctable
errors produce orthogonal results, the code is considered 'pure'.
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 and collaborators found a class of 5-qubit codes
which do the same, which also have the property of being
fault-tolerant. A 5-qubit code is the smallest possible code which
protects a single logical qubit against single-qubit errors.
* 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
([
https://arxiv.org/abs/quant-ph/9604038]), and by A. R. Calderbank,
Eric Rains, Peter Shor, and N. J. A. Sloane
([
https://arxiv.org/abs/quant-ph/9605005],
[
https://arxiv.org/abs/quant-ph/9608006]); these are also called
additive codes.
*Two dimensional Bacon-Shor codes are a family of codes parameterized
by integers m and n. There are nm qubits arranged in a square lattice.
* A newer idea is Alexei Kitaev's topological quantum codes and the
more general idea of a topological quantum computer.
* Todd Brun, Igor Devetak, and Min-Hsiu Hsieh also constructed the
entanglement-assisted stabilizer formalism as an extension of the
standard stabilizer formalism that incorporates quantum entanglement
shared between a sender and a receiver.
That these codes allow indeed for quantum computations of arbitrary
length is the content of the quantum 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%, provided that there are sufficiently many qubits
available.
Experimental realization
======================================================================
There have been several experimental realizations of CSS-based codes.
The first demonstration was with NMR qubits. Subsequently,
demonstrations have been made with linear optics, trapped ions, and
superconducting (transmon) qubits.
In 2016 for the first time QEC prolonged lifetime of quantum
information.
Other error correcting codes have also been implemented, such as one
aimed at correcting for photon loss, the dominant error source in
photonic qubit schemes.
See also
======================================================================
* Error detection and correction
* Soft error
Bibliography
======================================================================
*
*
*Freedman, Michael H.; Meyer, David A.; Luo, Feng: Z2-Systolic freedom
and quantum codes. 'Mathematics of quantum computation', 287�320,
Comput. Math. Ser., Chapman & Hall/CRC, Boca Raton, FL, 2002.
*
*
External links
======================================================================
*
*
[
http://www.newscientisttech.com/article.ns?id=dn9301&feedId=online-news_rss
20
Error-check breakthrough in quantum computing]
*
License
=========
All content on Gopherpedia comes from Wikipedia, and is licensed under CC-BY-SA
License URL:
http://creativecommons.org/licenses/by-sa/3.0/
Original Article:
http://en.wikipedia.org/wiki/Quantum_error_correction
