## Description

A family of \([[n,k,d]]\) CSS codes whose construction is based on two binary linear seed codes \(C_1\) and \(C_2\).

## Protection

The hypergraph product has distance \(d=O(\sqrt{n})\). The number of encoded logical qubits is \(k=O(k_1k_2)\) where \(k_1\) and \(k_2\) are the dimensions of the classical seed codes \(C_1\) and \(C_2\).

## Transversal Gates

Hadamard (up to logical SWAP gates) and control-\(Z\) on all logical qubits [3].

## Gates

Code deformation techniques yield Clifford gates [4].

## Decoding

ReShape decoder that uses minimum weight decoders for the classical codes used in the hypergraph construction [5].2D geometrically local syndrome extraction circuits with depth order \(O(\sqrt{n})\) using order \(O(n)\) ancilla qubits [6].Erasure-correction can be implemented approximately with \(O(n^2)\) operations, with a probabilistic version running in \(O(n^{1.5})\) operations [7].Improved BP-OSD decoder [8].

## Threshold

Circuit-level noise: \(0.1\%\) with all-to-all connected syndrome extraction circuits [6]. No threshold observed above physical noise rates at or above \(10^{-6}\) using 2D geometrically local syndrome extraction circuits.

## Parents

- Lifted-product (LP) code — Lifted-product codes for trivial group \(G\) are hypergraph-product codes.
- Homological product code — A homological product of chain complexes corresponding to two classical codes is a hypergraph product code [9].

## Child

## Cousins

- XYZ product code — The XYZ product code is based on a hypergraph product of three classical codes.
- Subsystem QPC — The subsystem QPC and hypergraph-product code constructions yield the same dimension and minimum distance, but the former does not yield QLDPC codes; see [1; pg. 18].
- Rotated surface code — Rotated code can be obtained from hypergraph product of two cyclic binary cyclic codes with palindromic generator polynomial ([2], Ex. 7).
- Kitaev surface code — Planar (toric) code can be obtained from hypergraph product of two repetition (cyclic) codes ([2], Ex. 6).

## 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]
- A. O. Quintavalle, P. Webster, and M. Vasmer, “Partitioning qubits in hypergraph product codes to implement logical gates”, (2022) arXiv:2204.10812
- [4]
- A. Krishna and D. Poulin, “Fault-Tolerant Gates on Hypergraph Product Codes”, Physical Review X 11, (2021) arXiv:1909.07424 DOI
- [5]
- A. O. Quintavalle and E. T. Campbell, “ReShape: a decoder for hypergraph product codes”, (2022) arXiv:2105.02370
- [6]
- 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
- [7]
- N. Connolly et al., “Fast erasure decoder for a class of quantum LDPC codes”, (2023) arXiv:2208.01002
- [8]
- O. Higgott and N. P. Breuckmann, “Improved single-shot decoding of higher dimensional hypergraph product codes”, (2022) arXiv:2206.03122
- [9]
- M. B. Hastings, J. Haah, and R. O’Donnell, “Fiber Bundle Codes: Breaking the \(N^{1/2} \operatorname{polylog}(N)\) Barrier for Quantum LDPC Codes”, (2020) arXiv:2009.03921

## Page edit log

- Victor V. Albert (2022-08-02) — most recent
- Victor V. Albert (2022-01-20)
- Joschka Roffe (2021-11-04)

## Cite as:

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