Stabilizer code

In quantum computing and quantum communication, a stabilizer code is a class of quantum codes for performing quantum error correction. The toric code, and surface codes more generally, are types of stabilizer codes considered very important for the practical realization of quantum information processing. In fact, the toric code and surface codes also belong to a special class of stabilizer codes, CSS codes. An example of a stabilizer code that is not a CSS code is the five-qubit error correcting code.

Stabilizer codes are strikingly similar to classical linear block codes in their operation and performance. Just as a classical linear block code can be defined by its parity-check matrix, a quantum stabilizer code also has a "parity check" structure defined by its stabilizers. However, stabilizers for a Template:Mvar-qubit code are [[Generalizations of Pauli matrices|Template:Mvar-qubit Pauli operator]]s instead of classical Template:Mvar-bit strings, and they must all commute with each other for the code to be valid.

The theory of stabilizer codes allows one to import some classical binary or quaternary codes for use as a quantum code. However, when importing the classical code, it must satisfy the dual-containing (or self-orthogonality) constraint. Researchers have found many examples of classical codes satisfying this constraint, but most classical codes do not. Nevertheless, it is still useful to import classical codes in this way. The entanglement-assisted stabilizer formalism can also overcome this difficulty.

Algebraic-geometry codes provide another source of stabilizer constructions. Matsumoto used algebraic curves to obtain asymptotically good binary stabilizer codes and to improve the Ashikhmin-Litsyn-Tsfasman bound for quantum codes.

Definition

