PaperlayerView exact revision on arXiv

Source-linked AI summary

An efficient decoder for a linear distance quantum LDPC code

Shouzhen Gu, Christopher A. Pattison, Eugene Tang

arXiv:2206.06557v1quant-phcs.ITmath.IT

TL;DR

Efficient decoding of asymptotically good qLDPC codes remains a challenge: previous efficient decoders were limited to errors of weight Θ(√(n log n)), while Θ(n)-weight correction is sought. This paper introduces an iterative decoder for quantum Tanner codes that reduces a local potential through constant-sized corrections. It runs in O(n) time and corrects errors of weight Θ(n).

  • Problem

    Previously known efficient qLDPC decoders corrected errors only up to Θ(√(n log n)), and whether good qLDPC codes could be efficiently decoded against Θ(n)-weight errors remained a natural question.

    Source: §1 · p. 1

  • Method

    An iterative decoder reduces local-view potential functions by applying constant-sized corrections within local views.

    Source: §1 · p. 2

  • Results

    For a family of asymptotically good quantum Tanner codes, the decoder corrects all errors of weight Θ(n) and runs in O(n) time.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The proof strengthens dual tensor-code robustness beyond [9], improving code distance by a constant factor and removing the requirement that dual tensor codes resist puncturing.

    Source: §5 · p. 24

    Although runtime is linear in blocklength, constant prefactors on the order of 2^∆2 render the decoder impractical in reality.

    Source: §5 · p. 24

Abstract

from arXiv · show

Recent developments have shown the existence of quantum low-density parity check (qLDPC) codes with constant rate and linear distance. A natural question concerns the efficient decodability of these codes. In this paper, we present a linear time decoder for the recent quantum Tanner codes construction of asymptotically good qLDPC codes, which can correct all errors of weight up to a constant fraction of the blocklength. Our decoder is an iterative algorithm which searches for corrections within constant-sized regions. At each step, the corrections are found by reducing a locally defined and efficiently computable cost function which serves as a proxy for the weight of the remaining error.

1 Introduction

Although asymptotically good qLDPC codes exist, previously known efficient decoders were limited to errors of weight Θ(√(n log n)). This paper gives a linear-time decoder for quantum Tanner codes that corrects errors up to a constant fraction of their distance.

1 Introduction

  • qLDPC codes are leading contenders [1] [2] for experimentally realizable fault-tolerant memories and may support constant-overhead fault-tolerant computation [3].The paper also notes a believed connection to the qPCP conjecture.Source: §1 · p. 1
  • Previously known efficient decoders corrected errors only up to Θ(√(n log n)), while the existence of good qLDPC codes motivates seeking Θ(n)-weight correction.The prior limit is stated for the best efficient decoder known at the time.Source: §1 · p. 1
  • Quantum Tanner codes combine two classical Tanner codes into a CSS code using a two-dimensional expanding complex.For particular local checks and complexes, the construction yields asymptotically good qLDPC codes.Source: §1 · p. 1
  • Inspired by small-set-flip, the decoder reduces a sum of local-view potential functions through constant-sized corrections, while its proof establishes that a suitable flip exists for errors not too large.The local potential measures distance from the local codespace; the proof tracks minimum-weight corrections by local view and strengthens the robustness of the random classical codes used in the construction.Source: §1 · p. 2
  • For quantum Tanner codes, the decoder corrects all errors of weight Θ(n) and runs in O(n) time.The paper states this result for a family of asymptotically good quantum Tanner codes.Source: §1 · p. 2

2 Quantum Tanner Codes

The section reviews the classical and quantum code ingredients, then builds quantum Tanner codes from left-right Cayley complexes and local tensor codes. It also specifies the expansion and robustness properties used in the construction, including a stronger robustness requirement that simplifies the code description.

2.1 Classical linear codes

  • Classical tensor codes are matrices whose columns and rows lie in their respective component codes, while Tanner codes impose a local-code condition at every graph vertex.Source: §2.1 · pp. 2–3

2.2 Quantum CSS codes

  • A CSS code uses separate X- and Z-type stabilizer generators whose commutation condition determines the underlying classical codes; good qLDPC families have constant-bounded rate and relative distance.Source: §2.2 · p. 3

