Hypergraph product (HGP) code[1,2] 

Also known as 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 codes. Codes from hypergraph products in higher dimension are called higher-dimensional HGP codes [3].

The \([[n,k,d]]\) CSS code's construction is based on two binary linear seed codes, \(i\in\{1,2\}\) \(C_i\) 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.

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)]]\)

Transversal Gates

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

Gates

Code deformation techniques yield Clifford gates [5].

Decoding

ReShape decoder that uses minimum weight decoders for the classical codes used in the hypergraph construction [6].2D geometrically local syndrome extraction circuits with depth order \(O(\sqrt{n})\) using order \(O(n)\) ancilla qubits [7].Improved BP-OSD decoder [8].Erasure-correction can be implemented approximately with \(O(n^2)\) operations with quantum generalizations [9] of the peeling and pruned peeling decoders [10], with a probabilistic version running in \(O(n^{1.5})\) operations.Syndrome measurements are distance-preserving because syndrome extraction circuits can be designed to avoid hook errors [11].Generalization [12] of Viderman's algorithm for expander codes [13].

Code Capacity Threshold

Some thresholds were determined in Ref. [14].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 [15]. 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 [7]. No threshold observed above physical noise rates at or above \(10^{-6}\) using 2D geometrically local syndrome extraction circuits.

Parents

Children

Cousins

  • 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 classical 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 [21].
  • 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 [22].
  • 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 [23].
  • Subsystem homological product code — SP codes are projected higher-dimensional HGP codes [24].
  • Subsystem hypergraph product (SHP) code — Two SHP codes can be gauge-fixed to yield an HGP code [25; 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 [26] 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]
A. Krishna and D. Poulin, “Fault-Tolerant Gates on Hypergraph Product Codes”, Physical Review X 11, (2021) arXiv:1909.07424 DOI
[6]
A. O. Quintavalle and E. T. Campbell, “ReShape: a decoder for hypergraph product codes”, (2022) arXiv:2105.02370
[7]
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
[8]
O. Higgott and N. P. Breuckmann, “Improved Single-Shot Decoding of Higher-Dimensional Hypergraph-Product Codes”, PRX Quantum 4, (2023) arXiv:2206.03122 DOI
[9]
N. Connolly et al., “Fast erasure decoder for a class of quantum LDPC codes”, (2023) arXiv:2208.01002
[10]
M. G. Luby et al., “Efficient erasure correcting codes”, IEEE Transactions on Information Theory 47, 569 (2001) DOI
[11]
A. G. Manes and J. Claes, “Distance-preserving stabilizer measurements in hypergraph product codes”, (2023) arXiv:2308.15520
[12]
A. Krishna, I. L. Navon, and M. Wootters, “Viderman’s algorithm for quantum LDPC codes”, (2023) arXiv:2310.07868
[13]
M. Viderman, “Linear-time decoding of regular expander codes”, ACM Transactions on Computation Theory 5, 1 (2013) DOI
[14]
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
[15]
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
[16]
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
[17]
S. Yang and R. Calderbank, “Spatially-Coupled QDLPC Codes”, (2023) arXiv:2305.00137
[18]
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
[19]
Y. Tan et al., “Fracton models from product codes”, (2024) arXiv:2312.08462
[20]
T. Rakovszky and V. Khemani, “The Physics of (good) LDPC Codes II. Product constructions”, (2024) arXiv:2402.16831
[21]
E. T. Campbell, “A theory of single-shot error correction for adversarial noise”, Quantum Science and Technology 4, 025006 (2019) arXiv:1805.09271 DOI
[22]
N. P. Breuckmann and J. N. Eberhardt, “Quantum Low-Density Parity-Check Codes”, PRX Quantum 2, (2021) arXiv:2103.06309 DOI
[23]
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
[24]
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
[25]
M. Li and T. J. Yoder, “A Numerical Study of Bravyi-Bacon-Shor and Subsystem Hypergraph Product Codes”, (2020) arXiv:2002.06257
[26]
R. Wang and L. P. Pryadko, “Distance bounds for generalized bicycle codes”, (2022) arXiv:2203.17216
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.), 2023. https://errorcorrectionzoo.org/c/hypergraph_product
BibTeX:
@incollection{eczoo_hypergraph_product, title={Hypergraph product (HGP) code}, booktitle={The Error Correction Zoo}, year={2023}, 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.), 2023. https://errorcorrectionzoo.org/c/hypergraph_product

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