Graph homology code[1] 

Description

This code's properties are derived from the size two chain complex associated with a particular graph. Given a connected simplicial (no self loops or muliedges) graph \(G = (V, E)\), which is not a tree, with incidence matrix \(\Gamma\) we can construct a code by choosing a parity check matrix which consists of all the linearly independent rows of \(\Gamma\). This is a \([n,k,d]\) code with \(n = |E|\), \(k = 1 - \mathcal{X}(G) = 1-|V|+|E|\), where \( \mathcal{X}(G)\) is the euler characteristic of the graph. The code distance is equal to the shortest size of a cycle, guaranteed to exist since \(G\) is not a tree.

Parent

Cousins

References

[1]
H. Bombin and M. A. Martin-Delgado, “Homological error correction: Classical and quantum codes”, Journal of Mathematical Physics 48, 052105 (2007) arXiv:quant-ph/0605094 DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: homological_classical

Cite as:
“Graph homology code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2021. https://errorcorrectionzoo.org/c/homological_classical
BibTeX:
@incollection{eczoo_homological_classical,
  title={Graph homology code},
  booktitle={The Error Correction Zoo},
  year={2021},
  editor={Albert, Victor V. and Faist, Philippe},
  url={https://errorcorrectionzoo.org/c/homological_classical}
}
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/homological_classical

Cite as:

“Graph homology code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2021. https://errorcorrectionzoo.org/c/homological_classical

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/bits/quantum_inspired/homological_classical.yml.