PaperlayerView exact revision on arXiv

Source-linked AI summary

Decoding quantum Tanner codes

Anthony Leverrier, Gilles Zémor

arXiv:2208.05537v3quant-phcs.ITmath.IT

TL;DR

Quantum Tanner codes need decoders that can handle adversarial errors, including when errors accumulate during decoding. This paper develops sequential and parallel decoders and proves logarithmic-time correction for the parallel decoder, alongside a linear minimum-distance result for codes on Ramanujan left-right Cayley complexes.

  • Problem

    Highly parallel decoding is needed because new errors accumulate while a decoder identifies earlier errors, and assumptions about error distributions are problematic when faults may be correlated.

    Source: §1 · pp. 1–2

  • Method

    The paper develops sequential and parallel quantum Tanner-code decoders that reduce a mismatch vector using local dual tensor codewords.

    Source: §1 · pp. 2, 5

  • Results

    The parallel decoder returns a valid correction in logarithmic time, and quantum Tanner codes on Ramanujan left-right Cayley complexes have linear minimum distance for sufficiently large constant degree.

    Source: §1 · pp. 4, 6

  • Takeaways & Limitations

    Logarithmic-time parallel decoding addresses the stated need to identify earlier errors while new errors continue to accumulate.

    Source: §1 · p. 1

    The proof requires large codes, and the decoder's performance against random noise remains to be investigated.

    Source: §1 · p. 7

Abstract

from arXiv · show

We introduce sequential and parallel decoders for quantum Tanner codes. When the Tanner code construction is applied to a sufficiently expanding square complex with robust local codes, we obtain a family of asymptotically good quantum low-density parity-check codes. In this case, our decoders provably correct arbitrary errors of weight linear in the code length, respectively in linear or logarithmic time. The same decoders are easily adapted to the expander lifted product codes of Panteleev and Kalachev. Along the way, we exploit recently established bounds on the robustness of random tensor codes to give a tighter bound on the minimum distance of quantum Tanner codes.

1 Introduction and Overview

The paper addresses the need for decoding that can handle adversarial errors and run in parallel, introducing sequential and parallel decoders for quantum Tanner codes. It also presents a linear minimum-distance bound and describes how the decoder extends to expander lifted product codes.

1 Introduction and Overview

  • Quantum Tanner codes impose constant-weight local constraints from dual tensor codes on qubits associated with square faces of a square complex.With local-code rates ρ and 1−ρ, the construction has encoding rate k/n ≥ (1−2ρ)^2.Source: §1 · pp. 2–4
  • For a sufficiently large constant degree, quantum Tanner codes on Ramanujan left-right Cayley complexes have linear minimum distance.The paper says the bound is sharper than [11] and tight in its dependence on ∆, since logical errors of weight at most n/∆ exist.Source: §1 · p. 4
  • The decoder forms a mismatch vector from local error estimates, then seeks local dual tensor codewords whose flips reduce its weight.The analysis uses expansion of the square complex and robustness of the local codes to establish a weight-reducing move.Source: §1 · p. 5
  • The parallel decoder applies candidate updates across four vertex classes, with ε trading correctable error weight against the number of parallel steps.The analysis establishes that linearly many vertices can be updated at each step.Source: §1 · pp. 6–7
  • The parallel decoder returns a valid correction in logarithmic time, while the paper also presents a simpler sequential decoder.The sequential decoder is inspired by the analysis in [24] and adapts small-set-flip decoding.Source: §1 · pp. 2, 6
  • The same algorithm applies to expander lifted product codes; the proof requires large codes, and random-noise performance remains an open question.The decoder also applies to hypergraph products, but with smaller correction capabilities because their distance scales like √n.Source: §1 · p. 7

2 Technical preliminaries

This section sets up the graph, code, and square-complex structures used to define quantum Tanner codes. It also states how local-code choices, expansion, and tensor-code robustness support their parameters.

2.1 Graph expansion

  • The graph-expansion preliminaries define a spectral eigenvalue parameter and Ramanujan condition, and state an expander mixing lemma for bipartite graphs.The supplied lemma passage identifies the graph and vertex-set assumptions but does not include its inequality.Source: §2.1 · pp. 7–8

