Good Quantum LDPC Codes with Linear Time Decoders

Irit Dinur; Min-Hsiu Hsieh; Ting-Chun Lin; Thomas Vidick

Source-linked AI summary

Good Quantum LDPC Codes with Linear Time Decoders

Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, Thomas Vidick

arXiv:2206.07750v1Jun 15, 2022quant-ph

TL;DR

The paper addresses the need for fault-tolerant quantum codes with low connectivity and efficient decoding. It constructs explicit good qLDPC codes with linear-time decoders and proves essentially optimal robustness for random tensor codes.

Problem
Quantum error correction needs qLDPC codes with constant-weight checks and bounded qubit connectivity for fault-tolerant computation.
Method
The construction uses expansion, local bit-flips or small-set flips, and robustness analysis of a pair of random base codes.
Results
Explicit infinite qLDPC families achieve constant maximum check weight, any rate r in (0,1/2), constant relative distance, and linear-time decoding up to linear distance.
Takeaways & Limitations
Random tensor codes are Θ(Δ)-robust with high probability, improving the prior Ω(Δ^(1/2−ε)) robustness guarantee.
Takeaways & Limitations
The paper does not resolve the open existence question for quantum PCPs, but identifies qLDPC advances as a possible avenue for progress.

Abstract

from arXiv · show

We construct a new explicit family of good quantum low-density parity-check codes which additionally have linear time decoders. Our codes are based on a three-term chain $(\mathbb{F}_2^{m\times m})^V \quad \xrightarrow{δ^0}\quad (\mathbb{F}_2^{m})^{E} \quad\xrightarrow{δ^1} \quad \mathbb{F}_2^F$ where $V$ ($X$-checks) are the vertices, $E$ (qubits) are the edges, and $F$ ($Z$-checks) are the squares of a left-right Cayley complex, and where the maps are defined based on a pair of constant-size random codes $C_A,C_B:\mathbb{F}_2^m\to\mathbb{F}_2^Δ$ where $Δ$ is the regularity of the underlying Cayley graphs. One of the main ingredients in the analysis is a proof of an essentially-optimal robustness property for the tensor product of two random codes.

1 Introduction

The paper addresses the open problem of efficiently decoding good qLDPC codes by constructing an explicit family with linear-time decoding. Its analysis combines expansion arguments with an essentially optimal robustness theorem for random tensor codes.

Recent constructions established good qLDPC codes with constant rate and relative distance, but efficient decoders remained an open question.
Theorem 1.1 gives an explicit infinite family with rate r for every r in (0,1/2), constant relative distance δ, bounded check weight w, and a linear-time decoder correcting up to linear distance.
The construction uses a three-term chain whose vertices, edges, and square faces represent X-checks, qubits, and Z-checks in a left-right Cayley complex.
The decoder uses local bit-flips or small-set flips, while the distance and decoding analyses rely on expansion and robustness.
Random tensor codes achieve Θ(n) robustness with high probability, improving prior n^(1/2+ε)-scale robustness and matching the best possible order up to constants.
The construction has rate at most 1/2, while whether higher-rate constructions also admit linear-time decoders remains open.

2.1 Chain complexes

Chain complexes organize vector spaces and linear boundary maps into a sequence whose consecutive compositions vanish. Their kernels and images define cycles and boundaries, with exactness when these spaces coincide.

A chain complex is a sequence of vector spaces generated by sets together with linear boundary operators.
Consecutive boundary operators satisfy B_{i-1}B_i = 0.
Co-boundary operators are transposes of boundary operators and automatically satisfy the corresponding composition-zero condition.
Elements in kernels are called cycles, while elements in images are called boundaries.
A chain complex is exact at i when its boundaries equal its cycles there.

2.2 Classical and quantum error correcting codes

Classical and quantum error-correcting codes are characterized through subspaces, parity checks, distances, and rates. Quantum CSS codes use compatible classical codes and an associated three-term chain complex.

A classical linear code is a k-dimensional subspace of F_2^n, with distance d, rate r = k/n, and relative distance δ = d/n.
A quantum CSS code consists of classical codes C_z and C_x satisfying H_x H_z^T = 0.
Quantum code distance is the minimum of the X-distance and Z-distance, defined through nontrivial logical operators modulo stabilizers.
A qLDPC code has parity-check matrices whose rows and columns contain only boundedly many nonzero entries.
Decoding seeks a correction differing from the actual error by stabilizers, and separates into independent X-error and Z-error tasks using their syndromes.

2.3 Expander graphs

Expander graphs provide explicit graph families and edge-expansion properties used in the paper’s code construction. Spectral expansion is defined through nontrivial adjacency eigenvalues and implies edge expansion.

