# Quantum low-density parity-check (QLDPC) code[1]

## Description

Also called a sparse quantum code. Member of a family of \([[n,k,d]]\) modular-qudit or Galois-qudit stabilizer codes for which the number of sites participating in each stabilizer generator and the number of stabilizer generators that each site participates in are both bounded by a constant as \(n\to\infty\). A geometrically local stabilizer code is a QLDPC code where the sites involved in any syndrome bit are contained in a fixed volume that does not scale with \(n\). As opposed to general stabilizer codes, syndrome extraction of the constant-weight check operators of a QLDPC codes can be done using a constant-depth circuit.

Notable \([[n,k,d]]\) QLDPC codes are summarized in Table I, demonstrating the steady improvement in code parameters that culminated in the first asymptotically good QLDPC codes.

\(k\) | \(d\) | Code |
---|---|---|

\(2\) | \(\sqrt{n}\) | |

\(2\) | \(\sqrt{n\sqrt{\log n}}\) | |

\(\Theta(n)\) | \(\sqrt{n}\) | |

\(\sqrt{n}/\log n\) | \(\sqrt{n} \log n\) | |

\(\sqrt{n}\) | \(\sqrt{n} \log^c n\) | |

\(n^{3/5}/\text{polylog}(n)\) | \(n^{3/5}/\text{polylog}(n)\) | |

\(\log n\) | \(n/\log n\) | |

\(\Theta(n)\) | \(\Theta(n)\) | |

\(\Theta(n)\) | \(\Theta(n)\) | |

\(\Theta(n)\) | \(\Theta(n)\) |

Strictly speaking, the term parity check describes only bitwise qubit error syndromes. Nevertheless, qudit stabilizer codes satisfying the above criteria are also called QLDPC codes.

## Protection

## Rate

Asymptotic scaling of \(k\) and \(d\) with \(n\) depends heavily on the code construction.

Geometrically local qubit codes are limited by the Bravyi-Poulin-Terhal (BPT) bound [2] (see also [3,4]), which states that \(d \leq O(n^{1-1/D})\) and \(k d^{2/D-1} = O(n)\) for \(D\)-dimensional lattice geometries. Codes on a \(D\)-dimensional Riemannian manifold with diameter \(L\) satisfy \(k = O(L^{D-2})\) [5].

For general graphs, distance is limited by graphs' connectivity, and a constant relative minimum distance can be achieved only for graphs that contain expanders [6]. Conversely, a code with parameters \(k\) and \(d\) requires a graph with \(\Omega(d)\) edges of length \(\Omega(d/n^{1/D})\) [7].

## Gates

## Decoding

## Fault Tolerance

## Code Capacity Threshold

## Threshold

## Notes

## Parents

## Children

- Fracton code — Fracton codes admit geometrically local stabilizer generators on a cubic lattice.
- Generalized homological-product code — Homological products are a primary tool for generating QLDPC codes with favorable parameters. Typically, whenever the input codes are LDPC or QLDPC, the resulting code will be QLDPC with non geometrically local stabilizer generators.
- Good QLDPC code
- Translationally invariant stabilizer code — Translationally-invariant stabilizer codes are geometrically local.
- Classical-product code
- Hierarchical code

## Cousins

- Low-density parity-check (LDPC) code
- Topological code — Topological codes are not generally defined using Pauli strings. However, for appropriate tesselations, the codespace is the ground-state subspace of a geometrically local Hamiltonian. In this sense, topological codes are QLDPC codes. On the other hand, chain complexes describing some QLDPC codes can be 'lifted' into higher-dimensional manifolds admitting some notion of geometric locality [26]. This opens up the possibility that some QLDPC codes, despite not being geometrically local, can in fact be associated with a geometrically local theory described by a category.
- Dynamically-generated QECC — QLDPC codes can arise from a dynamical process [27].
- Quantum locally testable code (QLTC) — Stabilizer LTCs are QLDPC. More general QLTCs are not defined using Pauli strings, but the codespace is the ground-state subspace of a local Hamiltonian. In this sense, QLTCs are QLDPC codes.
- Honeycomb Floquet code — The Floquet check operators are weight-two, and each qubit participates in one check each round.
- Generalized bicycle (GB) code — A code GB\((a,b)\) is given by the sum of weights of polynomials \(a(x)\) and \(b(x)\). The GB code ansatz is convenient for designing quantum LDPC codes.

## References

