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