Alternative names: Graph theoretic code, Graph homology code, Graph code.
Description
A code whose parity-check matrix forms the incidence matrix of a graph. This code's properties are derived from the size two chain complex associated with the graph.
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 parity check matrix \(H\) is an \(|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.
Protection
More generally, an \([n,k,d]\) cycle code constructed out of a graph with \(n = |E|\), \(k = 1 - \mathcal{X}(G) = 1-|V|+|E|\), where \( \mathcal{X}(G)\) is the euler characteristic of the graph [7]. 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. [7] 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. [7] for a brief exposition.
- Homological code— Cycle codes feature in generalizations of the surface code [7].
- 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 [8; Appx. A.2.1][9; Sec. VII.A].
Primary Hierarchy
Parents
Incidence matrices of graphs have no repeated columns since that would correspond to multi-edges.
Cycle code
Children
References
- [1]
- Kasami, T. "A topological approach to construction of group codes." J. Inst. Elec. Commun. Engrs.(Japan) 44 (1961): 1316-1321.
- [2]
- Huffman, D. A. "A graph-theoretic formulation of binary group codes." Summaries of papers presented at ICMCI, part 3 (1964): 29-30.
- [3]
- Frazer, W. D. "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]
- 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
- [8]
- 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
- [9]
- 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