Glossary of concepts

CSS-to-homology correspondence
view in context →

CSS codes and their properties can be formulated in terms of homology theory, yielding a powerful correspondence between codes and chain complexes, the primary homological structures. There exists a many-to-one mapping from size three chain complexes to CSS codes [1][2][3][4] 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.

Cyclic-to-polynomial correspondence
view in context →

Binary and \(q\)-ary cyclic codes and their properties can be naturally formulated using the theory of polynomials. Cyclic codes correspond to ideals in a particular polynomial ring. Codewords \(c_1 c_2 \cdots c_n\) of a \(q\)-ary Galois-field code can be thought of as coefficients in a polynomial \(c_1+c_2 x+\cdots+c_n x^{n-1}\) in the set of polynomials with \(q\)-ary coefficients, \(\mathbb{F}_q[x]\) with \(\mathbb{F}_q=GF(q)\). Polynomials corresponding to codewords of a linear cyclic code form an ideal (i.e., are closed under multiplication and addition) in the ring \(\mathbb{F}_q[x]/(x^n-1)\) (i.e., the set of equivalence classes of polynomials congruent modulo \(x^n-1\)). Multiplication of a codeword polynomial \(c(x)\) by \(x\) in such a ring corresponds to a cyclic shift of the corresponding codeword string.

Knill-Laflamme conditions
view in context →

In a finite-dimensional Hilbert space, there are necessary and sufficient conditions for a code to successfully correct a set of errors. These are called the Knill-Laflamme conditions [5][6][7; Thm. 10.1]. A code defined by a partial isometry \(U\) with code space projector \(\Pi = U U^\dagger\) can correct a set of errors \(\{ E_j \}\) if and only if \begin{align} \Pi E_i^\dagger E_j \Pi = c_{ij}\, \Pi\qquad\text{for all \(i,j\),} \end{align} where \(c_{ij}\) can be arbitrary numbers.


A. Y. Kitaev, “Quantum computations: algorithms and error correction”, Russian Mathematical Surveys 52, 1191 (1997). DOI
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
Sergey Bravyi and Matthew B. Hastings, “Homological Product Codes”. 1311.0885
Nikolas P. Breuckmann, “PhD thesis: Homological Quantum Codes Beyond the Toric Code”. 1802.01520
E. Knill, R. Laflamme, and L. Viola, “Theory of Quantum Error Correction for General Noise”, Physical Review Letters 84, 2525 (2000). DOI; quant-ph/9604034
J. Preskill. Lecture notes on Quantum Computation. (1997–2020) URL
M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 2012). DOI