Calderbank-Shor-Steane (CSS) stabilizer code[1][2][3]

Description

An \([[n,k,d]]\) stabilizer code admitting a set of stabilizer generators that are either \(Z\)-type or \(X\)-type Pauli strings. The stabilizer generator matrix is of the form \begin{align} H=\begin{pmatrix}0 & H_{Z}\\ H_{X} & 0 \end{pmatrix} \label{eq:parity} \end{align} such that the rows of the two blocks must be orthogonal \begin{align} H_X H_Z^T=0~. \label{eq:comm} \end{align} The above condition guarantees that the \(X\)-stabilizer generators, defined in the symplectic representation as rows of \(H_X\), commute with the \(Z\)-stabilizer generators associated with \(H_Z\).

Encoding is based on two related binary linear codes, an \([n,k_X,d^\prime_X]\) code \(C_X\) and \([n,k_Z,d^\prime_Z]\) code \(C_Z\), satisfying \(C_X^\perp \subseteq C_Z\). The resulting CSS code has \(k=k_X+k_Z-n\) logical qubits and distance \(d\geq\min\{d^\prime_X,d^\prime_Z\}\). The \(H_X\) (\(H_Z\)) block of \(H\) \eqref{eq:parity} is the parity-check matrix of the code \(C_X\) (\(C_Z\)). The requirement \(C_X^\perp \subseteq C_Z\) guarantees \eqref{eq:comm}. Basis states for the code are, for \(\gamma \in C_X\), \begin{align} |\gamma + C_Z^\perp \rangle = \frac{1}{\sqrt{|C_Z^\perp|}} \sum_{\eta \in C_Z^\perp} |\gamma + \eta\rangle. \end{align}

A CSS code has stabilizer weight \(w\) if the highest weight of any stabilizer generator is \(w\), i.e., any row of \(H_X\) and \(H_Z\) has weight at most \(w\). In the context of comparing weight as well as of determining distances for noise models biased toward \(X\)- or \(Z\)-type errors, an extended notation for CSS codes is \([[n,k,(d_X,d_Z),w]]\). The quantity \(\min\{d_X,d_Z\}\) is often called the worst-case minimum distance.

There exists a many-to-one mapping from size three chain complexes to CSS codes [4][5][6][7] that allows one to extract code properties from topological features of the complexes. Codes constructed in this manner are sometimes called homological CSS codes, but they are equivalent to CSS codes. This mapping of codes to manifolds allows the application of structures from topology to error correction, yielding various QLDPC codes with favorable properties.

A chain complex of size three is given by binary vector spaces \(A_2\), \(A_1\), \(A_0\) and binary matrices \(\partial_{i=1,2}\) (called boundary operators) \(A_i\) to \(A_{i-1}\) that satisfy \(\partial_1 \partial_2 = 0\). Such a complex is typically denoted as \begin{align} A_2 \xrightarrow{\partial_2} A_1 \xrightarrow{\partial_1} A_0~. \label{eq:chain} \end{align} One constructs a CSS code by associating a physical qubit to every basis element of \(A_1\), and defining parity-check matrices \(H_X=\partial_1^T\) and \(H_Z=\partial_2\)). That way, the spaces \(A_0\) and \(A_2\) can be associated with \(X\)-type and \(Z\)-type Pauli operators, respectively, and boundary operators determine the Paulis making up the stabilizer generators. The requirement \(\partial_1 \partial_2 = 0\) guarantees that the \(X\)-stabilizer generators associated with \(H_X\) commute with the \(Z\)-stabilizer generators associated with \(H_Z\).

Usually, the chain complex \eqref{eq:chain} used in the construction comes from the chain complex associated with a cellulation of a manifold. When the manifold is a two-dimensional surface, its entire chain is used. Higher-dimensional manifolds allow for longer chain complexes, and one can use the three largest non-trivial vector spaces in its chain.

Protection

Detects errors on \(d-1\) qubits, corrects errors on \(\left\lfloor (d-1)/2 \right\rfloor\) qubits.

