| quantum low-density parity-check code | |
|---|---|
| Name | Quantum LDPC code |
| Type | Quantum error-correcting code |
| Field | Quantum information theory / Quantum computing |
| Introduced | 1990s–2010s |
| Notable examples | Surface code, Kitaev's toric code, Hypergraph product code |
| Applications | Fault-tolerant Quantum computation, quantum memory |
quantum low-density parity-check code
Quantum low-density parity-check codes are a class of quantum error correction codes defined by sparse stabilizer generator matrices, generalizing classical LDPC codes to the quantum setting. They provide a framework for protecting quantum information in qubit registers against decoherence and operational errors using a small number of local parity constraints per qubit. Quantum LDPC codes matter for scalable quantum computing because they promise reduced overhead for fault tolerance compared with concatenated schemes and are closely linked to topological quantum error correction approaches.
A quantum low-density parity-check (QLDPC) code is specified by a set of commuting stabilizer operators whose representation as binary parity-check matrices is sparse: each row (stabilizer) and each column (qubit) has weight bounded by a small constant or slowly growing function of the block size. Formally, QLDPC codes are stabilizer codes in the Calderbank–Shor–Steane (CSS) or general stabilizer formalism, where parity-check matrices H_X and H_Z satisfy H_X H_Z^T = 0 over GF(2). Important parameters include code length n, number of logical qubits k, and distance d, often denoted n,k,d for quantum codes. Sparsity relates to practical decoding: each qubit participates in few checks, and each check involves few qubits, which reduces circuit depth when measuring stabilizers on platforms such as superconducting qubit or trapped ion processors.
Constructions of QLDPC codes fall into families derived from classical LDPC constructions or from geometric/topological models. The Kitaev's toric code and surface code are prototypical sparse stabilizer codes with local checks on a 2D lattice; they are often presented as 2D QLDPC codes. Algebraic constructions include the Calderbank–Shor–Steane (CSS) construction applied to pairs of classical LDPC codes, and the Tillich–Zémor hypergraph product and related Hastings–Haah–O'Donnell products that produce constant-rate QLDPC codes from classical LDPC constituents. More recent breakthroughs produced asymptotically good QLDPC families with constant rate and linear distance using tools from expander graphs and homological algebra; notable works include constructions by Panteleev and Kalachev and by Hastings and collaborators. Other explicit examples are quantum turbo codes and constructions based on finite geometry and Cayley graphs.
Key performance metrics for QLDPC codes include distance scaling, rate, and threshold under realistic noise models. Surface-like QLDPC codes exhibit thresholds against local stochastic noise that are amenable to planar hardware; the surface code threshold is one of the highest known for local stabilizer codes. Recent asymptotically good QLDPC constructions achieve constant rate (k = Θ(n)) and distance d = Θ(n), improving theoretical trade-offs compared with earlier families where distance scaled only sublinearly. Threshold analysis typically uses percolation theory, statistical mechanical mappings, and numerical simulations of decoders; thresholds depend strongly on syndrome measurement error models and the locality of stabilizers. For practical quantum computing, finite-size thresholds and the qubit overhead to reach target logical error rates remain central engineering concerns.
Decoding QLDPC codes requires algorithms that infer likely error patterns from noisy syndrome measurements. Standard methods adapted from classical LDPC decoding include belief propagation and message-passing algorithms, but naive application fails due to quantum degeneracy and short loops in code graphs. For CSS QLDPC codes, separate decoders for X and Z components are common. Other approaches include minimum-weight perfect matching (used for surface code), union-find decoders, and tailored iterative decoders that incorporate degeneracy-aware heuristics. Recent research explores neural-network-assisted decoding and decoders exploiting the structure of product codes (e.g., decoders for hypergraph product code). Complexity and decoding latency are critical: sparse checks enable faster syndrome extraction, but practical decoders must tolerate measurement noise and operate within hardware timing constraints set by qubit coherence times.
Physical realization of QLDPC codes focuses on architectures that support the required stabilizer measurements with low error rates and limited qubit connectivity. Leading platforms include superconducting qubits, trapped ions, neutral atoms, and photonic systems. 2D local QLDPC codes such as the surface code match well with planar superconducting layouts, while more exotic LDPC constructions may require higher connectivity achievable in modular ion-trap networks or photonic interconnects. Fault-tolerant protocols integrate syndrome extraction circuits, magic state distillation when implementing non-Clifford gates, and careful scheduling to avoid correlated faults. QLDPC codes promise reduced overhead in terms of physical qubits per logical qubit compared with concatenated codes, but achieving this in practice depends on implementing low-error, parallel stabilizer measurements and scalable classical decoding infrastructure.
QLDPC codes inherit many ideas from classical low-density parity-check code theory—sparse parity-check matrices, message-passing decoding, and expander-based constructions—but quantum constraints (commutation, degeneracy) impose additional algebraic structure. Topological codes like the toric code and surface code are special instances of QLDPC codes with geometric locality and homological interpretations via homology of cell complexes. Algebraic constructions using hypergraph products connect classical LDPC families (e.g., those from Gallager) to quantum codes, enabling trade-offs between rate and distance. The interplay among classical coding theory, condensed matter physics perspectives (topological order), and computer science complexity theory continues to drive progress in constructing practically useful QLDPC families.
Category:Quantum error correction Category:Quantum information theory