[Jump to code hierarchy]

Hypergraph product (HGP) code[1,2]

Alternative names: Quantum hypergraph (QHG) code, Tillich-Zemor product code.

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.

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. The case when the two seed codes are equal, \(C_1=C_2\), is called a square hypergraph product code. If, in addition, \(\text{im} H = \text{im} H^T\), the hypergraph product code is called a symmetric hypergraph product code [3].

Protection

If \([n_i, k_i, d_i]\) (\([r_i, k^T_i, d^T_i]\)) are the parameters of the codes \(\mathrm{ker}H_i\) (\(\mathrm{ker}H_i^T\), taking (\(d=\infty\) if \(k=0\)), the hypergraph product has parameters \([[n_1 n_2 + r_1 r_2, k_1 k_2 + k_1^T k_2^T, \min(d_1, d_2, d_1^T, d_2^T)]]\)

Encoding

Fault-tolerant state preparation via dimension jump [4].

Transversal Gates

Hadamard (up to logical SWAP gates) and control-\(Z\) on all logical qubits [3].Patch-transversal gates inherited from the automorphism group of the underlying classical codes [5; Appx. D].Orientation-preserving constant-depth circuits can only implemenent gates in the Clifford group [6].Permutation-based gates (automorphism gadgets) can be inherited from the underlying classical codes in the hypergraph construction [7].

Gates

Code deformation techniques yield Clifford gates [8].Piecable fault-tolerant circuits, transversal gates, and magic-state injection yield a universal gate set for symmetric hypergraph product codes [3].Targeted logical gates [9].Logical gates via Dehn twists for hypergraph products of cyclic codes [10].

Decoding

Single-ancilla syndrome extraction circuits do not admit hook errors [11].ReShape decoder that uses minimum weight decoders for the classical codes used in the hypergraph construction [12].2D geometrically local syndrome extraction circuits with depth order \(O(\sqrt{n})\) using order \(O(n)\) ancilla qubits [13].Improved BP-OSD decoder [14].Erasure correction can be implemented approximately with \(O(n^2)\) operations with quantum generalizations [15] of the peeling and pruned peeling decoders [16], with a probabilistic version running in \(O(n^{1.5})\) operations. Other nearly optimal erasure decoders exist [17,18]. Initial hypergraph product codes can be further optimized against the erasure channel using reinforcement learning [19].Syndrome measurements are distance-preserving because syndrome extraction circuits can be designed to avoid hook errors [20].Generalization [21] of Viderman’s algorithm for expander codes [22].Linear time iterative decoder [23].

Fault Tolerance

Piecable fault-tolerant circuits, transversal gates, and magic-state injection yield a universal gate set for symmetric hypergraph product codes [3].Single-ancilla syndrome extraction circuits do not admit hook errors [11].There is a fault-tolerant universal computation scheme for hypergraph-product codes concatenated with the \([[4,2,2]]\) code in which the full syndrome measurement on the lower hypergraph product code is performed only if an error is detected at the upper four-qubit code [24].

Code Capacity Threshold

Some thresholds were determined in Ref. [25].Bounds on code capacity thresholds using ML decoding can be obtained by mapping the effect of noise on the code to a statistical mechanical model [26]. For example, a threshold of \(7\%\) was obtained under independent \(X\) and \(Z\) noise for codes obtained from random \((3,4)\)-regular Gallager codes.

Threshold

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

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) [29].
  • XYZ product code— Hypergraph (XYZ) product codes are constructed out of hypergraph products of two (three) classical linear codes.
  • Neural network quantum code— Using reinforcement learning, hypergraph product codes can be further optimized against the erasure channel [19] and can be weight reduced while maintaining distance [30].
  • \([[4,2,2]]\) Four-qubit code— There is a fault-tolerant universal computation scheme for hypergraph-product codes concatenated with the \([[4,2,2]]\) code in which the full syndrome measurement on the lower hypergraph product code is performed only if an error is detected at the upper four-qubit code [24].
  • Concatenated qubit code— There is a fault-tolerant universal computation scheme for hypergraph-product codes concatenated with the \([[4,2,2]]\) code in which the full syndrome measurement on the lower hypergraph product code is performed only if an error is detected at the upper four-qubit code [24].
  • Compactified \(\mathbb{R}\) gauge theory code— The compactified \(\mathbb{R}\) gauge theory code is constructed from a hypergraph product of two repetition codes over the integers.
  • Tiger surface code— The tiger surface code is constructed from a hypergraph product of two repetition codes over the integers.
  • Quantum locally recoverable code (QLRC)— A variant of the hypergraph product can be used to define QLRCs with intersecting recovery sets [31].
  • 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 [32].
  • Self-correcting quantum code— There are bounds on the energy barrier of hypergraph product codes [33].
  • 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\) [34].
  • 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 [35].
  • Kitaev surface code— The planar surface code on a square lattice can be obtained from a hypergraph product of two repetition codes with single-site checks on their ends [2; Exam. 6].
  • Rotated surface code— The rotated surface code can be obtained from hypergraph product of two cyclic linear binary codes with palindromic generator polynomial [2; Exam. 7].
  • Subsystem hypergraph product (SHP) code— Two SHP codes can be gauge-fixed to yield an HGP code [36; 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 to a rotated HGP code with periodicity vectors \(\vec{L}_{1}\) and \(\vec{L}_{2}\) such that \(\lvert{\vec{L}_{1}\times\vec{L}_{2}\rvert=\ell}\) [37].

Member of code lists

Primary Hierarchy

Quantum Domain
Qubit Kingdom
Qubit codeQECC Quantum
Union stabilizer (USt) codeQECC Quantum
Qubit stabilizer codeStabilizer Hamiltonian-based Qubit QECC Quantum
Coherent-parity-check (CPC) code
Qubit CSS codeCSS Stabilizer Hamiltonian-based QECC Quantum
Generalized homological-product qubit CSS codeGeneralized homological-product QLDPC CSS Stabilizer Hamiltonian-based QECC Quantum
Higher-dimensional homological product code
Parents
Higher-dimensional homological product code
Multi-dimensional homological products of two length-one chain complexes reduce to HGP codes.
Homological product codeQubit Generalized homological-product QLDPC CSS Stabilizer Hamiltonian-based QECC Quantum
A homological-product code of length-one chain complexes reduce to an HGP code.
Quantum spatially coupled (SC-QLDPC) codeLattice stabilizer QLDPC Stabilizer Hamiltonian-based Qubit QECC Quantum
Hypergraph-product stabilizer generator matrices can be used as sub-matrices to define a 2D SC-QLDPC code [38].
Galois-qudit HGP codeGeneralized homological-product QLDPC CSS Stabilizer Hamiltonian-based QECC Quantum
Hypergraph product codes are Galois-qudit hypergraph-product codes for qudit dimension \(q=2\).
Hypergraph product (HGP) code
Children
Fibonacci fractal spin-liquid code
The Fibonacci fractal spin-liquid code is a hypergraph product of the repetition code and the Fibonacci code [39], and can be formulated directly as a BP code [40].
Sierpinski prism model code
The Sierpinski prism model code is a hypergraph product of the repetition code and the Newman-Moore code [41], and can be formulated directly as an LP code [40].
Two-foliated fracton code
The two-foliated fracton code is a hypergraph product of the repetition code and the plaquette Ising code on a square lattice with periodic boundary conditions [42].
La-cross code
La-cross codes are constructed using a hypergraph product a cyclic LDPC code with itself.
Long-range enhanced surface code (LRESC)
LRESCs are constructed using a hypergraph product a concatenated LDPC-repetition code with itself.
Quantum expander code
Tillich-Zémor code
Toric code
The toric code can be obtained from a hypergraph product of two repetition codes [2; Exam. 6]. Other hypergraph products of two repetition codes yield the related \([[2d^2-2d+1,1,d]]\) CSS code family [2; Exam. 5].
Fractal surface code
The fractal product code is a hypergraph product of two classical codes defined on a Sierpinski carpet graph [43].

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 348 (2012) arXiv:1202.0928 DOI
[3]
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
[4]
Y. Hong, “Single-shot preparation of hypergraph product codes via dimension jump”, Quantum 9, 1879 (2025) arXiv:2410.05171 DOI
[5]
Y. Hong, M. Marinelli, A. M. Kaufman, and A. Lucas, “Long-range-enhanced surface codes”, Physical Review A 110, (2024) arXiv:2309.11719 DOI
[6]
E. X. Fu, H. Zheng, Z. Li, and Z.-W. Liu, “No-go theorems for logical gates on product quantum codes”, (2025) arXiv:2507.16797
[7]
N. Berthusen, M. J. Gullans, Y. Hong, M. Mudassar, and S. J. S. Tan, “Automorphism gadgets in homological product codes”, (2025) arXiv:2508.04794
[8]
A. Krishna and D. Poulin, “Fault-Tolerant Gates on Hypergraph Product Codes”, Physical Review X 11, (2021) arXiv:1909.07424 DOI
[9]
A. Patra and A. Barg, “Targeted Clifford logical gates for hypergraph product codes”, Quantum 9, 1842 (2025) arXiv:2411.17050 DOI
[10]
R. Tiew and N. P. Breuckmann, “Low-Overhead Entangling Gates from Generalised Dehn Twists”, (2024) arXiv:2411.03302
[11]
S. J. S. Tan and L. Stambler, “Effective Distance of Higher Dimensional HGPs and Weight-Reduced Quantum LDPC Codes”, (2025) arXiv:2409.02193
[12]
A. O. Quintavalle and E. T. Campbell, “ReShape: a decoder for hypergraph product codes”, (2022) arXiv:2105.02370
[13]
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
[14]
O. Higgott and N. P. Breuckmann, “Improved Single-Shot Decoding of Higher-Dimensional Hypergraph-Product Codes”, PRX Quantum 4, (2023) arXiv:2206.03122 DOI
[15]
N. Connolly, V. Londe, A. Leverrier, and N. Delfosse, “Fast erasure decoder for hypergraph product codes”, Quantum 8, 1450 (2024) arXiv:2208.01002 DOI
[16]
M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman, “Efficient erasure correcting codes”, IEEE Transactions on Information Theory 47, 569 (2001) DOI
[17]
M. Gökduman, H. Yao, and H. D. Pfister, “Erasure Decoding for Quantum LDPC Codes via Belief Propagation with Guided Decimation”, 2024 60th Annual Allerton Conference on Communication, Control, and Computing 1 (2024) arXiv:2411.08177 DOI
[18]
H. Yao, M. Gökduman, and H. D. Pfister, “Cluster Decomposition for Improved Erasure Decoding of Quantum LDPC Codes”, (2024) arXiv:2412.08817
[19]
B. C. A. Freire, N. Delfosse, and A. Leverrier, “Optimizing hypergraph product codes with random walks, simulated annealing and reinforcement learning”, (2025) arXiv:2501.09622
[20]
A. G. Manes and J. Claes, “Distance-preserving stabilizer measurements in hypergraph product codes”, Quantum 9, 1618 (2025) arXiv:2308.15520 DOI
[21]
A. Krishna, I. L. Navon, and M. Wootters, “Viderman’s algorithm for quantum LDPC codes”, (2023) arXiv:2310.07868
[22]
M. Viderman, “Linear-time decoding of regular expander codes”, ACM Transactions on Computation Theory 5, 1 (2013) DOI
[23]
A. K. Pradhan, N. Raveendran, N. Rengaswamy, and B. Vasić, “Linear Time Iterative Decoders for Hypergraph-Product and Lifted-Product Codes”, (2025) arXiv:2504.01728
[24]
N. Berthusen, S. J. S. Tan, E. Huang, and D. Gottesman, “Adaptive Syndrome Extraction”, PRX Quantum 6, (2025) arXiv:2502.14835 DOI
[25]
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
[26]
A. A. Kovalev, S. Prabhakar, I. Dumer, and L. P. Pryadko, “Numerical and analytical bounds on threshold error rates for hypergraph-product codes”, Physical Review A 97, (2018) arXiv:1804.01950 DOI
[27]
D. P. DiVincenzo and P. Aliferis, “Effective Fault-Tolerant Quantum Computation with Slow Measurements”, Physical Review Letters 98, (2007) arXiv:quant-ph/0607047 DOI
[28]
O. Chandra, G. Muraleedharan, and G. K. Brennen, “Nonlocal resources for error correction in quantum low-density parity-check codes”, Physical Review Research 7, (2025) arXiv:2409.05818 DOI
[29]
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) 427 (2017) arXiv:1510.02082 DOI
[30]
A. Y. He and Z.-W. Liu, “Discovering highly efficient low-weight quantum error-correcting codes with reinforcement learning”, (2025) arXiv:2502.14372
[31]
K. Bu, W. Gu, and X. Li, “Quantum locally recoverable code with intersecting recovery sets”, (2025) arXiv:2501.10354
[32]
E. T. Campbell, “A theory of single-shot error correction for adversarial noise”, Quantum Science and Technology 4, 025006 (2019) arXiv:1805.09271 DOI
[33]
G. Zhao, A. C. Doherty, and I. H. Kim, “Energy Barrier of Hypergraph Product Codes”, Physical Review Letters 134, (2025) arXiv:2407.20526 DOI
[34]
T. R. Scruby, A. Pesah, and M. Webster, “Quantum Rainbow Codes”, (2024) arXiv:2408.13130
[35]
N. P. Breuckmann and J. N. Eberhardt, “Quantum Low-Density Parity-Check Codes”, PRX Quantum 2, (2021) arXiv:2103.06309 DOI
[36]
M. Li and T. J. Yoder, “A Numerical Study of Bravyi-Bacon-Shor and Subsystem Hypergraph Product Codes”, (2020) arXiv:2002.06257
[37]
R. Wang and L. P. Pryadko, “Distance bounds for generalized bicycle codes”, (2022) arXiv:2203.17216
[38]
S. Yang and R. Calderbank, “Spatially-Coupled QLDPC Codes”, Quantum 9, 1693 (2025) arXiv:2305.00137 DOI
[39]
B. Yoshida, “Exotic topological order in fractal spin liquids”, Physical Review B 88, (2013) arXiv:1302.6248 DOI
[40]
Y. Tan, B. Roberts, N. Tantivasadakarn, B. Yoshida, and N. Y. Yao, “Fracton models from product codes”, (2024) arXiv:2312.08462
[41]
T. Rakovszky and V. Khemani, “The Physics of (good) LDPC Codes II. Product constructions”, (2024) arXiv:2402.16831
[42]
N. P. Breuckmann, M. Davydova, J. N. Eberhardt, and N. Tantivasadakarn, “Cups and Gates I: Cohomology invariants and logical quantum operations”, (2024) arXiv:2410.16250
[43]
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
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: hypergraph_product

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

Cite as:

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/quantum/qubits/stabilizer/qldpc/balanced_product/tensor/singlesector/hypergraph/hypergraph_product.yml.