## Description

A member of a family of CSS codes whose stabilizer generator matrix is obtained from a hypergraph product of two classical linear binary codes. Codes from hypergraph products in higher dimension are called higher-dimensional HGP codes [3].

More technically, the \(x\)- and \(Z\)-type stabilizer generator matrices of a hypergraph product code are, respectively, the boundary and coboundary operators of the 2-complex obtained from the tensor product of a chain complex and cochain complex corresponding to two classical linear binary seed codes. Let the two seed codes be \(C_i\) for \(i\in\{1,2\}\) with parameters \([n_i, k_i, d_i]\), defined as the kernel of \(r_i \times n_i\) check matrices \(H_i\) of rank \(n_i - k_i\). The hypergraph product yields two classical codes \(C_{X,Z}\) with parity-check matrices \begin{align} H_{X}&=\begin{pmatrix}H_{1}\otimes I_{n_{2}} & \,\,I_{r_{1}}\otimes H_{2}^{T}\end{pmatrix}\tag*{(1)}\\ H_{Z}&=\begin{pmatrix}I_{n_{1}}\otimes H_{2} & \,\,H_{1}^{T}\otimes I_{r_{2}}\end{pmatrix}~, \tag*{(2)}\end{align} where \(I_m\) is the \(m\)-dimensional identity matrix. These two codes then yield a hypergraph product code via the CSS construction.

In general, the stabilizer generator matrices of an \(m\)-dimensional hypergraph product code are the boundary and co-boundary operators of a 2-dimensional chain complex contained within an \(m\)-complex that is recursively constructed by taking the tensor product of an \((m-1)\)-complex and a 1-complex, with the 1-complex corresponding to some classical linear binary code.

## Protection

## Transversal Gates

## Gates

## Decoding

## Fault Tolerance

## Code Capacity Threshold

## Threshold

## Parents

- Homological product code — A homological product of chain complexes corresponding to two linear binary codes is a hypergraph product code [20].
- Quantum spatially coupled (SC-QLDPC) code — Hypergraph-product stabilizer generator matrices can be used as sub-matrices to define a 2D SC-QLDPC code [21].
- Galois-qudit HGP code — Hypergraph product codes are Galois-qudit hypergraph-product codes for qudit dimension \(q=2\).

## Children

- Sierpinsky fractal spin-liquid (SFSL) code — The Sierpinsky fractal spin-liquid code is the hypergraph product of the repetition code and the Newman-Moore code [22,23].
- La-cross code — La-cross codes are constructed using the hypergraph product a cyclic LDPC code with itself.
- Long-range enhanced surface code (LRESC) — LRESCs are constructed using the hypergraph product a concatenated LDPC-repetition code with itself.
- Quantum expander code
- Toric code — The toric code can be obtained from a hypergraph product of two repetition codes [2; Ex. 6]. Other hypergraph products of two repetition codes yield the related \([[2d^2-2d+1,1,d]]\) CSS code family [2; Exam. 5].

## Cousins

- Locally testable code (LTC) — Applying the hypergraph product to an LTC yields a code which provides an explicit example of No Low-Error Trivial States (NLETS) [24].
- XYZ product code — Hypergraph (XYZ) product codes are constructed out of hypergraph products of two (three) classical linear codes.
- Linear binary code — Hypergraph product codes are constructed out of two linear binary codes.
- Single-shot code — Two-fold application of the hypergraph product to a pair of binary linear codes yields single-shot QLDPC codes that exploit redundancy in their stabilizer generators [25].
- Self-correcting quantum code — There are bounds on the energy barrier of hypergraph product codes [26].
- Quantum rainbow code — Hypergraph products of color codes yield quantum rainbow codes with growing distance and transversal gates in the Clifford hierarchy. In particular, utilizing this construction for quasi-hyperbolic color codes yields an \([[n,O(n),O(\log n)]]\) triorthogonal code family with magic-state yield parameter \(\gamma\to 0\) [27].
- High-dimensional expander (HDX) code — Ramanujan codes utilize the hypergraph product with a twist, which is an automorphism on one of the complexes in the tensor product, in order to increase distance [28].
- Rotated surface code — Rotated code can be obtained from hypergraph product of two cyclic binary cyclic codes with palindromic generator polynomial ([2], Ex. 7).
- Fractal surface code — The fractal product code is a hypergraph product of two classical codes defined on a Sierpinski carpet graph [29].
- Subsystem homological product code — SP codes are projected higher-dimensional HGP codes [30].
- Subsystem hypergraph product (SHP) code — Two SHP codes can be gauge-fixed to yield an HGP code [31; Sec. III]. The SHP and HGP code constructions yield the same dimension and minimum distance, but the former does not yield QLDPC codes; see [1; pg. 18].
- Generalized bicycle (GB) code — An arbitrary qubit GB code of length \(2\ell\) is equivalent [32] to a rotated quantum hypergraph-product code with periodicity vectors \(\vec{L}_{1}\) and \(\vec{L}_{2}\) such that \(\lvert{\vec{L}_{1}\times\vec{L}_{2}\rvert=\ell}\).

## References