2.3 Left-Right Cayley complexes

  • The left-right Cayley complex uses two symmetric generating sets satisfying TNC; its faces are indexed locally by A × B, and TNC ensures each square has four distinct vertices.Source: §2.3 · pp. 3–4

2.4 Quantum Tanner codes construction

  • Quantum Tanner codes place qubits on complex squares, use local tensor-code checks for Z stabilizers and dual-tensor-code checks for X stabilizers, and commute by the complex's incidence structure.Source: §2.4 · p. 4
  • For certain choices of left-right Cayley complex and local codes, the construction yields an infinite family of good quantum codes.Source: §2.4 · p. 5

2.5 Expanding Cayley complex and robust local codes

  • The construction uses expanding Cayley complexes and requires robust dual tensor codes; w-robustness confines a codeword's support to a bounded number of nonzero rows and columns.Source: §2.5 · pp. 5–6
  • The decoder proof needs dual tensor codes with robustness ∆^(3/2+ε); this higher parameter removes the puncturing-resistance requirement and simplifies the code description.The earlier result cited in the paper established robustness ∆^(3/2−ε).Source: §2.5 · p. 6

3 Decoding algorithm

The decoder uses syndrome-computable local potentials to choose constant-sized corrections within local views. It corrects errors up to a constant fraction of code distance in linear time.

3 Decoding algorithm

  • Because local codes make syndrome weight basis-dependent, the decoder uses each local view's distance to its local codespace as a syndrome-computable potential.The algorithm searches for constant-sized corrections within local views that decrease the global potential.Source: §3 · p. 7
  • For errors up to a constant fraction of code distance, a local-view correction decreases the global potential, enabling successful decoding.The decoder's correctness argument establishes that a potential-decreasing correction exists when the error is within the stated range.Source: §3 · pp. 7–8
  • Theorem 13 gives Algorithm 1 a runtime of O(n), with local potentials computed in constant time and at most O(n) iterations.Each iteration updates only a constant number of local views and candidate corrections.Source: §3 · p. 8
  • Under the stated independent-error model, the decoder's failure probability is O(e^-an) for p < p*.The paper identifies p* as a lower bound for the accuracy threshold under independent bit- and phase-flip noise.Source: §3 · p. 9

4 Proof of Theorem 10

The proof of Theorem 10 splits into three cases, using potential-decreasing flips in the first two and a local-view argument in the remaining case. The latter constructs a special vertex and uses local-view decomposition and robustness to derive a contradiction.

4.1 Proof of Cases 1 and 2

  • For metastable R without the low-overlap property, there exist v ∈ V1 and f ⊆ Q(v) such that flipping the qubits of f decreases the total potential.If flipping a subset R̂ ⊆ R(e) does not decrease global potential, reversing its edge directions gives valid locally minimum-weight corrections for e + R̂ and leaves the nearest codewords at each vertex unchanged.Source: §4.1 · pp. 11–12

4.2 Proof of Case 3

  • For case 3, a reduced error under metastability, low overlap, and sufficient dual tensor-code robustness leads to a special vertex whose local view yields a potential-decreasing flip or a contradiction.The contradiction follows because robustness implies sufficient overlap with a Z-stabilizer to reduce the weight of the initially reduced error.Source: §4.2 · p. 13

4.2.1 Existence of v0 ∈V0

  • Under the low-overlap property, the non-trivially corrected vertices form the vertex set of the residual-error subgraph, which has large minimum degree.This construction supports finding a V0 vertex whose local view has many rows and columns close to non-trivial codewords of CA and CB.Source: §4.2.1 · p. 13
  • For a normal vertex v, every row and column of its nearest codeword cv is within ∆^1/2+ε/δ of a local-code codeword, and at least one is close to a nonzero codeword.This follows from decomposing cv into row- and column-supported parts; the nonzero conclusion uses that cv is nonzero for v in Y.Source: §4.2.1 · p. 15
  • At least one vertex v0 in W has many dense edges and few exceptional neighbors, enabling the local analysis used to prove Theorem 10.A positive fraction of W has at least α∆ dense edges, while the bounds on exceptional vertices and their edges to W yield a vertex satisfying both conditions.Source: §4.2.1 · pp. 17–18

