Quantum low-density parity-check (QLDPC) code 

Also known as Sparse quantum code.

Description

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 \(w\) as \(n\to\infty\); can be denoted by \([[n,k,d,w]]\). Sometimes, the two parameters are explicitly stated: each site of an an \((l,w)\)-regular QLDPC code is acted on by \(\leq l\) generators of weight \(\leq w\). QLDPC codes can correct many stochastic errors far beyond the distance, which may not scale as favorably. Together with more accurate, faster, and easier-to-parallelize measurements than those of general stabilizer codes, this property makes QLDPC codes interesting in practice.

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

Kitaev toric

\(2\)

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

Freedman-Meyer-Luo

\(\Theta(n)\)

\(\sqrt{n}\)

hypergraph product

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

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

high-dimensional expander (HDX)

\(\sqrt{n}\)

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

tensor-product HDX

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

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

fiber-bundle

\(\log n\)

\(n/\log n\)

lifted-product (LP)

\(\Theta(n)\)

\(\Theta(n)\)

expander LP

\(\Theta(n)\)

\(\Theta(n)\)

quantum Tanner

\(\Theta(n)\)

\(\Theta(n)\)

Dinur-Hsieh-Lin-Vidick

Table I: Notable QLDPC codes; \(c\) is a positive integer.

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

Detects errors on \(d-1\) sites, corrects errors on \(\left\lfloor (d-1)/2 \right\rfloor\) sites. Code distance may not be a reliable marker of code performance.

Since QLDPC codes are stabilizer QLRCs whose locality \(r = w\), their relative distance is bounded by [1; Thm. 4] \begin{align} \delta = \frac{d}{n} \leq \frac{1}{2} - \Omega\left(\frac{1}{r}\right)~. \tag*{(1)}\end{align}

Rate

Asymptotic scaling of \(k\) and \(d\) with \(n\) depends heavily on the code construction. Bounds generalizing the BPT bound to QLDPC codes depend on the separation profile of the code's underlying connectivity graph [2,3]. A constant relative minimum distance can be achieved only for graphs that contain expanders [2]. Conversely, a code with parameters \(k\) and \(d\) requires a graph with \(\Omega(d)\) edges of length \(\Omega(d/n^{1/D})\) [4]. Random QLDPC codes found by solving certain constraint satisfaction problems (CSPs) practically achieve the capacity of the erasure channel [5].

Qubit QLDPC codes cannot attain the capacity of the erasure channel [6], but this capacity can be attained by code families with weight \(w = O(\text{polylog}n)\) [7].

Encoding

Fault-tolerant encodes utilizing pre-shared entanglement [8].

Decoding

Iterative error estimation based on the MIN-SUM and SUM-PRODUCT algorithms [9].Belief-propagation (BP) decoder [10] is a quantum version of the classical BP decoder, but performance suffers due to degeneracy [11]. Various post-processing algorithms have been proposed (see below and also Refs. [12,13]).BP-OSD decoder, scaling as \(O(n^3)\), adds a post-processing step based on ordered statistics decoding (OSD) to the belief propogation (BP) decoder [14]. For an open-source implementation, see [15,16].Neural BP decoder [17] for qubit codes.Partially and fully decoupled BP decoders, which use the decoupling representation, yield improvements against depolarizing noise [18].Message-passing decoder utilizing stabilizer inactivation (MP-SI a.k.a. BP-SI) for CSS-type QLDPC qubit codes [19].BP localized statistics decoding (BP-LSD) that exploits error clustering [20].Syndrome-based linear programming (SB-LP) algorithm can be applied as a post-processing step after syndrome-based min-sum (SM-MS) decoding [21].BP guided decimation (BPGD) decoder [22].Ambiguity clustering (AC) decoder, in which measurement data is divided into clusters and decoded independently [23].Non-binary decoding algorithm for CSS-type QLDPC codes [24].2D geometrically local syndrome extraction circuits with bounded depth using order \(O(n^2)\) ancilla qubits [25]. For CSS codes, syndrome extraction can be implemented in constant depth [26].Soft (i.e., analog) syndrome iterative belief propagation for CSS-type QLDPC codes, utilizing the continuous signal obtained in the physical implementation of the stabilizer measurement (as opposed to discretizing the signal into a syndrome bit) [27].Extensions of the union-find decoder for qubit QLDPC codes [28,29].Sliding-window decoding [30].Closed-branch decoder [31].BP with guided decimation guessing (GDG) sliding-window decoder for CSS qubit codes [32].