- [1]
- D. J. C. MacKay, G. Mitchison, and P. L. McFadden, “Sparse-Graph Codes for Quantum Error Correction”, IEEE Transactions on Information Theory 50, 2315 (2004) arXiv:quant-ph/0304161 DOI
- [2]
- S. Bravyi, D. Poulin, and B. Terhal, “Tradeoffs for Reliable Quantum Information Storage in 2D Systems”, Physical Review Letters 104, (2010) arXiv:0909.5200 DOI
- [3]
- S. Bravyi and B. Terhal, “A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes”, New Journal of Physics 11, 043029 (2009) arXiv:0810.1983 DOI
- [4]
- S. Bravyi, “Subsystem codes with spatially local generators”, Physical Review A 83, (2011) arXiv:1008.1029 DOI
- [5]
- J. Haah, “A degeneracy bound for homogeneous topological order”, SciPost Physics 10, (2021) arXiv:2009.13551 DOI
- [6]
- N. Baspin and A. Krishna, “Connectivity constrains quantum codes”, Quantum 6, 711 (2022) arXiv:2106.00765 DOI
- [7]
- N. Baspin and A. Krishna, “Quantifying Nonlocality: How Outperforming Local Quantum Codes Is Expensive”, Physical Review Letters 129, (2022) arXiv:2109.10982 DOI
- [8]
- S. Bravyi and R. König, “Classification of Topologically Protected Gates for Local Stabilizer Codes”, Physical Review Letters 110, (2013) arXiv:1206.1609 DOI
- [9]
- D. Poulin and Y. Chung, “On the iterative decoding of sparse quantum codes”, (2008) arXiv:0801.1241
- [10]
- S. Miao et al., “Neural Belief Propagation Decoding of Quantum LDPC Codes Using Overcomplete Check Matrices”, (2023) arXiv:2212.10245
- [11]
- Z. Babar et al., “Fifteen Years of Quantum LDPC Coding and Improved Decoding Strategies”, IEEE Access 3, 2492 (2015) DOI
- [12]
- P. Panteleev and G. Kalachev, “Degenerate Quantum LDPC Codes With Good Finite Length Performance”, Quantum 5, 585 (2021) arXiv:1904.02703 DOI
- [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]
- N. Raveendran et al., “Soft Syndrome Decoding of Quantum LDPC Codes for Joint Correction of Data and Syndrome Errors”, (2022) arXiv:2205.02341
- [15]
- J. du Crest, M. Mhalla, and V. Savin, “Stabilizer Inactivation for Message-Passing Decoding of Quantum LDPC Codes”, (2023) arXiv:2205.06125
- [16]
- L. Berent, L. Burgholzer, and R. Wille, “Software Tools for Decoding Quantum Low-Density Parity-Check Codes”, Proceedings of the 28th Asia and South Pacific Design Automation Conference (2023) arXiv:2209.01180 DOI
- [17]
- L. Z. Cohen et al., “Low-overhead fault-tolerant quantum computing using long-range connectivity”, Science Advances 8, (2022) arXiv:2110.10794 DOI
- [18]
- D. Gottesman, “Fault-Tolerant Quantum Computation with Constant Overhead”, (2014) arXiv:1310.2984
- [19]
- O. Fawzi, A. Grospellier, and A. Leverrier, “Constant Overhead Quantum Fault-Tolerance with Quantum Expander Codes”, 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) (2018) arXiv:1808.03821 DOI
- [20]
- N. Rengaswamy et al., “Entanglement Purification with Quantum LDPC Codes and Iterative Decoding”, (2022) arXiv:2210.14143
- [21]
- E. Dennis et al., “Topological quantum memory”, Journal of Mathematical Physics 43, 4452 (2002) arXiv:quant-ph/0110143 DOI
- [22]
- 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
- [23]
- A. A. Kovalev and L. P. Pryadko, “Spin glass reflection of the decoding transition for quantum error correcting codes”, (2014) arXiv:1311.7688
- [24]
- I. Dumer, A. A. Kovalev, and L. P. Pryadko, “Thresholds for Correcting Errors, Erasures, and Faulty Syndrome Measurements in Degenerate Quantum Codes”, Physical Review Letters 115, (2015) arXiv:1412.6172 DOI
- [25]
- N. P. Breuckmann and J. N. Eberhardt, “Quantum Low-Density Parity-Check Codes”, PRX Quantum 2, (2021) arXiv:2103.06309 DOI
- [26]
- M. Freedman and M. B. Hastings, “Building manifolds from quantum codes”, (2021) arXiv:2012.02249
- [27]
- M. Ippoliti et al., “Entanglement Phase Transitions in Measurement-Only Dynamics”, Physical Review X 11, (2021) arXiv:2004.09560 DOI

## Page edit log

- Victor V. Albert (2022-10-02) — most recent
- Eugene Tang (2022-10-02)
- Victor V. Albert (2022-09-16)
- Victor V. Albert (2022-05-13)
- Victor V. Albert (2022-01-24)
- Xiaozhen Fu (2021-12-12)

## Cite as:

“Quantum low-density parity-check (QLDPC) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/qldpc