Hypergraph product (HGP) code[1,2] 

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].Improved BP-OSD decoder [7].Erasure-correction can be implemented approximately with \(O(n^2)\) operations with quantum generalizations [8] of the peeling and pruned peeling decoders [9], with a probabilistic version running in \(O(n^{1.5})\) operations.

Code Capacity Threshold

The threshold under ML decoding corresponds to the value of critical point of a two-dimensional random-bond Ising model on the Nishimori line [10–12] (see also [13]).

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

Children

Cousins

  • 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 [16].
  • XYZ product code — The XYZ product code is based on a hypergraph product of three classical codes.
  • Rotated surface code — Rotated code can be obtained from hypergraph product of two cyclic binary cyclic codes with palindromic generator polynomial ([2], Ex. 7).
  • 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].
  • Generalized bicycle (GB) code — An arbitrary GB code of length \(2\ell\) is equivalent 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}=\ell}\rvert\).

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]
O. Higgott and N. P. Breuckmann, “Improved Single-Shot Decoding of Higher-Dimensional Hypergraph-Product Codes”, PRX Quantum 4, (2023) arXiv:2206.03122 DOI
[8]
N. Connolly et al., “Fast erasure decoder for a class of quantum LDPC codes”, (2023) arXiv:2208.01002
[9]
M. G. Luby et al., “Efficient erasure correcting codes”, IEEE Transactions on Information Theory 47, 569 (2001) DOI
[10]
H. Nishimori, “Geometry-Induced Phase Transition in the ±JIsing Model”, Journal of the Physical Society of Japan 55, 3305 (1986) DOI
[11]
E. Dennis et al., “Topological quantum memory”, Journal of Mathematical Physics 43, 4452 (2002) arXiv:quant-ph/0110143 DOI
[12]
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
[13]
R. Fan et al., “Diagnostics of mixed-state topological order and breakdown of quantum memory”, (2023) arXiv:2301.05689
[14]
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
[15]
S. Yang and R. Calderbank, “Quantum Spatially-Coupled Codes”, (2023) arXiv:2305.00137
[16]
N. P. Breuckmann and J. N. Eberhardt, “Quantum Low-Density Parity-Check Codes”, PRX Quantum 2, (2021) arXiv:2103.06309 DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

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.), 2022. https://errorcorrectionzoo.org/c/hypergraph_product
BibTeX:
@incollection{eczoo_hypergraph_product,
  title={Hypergraph product (HGP) code},
  booktitle={The Error Correction Zoo},
  year={2022},
  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.), 2022. https://errorcorrectionzoo.org/c/hypergraph_product

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