The stabilizer formalism is based on the [[Pauli group#Multi-qubit Pauli group|Template:Mvar-qubit Pauli group]] Template:Math, and extensively uses the facts that Hermitian operators (ones with scalar factors Template:Math instead of Template:Math) in Template:Math have eigenvalues $\pm 1$, and that two operators in Template:Math either commute or anti-commute.

A stabilizer of a stabilizer code with Template:Mvar physical qubits is an Template:Mvar-qubit Pauli operator Template:Math such that all valid code states $|\psi ⟩$ lie in the Template:Math-eigenspace of Template:Mvar, i.e., Template:Tmath. A stabilizer code is defined by its stabilizers in the sense that the converse is also true: A state $|\psi ⟩$ is a valid code state for the stabilizer code if and only if Template:Tmath holds for each stabilizer Template:Mvar. Therefore the simultaneous Template:Math-eigenspace of the stabilizers constitutes the codespace of the stabilizer code.

Any two stabilizers Template:Mvar and Template:Mvar must commute and Template:Mvar must also be a stabilizer. Therefore the stabilizers of a code form the stabilizer group $𝒮$, an abelian subgroup of Template:Math. Conversely, any abelian subgroup of Template:Math that does not contain $-I^{\otimes n}$ is a valid stabilizer group that defines a stabilizer code.

The number of logical qubits encoded in a stabilizer code is determined by the size of the codespace, which is in turn determined by the number of physical qubits and the size of the stabilizer group. For a Template:Mvar-qubit stabilizer code encoding Template:Mvar logical qubits (denoted as an Template:Math code), the codespace has Template:Math dimensions, and the stabilizer group $𝒮$ has Template:Math elements. Since all non-unit Hermitian elements of Template:Math have order 2, $𝒮$ can be generated by Template:Math independent generators:

$𝒮=⟨g_1,\dots ,g_{n-k}⟩.$

The generators must be independent in the sense that none of them are a product of any number of other generators, or the negation thereof (otherwise they would generate $-I^{\otimes n}$). They are analogous to the rows of the parity-check matrix of a classical linear block code.

Examples

Classical repetition code

Template:Main As a simple example, the 3-bit Template:Math classical repetition code can be regarded as a Template:Math quantum stabilizer code. It encodes Template:Math logical qubit into Template:Math physical qubits, and protects against a single bit-flip error (represented as a Pauli Template:Mvar operator Template:Mvar in a quantum information context). However, since it does not protect against single-qubit phase-flip errors Template:Mvar, its code distance as a quantum code is Template:Math.

The stabilizer group of the 3-qubit repetition code has Template:Math generators:

$\begin{array}{ccccc}{g}_1& =& Z& Z& I\\ g_2& =& I& Z& Z\end{array}$

The stabilizer Template:Math indicates that, if the first and second qubits in a valid code state are both measured in the Template:Mvar basis, the results will always be the same (i.e., the product of Template:Mvar eigenvalues will always be Template:Math). Similarly, Template:Math indicates that the Template:Mvar basis measurement on the second and third qubits always yield the same result. Unsurprisingly, the codespace of this code is

$\text{Span}(|000⟩,|111⟩)$.

Usually, the physical state $|000⟩$ and $|111⟩$ are identified with the $|0⟩$ and $|1⟩$ states of the logical qubit respectively (often written as $|\bar{0}⟩$ and $|\bar{1}⟩$ to distinguish them from physical states). As a quantum code, the codespace also includes superpositions of $|\bar{0}⟩$ and $|\bar{1}⟩$, such as $|\overline{+}⟩=|000⟩+|111⟩$ and $|\overline{-}⟩=|000⟩-|111⟩$. Note that a phase-flip error Template:Mvar on any one physical qubit will change $|\overline{+}⟩$ to $|\overline{-}⟩$, and vice versa.

Five-qubit code

Template:Main An example of a stabilizer code is the five qubit Template:Math stabilizer code. It encodes Template:Math logical qubit into Template:Math physical qubits. Its stabilizer group has Template:Math generators:

$\begin{array}{ccccccc}{g}_1& =& X& Z& Z& X& I\\ g_2& =& I& X& Z& Z& X\\ g_3& =& X& I& X& Z& Z\\ g_4& =& Z& X& I& X& Z\end{array}$

As we will show later, this code protects against an arbitrary single-qubit error, and thus it has code distance Template:Math.

Logical operators

There are many ways to decompose a Template:Math-dimension codespace into Template:Mvar logical qubits, and one way to specify such a decomposition is by giving Pauli Template:Mvar and Template:Mvar operators for each logical qubit. For stabilizer codes, there exists decompositions where these logical Template:Mvar and Template:Mvar operators are also elements of Template:Math.

By definition, a logical operator Template:Mvar must map a valid code state $|\psi ⟩$ into a valid code state Template:Tmath. This means that for each stabilizer Template:Mvar, $SP|\psi ⟩=P|\psi ⟩=PS|\psi ⟩$ (the second equality holds since $|\psi ⟩$ is itself a valid code state), which is always true when Template:Mvar and Template:Mvar commute and never true when they anti-commute. Therefore the set of valid logical operators in Template:Math is Template:Tmath, the centralizer of $𝒮$ (i.e., the subgroup of elements that commute with all members of Template:Tmath, also known as the commutant).

However, not all these logical operators act non-trivially on the logical qubit. In particular, since $𝒮$ is an abelian subgroup, $𝒮$ is also contained in Template:Tmath. In fact, when Template:Tmath, Template:Tmath, meaning that Template:Mvar implements the logical identity operator $I^{\otimes k}$. Furthermore, for any other logical operator Template:Mvar, Template:Mvar acts identically to Template:Mvar on the code state, and thus they implement the same logical operator. Factoring out this equivalence gives the quotient group Template:Tmath, which is isomorphic to Template:Math. Therefore all Template:Mvar-qubit logical Pauli operators can be chosen to be Template:Mvar-qubit physical Pauli operators.

To explicitly specify the logical qubit decomposition, one usually chooses logical operators Template:Math. Each of these operators Template:Mvar or Template:Mvar is a representative for the equivalence class $\overline{Z_i}𝒮$ or $\overline{X_i}𝒮$ implementing the same logical operator. These operators need to satisfy the following conditions:

• Template:Math are all independent: The product of any nonempty subset of these operators cannot be a scalar multiple of $I^{\otimes n}$.
• Among Template:Math, the only pairs that anti-commute are Template:Mvar and Template:Mvar for the same Template:Mvar. Other pairs — two logical operators on different logical qubits, one logical operator and one stabilizer generator, or two stabilizer generators — all commute.

Examples

For the 3-qubit repetition code described above, the stabilizer generators (repeated for convenience) and logical operator representatives can be chosen as:

$\begin{array}{ccccc}{g}_1& =& Z& Z& I\\ g_2& =& I& Z& Z\\ \bar{Z}& =& Z& I& I\\ \bar{X}& =& X& X& X\end{array}$

Other single-qubit Template:Mvar operators are alternative implementations of the logical Template:Mvar operator: Template:Math, Template:Math. This is consistent with the above observation that any single-qubit phase-flip error changes $|\overline{+}⟩$ to $|\overline{-}⟩$, and vice versa. It is also straightforward to check that applying Template:Math, i.e., bit-flipping all three qubits, changes $|\bar{0}⟩$ to $|\bar{1}⟩$, and vice versa.

For the five-qubit code, the logical operator representatives are usually chosen as:

$\begin{array}{ccccccc}{g}_1& =& X& Z& Z& X& I\\ g_2& =& I& X& Z& Z& X\\ g_3& =& X& I& X& Z& Z\\ g_4& =& Z& X& I& X& Z\\ \bar{Z}& =& Z& Z& Z& Z& Z\\ \bar{X}& =& X& X& X& X& X\end{array}$

Note, however, that these are not the logical operator representative candidates with the lowest weight (number of non-Template:Mvar Pauli factors). For example, Template:Math has weight 3.

Stabilizer error-correction conditions

One of the fundamental notions in quantum error correction theory is that it suffices to correct a discrete error set with support in the Pauli group ${\mathrm{\Pi }}^n$. Suppose that the errors affecting an encoded quantum state are a subset $ℰ$ of the Pauli group ${\mathrm{\Pi }}^n$:

$ℰ\subset {\mathrm{\Pi }}^n.$

Because $ℰ$ and $𝒮$ are both subsets of ${\mathrm{\Pi }}^n$, an error $E\in ℰ$ either commutes or anti-commutes with any particular element $S\in 𝒮$. If Template:Mvar anti-commutes with an element Template:Mvar, then $SE|\psi ⟩=-ES|\psi ⟩=-E|\psi ⟩$ which means that $E|\psi ⟩$ is in the Template:Math-eigenspace of Template:Mvar rather than the Template:Math-eigenspace, and thus Template:Mvar is detectable by measuring Template:Mvar. Actually it suffices to measure each stabilizer generator Template:Mvar, since if Template:Mvar commutes with every Template:Mvar, then Template:Mvar will also commute with the product of any number of them. In this case $E\in C(𝒮)$ is a logical operator and thus cannot be detected by the code.

However, $E\in 𝒮$ is again a special case, where Template:Mvar implements the logical identity operator: Even though it is not detectable, it also does not corrupt the encoded state. This also holds for any scalar multiple of $E\in 𝒮$, since a global phase has no physical effect. We define an undetectable logical error Template:Mvar as one that is undetectable but does corrupt the encoded state, i.e.,

$E\in C(𝒮)\setminus \{+1,+i,-1,-i\}\otimes 𝒮=C(𝒮)\setminus C(C(𝒮)).$

The equality above gives an alternative characterization of an undetectable logical error Template:Mvar: Template:Mvar must commute with all stabilizers, but not with all logical operators. This characterization is often more convenient since one only need to check commutativity with the generators Template:Math, instead of solving a system of linear equations to determine if Template:Mvar is the product of some subset of Template:Math up to global phase.

Operationally, each stabilizer generator Template:Mvar can be measured via a parity measurement without disturbing states in the codespace. The combination of results of measuring each Template:Mvar is known as the syndrome $𝐫$, represented as a binary vector $𝐫$ with length $n-k$ whose elements indicate whether the error Template:Mvar commutes or anti-commutes with each stabilizer generator Template:Mvar.

Knill–Laflamme conditions

When using a stabilizer code as an error correction code, one must also choose a correction Template:Math for each syndrome. If there exists another possible error Template:Math with the same syndrome as Template:Math, then after correction there may be a residual error Template:Math. The condition that Template:Math has the same syndrome as Template:Math is equivalent to that Template:Math is undetectable, i.e., $E_1^{†}{E}_2\in C(𝒮)$. However, if Template:Math does not corrupt the logical qubits, then the error correction will be successful anyway. Therefore, a stabilizer code can perfectly correct a set of Pauli errors $ℰ$ as long as there does not exist $E_1,E_2\in ℰ$ such that Template:Math is an undetectable logical error.

Examples

The 3-qubit repetition code can correct single-qubit bit-flip errors, which means that it satisfies the error-correction conditions for $ℰ=\{I,X_1,X_2,X_3\}$. Indeed, the only undetectable logical error that consists only of Template:Mvar and Template:Mvar is Template:Mvar with weight 3, and the product of two errors in $ℰ$ . This can also be verified by explicitly checking the corrections corresponding to each syndrome:

Syndrome	Correction
Template:Math	Template:Mvar
Template:Math	Template:Math
Template:Math	Template:Math
Template:Math	Template:Math

The five-qubit code can correct any single-qubit error, i.e., it satisfies the error-correction conditions for $ℰ=\{I,X_i,Y_i,Z_i\}$ (Template:Math distinct errors). This can be verified either by showing that all undetectable logical errors of this code has weight at least 3, or by explicitly checking the Template:Math syndromes. For the five-qubit code again each syndrome corresponds to one error in $ℰ$, although this is not typical for stabilizer codes: For codes like the surface code with high code distances and relatively low-weight stabilizers, one syndrome will usually correspond to many correctable errors that differ from each other by stabilizers.

Relation between Pauli group and binary vectors

The Pauli group has a binary vector representation based on the following mapping:

Template:Tmath

This mapping maps Template:Tmath to vectors in Template:Tmath, such that multiplication of Pauli operators is equivalent to addition of binary vectors up to a global phase. Furthermore, Template:Tmath can be equipped with a symplectic algebra, such that the symplectic product of two binary vectors indicate whether the corresponding Pauli operators commute.

The above binary representation and symplectic algebra are especially useful in making the relation between classical linear error correction and quantum stabilizer codes more explicit. In the language of symplectic vector spaces, a symplectic subspace corresponds to a direct sum of Pauli algebras (i.e., encoded qubits), while an isotropic subspace corresponds to a set of stabilizers.

References

• D. Gottesman, "Stabilizer codes and quantum error correction," quant-ph/9705052, Caltech Ph.D. thesis. https://arxiv.org/abs/quant-ph/9705052
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• A. Calderbank, E. Rains, P. Shor, and N. Sloane, “Quantum error correction via codes over GF(4),” IEEE Trans. Inf. Theory, vol. 44, pp. 1369–1387, 1998. Available at https://arxiv.org/abs/quant-ph/9608006