Description
A code whose parity-check matrix is obtained from the incidence matrix of a graph over \(\mathbb{F}_2\). This code’s properties are derived from the size two chain complex associated with the graph. Not every binary linear code is homological, but there exist homological families that asymptotically saturate the Hamming bound [6].
Let \(G\) be a finite, undirected, connected graph without loops and multiple edges. Let \(|V|\) be its number of vertices and \(|E|\) be its number of edges. Its incidence matrix is a \(|V| \times |E|\) matrix whose rows are indexed by the vertices of \(G\), and whose columns are indexed by the edges of \(G\). The matrix element \(H_{ij}=1\) if vertex \(i\) belongs to the edge \(j\) and \(H_{ij}=0\) otherwise. Over \(\mathbb{F}_2\), one row is redundant for a connected graph, so a parity-check matrix of the cycle code can be taken to be any full-rank set of \(|V|-1\) rows.
Protection
More generally, an \([n,k,d]\) cycle code constructed out of a connected graph has \(n = |E|\) and \(k = 1 - \chi(G) = 1-|V|+|E|\), where \(\chi(G)\) is the Euler characteristic of the graph [8]. The code distance is equal to the shortest size of a cycle, guaranteed to exist since \(G\) is not a tree.Cousins
- Graph-adjacency code— Graph-adjacency (cycle) codes’ generator (parity-check) matrices are defined using adjacency (incidence) matrices of graphs.
- Quantum-inspired classical block code— Cycle codes have been known in classical coding theory, and have been rediscovered in the quantum context; see Ref. [8] for a brief exposition.
- Generalized homological-product code— Cycle codes have been known in classical coding theory, and have been rediscovered in the quantum context; see Ref. [8] for a brief exposition.
- Homological code— Cycle codes feature in generalizations of the surface code [8].
- Perfect binary code— A family of cycle codes saturate the asymptotic Hamming bound [6].
- Qubit CSS code— Cycle codes, including the Petersen cycle and Hoffman-Singleton cycle codes, feature in magic-state distillation protocols [9; Appx. A.2.1][10; Sec. VII.A].
Primary Hierarchy
References
- [1]
- T. Kasami, “A topological approach to construction of group codes.” J. Inst. Elec. Commun. Engrs.(Japan) 44 (1961): 1316-1321.
- [2]
- D. A. Huffman, “A graph-theoretic formulation of binary group codes.” Summaries of papers presented at ICMCI, part 3 (1964): 29-30.
- [3]
- W. D. Frazer, “A graph theoretic approach to linear codes.” Proc. Second Annual Allerton Conf. On Circuit & System Theory. 1964.
- [4]
- S. Hakimi and H. Frank, “Cut-set matrices and linear codes (Corresp.)”, IEEE Transactions on Information Theory 11, 457 (1965) DOI
- [5]
- S. Hakimi and J. Bredeson, “Graph theoretic error-correcting codes”, IEEE Transactions on Information Theory 14, 584 (1968) DOI
- [6]
- H. Bombin and M. A. Martin-Delgado, “Homological error correction: Classical and quantum codes”, Journal of Mathematical Physics 48, (2007) arXiv:quant-ph/0605094 DOI
- [7]
- P. Dankelmann, J. D. Key, and B. G. Rodrigues, “Codes from incidence matrices of graphs”, Designs, Codes and Cryptography 68, 373 (2012) DOI
- [8]
- G. Zémor, “On Cayley Graphs, Surface Codes, and the Limits of Homological Coding for Quantum Error Correction”, Lecture Notes in Computer Science 259 (2009) DOI
- [9]
- J. Haah, M. B. Hastings, D. Poulin, and D. Wecker, “Magic state distillation with low space overhead and optimal asymptotic input count”, Quantum 1, 31 (2017) arXiv:1703.07847 DOI
- [10]
- Quantum Information and Computation 18, (2018) arXiv:1709.02789 DOI
Page edit log
- Fengxing Zhu (2024-03-16) — most recent
- Victor V. Albert (2024-03-16)
- Victor V. Albert (2021-12-16)
- Seyed Sajjad Nezhadi (2021-12-14)
Cite as:
“Cycle code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/homological_classical