2.2 Tanner codes

  • Expander graphs with local codes of rate above 1/2 yield Tanner-code families whose rate and minimum distance are both Ω(n).The stated condition also requires the graph eigenvalue bound λ(G_i) ≤ λ < d0.Source: §2.2 · p. 8

2.3 Quantum CSS codes

  • A quantum CSS code uses two classical codes with C⊥0 ⊂ C1; it is LDPC when both are kernels of sparse parity-check matrices.The code dimension counts logical qubits, and the paper considers independently decoding sufficiently low-weight adversarial errors.Source: §2.3 · pp. 8–9

2.4 Left-right Cayley complexes (quadripartite version)

  • Quantum Tanner codes impose local constraints on square neighborhoods of a quadripartite left-right Cayley complex; their generators use tensor-code bases on the respective vertex classes.C0 is a Tanner code on G□0 with local constraints corresponding to the dual tensor code.Source: §2.4 · p. 9, §2.6 · p. 11
  • The square complex uses four copies of a group, with A- and B-edges defining squares; the quadripartite version avoids an additional condition on group and generators.The generators are chosen so the left and right Cayley graphs are non-bipartite Ramanujan graphs.Source: §2.4 · pp. 9–10

2.5 Labelling Q-neighbourhoods

  • Each vertex’s Q-neighbourhood is labeled bijectively by A × B, and adjacent vertices share a column across B-edges or a row across A-edges.These shared labels align coordinates between neighboring local views.Source: §2.5 · pp. 10–11

2.6 Local codes

  • For inner-code rate ρ, the quantum Tanner code has dimension at least (1 − 2ρ)^2|Q| when dim CB = Δ − dim CA and dim CA = ρΔ.The construction counts constraints to obtain this lower bound.Source: §2.6 · p. 11

2.7 Robustness of (dual) tensor codes

  • For random inner codes, the dual tensor code is κ-product-expanding with high probability as Δ grows; this robustness bounds decompositions into row and column components.The application uses inner-code rates satisfying ρB = 1 − ρA, and the cited result gives essentially tight bounds.Source: §2.7 · p. 12

3 Minimum distance

The section derives a lower bound on quantum Tanner code minimum distance by combining minimal representations with robustness and expansion arguments.

3 Minimum distance

  • A minimal representation minimizes the total number of local codewords and can be maintained within the same coset while reducing that norm.The proof chooses a minimum-norm representative in the coset before applying the distance argument.Source: §3 · pp. 13–14
  • The section derives a lower bound on quantum minimum distance from a lower bound on the norm of nontrivial codewords.The argument applies the bound to nontrivial codewords of C1 and, by symmetry, C0.Source: §3 · pp. 13–14
  • Robustness bounds the codeword weight using the counts of local column and row codewords in a minimal representation.The argument obtains corresponding bounds for the two paired sums by symmetry.Source: §3 · p. 14
  • Robustness limits exceptional vertices for small active sets, while clustering of nonzero local columns forces too many exceptions, yielding a contradiction.The contradiction uses the bound on exceptional vertices together with the lower bound on the size of the clustered set.Source: §3 · pp. 14–16

4 Description of the decoders

Both decoders form a mismatch from local syndrome-based error estimates, decompose it into local codewords, and use a shared postprocessing step. Their decomposition procedures differ: one is greedy and sequential, while the other updates disjoint local views in parallel.

4 Description of the decoders

  • The shared pipeline builds a mismatch from local minimum-weight error estimates matching the syndrome, then uses the decomposition to compute the corrected error.The preprocessing can be parallelized, and postprocessing is local to components of the relevant vertex partition.Source: §4 · pp. 16–18
  • The sequential decoder repeatedly adds a local dual tensor codeword that sufficiently decreases mismatch weight, decomposes it into minimum-size column and row parts, and stops when the mismatch is zero.The resulting local parts are accumulated into the decomposition of the mismatch.Source: §4 · pp. 16–17
  • The parallel decoder updates disjoint local views in four successive substeps, one for each vertex class, choosing a weight-decreasing codeword at each eligible vertex.Each chosen update reduces the mismatch weight by at least half the codeword weight; the procedure repeats across rounds.Source: §4 · p. 17