Expander graphs support important theoretical-computer-science constructions, including classical expander codes.
A Δ-regular graph is a λ-spectral expander when the largest absolute value among its nonprincipal adjacency eigenvalues is at most λ.
The paper uses spectral expanders because explicit infinite families are known and spectral expansion implies edge expansion needed for its results.
The left-right Cayley complex is illustrated as a 4-fold complex built from vertices, edges, and faces.
The expander mixing lemma supplies bounds for subsets and vectors in a Δ-regular λ-spectral expander.

2.4 Left-right Cayley complexes

The left-right Cayley complex is built from a finite group and inverse-closed generator sets, with vertices, edges, and square faces arranged by commuting left and right actions.

Complex structure: The complex has four vertex copies, V = V00 ∪ V10 ∪ V01 ∪ V11, each identified with the group G.Vertices are distinguished by two binary labels.
Complex structure: Its edges split into vertical E| and horizontal E− components, each consisting of two edge families.The edge sets are E = E| ∪ E− = (E˚0 ∪ E˚1) ∪ (E0˚ ∪ E1˚).
Complex structure: Each face is a square (g, ag, gb, agb) indexed by g ∈ G and generator pair (a, b) ∈ A × B.The square connects the four vertex copies through left multiplication by a and right multiplication by b.
Complex structure: The construction relies on the commutation of left and right actions, which makes the square faces well-defined.The relation a(gb) = (ag)b ensures consistent face labeling.
Neighborhoods: Neighborhoods record incidence and two-step access among vertices, edges, and faces in the complex.For example, E˚0(v00) contains edges incident to v00, while E1˚(v00) is reached by a vertical then horizontal move.

2.5 Expansion properties of left-right Cayley complexes

The section establishes expansion properties for graphs derived from the left-right Cayley complex, assuming the underlying Cayley graphs are spectral expanders.

Edge expansion: The opposing-edge adjacency graph M1 decomposes into copies of double covers of Cay(G, A) and Cay(G, B).This decomposition reduces its expansion analysis to the two underlying spectral expanders.
Proof strategy: The expansion proofs partition edge sets across disjoint expander subgraphs and combine the resulting bounds.The argument uses the decomposition of M1 and the corresponding componentwise inequalities.
Edge expansion: M0 is formed from M1 through the edge-vertex incidence matrices as M0 = U M1 D.It connects edges whose endpoints are themselves connected through another edge.
Assumptions: For any subset S of edges, the analysis applies when Cay(G, A) and Cay(G, B) are λ-spectral expanders.The same spectral-expansion assumption is used for the stated edge-set bounds.
Co-expansion: Co-expansion is established for an associated graph as a separate expansion property of the complex.This is stated as the third lemma in the sequence of expansion results.

2.6 Tensor codes and robustness

Tensor-code robustness measures whether low-weight sums of column-code and row-code components admit sparse decompositions; random code pairs achieve linear robustness with high probability.

Chain-complex connection: The associated three-term chain complex is exact, so every kernel element of B1 lies in the image of B2.This exactness identifies robustness with agreement testability up to normalization.
Random-code result: Θ(∆) robustness improves the prior Ω(∆^(1/2−ε)) guarantee for uniformly random code pairs.The result is stated for equal code lengths na = nb = ∆.
Random-code result: With probability tending to 1, random codes of dimensions ρa∆ and ρb∆ have distance δ1∆ and robustness δ2∆.The theorem fixes ρa, ρb ∈ (0, 1) and takes ∆ to infinity.

2.7 Tanner codes

Tanner codes combine a graph with a fixed local code by copying edge values to incident vertices and applying local parity checks.

Construction: The Tanner construction combines a large graph with a small local code to produce an infinite family when the graph family is explicit.Expander graphs can transfer desirable properties from the local code to the Tanner code.
Construction: For a ∆-regular bipartite graph, the Tanner code applies a local parity-check matrix H to the ∆ incident edge values at every vertex.The construction is defined through copying edge values to incident vertices followed by local checks.
Operator description: The operator can be described by submatrices T(G, H)v_e that restrict inputs to one edge and outputs to one vertex.This edge-vertex restriction is used to analyze the construction locally.

2.8 Expansion properties of chain complexes

The section relates several expansion notions for chain complexes to code properties and analyzes a local-flip decoder. For the construction, co-local minimal expansion is established while local minimal expansion is not.

Expansion notions: The chain-complex distance framework includes (co)-systolic distance, small-set (co)-boundary expansion, and (co)-locally-minimal expansion.The complex uses a geometric-object norm that differs from Hamming weight by a constant factor.
Application to the construction: The construction has small-set co-locally-minimal expansion but not small-set locally-minimal expansion.A face flip affects four incident edges, whereas a vertex flip affects 2∆ edges, leaving more freedom for vertex flips.
Relations among properties: Small-set boundary expansion implies systolic distance and local testability, with bounded degree making these equivalent to linear distance and local testability.The systolic implication follows by showing sufficiently small cycles are boundaries.
Relations among properties: Small-set (co)-locally-minimal expansion implies small-set (co)-boundary expansion under a gap condition on possible weights.The resulting parameters are adjusted by the local-flip decrease and the weight-gap parameter.
Local flip decoding: The local flip decoder repeatedly applies a weight-reducing single-face correction and outputs the sum of all selected corrections.Each iteration reduces the current one-chain weight, and the output satisfies boundary-expansion and correction-size bounds.