4.2.2 The local view at v0

  • The identities combine y0 with the row-specific and column-specific parts of R: y0[v, ·] ⊔ Rrow[v, ·] = cv[v0, ·], and y0[·, v′] ⊔ Rcol[·, v′] = cv′[·, v0] (82).For [v, v′] ∈ Q(v0), Rrow[v, ·] = 0 if v /∈ Y, and Rcol[·, v′] = 0 if v′ /∈ Y.Source: §4.2.2 · p. 19
  • If no subset of Q(v0) lowers the global potential when flipped, then R0 must have sufficiently low weight for robustness to yield a stabilizer c0 with |e + c0| < |e|, contradicting that e is reduced.The argument uses the low-weight scenario: columns and rows of e0 are close to local-code codewords, and dual-tensor robustness supplies the stabilizer.Source: §4.2.2 · p. 19
  • After flipping e ∩ R0, the local minimum corrections and residual errors remain invariant, with ˜R = R, ˜y = y, and ˜e0 = y0.The R-flipping Lemma supplies the local minimum corrections for the flipped configuration, enabling further analysis of its potential.Source: §4.2.2 · p. 20
  • If no subset of Q(v0) lowers the global potential, Lemma 41 bounds the size of R0, enabling the remaining proof steps.The proof derives the bound by comparing potential changes after flipping R0 and local corrections; the excerpt omits the bound’s displayed formula.Source: §4.2.2 · pp. 21–22
  • The proof bounds the weight of y0 using dense edges from v0 to normal neighboring vertices and lower bounds on their local codeword restrictions.It separately accounts for exceptional vertices when summing contributions to the local view.Source: §4.2.2 · p. 23
  • Robustness yields c0 with |y0 − c0| ≤ 15Δ^(3/2+ε)/δ, leading to |e0 + c0| ≤ 18Δ^(3/2+ε) < |e0| and contradicting reducedness.The comparison applies for sufficiently large Δ under the stated parameter conditions; the proof also uses |e0| ≥ |y0| ≥ (αδ/4)Δ².Source: §4.2.2 · p. 23

5 Discussion and Conclusion

The paper establishes a linear-time decoder for quantum Tanner codes that corrects errors up to a constant fraction of the distance. Its discussion highlights stronger dual-tensor robustness, practical runtime costs, and open questions about decoding other good qLDPC constructions.

5 Discussion and Conclusion

  • Linear-time decoding corrects all errors up to a constant fraction of the code distance, and the decoder also implies soundness and a stochastic-noise accuracy threshold.The correction guarantee is stated as |e| ≲ δn/∆^(7/2+ε).Source: §5 · p. 24
  • Dual tensor codes with robustness ∆^(3/2+ε), beyond the parameter established in [9], improve code distance and remove the construction’s puncturing-resistance requirement.The stronger robustness is also an important component of the decoder correctness proof.Source: §5 · p. 24
  • The decoder is linear-time asymptotically, but checking all subsets of ∆²-sized local views incurs prefactors on the order of 2^(∆²), making it impractical in reality.The authors identify reducing check weights as one possible route to lower absolute runtime.Source: §5 · p. 24
  • Efficient decoding remains unknown for the Panteleev–Kalachev codes [8], and efficient decoders for balanced-product codes [7] with non-trivial local codes remain an open problem.The authors ask whether their decoder can be modified for the Panteleev–Kalachev construction.Source: §5 · p. 24
  • The current decoder checks local views at vertices of both V0 and V1, unlike small-set-flip, and the authors suggest tighter analysis might eliminate one vertex type.Better understanding candidate flip-sets may also help reduce runtime.Source: §5 · p. 24

A Existence of dual tensor codes with sufficiently high robustness

The appendix establishes sufficiently robust dual tensor codes as an ingredient in proving decoder correctness. It defines robustness through sparse row-and-column support and uses a decomposition property and a probabilistic existence argument.

A Existence of dual tensor codes with sufficiently high robustness

  • Sufficient robustness means ∆^(3/2+ε)-robustness for some ε > 0; robustness bounds the row and column support of low-weight codewords.The general w-robust condition requires support on at most |X|/dA columns and |X|/dB rows.Source: A Existence of dual tensor codes with… · p. 26
  • A dual-tensor codeword supported on fewer than d rows and columns decomposes into row and column codewords respecting those supports.The stated decomposition is X = r + c, with each component vanishing outside the corresponding row or column support.Source: A Existence of dual tensor codes with… · p. 26
  • The appendix uses a probabilistic argument to show that randomly chosen dual tensor codes are sufficiently robust with high probability.This existence argument supplies a component required by the quantum Tanner code construction and decoder-correctness proof.Source: A Existence of dual tensor codes with… · p. 26