5 Sequential decoding

This section presents a sequential decoder that repeatedly flips local dual tensor codewords to reduce mismatch, and proves its convergence to a valid correction under stated sparsity and error-weight conditions. The proof of Theorem 13 applies (7) to the sum of local increments to establish when the resulting bound falls below the quantum code’s minimum distance.

5 Sequential decoding

  • For any mismatch whose minimum decomposition has sufficiently few active vertices, Theorem 12 guarantees a local dual tensor codeword; the decoder adds updates until mismatch is zero, outputting their sum, Z.Source: §5 · pp. 19–20

5.2 Proof of Theorem 13

  • For errors below Theorem 13’s stated weight bound, the sequential decoder returns a correction equivalent to the error.The proof tracks the mismatch decomposition norm to keep active-vertex counts within Theorem 12’s condition, then checks correctness using the code’s minimum distance.Source: §5 · p. 20, §5.2 · pp. 24–25

5.1 Proof of Theorem 12

  • The proof of Theorem 12 analyzes a minimum mismatch decomposition and derives a contradiction from the assumption that the sequential decoder is stalled.It studies the support of the intersection of the decomposition components, which is smaller than the set considered in the minimum-distance analysis.Source: §5.1 · pp. 20–21

5.1.1 A stalled sequential decoder, Exceptional vertices, ordinary rows and columns

  • For a stalled decoder, the proof classifies active vertices as exceptional or ordinary by local representation size and derives constraints on local codewords and ordinary columns.Active vertices are those whose local view of the decomposition is nonzero.Source: §5.1.1 · p. 21

5.1.2 Exceptional vertices are rare

  • Exceptional vertices are rare, as shown by bounding their number using robustness and the expander mixing lemma.The proof states the bound for one vertex class and notes that the other cases are similar.Source: §5.1.2 · pp. 22–23

5.1.3 Ordinary columns and rows cluster

  • Lemma 16 establishes a clustering bound for vertices whose local neighborhoods share ordinary columns or rows.Its proof uses a graph induced by the shared local-view structure and the expander mixing lemma.Source: §5.1.3 · p. 23

5.1.4 Obtaining a contradiction

  • The proof combines the rarity of exceptional vertices with clustering of ordinary columns or rows to contradict the assumption that decoding is stalled.The contradiction follows because the clustering argument forces too many exceptional vertices, exceeding the bound from Lemma 15.Source: §5.1.4 · p. 24

5.2 Proof of Theorem 13

  • For |e| ≤ Δ, the derived bound is below the quantum code’s minimum distance, completing the proof of Theorem 13.The bound is obtained by applying (7) to the sum over all local increments used by the decoder.Source: §5.2 · p. 26

6 Parallel Decoding

The section establishes a logarithmic-time parallel decoding guarantee by relating parallel rounds to sequential decoding and proving termination under stated small-error conditions.

6 Parallel Decoding

  • When sequential decoding with parameter ε converges, one parallel round reduces the mismatch weight by the amount guaranteed by Lemma 18.The numerical bound is incomplete in the supplied passage.Source: §6 · p. 26
  • Below Lemma 19’s stated error-weight threshold, sequential decoding with parameter 1/2 terminates, and switching to ε also guarantees termination of mismatch decomposition.The threshold’s value is not included in the supplied passages.Source: §6 · p. 29
  • For ε ∈ (0, 1/6) and errors below Theorem 20’s stated weight threshold, the parallel decoder returns a valid correction in logarithmic time.The supplied passage does not include the threshold’s value.Source: §6 · p. 30
  • The proof treats each parallel substep as successive parameter-1/2 sequential increments, allowing Lemmas 19 and 18 to establish termination in logarithmically many rounds.This argument applies the lemmas after any number of parallel rounds.Source: §6 · p. 30
Loading 2208.05537v3…