Using the relation to chain complexes, the number of encoded logical qubits is equal to the dimension of the first \(\mathbb{Z}_2\)-homology of the chain complex, \(H_1(\partial, \mathbb{Z}_2) = \frac{\text{Ker}(\partial_1)}{\text{Im}(\partial_2)}\). The distance of the CSS code is equal to the minimum of the combinatorial (\(d-1\))-systole of the cellulated \(d\)-dimensional manifold and its dual.

Encoding

Stabilizer measurement [8].

Gates

LDPC CSS code symmetries called \(XZ\)-dualities allow for fold-transversal gates, i.e., transversal gates followed by qubit permutations [9].

Decoding

Coherent decoders allow for measurement-free error correction [10]. One method is table/multi-control decoding [11], which scales exponentially with the number of ancillas used in syndrome measurement. Another method, the Ising-based decoder, utilizes the mapping of the effect of the noise to a statistical mechanical model [12][13] such that the decoding problem maps to preparation of the ground state of an Ising model.

Fault Tolerance

Steane error correction [14].

Code Capacity Threshold

Bounds on code capacity thresholds for various noise models exist in terms of stabilizer generator weights [15][16].

Notes

Introduction to CSS-to-homology dictionary by M. Hastings.Using linear programming to solve a set of equations and inequalities on weight distribution of a classical self-orthogonal code \(C=(n, 2^n-k)\) and its dual, one can find a \(C\) such that the \([[n,k,d]]\) CSS code constructed using \(C\) and its dual would have rate and distance close to the Singleton bound [17].Original requirement of \(C_X^\perp \subset C_Z\) [1] has been relaxed to absorb hypergraph product codes.

Parents

  • Qubit stabilizer code — Stabilizer generators can be expressed as either only \(X\)-type or only \(Z\)-type. However, any \([[n,k,d]]\) stabilizer code can be mapped onto a \([[4n,2k,2d]]\) weakly self-dual CSS code, with the mapping preserving geometric locality of a code up to a constant factor [18].
  • Movassagh-Ouyang Hamiltonian code — Movassagh-Ouyang codes stem from a prescription that converts an arbitrary classical code into a quantum code.

Children

Cousins

  • Linear binary code — Construction uses two related binary linear codes \(C_X\) and \(C_Z\).
  • Dual linear code — CSS codes for which \(C_X=C_Z \equiv C\) are called weakly self-dual since \(C^{\perp} \subseteq C\). The stabilizer group of such codes is invariant under the Hadamard gate exchanging \(X\) and \(Z\).
  • Entanglement-assisted (EA) stabilizer code — As opposed to CSS codes, EA stabilizer codes can be constructed from any linear binary code.
  • Galois-qudit CSS code — Extension of qubit CSS codes to Galois qudits.
  • Generalized homological product code — The notion of homological products arose from interpreting CSS codes in terms of chain complexes over manifolds, but some generalized products no longer yield CSS codes.
  • Graph homology code — CSS codes can also be constructed using homology techniques but for manifolds of dimension two or greater.
  • Group GKP code — An \(n\)-qubit CSS code corresponds to the \(C_1^\perp \subseteq C_2 \subset \mathbb{Z}_2^{\times n}\) group construction.
  • Homological bosonic code — CSS and homological CV codes utilize chain complexes in code construction, with the latter complexes having trivial homology.
  • Majorana stabilizer code — When constructing a Majorana stabilizer code from a weakly self-dual classical code with an odd number of bits and generator matrix \(G\), a more complex procedure must be applied to ensure that the fermion code has an even number of Majorana zero modes, and thus a physical Hilbert space [18][19]. Rather than taking \(G\) to be the stabilizer matrix as in the even case, we take \(G\oplus G\). This is a concatenation of classical codes as in the CSS construction and it yields a mapping \([2N-1,k,d]\rightarrow [[2N-1,2N-1-k,d^\perp]]_f\). This procedure may be further generalized by concatenating two different weakly self-dual classical codes with an odd number of bits, as is often done in the CSS construction.
  • Modular-qudit CSS code — Extension of CSS codes to modular-integer qudits.
  • XP stabilizer code — Each XP-regular code can be mapped to a CSS code with a similar logical operator structure [20].