Fault Tolerance

Lattice surgery techniques with ancilla qubits [33,34]. In one such technique, one first performs a logical measurement by code switching into a code whose stabilizer group includes the original stabilizers together with the logical Paulis that are to be measured. Then, one can reduce the weight of the output code using weight reduction.Fault-tolerance with constant overhead can be performed on certain QLDPC codes [35], e.g., quantum expander codes [36].GHZ state distillation for Steane error correction [37].

Code Capacity Threshold

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 [38–40].Bounds on code capacity thresholds for various noise models exist in terms of stabilizer generator weights [41].

Threshold

QLDPC codes with a constant encoding rate can reduce the overhead of fault-tolerant quantum computation to be constant [35].

Notes

Infleqtion QLDPC package for estimating distance and creating various qubit and Galois-qudit QLDPC CSS codes [42]Links to code tables of notable QLDPC codes [43].Reviews of QLDPC codes provided in Refs. [24,43].There exist distance-dependent [44; Thm. 1] and rate-dependent [44; Thm. 3ii] lower bounds on the degree of entanglement of a qubit QLDPC code.

Parents

Children

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 [45].
  • Dynamically-generated QECC — QLDPC codes can arise from a dynamical process [46].
  • Hamiltonian-based code — QLDPC code Hamiltonians can be simulated, with the help of perturbation theory, by two-dimensional Hamiltonians with non-commuting terms whose interactions scale with \(n\) [47].
  • Single-shot code — Qubit QLDPC codes satisfying linear confinement are single shot [48]. Any code that admits a local greedy decoder also satisfies linear confinement, and so is single shot [34].
  • Low-density generator-matrix (LDGM) code — LDGM codes can yield CSS [49–52] and non-CSS [53,54] QLDPC codes. Some of the LDGM-based CSS codes have \(n\)-independent minimum distance and no code capacity threshold [55; Sec. 4.2].
  • Random stabilizer code — Random QLDPC codes found by solving certain constraint satisfaction problems (CSPs) practically achieve the capacity of the erasure channel [5].
  • Quasi-cyclic LDPC (QC-LDPC) code — QC-LDPC codes can be used to make QLDPC codes using various non-CSS constructions [56].
  • 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.
  • Sparse subsystem code — Sparse subsystem codes reduce to QLDPC codes when there are no gauge qudits.
  • Honeycomb Floquet code — The Floquet check operators are weight-two, and each qubit participates in one check each round.
  • Spacetime circuit code — General spacetime circuit codes can be sparsified to yield QLDPC spacetime circuit codes [57].
  • EA QLDPC code
  • Bicycle code — Bicycle codes are the first QLDPC codes [58].
  • \(D\)-dimensional twisted toric code — It is conjectured that appropriate twisted boundary conditions yield multi-dimensional toric code families with linear distance and logarithmic-weight stabilizer generators [59].
  • Two-block CSS code — When matrices \(A\) and \(B\) have row and column weights bounded by \(W\), a two-block CSS code is a quantum LDPC code with stabilizer generators bounded by \(2W\).
  • Distance-balanced code — Lattice surgery techniques for QLDPC codes [33,34] utilize weight reduction.
  • Two-block group-algebra (2BGA) codes — Given group algebra elements \(a,b\in \mathbb{F}_q[G]\) with weights \(W_a\) and \(W_b\) (i.e., number of non-zero terms in the expansion), the 2BGA code LP\((a,b)\) has stabilizer generators of uniform weight \(W_a+W_b\).
  • Generalized bicycle (GB) code — Stabilizer generators of the code GB\((a,b)\) have weights given by the sum of weights of polynomials \(a(x)\) and \(b(x)\). The GB code ansatz is convenient for designing QLDPC codes and several extensions exist [60].

References

