An error correcting code for a set of errors *E _{i}* consists of a mapping

*C*that embeds

*n*data bits in

*n*+

*k*code bits (without making any error) together with a syndrome extraction operator

*S*that maps

_{C}*n*+

*k*code bits to the set of indices of correctable errors

*E*such that

_{i}*i*=

*S*(

_{C}*E*(

_{i}*C*(

*x*))). The

*k*bits of

*C(x)*provide the desired redundancy in the

*n*bit message.

In the encoding stage, given an error correcting code *C* with syndrome extraction operator *S _{C}*, an

*n*-bit quantum state |

*ψ*〉 is encoded in a

*n*+

*k*-bit quantum state |Φ〉 =

*C*|

*ψ*〉 . Now assume that |Φ〉 has been corrupted to Σ

_{i}

*e*

_{i}

*E*

_{i}|Φ〉.

In the error detection stage, apply *S _{C}* to Σ

_{i}

*e*

_{i}

*E*

_{i}|Φ〉 padded with sufficient |0〉 bits,

Quantum parallelism gives a superposition of different errors each associated with their respective error index *i*. Next, measure the |*i*〉 component of the result. This will yield a (random) value *i _{0}* and project the state to

*E*. Finally, in the recovery stage, apply the inverse error map

_{i0}|Φ,*i*〉_{0}*E*to the first

_{i0}^{-1}*n*+

*k*qubits of

*E*to get the corrected state |Φ〉.

_{i0}|Φ,*i*〉_{0}*Example*

Consider the simple error correcting code C that maps |0〉 to |000〉 and |1〉 to |111〉. *C* can correct single bit flip errors

The syndrome extraction operator is

with the corresponding error correction operators shown in the table below. In this example *E _{i}* =

*E*. Note that operations like

_{i}^{-1}*x*0 XOR

*x*2 are parity checks.

Consider the quantum bit |*ψ*〉 = (1/√2) (|0〉 – |1〉), which is encoded as

*C*|*ψ*〉 = |Φ〉 = (1/√2) (|000〉 – |111〉),

and the error

The resulting error state is

Next apply the syndrome extraction^{17} to (*E*|Φ〉) ⊗ |000〉,

Measuring the last three bits will yield either |110〉 or |101〉. Assume that |110〉 is measured, then the state becomes

Note that almost magically a part of the error has disappeared. The remaining part of the error can be removed by applying the inverse error operator *X ⊗ I ⊗ I*, corresponding to the measured value |110〉, to the first three bits, to produce

What we have demonstrated just now is that it is possible to use several entangled qubits to represent one logical qubit. Such entanglement spreads out the state of the qubit in a way that errors in any “part” of the entangled qubit can be detected, diagnosed, and corrected. Thus, while entangling qubits with the environment may introduce errors, entangling qubits with themselves might immunize them from such errors. A remarkable aspect of the CSS codes is that the process of error correction has an essential digital character to it, even though a qubit can be in a continuum of possible states. Error detection involves the performance of a series of binary-valued quantum measurements. Then these bit values provide an instruction for an error detection step, which involves a discrete rotation of a specific state. This digital character derives from the fact that any error which the environment can cause on a single qubit acts in a subspace orthogonal to the state space of the coded qubit itself. This leaves the complex coefficients, to a very high accuracy, untouched by the error process (error containment), and allows the error detection and correction steps to work in a way which is oblivious to their values.

The need for error correction will, of course, diminish as the technology required to build reliable quantum computer improves. At one time it appeared that building a 1,000 qubit computer may be out of reach. Advances in fabrication techniques, and improved control and measurement techniques, it no longer appears so.

^{17}This is the operator, *SC* : |x0, x1, x2, 0, 0, 0〉 → |x0, x1, x2, x0 XOR x1, x0 XOR x2, x1 XOR x2〉.