A.1 Lemmas about random codes

The section shows how results can move among related random-code ensembles: conditioned on full rank, two matrix-based constructions induce the uniform subspace distribution. Full-rank failures are exponentially unlikely, and the resulting distributions are close enough to switch ensembles with exponentially small overhead.

A.1 Lemmas about random codes

  • The section switches among parity-check-matrix, generator-matrix, and uniform-subspace ensembles to use the most convenient distribution for each proof step.The constructions define codes as ker H, col G, or a uniformly random subspace of the specified dimension.Source: §A.1 · pp. 26–27
  • Conditioned on full rank, the parity-check and generator constructions induce the same distribution as a uniformly random subspace of the corresponding dimension.The equality is stated for the three random-code ensembles.Source: §A.1 · p. 27
  • Full-rank failure probabilities are exponentially small, so the related random-code distributions are close and can be switched with exponentially small overhead.The section states exponentially small rank-failure bounds and a total-variation comparison among the ensembles.Source: §A.1 · pp. 27–28

A.2 Random codes are sufficiently robust

This section shows that random dual tensor codes are sufficiently robust with high probability, establishing sparse robustness including after puncturing and connecting punctured sparse robustness to ordinary robustness. It also establishes Δ^(3/2+ε)-robustness and linear distance with high probability, and notes that the theorem’s restriction on ε is not tight.

A.2 Random codes are sufficiently robust

  • Sparse robustness excludes nonzero sparse codewords, where sparse means each row and column has weight at most Δ^(1/2+2ε).Sparse and low-weight are distinct notions, and neither implies the other; the proof establishes robustness against low-weight codewords by first proving sparse robustness.Source: §A.2 · p. 29
  • For sufficiently large Δ, sparse robustness with respect to puncturing implies Δ^(3/2+ε/2)-robustness for dual tensor codes of distance d = δΔ.The proof punctures away high-weight rows and columns so that the remaining matrix is sparse, then uses punctured sparse robustness to force it to vanish.Source: §A.2 · p. 29
  • Distance d ≥ δΔ rules out sparse codewords supported on at most γδΔ nonzero rows and columns, reducing the sparse-robustness proof to larger supports.Lemma 52 supplies this reduction for sufficiently large Δ.Source: §A.2 · p. 30
  • 2^-Θ(Δ^(3/2−2ε)) bounds the probability that random dual tensor codes have distance d ≥ δΔ but are not sparse robust.Theorem 53 assumes fixed ρA, ρB ∈ (0, 1), ε ∈ (0, 1/14), and δ ∈ (0, 1).Source: §A.2 · pp. 30, 34
  • With high probability, random dual tensor codes have distance d ≥ δΔ and are sparse robust with respect to puncturing when δ < min(h^-1(ρA), h^-1(ρB)) and δ < 1/2.The result assumes fixed ρA, ρB ∈ (0, 1) and ε ∈ (0, 1/14); it implies sufficient robustness via Lemma 51.Source: §A.2 · p. 35
  • For each punctured code pair, the probability of failing strong robustness while retaining distance at least 0.9δ∆ is at most 2^-Θ(∆^(3/2−2ε)).The proof then bounds the number of puncturing choices and uses a union bound to control failure for the unpunctured code pair.Source: §A.2 · pp. 35–36
  • 1 − 2^-Ω(∆) is a lower bound on the probability that random codes CA, CB yield both dual tensor codes with ∆^(3/2+ε)-robustness and distance at least δ∆.The codes have length ∆ and rates ρ and 1−ρ; the theorem assumes ε ∈ (0, 1/28), ρ ∈ (0, 1/2), and δ < h^-1(ρ).Source: §A.2 · p. 36
  • The restriction ε < 1/28 is needed because Lemma 51 halves Theorem 53’s robustness parameter, but tighter exponent tracking gives existence for any ε < 1/6.The decoder itself only needs dual tensor codes with ∆^(3/2+ε)-robustness for any ε > 0.Source: §A.2 · p. 36
Loading 2206.06557v1…