[1]
L. Golowich and V. Guruswami, “Quantum Locally Recoverable Codes”, (2023) arXiv:2311.08653
[2]
N. Baspin and A. Krishna, “Connectivity constrains quantum codes”, Quantum 6, 711 (2022) arXiv:2106.00765 DOI
[3]
N. Baspin et al., “Improved rate-distance trade-offs for quantum codes with restricted connectivity”, (2023) arXiv:2307.03283
[4]
N. Baspin and A. Krishna, “Quantifying Nonlocality: How Outperforming Local Quantum Codes Is Expensive”, Physical Review Letters 129, (2022) arXiv:2109.10982 DOI
[5]
M. Tremblay, G. Duclos-Cianci, and S. Kourtis, “Finite-rate sparse quantum codes aplenty”, Quantum 7, 985 (2023) arXiv:2207.03562 DOI
[6]
N. Delfosse and G. Zémor, “Upper Bounds on the Rate of Low Density Stabilizer Codes for the Quantum Erasure Channel”, (2012) arXiv:1205.7036
[7]
S. Lloyd, P. Shor, and K. Thompson, “polylog-LDPC Capacity Achieving Codes for the Noisy Quantum Erasure Channel”, (2017) arXiv:1703.00382
[8]
A. K. Sharma and S. S. Garani, “Fault-Tolerant Quantum LDPC Encoders”, (2024) arXiv:2405.07242
[9]
T. Camara, H. Ollivier, and J.-P. Tillich, “Constructions and performance of classes of quantum LDPC codes”, (2005) arXiv:quant-ph/0502086
[10]
D. Poulin and Y. Chung, “On the iterative decoding of sparse quantum codes”, (2008) arXiv:0801.1241
[11]
N. Raveendran and B. Vasić, “Trapping Sets of Quantum LDPC Codes”, Quantum 5, 562 (2021) arXiv:2012.15297 DOI
[12]
J. Kim, H. Jung, and J. Ha, “Low-Complexity Decoding Algorithm Utilizing Degeneracy for Quantum LDPC Codes”, MILCOM 2023 - 2023 IEEE Military Communications Conference (MILCOM) (2023) DOI
[13]
T.-H. Huang and Y.-L. Ueng, “A Binary BP Decoding Using Posterior Adjustment for Quantum LDPC Codes”, ICASSP 2024 - 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (2024) DOI
[14]
P. Panteleev and G. Kalachev, “Degenerate Quantum LDPC Codes With Good Finite Length Performance”, Quantum 5, 585 (2021) arXiv:1904.02703 DOI
[15]
J. Roffe et al., “Decoding across the quantum low-density parity-check code landscape”, Physical Review Research 2, (2020) arXiv:2005.07016 DOI
[16]
Roffe, Joschka. "LDPC: Python tools for low density parity check codes." (2022).
[17]
S. Miao et al., “Neural Belief Propagation Decoding of Quantum LDPC Codes Using Overcomplete Check Matrices”, (2023) arXiv:2212.10245
[18]
Z. Yi et al., “Improved belief propagation decoding algorithm based on decoupling representation of Pauli operators for quantum LDPC codes”, (2023) arXiv:2305.17505
[19]
J. du Crest, M. Mhalla, and V. Savin, “Stabilizer Inactivation for Message-Passing Decoding of Quantum LDPC Codes”, (2023) arXiv:2205.06125
[20]
T. Hillmann et al., “Localized statistics decoding: A parallel decoding algorithm for quantum low-density parity-check codes”, (2024) arXiv:2406.18655
[21]
S. Javed et al., “Low-Complexity Linear Programming Based Decoding of Quantum LDPC codes”, (2024) arXiv:2311.18488
[22]
H. Yao et al., “Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation”, (2024) arXiv:2312.10950
[23]
S. Wolanski and B. Barber, “Ambiguity Clustering: an accurate and efficient decoder for qLDPC codes”, (2024) arXiv:2406.14527
[24]
Z. Babar et al., “Fifteen Years of Quantum LDPC Coding and Improved Decoding Strategies”, IEEE Access 3, 2492 (2015) DOI
[25]
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
[26]
M. A. Tremblay, N. Delfosse, and M. E. Beverland, “Constant-Overhead Quantum Error Correction with Thin Planar Connectivity”, Physical Review Letters 129, (2022) arXiv:2109.14609 DOI
[27]
N. Raveendran et al., “Soft Syndrome Decoding of Quantum LDPC Codes for Joint Correction of Data and Syndrome Errors”, (2022) arXiv:2205.02341
[28]
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
[29]
M. C. Löbl et al., “Breadth-first graph traversal union-find decoder”, (2024) arXiv:2407.15988
[30]
S. Huang and S. Puri, “Improved Noisy Syndrome Decoding of Quantum LDPC Codes with Sliding Window”, (2023) arXiv:2311.03307
[31]
A. deMarti iOlius and J. E. Martinez, “The closed-branch decoder for quantum LDPC codes”, (2024) arXiv:2402.01532
[32]
A. Gong, S. Cammerer, and J. M. Renes, “Toward Low-latency Iterative Decoding of QLDPC Codes Under Circuit-Level Noise”, (2024) arXiv:2403.18901
[33]
L. Z. Cohen et al., “Low-overhead fault-tolerant quantum computing using long-range connectivity”, Science Advances 8, (2022) arXiv:2110.10794 DOI
[34]
Q. Xu et al., “Constant-Overhead Fault-Tolerant Quantum Computation with Reconfigurable Atom Arrays”, (2023) arXiv:2308.08648
[35]
D. Gottesman, “Fault-Tolerant Quantum Computation with Constant Overhead”, (2014) arXiv:1310.2984
[36]
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
[37]
N. Rengaswamy et al., “Entanglement Purification with Quantum LDPC Codes and Iterative Decoding”, Quantum 8, 1233 (2024) arXiv:2210.14143 DOI
[38]
E. Dennis et al., “Topological quantum memory”, Journal of Mathematical Physics 43, 4452 (2002) arXiv:quant-ph/0110143 DOI
[39]
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
[40]
A. A. Kovalev and L. P. Pryadko, “Spin glass reflection of the decoding transition for quantum error correcting codes”, (2014) arXiv:1311.7688
[41]
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
[42]
Michael A. Perlin. qLDPC. https://github.com/Infleqtion/qLDPC, 2023.
[43]
N. P. Breuckmann and J. N. Eberhardt, “Quantum Low-Density Parity-Check Codes”, PRX Quantum 2, (2021) arXiv:2103.06309 DOI
[44]
S. Bravyi et al., “How much entanglement is needed for quantum error correction?”, (2024) arXiv:2405.01332
[45]
M. Freedman and M. B. Hastings, “Building manifolds from quantum codes”, (2021) arXiv:2012.02249
[46]
M. Ippoliti et al., “Entanglement Phase Transitions in Measurement-Only Dynamics”, Physical Review X 11, (2021) arXiv:2004.09560 DOI
[47]
H. Apel and N. Baspin, “Simulating LDPC code Hamiltonians on 2D lattices”, (2023) arXiv:2308.13277
[48]
A. O. Quintavalle et al., “Single-Shot Error Correction of Three-Dimensional Homological Product Codes”, PRX Quantum 2, (2021) arXiv:2009.11790 DOI
[49]
Hatuying Lou and J. Garcia-Frias, “Quantum error-correction using codes with low density generator matrix”, IEEE 6th Workshop on Signal Processing Advances in Wireless Communications, 2005. DOI
[50]
H. Lou and J. Garcia-Frias, "On the Application of Error-Correcting Codes with Low-Density Generator Matrix over Different Quantum Channels," 4th International Symposium on Turbo Codes & Related Topics; 6th International ITG-Conference on Source and Channel Coding, Munich, Germany, 2006, pp. 1-6.
[51]
J. Garcia-Frias and Kejing Liu, “Design of near-optimum quantum error-correcting codes based on generator and parity-check matrices of LDGM codes”, 2008 42nd Annual Conference on Information Sciences and Systems (2008) DOI
[52]
P. Fuentes et al., “Design of low-density-generator-matrix–based quantum codes for asymmetric quantum channels”, Physical Review A 103, (2021) DOI
[53]
P. Fuentes et al., “Approach for the construction of non-Calderbank-Steane-Shor low-density-generator-matrix–based quantum codes”, Physical Review A 102, (2020) DOI
[54]
P. Fuentes et al., “Performance of non-CSS LDGM-based quantum codes over the misidentified depolarizing channel”, 2020 IEEE International Conference on Quantum Computing and Engineering (QCE) (2020) DOI
[55]
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
[56]
P. Tan and J. Li, “Efficient Quantum Stabilizer Codes: LDPC and LDPC-Convolutional Constructions”, IEEE Transactions on Information Theory 56, 476 (2010) DOI
[57]
N. Delfosse and A. Paetznick, “Spacetime codes of Clifford circuits”, (2023) arXiv:2304.05943
[58]
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
[59]
M. B. Hastings, “Quantum Codes from High-Dimensional Manifolds”, (2016) arXiv:1608.05089
[60]
N. Koukoulekidis et al., “Small Quantum Codes from Algebraic Extensions of Generalized Bicycle Codes”, (2024) arXiv:2401.07583
Page edit log

Your contribution is welcome!

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

edit on this site

Zoo Code ID: qldpc

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
BibTeX:
@incollection{eczoo_qldpc, title={Quantum low-density parity-check (QLDPC) code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/qldpc} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/qldpc

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/quantum/properties/stabilizer/qldpc/qldpc.yml.