- [1]
- J.-P. Tillich and G. Zemor, “Quantum LDPC Codes With Positive Rate and Minimum Distance Proportional to the Square Root of the Blocklength”, IEEE Transactions on Information Theory 60, 1193 (2014) arXiv:0903.0566 DOI
- [2]
- A. A. Kovalev and L. P. Pryadko, “Improved quantum hypergraph-product LDPC codes”, 2012 IEEE International Symposium on Information Theory Proceedings (2012) arXiv:1202.0928 DOI
- [3]
- W. Zeng and L. P. Pryadko, “Higher-Dimensional Quantum Hypergraph-Product Codes with Finite Rates”, Physical Review Letters 122, (2019) arXiv:1810.01519 DOI
- [4]
- A. O. Quintavalle, P. Webster, and M. Vasmer, “Partitioning qubits in hypergraph product codes to implement logical gates”, Quantum 7, 1153 (2023) arXiv:2204.10812 DOI
- [5]
- Y. Hong et al., “Long-range-enhanced surface codes”, Physical Review A 110, (2024) arXiv:2309.11719 DOI
- [6]
- A. Krishna and D. Poulin, “Fault-Tolerant Gates on Hypergraph Product Codes”, Physical Review X 11, (2021) arXiv:1909.07424 DOI
- [7]
- S. J. S. Tan and L. Stambler, “Effective Distance of Higher Dimensional HGPs and Weight-Reduced Quantum LDPC Codes”, (2024) arXiv:2409.02193
- [8]
- A. O. Quintavalle and E. T. Campbell, “ReShape: a decoder for hypergraph product codes”, (2022) arXiv:2105.02370
- [9]
- N. Delfosse, M. E. Beverland, and M. A. Tremblay, “Bounds on stabilizer measurement circuits and obstructions to local implementations of quantum LDPC codes”, (2021) arXiv:2109.14599
- [10]
- O. Higgott and N. P. Breuckmann, “Improved Single-Shot Decoding of Higher-Dimensional Hypergraph-Product Codes”, PRX Quantum 4, (2023) arXiv:2206.03122 DOI
- [11]
- N. Connolly et al., “Fast erasure decoder for hypergraph product codes”, Quantum 8, 1450 (2024) arXiv:2208.01002 DOI
- [12]
- M. G. Luby et al., “Efficient erasure correcting codes”, IEEE Transactions on Information Theory 47, 569 (2001) DOI
- [13]
- A. G. Manes and J. Claes, “Distance-preserving stabilizer measurements in hypergraph product codes”, (2023) arXiv:2308.15520
- [14]
- A. Krishna, I. L. Navon, and M. Wootters, “Viderman’s algorithm for quantum LDPC codes”, (2023) arXiv:2310.07868
- [15]
- M. Viderman, “Linear-time decoding of regular expander codes”, ACM Transactions on Computation Theory 5, 1 (2013) DOI
- [16]
- 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) arXiv:1208.2317 DOI
- [17]
- A. A. Kovalev et al., “Numerical and analytical bounds on threshold error rates for hypergraph-product codes”, Physical Review A 97, (2018) arXiv:1804.01950 DOI
- [18]
- D. P. DiVincenzo and P. Aliferis, “Effective Fault-Tolerant Quantum Computation with Slow Measurements”, Physical Review Letters 98, (2007) arXiv:quant-ph/0607047 DOI
- [19]
- O. Chandra, G. Muraleedharan, and G. K. Brennen, “Non-local resources for error correction in quantum LDPC codes”, (2024) arXiv:2409.05818
- [20]
- M. B. Hastings, J. Haah, and R. O’Donnell, “Fiber bundle codes: breaking the n \({}^{\text{1/2}}\) polylog( n ) barrier for Quantum LDPC codes”, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing 17, 1276 (2021) arXiv:2009.03921 DOI
- [21]
- S. Yang and R. Calderbank, “Spatially-Coupled QDLPC Codes”, (2023) arXiv:2305.00137
- [22]
- Y. Tan et al., “Fracton models from product codes”, (2024) arXiv:2312.08462
- [23]
- T. Rakovszky and V. Khemani, “The Physics of (good) LDPC Codes II. Product constructions”, (2024) arXiv:2402.16831
- [24]
- L. Eldar and A. W. Harrow, “Local Hamiltonians Whose Ground States Are Hard to Approximate”, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) (2017) arXiv:1510.02082 DOI
- [25]
- E. T. Campbell, “A theory of single-shot error correction for adversarial noise”, Quantum Science and Technology 4, 025006 (2019) arXiv:1805.09271 DOI
- [26]
- G. Zhao, A. C. Doherty, and I. H. Kim, “On the energy barrier of hypergraph product codes”, (2024) arXiv:2407.20526
- [27]
- T. R. Scruby, A. Pesah, and M. Webster, “Quantum Rainbow Codes”, (2024) arXiv:2408.13130
- [28]
- N. P. Breuckmann and J. N. Eberhardt, “Quantum Low-Density Parity-Check Codes”, PRX Quantum 2, (2021) arXiv:2103.06309 DOI
- [29]
- C. G. Brell, “A proposal for self-correcting stabilizer quantum memories in 3 dimensions (or slightly less)”, New Journal of Physics 18, 013050 (2016) arXiv:1411.7046 DOI
- [30]
- W. Zeng and L. P. Pryadko, “Minimal distances for certain quantum product codes and tensor products of chain complexes”, Physical Review A 102, (2020) arXiv:2007.12152 DOI
- [31]
- M. Li and T. J. Yoder, “A Numerical Study of Bravyi-Bacon-Shor and Subsystem Hypergraph Product Codes”, (2020) arXiv:2002.06257
- [32]
- R. Wang and L. P. Pryadko, “Distance bounds for generalized bicycle codes”, (2022) arXiv:2203.17216

## Page edit log

- Victor V. Albert (2024-08-19) — most recent
- Shi Jie Samuel Tan (2024-08-19)
- Christopher A. Pattison (2023-10-25)
- Victor V. Albert (2022-08-02)
- Victor V. Albert (2022-01-20)
- Joschka Roffe (2021-11-04)

## Cite as:

“Hypergraph product (HGP) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/hypergraph_product