Quantum systems spontaneously interact with their environment, manifesting as errors in a quantum computation. Quantum error correction, and the theory of fault-tolerant quantum computation in general, has been developed to ensure reliable logical operations in the presence of noise.
The key idea behind quantum error correction is the use of redundancy to represent or encode quantum information. The simplest example of an encoding is a repetition code, wherein a qubit is associated with a two-dimensional space spanned by |000⟩ and |111⟩, i.e., |ψ⟩ = α|000⟩ + β|111⟩. For simplicity let us consider the effect of a generic single-qubit Pauli error P on |ψ⟩. P is incapable of transforming one encoded state to another. Moreover, a simple majority vote can infer the state of the logical qubit given P|ψ⟩. This is quantum error correction in its simplest form.
In general, a [[n, k]] quantum error-correcting code Q is identified by a 2k dimensional subspace of a 2n dimensional Hilbert space. It is often convenient to restrict to a subset of codes that admit a succinct description — as a common eigenspace of a set of mutually commuting Pauli operators — known as stabilizer codes. In general, a [[n, k]] stabilizer code Q is a common eigenspace with eigenvalue + 1, of a set of n − k independent commuting Pauli matrices, which are called stabilizer generators. For our earlier example of a repetition code, it is easy to verify that the corresponding stabilizer generators are Z1Z2 and Z2Z3.
Stabilizer codes are, by far, the most widely used class of codes. Popular examples include the , , and . An in-depth survey of stabilizer codes for quantum error correction can be found in Daniel Gottesman's and the two popular texts by Michael Nielsen and Isaac Chuang, and by Daniel Lidar and Todd Brun.
In the stabilizer formalism, quantum error correction comprises two steps. The first is syndrome extraction: detecting the presence of an error using quantum measurements. The second, decoding, refers to inferring the error from the observed measurement outcomes.
For Pauli errors, inferring the error is tantamount to recovery, since errors square to the identity. Ideally, encoded states |ψ⟩ should satisfy Si|ψ⟩ = |ψ⟩. Any deviation from this rule indicates the presence of errors on the encoded state. In other words, a Pauli error P on the encoded state will result in Si(P|ψ⟩) = si(P|ψ⟩), whenever SiP = ( − 1)siPSi. The binary sequence s1…sn − k is called the error syndrome. It provides important information on the unknown Pauli error P.
Decoding involves inferring the most likely error given its error syndrome. This is a classical algorithm that performs a statistical inference given the physical error model. Popular strategies include minimum weight decoding and maximum likelihood decoding. For surface codes, the former is implemented by . Other types of decoding include the and the (see also ).