Source-linked AI summary
Quantum Expander Codes
Anthony Leverrier, Jean-Pierre Tillich, Gilles Zémor
TL;DR
Quantum LDPC codes need efficient decoding, but quantum errors cannot generally be resolved by deciding individual qubits. This paper adapts classical expander-code decoding to quantum product codes, achieving linear-time decoding for adversarial errors up to a constant fraction of minimum distance.
Problem
Efficient decoding of quantum LDPC codes is difficult because errors are equivalent up to stabilizers, making individual qubit values non-unique.
Source: §1 · pp. 2–3Method
The decoder exploits expansion in the original classical code and searches within stabilizer-generator supports for qubit patterns that reduce syndrome weight.
Source: §1 · p. 3Results
Takeaways & Limitations
The result shows that expansion inherited from the classical code can support decoding even though the quantum code’s factor graphs are not strictly expanding.
Source: §1 · p. 3The treatment restricts the more general construction to the case G=G1=G2 for ease of description and notation.
Source: §2 · p. 6
Abstract
from arXiv · showhide
We present an efficient decoding algorithm for constant rate quantum hypergraph-product LDPC codes which provably corrects adversarial errors of weight $\Omega(\sqrt{n})$ for codes of length $n$. The algorithm runs in time linear in the number of qubits, which makes its performance the strongest to date for linear-time decoding of quantum codes. The algorithm relies on expanding properties, not of the quantum code's factor graph directly, but of the factor graph of the original classical code it is constructed from.
1 Introduction
The paper develops a linear-time decoder for quantum product codes by leveraging expansion in the original classical code, while addressing why quantum decoding cannot simply decide each qubit independently. It also connects the construction to low-weight robustness and the challenge of quantum local testability.
1 Introduction
- Fast decoding is motivated by quantum LDPC codes’ potential role in fault-tolerant quantum computation, where decoders are expected to run in near-linear time.The cited fault-tolerant scheme uses quantum LDPC codes as an essential component.Source: §1 · p. 2
- Known quantum LDPC constructions have not significantly exceeded n^1/2 distance, and whether asymptotically good quantum LDPC codes exist remains open.The paper situates product codes among constant-rate constructions with distance growing as n^1/2.Source: §1 · p. 2
- Quantum decoding cannot generally recover individual error bits: errors are equivalent up to stabilizer vectors, so a qubit has no uniquely correct value.The decoder’s output is defined only up to addition of stabilizer vectors.Source: §1 · pp. 2–3
- The paper provides a decoding algorithm for product codes, addressing the lack of a decoder for that constant-rate, growing-distance construction.Other cited decoding approaches are tied to surface-code structure or have unclear adversarial performance for 4-dimensional hyperbolic codes.Source: §1 · p. 3
- The decoder uses expansion in the original classical code and works with stabilizer generators, finding qubit patterns in a generator’s support that decrease syndrome weight.The quantum codes’ Tanner graphs are not themselves strictly expanding, but retain enough expanding structure for decoding.Source: §1 · p. 3
- The construction is robust for errors up to a constant fraction of minimum distance, but does not exhibit quantum locally testable codes.The authors say extending robustness beyond low-weight errors appears harder because the random expander codes used are not locally testable.Source: §1 · p. 4
2 Expansion, code construction and main result
The paper builds quantum codes from a biregular bipartite graph and uses two-sided expansion to obtain linear-time decoding with adversarial-error tolerance proportional to the code's minimum distance.
2 Expansion, code construction and main result
- Left-right expansion requires every sufficiently small subset on either side to have nearly degree-times-size many neighbors.The definition applies separate subset-size and neighbor-expansion bounds to the left and right vertex sets.Source: §2 · p. 4
- A code's Tanner graph is the incidence graph between parity-check rows and columns, and different parity-check matrices can give the same code different factor graphs.The classical decoding result cited here gives linear-time decoding under left expansion when δA < 1/4.Source: §2 · pp. 4–5
- The quantum construction uses two factor graphs, GX and GZ, with common left vertex sets A² ∪ B² and respective right sets A × B and B × A.The two classical codes are constructed from the same base bipartite graph.Source: §2 · p. 5
- The resulting parity-check matrices have mutually orthogonal rows and constant row weight ΔA + ΔB, yielding a valid CSS quantum LDPC code.The construction's code parameters involve the classical minimum distance d and transpose minimum distance dT; the latter need not be infinite for a typical biregular-graph matrix.Source: §2 · pp. 5–6
- For fixed degrees with ΔA < ΔB, the quantum code family has rate bounded below by a nonzero constant and typical minimum distance scaling as √n.The construction restricts the more general product-code construction to one graph used in both factors, for simpler description and notation.Source: §2 · p. 6
- Under δA, δB < 1/6, the decoder runs in linear time and corrects a constant fraction of the minimum distance in adversarial errors.The theorem requires both left and right expansion; the paper notes no known constructions achieve the stated expansion values, though random choice can produce suitable graphs.Source: §2 · p. 6
3 Description of the decoding algorithm
The decoder handles X and Z errors separately, iteratively choosing generator-supported flips that decrease syndrome weight. It outputs an error equivalent to the original modulo Z-generators when decoding succeeds, and runs in linear time in the number of qubits.
3 Description of the decoding algorithm
- For each error type, the decoder uses its syndrome to find a generator-supported flip that strictly decreases syndrome weight.The algorithm treats X and Z errors independently and describes the procedure for X errors; the Z case is symmetric.Source: §3 · p. 7
- Each iteration selects a largest eligible flip whose support lies in a generator and whose application decreases the current syndrome weight.The decoder updates the syndrome after each flip and repeats the search.Source: §3 · pp. 7–8
- If no decreasing flip is available, the decoder fails when the syndrome is nonzero; otherwise it outputs the accumulated flips.The output is equivalent to the original error modulo Z-generators when the small-error guarantee applies.Source: §3 · p. 8
- Careful updates to the list of generators to re-examine give a linear-time implementation in the number of qubits.Source: §3 · p. 8
4 Analysis of the decoding algorithm
For initial errors below the stated threshold, the decoder avoids failure and correctly decodes. The analysis builds this guarantee from expansion, critical generators, and syndrome-reducing flips that do not increase reduced error weight.
4 Analysis of the decoding algorithm
- Left-right expansion with δA, δB < 1/2 gives the associated quantum code minimum distance at least min(γA nA, γB nB).Source: §4 · p. 8
- The critical-generator argument adapts Sipser and Spielman's unique-neighbor strategy to generators, using expansion to identify local syndrome structure.The proof uses unique-neighbor expansion derived from graph expansion.Source: §4 · pp. 8–9
- Every nonzero error of weight at most min(γA nA, γB nB) has a critical generator.Source: §4 · p. 9
- When reduced error weight is at most min(γA nA, γB nB), a generator-supported flip can lower syndrome weight by at least |e1|/3 without increasing reduced weight.Source: §4 · p. 10
- Initial error weight below w0 guarantees that the decoder avoids failure and correctly decodes the error.The proof bounds the accumulated flips and establishes that the output is a valid representative of the initial error.Source: §4 · pp. 10–11
5 Concluding comments and questions
The paper's linear-time decoder corrects up to Ω(n^1/2) adversarial quantum errors. The conclusion identifies linear-scale correction and constructive base-graph expansion as open directions.
5 Concluding comments and questions
- The linear-time decoder corrects up to Ω(n^1/2) adversarial quantum errors over n qubits.The conclusion describes this as the largest such asymptotic quantity to date.Source: §5 · p. 11
- Prior work shows that these codes may correct a linear number of random depolarizing errors with vanishing decoding-error probability, but without a decoding-complexity limit.The conclusion asks whether the present ideas can extend to linear or quasi-linear-time decoding in that setting.Source: §5 · p. 11
- The authors ask whether the left-right expanding base graph can be constructed rather than chosen randomly.Source: §5 · p. 11
- The paper asks whether the expansion-coefficient bound δA, δB < 1/6 can be decreased further.Source: §5 · p. 11
Appendices
Figure 1 depicts a critical generator partitioned into error, clean, and small-relative-size sets, and shows how flips affect syndrome weights.
Appendices
- Figure 1 partitions a critical generator into error sets, clean sets, and small-relative-size χ sets; flipping selected sets lowers some syndrome weights from 1 to 0 while others stay unchanged or increase by 1.Source: Figure 1 · p. 13
A Proof of Lemma 7
The proof partitions a generator according to the error support and neighbor multiplicities, then treats empty and nonempty error components separately.
A Proof of Lemma 7
- The error support is split into its A2 and B2 vertices, with EA also projected onto its second coordinate.The projection is the set of A vertices whose corresponding A-coordinate slice intersects EA.Source: A Proof of Lemma 7 · p. 13
- The generator is partitioned into four components, separating A2 errors from error-free entries and B2 entries with unique versus multiple neighbors.The B2 distinction is defined with respect to E2.Source: A Proof of Lemma 7 · p. 14
- When EA is empty, the proof proceeds symmetrically with A and B interchanged; it separately addresses the case where both EA and EB are nonempty.Source: A Proof of Lemma 7 · p. 14
B Proof of Lemma 8
The proof selects a correction supported within a promised generator by comparing syndrome-weight decreases across cases. It aims to lower the syndrome while keeping reduced weight no greater than the original error weight.
B Proof of Lemma 8
- The correction e1 is sought within gba so that the syndrome weight strictly decreases and the resulting reduced weight is at most |e|.Source: B Proof of Lemma 8 · p. 15
- Four cases choose e1’s support according to x, y and their complemented quantities, including xa ∪ xb, ¯xa ∪ ¯xb, or a larger union.Source: B Proof of Lemma 8 · p. 15
- Flipping xa ∪ xb or ¯xa ∪ ¯xb reduces syndrome support on Sa¯b and S¯ab, while increases may occur on the corresponding Sa, Sb regions.Source: B Proof of Lemma 8 · pp. 15–16
- In cases 1 and 2, choosing xa ∪ xb gives wR(e + e1) < |e|; in case 3, ¯xa ∪ ¯xb decreases syndrome weight by at least |e1|/3.Source: B Proof of Lemma 8 · pp. 16–17
- In case 3, the flip may raise Hamming weight, but an equivalent representative has weight below |e|; case 4 offers choices with syndrome decrease at least |e1|/3 and reduced weight at most |e|.Source: B Proof of Lemma 8 · p. 17