Zoo code information

Internal code ID: css

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: css

Cite as:
“Calderbank-Shor-Steane (CSS) stabilizer code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/css
BibTeX:
@incollection{eczoo_css, title={Calderbank-Shor-Steane (CSS) stabilizer code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/css} }
Permanent link:
https://errorcorrectionzoo.org/c/css

References

[1]
A. R. Calderbank and P. W. Shor, “Good quantum error-correcting codes exist”, Physical Review A 54, 1098 (1996). DOI; quant-ph/9512032
[2]
A. M. Steane, “Error Correcting Codes in Quantum Theory”, Physical Review Letters 77, 793 (1996). DOI
[3]
“Multiple-particle interference and quantum error correction”, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 452, 2551 (1996). DOI; quant-ph/9601029
[4]
A. Y. Kitaev, “Quantum computations: algorithms and error correction”, Russian Mathematical Surveys 52, 1191 (1997). DOI
[5]
H. Bombin and M. A. Martin-Delgado, “Homological error correction: Classical and quantum codes”, Journal of Mathematical Physics 48, 052105 (2007). DOI; quant-ph/0605094
[6]
Sergey Bravyi and Matthew B. Hastings, “Homological Product Codes”. 1311.0885
[7]
Nikolas P. Breuckmann, “PhD thesis: Homological Quantum Codes Beyond the Toric Code”. 1802.01520
[8]
J. Łodyga et al., “Simple scheme for encoding and decoding a qubit in unknown state for various topological codes”, Scientific Reports 5, (2015). DOI; 1404.2495
[9]
Nikolas P. Breuckmann and Simon Burton, “Fold-Transversal Clifford Gates for Quantum Codes”. 2202.06647
[10]
Toshiaki Inada et al., “Measurement-Free Ultrafast Quantum Error Correction by Using Multi-Controlled Gates in Higher-Dimensional State Space”. 2109.00086
[11]
G. A. Paz-Silva, G. K. Brennen, and J. Twamley, “Fault Tolerance with Noisy and Slow Measurements and Preparation”, Physical Review Letters 105, (2010). DOI; 1002.1536
[12]
E. Dennis et al., “Topological quantum memory”, Journal of Mathematical Physics 43, 4452 (2002). DOI; quant-ph/0110143
[13]
Albert T. Schmitz, “Thermal Stability of Dynamical Phase Transitions in Higher Dimensional Stabilizer Codes”. 2002.11733
[14]
A. M. Steane, “Active Stabilization, Quantum Computation, and Quantum State Synthesis”, Physical Review Letters 78, 2252 (1997). DOI; quant-ph/9611027
[15]
A. A. Kovalev and L. P. Pryadko, “Fault tolerance of quantum low-density parity check codes with sublinear distance scaling”, Physical Review A 87, (2013). DOI; 1208.2317
[16]
I. Dumer, A. A. Kovalev, and L. P. Pryadko, “Thresholds for Correcting Errors, Erasures, and Faulty Syndrome Measurements in Degenerate Quantum Codes”, Physical Review Letters 115, (2015). DOI; 1412.6172
[17]
A. R. Calderbank et al., “Quantum Error Correction via Codes over GF(4)”. quant-ph/9608006
[18]
S. Bravyi, B. M. Terhal, and B. Leemhuis, “Majorana fermion codes”, New Journal of Physics 12, 083039 (2010). DOI; 1004.3791
[19]
Sagar Vijay and Liang Fu, “Quantum Error Correction for Complex and Majorana Fermion Qubits”. 1703.00459
[20]
Mark A. Webster, Benjamin J. Brown, and Stephen D. Bartlett, “The XP Stabiliser Formalism: a Generalisation of the Pauli Stabiliser Formalism with Arbitrary Phases”. 2203.00103

Cite as:

“Calderbank-Shor-Steane (CSS) stabilizer code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/css

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/quantum/qubits/CSS.yml.