3 Linear dimension and linear distance

The paper builds a quantum code from four Tanner-code components on a 4-fold left-right Cayley complex. It proves the resulting complex is well-defined, low-density, and has linear distance under expansion and robust-code assumptions.

Construction: The construction combines four Tanner codes on subgraphs induced by a 4-fold left-right Cayley complex.The complex uses vertices, horizontal and vertical edges, and square faces, with local codes C_A and C_B.
Explicitness: A good local code pair can be found by brute force at fixed ∆, while explicit Ramanujan graphs keep the resulting family explicit.The required condition is d1d2 − λd2 − 8λ∆ > 0, with λ = Θ(∆^1/2).
Basic code properties: Lemma 3.1 establishes that the resulting object is a well-defined chain complex.The proof verifies that the composition of consecutive boundary maps vanishes on incident and nonincident elements.
Basic code properties: Each row and column of the boundary maps has at most 4∆ nonzero entries, so the associated quantum code is low density.This is the stated content of Lemma 3.2.
Expansion and distance: For suitable spectral expanders and base-code distance and robustness d1,d2 = Θ(∆), the quantum code has linear distance.The proof derives co-systolic distance, transfers co-expansion to expansion, and then obtains linear systolic distance.
Expansion and distance: Co-expansion provides corrections that make inconsistent local guesses consistent, supporting the subsequent expansion and distance analysis.The correction vectors are bounded in number relative to the local discrepancies.

4 Linear time decoder

The paper develops a linear-time co-decoder and decoder using local small-set flips, reconstruction, expansion, and robustness arguments. Preprocessing reduces the full decoder’s complexity to linear time while preserving correctness up to linear distance.

Decoder framework: The decoding task is divided into a decoder and co-decoder, recovering corrections from the two syndrome directions.The decoder and co-decoder return representatives differing from the error by the appropriate boundary or coboundary.
Co-decoder: The co-decoder uses a small-set-flip procedure that repeatedly applies local flips reducing the syndrome weight.Its correctness follows from lemmas showing short errors remain short and nonzero errors remain reducible.
Co-decoder: The co-decoder’s analysis combines expansion with distance and robustness bounds under a co-local minimality condition.These bounds imply that the error vanishes when the decoder stops, yielding a correct correction.
Correctness and guarantees: The decoder is correct up to linear distance because short errors remain controlled and the final residual differs from the error by a co-boundary.The co-decoder theorem transfers to the decoder theorem, and the construction’s remaining steps are linear-time operations.
Robustness to measurement errors: The method also supports small measurement errors, leaving a residual error bounded by a constant times the number of measurement errors.This is identified as an error-reduction property used in linear-time classical code constructions.
Linear-time implementation: Preprocessing maintains a list of flippable vertices and updates only neighboring candidates after each flip.This avoids rescanning all vertices while preserving the behavior of the simple small-set-flip decoder.
Linear-time implementation: Θ(|X^(1)|) is the overall complexity of the full small-set-flip decoder.Initialization and each main-loop update have bounded local cost because the code parameters and regularity are constant.
Decoder: The decoder reconstructs local information around vertices and corrects inconsistencies using the co-decoder.The construction tracks unknown intermediate variables and produces a good approximation to them.

5 Optimal Robust Tensor Codes

The section proves that tensor products of random codes achieve linear, essentially optimal robustness with high probability. The proof combines distance, puncturing, rank-organized counting, and a structural analysis of low-weight codewords.

The robustness parameter is Θ(∆), which is optimal up to constants because matrix weight is quadratic while the required rows and columns are linear.
The proof uses puncturing and a new rank-organized counting argument to show that low-weight codewords are structured.The argument counts bad matrices by rank, bounds their probability of being codewords, and applies a union bound.
Random codes of rates ρa and ρb have linear distance and δ2∆ robustness with probability tending to 1 as ∆ grows.The theorem applies to uniformly sampled codes of length ∆ and dimensions ρa∆ and ρb∆.
Removing a few heavy rows and columns from a low-weight codeword leaves zero, so the original codeword is supported on only a few rows and columns.Distance then limits cancellations to their small intersection, yielding the robustness inequality.
For punctured random codes, every nonzero codeword has a row or column of weight at least t=τ∆ with high probability.Equivalently, a codeword whose rows and columns all have weight below t must be zero.