An error correcting code for a set of errors Ei 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 SC that maps n + k code bits to the set of indices of correctable errors Ei such that i = SC (Ei (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 SC, an n-bit quantum state |ψ〉 is encoded in a n + k-bit quantum state |Φ〉 = C|ψ〉 . Now assume that |Φ〉 has been corrupted to ΣieiEi|Φ〉.
In the error detection stage, apply SC to ΣieiEi|Φ〉 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 i0 and project the state to Ei0|Φ, i0〉 . Finally, in the recovery stage, apply the inverse error map Ei0-1 to the first n + k qubits of Ei0|Φ, i0〉 to get the corrected state |Φ〉.
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 Ei = Ei-1. Note that operations like x0 XOR x2 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 extraction17 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.
17This is the operator, SC : |x0, x1, x2, 0, 0, 0〉 → |x0, x1, x2, x0 XOR x1, x0 XOR x2, x1 XOR x2〉.