Source-linked AI summary
Fiber Bundle Codes: Breaking the $N^{1/2} \operatorname{polylog}(N)$ Barrier for Quantum LDPC Codes
Matthew B. Hastings, Jeongwan Haah, Ryan O'Donnell
TL;DR
Quantum LDPC codes with distance beyond N^1/2 polylog(N) remain difficult to construct. This paper generalizes the homological product using a twisted fiber bundle construction, obtaining distance Ω(N^3/5/polylog(N)) together with Ω(N^3/5/polylog(N)) logical qubits.
Problem
Constructing quantum LDPC codes on N qubits with distance greater than N^1/2 polylog(N) has been a longstanding open problem.
Method
The paper generalizes the homological product to a twisted homological product based on fiber bundles, then applies weight reduction and distance balancing.
Results
Distance d = Ω(N^3/5/polylog(N)) and Ω(N^3/5/polylog(N)) logical qubits are achieved by a family of quantum LDPC codes.
Takeaways & Limitations
The construction provides a quantum LDPC code family whose distance exceeds the previously described N^1/2 polylog(N) scale.
Takeaways & Limitations
The paper does not optimize the polylogarithmic factors in the distance for simplicity of presentation.
Abstract
from arXiv · showhide
We present a quantum LDPC code family that has distance $Ω(N^{3/5}/\operatorname{polylog}(N))$ and $\tildeΘ(N^{3/5})$ logical qubits. This is the first quantum LDPC code construction which achieves distance greater than $N^{1/2} \operatorname{polylog}(N)$. The construction is based on generalizing the homological product of codes to a fiber bundle.
1 Introduction
The paper develops fiber bundle quantum LDPC codes to address the longstanding challenge of achieving distance beyond N^1/2 polylog(N), culminating in distance Ω(N^3/5/polylog(N)) and Ω(N^3/5/polylog(N)) logical qubits.
- Introduction: Distance Ω(N^3/5/polylog(N)) solves the longstanding problem of constructing quantum LDPC codes beyond N^1/2 polylog(N).The construction also gives partial decoding results: polynomial-time decoding for bit-flip errors and a conjectured efficient algorithm for phase errors.
- Construction: The construction generalizes the homological product into a twisted homological product inspired by fiber bundles.Weight reduction and distance balancing convert the resulting codes into quantum LDPC codes.
- Intermediate code: Theorem 1.1 gives dX = Ω(N^1/2/polylog(N)) and dZ = Ω(N^3/4/polylog(N)), with Θ(N^1/2) logical qubits and polylogarithmic stabilizer participation.The theorem's intermediate code has polylogarithmic stabilizer weight and qubit participation, rather than constant LDPC parameters.
- LDPC corollary: Corollary 1.2 gives quantum LDPC codes with distance d = Ω(N^3/5/polylog(N)) and Ω(N^3/5/polylog(N)) logical qubits.Distance balancing is applied because the intermediate code has unequal X- and Z-distances.
- Topological motivation: Fiber bundles extend manifold products by allowing global twists while retaining a locally product-like structure.The paper uses this topological generalization to enrich the structure available for quantum-code constructions.
2 Fiber Bundle Codes
The paper constructs quantum CSS codes from twisted fiber-bundle chain complexes, extending the homological product with base–fiber twists. For a circle fiber and suitable random base, the construction preserves first (co)homology while yielding explicit distance and logical-qubit scalings.
- Construction: The construction starts from chain complexes and generalizes the homological product by twisting boundary maps to form fiber bundles.The untwisted product uses tensor-product chain spaces, while the twisted construction modifies boundaries using fiber automorphisms.
- Construction: For a 1-complex base, the twisted boundary maps satisfy ∂E^r+1 = 0, so the construction defines a chain complex.Higher-dimensional bases require additional conditions and may need extra boundary-map terms.
- Construction: A bundle 1-cell is horizontal when it lifts a base 1-cell and vertical when it vanishes under projection.Every bundle 1-chain decomposes uniquely into horizontal and vertical parts.
- Homology and cohomology: Under the stated conditions, bundle projection induces isomorphisms between H1(E) and H1(B), and between their corresponding cohomology groups.Consequently, the first Betti numbers agree: b1(E) = b1(B).
- Code definition: The fiber bundle code is a CSS code whose qubits and logical operators come from dimension-1 cells, homology, and cohomology of E2 → E1 → E0.The complex uses a circle fiber and a base complex, with bundle 1-cells corresponding to qubits.
- Parameters and performance: Choosing nB ∼ mF gives N = Θ(nB^2), dX = Ω(N^1/2/log^2 N), dZ = Ω(N^3/4/log^2 N), and Θ(nB) logical qubits.The construction first establishes dX = Ω(mF/log^2 nB) and dZ = Ω(nB·mF^1/2/log^2 nB) when nB ≥ mF.
- Parameters and performance: The polylogarithmic factors are not optimized, and parameter adjustments can slightly improve them.The paper explicitly notes that the distance polylogarithms can be improved by changing parameter choices.
3 The random base code, with twists
The construction uses a random classical LDPC base code with expansion, full rank, and linear distance, then proves lower bounds on representative weights for the resulting bundle.
- Expansion properties: With probability 1 − O(1/n^100), every small check set has neighborhood size at least .9Δ|S|, and one check in the set has more than .81Δ counique neighbors.The latter gives a strict majority of counique neighbors for some check vertex.
- Cohomology and homology weights: For any twists, a nontrivial H1(E) representative has either horizontal weight at least mF/2 or vertical-shadow weight Ω(n/Δ), yielding total weight Ω(mF/Δ) when n ≥ mF.The proof analyzes the shadow of the vertical part and uses counique-neighbor expansion of the base code.
- Cohomology and homology weights: When m = Θ(n), every nontrivial H1(E) representative has weight Ω(nℓ/Δ) with high probability.A homologous representative can be chosen so that every nonzero horizontal cell lies at fiber position 0 mod ℓ.
4 Coding Bounds for Twist Graph Code
The twist graph code converts bundle checks into graph-coupled parity checks, while spectral expansion and probabilistic bounds show that low-weight words violate many checks.
- Twist graph code: The twist graph has ℓ vertices and k edge types, with one incoming and one outgoing edge of each type at every vertex.Its undirected version is 2k-regular, and κS denotes the second-largest eigenvalue magnitude.
- Twist graph code: With probability at least .999, choosing k = O(log ℓ/κ^2) gives twist-graph spectral parameter κS ≤ ϵ.The construction ultimately uses k = O(log ℓ) = O(log mF) for a small universal ϵ.
- Code definition: B(S⃗) has block length ℓ·n and imposes type-τ checks on the pair of words attached to each directed edge of type τ.The code is formed by applying all type-τ checks to (wu,wv) for every directed edge (u,v).
- Violation bounds: Except with probability O(1/n^100), every sufficiently small pair (y,z) violates a number of checks proportional to its combined weight.Lemma 4.6 applies to pairs with |y|, |z| ≤ 4n/Δ.
- Violation bounds: Even when one word is heavy, aggregating checks across almost all edge types produces at least .01n parity-check violations.This holds for |x| ≥ 4n/Δ, at least .98k types, and auxiliary words of weight at most 2n/Δ.
- Final coding bound: Every word of relative weight at most ϵ = .0002/Δ violates at least .004|w| parity checks in B(S⃗).The theorem assumes the conclusions of Lemmas 4.6 and 4.7 and bounds words with |w| ≤ ϵℓn.
5 Decoding
The paper develops polynomial-time decoding procedures for fiber bundle codes, including a proven decoder for cohomology and a conjectured homology decoder. Erasure decoding is also achieved in near-linear time under a bounded-erasure assumption.
- Decoding cohomology: Polynomial-time decoding recovers arbitrary errors up to a polylogarithmic fraction of dX under the assumptions of Lemma 3.7.The decoder reconstructs errors up to stabilizers.
- Decoding cohomology: The cohomology decoder first constructs an arbitrary chain earb with syndrome s and bounded vertical-shadow weight.It uses the map K to reduce the construction to finding eb satisfying ∂Teb = K(s) and |eb| ≤ |s|.
- Decoding cohomology: Expansion enables a greedy algorithm to construct eb and terminate after at most |K(s)| toggles when the initial error satisfies the stated weight bound.The resulting chain obeys ∂Teb = K(s) and |eb| ≤ |K(s)| ≤ |s|.
- Decoding cohomology: The second decoding stage repeatedly amends fixable base 0-cells by reducing horizontal weight until no further fixes remain.Termination occurs after at most N fixes because horizontal weight strictly decreases.
- Decoding homology: The proposed homology decoder is conjectured, but not proved, to correct errors up to a polylogarithmic fraction of dZ.Its erasure-decoding counterpart uses belief propagation to peel erased cells and achieves time |D| poly(∆, log |D|) when |D| < mF/(105∆^2).
- Erasure decoding: Erasure decoding reduces the remaining erased set to zero while maintaining a correction whose combined weight is below dX, implying the zero cohomology class.The procedure decreases |D| at each transition and runs in near-linear time in |D| up to poly(∆, log |D|) factors.
A Weight Reduction and Chain Homotopy
The appendix weight-reduces the classical base code before constructing the fiber bundle code over it. Its organizing equivalence notion is homotopy equivalence of chain complexes with additional Lipschitz bounds.
- Weight reduction: The appendix first weight-reduces the classical base code and then constructs the fiber bundle code as a bundle over the reduced code.This provides the route from the original construction to a weight-reduced code.
- Chain homotopy: Homotopy equivalence of chain complexes is combined with Lipschitz bounds to relate the original and weight-reduced codes.The appendix establishes homotopy equivalences between two classical base codes and between the fiber bundle code and a weight-reduced code.
A.1 Review on Chain maps and homotopies
The appendix reviews chain maps, chain homotopies, and homotopy equivalence as algebraic tools for comparing chain complexes and their induced homology and cohomology maps.
- Chain maps: A chain map is a degree-preserving linear map between chain complexes that respects the boundary operators.The transpose of a chain map commutes with coboundary operators and is called a cochain map.
- Chain homotopies: A chain homotopy relates two chain maps through a linear map of adjacent degree, equivalently represented as a chain map from an interval complex tensor product.The two definitions are shown to be equivalent.
- Homotopy equivalence: Homotopic chain maps induce identical maps on homology and cohomology, while a homotopy equivalence induces isomorphisms on both.These induced maps need not be injective or surjective for an arbitrary chain map.
A.2 Distance and Decoding
The appendix connects Lipschitz-controlled homotopy equivalences to code distance and decoding, showing how a decoder transfers between homotopy-equivalent chain-complex codes with a distance-dependent loss.
- Distance bounds: The chain weight is the Hamming weight in the paper’s examples, and Lipschitz constants bound how much maps can increase that weight.The definitions apply more generally to any chosen weight function.
- Distance bounds: Lipschitz-controlled homotopy equivalence lower-bounds the distances of one code using the corresponding distance of the other.The bound divides by the relevant Lipschitz constant for the chain map or transposed inverse map.
- Limitations: The appendix notes that its distance bounds are probably not tight because they use only a particular Lipschitz constant.The bound is used to lower-bound the distance of the weight-reduced code.
- Decoder transfer: A decoder for a code defined by B transfers to a code defined by A when the chain complexes are homotopically equivalent.The transferred decoder succeeds for errors up to Kj(f)^−1 · W(O).
A.3 Cell Combining and Collapsing and Weight-Reducing the Classical Codes
Cell combining merges two cells into one through a homotopy-equivalent chain-complex transformation, illustrated by deforming one edge until it disappears.
- Cell combining merges two cells into a single cell while preserving homotopy equivalence between the corresponding chain complexes.The procedure supports deriving the original classical or fiber bundle code from a weight-reduced code.
- Figure 2 depicts the process by deforming the shared 0-cell until the second 1-cell shrinks away and its boundary is mapped onto other 0-cells.
A.3.1 Cell combining
Cell combining replaces two 1-cells incident to one 0-cell with a single 1-cell using explicit maps that form a homotopy equivalence.
- Cell combining removes 1-cells e1 and e2 and 0-cell v, replacing them with a new 1-cell e and a modified boundary operator.The new boundary is defined as ∂B = f ◦ ∂A ◦ g.
- The map f sends e1 to e and e2 to zero, while mapping v to v + ∂Ae2 and preserving the other cells.
- The map g sends e to e1 − e2 and preserves all other 1-cells and 0-cells.
- The maps f and g are chain maps and establish a homotopy equivalence between complexes A and B.
- The homotopy between gf and the identity is constructed using a map h that sends v to e2 and vanishes elsewhere.
A.3.2 Cell collapsing
Cell collapsing is the dual operation to cell combining: it removes a 1-cell while identifying its two boundary 0-cells.
- Cell collapsing maps a 1-cell e to zero and maps its two boundary 0-cells v1 and v2 to the same image.The construction is obtained by interchanging 1-cells and 0-cells and using the transposed boundary operator.
A.4 Weight reducing
Weight reduction replaces high-weight code elements with auxiliary bits and checks, then uses cell combining and collapsing to recover a homotopy-equivalent code with controlled map locality.
- A.4 Weight reducing: The construction reduces boundary and coboundary weights by copying bits, enforcing equality with auxiliary checks, and applying the dual procedure to checks.
- A.4 Weight reducing: A weight-reduced code creates |∂b| bits for each original bit b and |∂Tc| checks for each original check c, plus auxiliary checks and bits.
- A.4 Weight reducing: The weight-reduced code has O(N0+E) checks and O(N1 + E) bits when the original code has N1 bits, N0 checks, and E nonzero boundary entries.
- A.4 Weight reducing: Auxiliary checks connect adjacent copies of each bit, while auxiliary bits connect adjacent copies associated with each check.
- A.4 Weight reducing: The weight-reduced code is homotopy equivalent to the original classical code.
- A.4 Weight reducing: The maps f, g, fT, and gT have Lipschitz constants O(max(d1, d2)).After cell collapsing, the Lipschitz constant on all cells is O(max(d0, d1)).
- A.4 Weight reducing: Removing auxiliary checks by cell combining and auxiliary bits by cell collapsing yields the homotopy equivalence.
A.5 Weight-reducing the fiber bundle code
The paper weight-reduces the fiber bundle code by transferring its twists to a weight-reduced base while preserving homotopy equivalence. The resulting distance remains within a polylogarithmic factor of the original code's distance.
- Construction: The weight-reduced fiber bundle uses a weight-reduced base code and assigns original twists only to corresponding Tanner graph edges.All twists involving auxiliary bits or checks are set to zero.
- Homotopy equivalence: The weight-reduced and original fiber bundle codes are homotopy equivalent, with equivalence maps and duals having Lipschitz constants O(max(d1, d2)).The twisted equivalence is obtained from the untwisted case using gauge redundancy.
- Homotopy equivalence: Gauge redundancy can zero all twists involving the single bit or check modified by each local combining or collapsing step.This permits tensoring the classical homotopy equivalences with the identity on the fiber.
- Homotopy equivalence: The composition of O(N) local homotopy equivalences has Lipschitz constant at most the maximum local constant, because each cell is merged or split only once.The composition therefore avoids multiplying all local Lipschitz bounds.
- Distance: The weight-reduced fiber bundle's distance is within a polylogarithmic factor of the original fiber bundle code's distance.The bound is not claimed to be optimal because it uses only that the mapped chain is closed, not that the original chain itself is closed.
B Notation
This notation section defines the bundle, its base and fiber, the associated cell counts, and parameters used to specify the construction.
- Bundle components: B denotes the base of the bundle, F denotes its fiber, and E denotes the fiber bundle.The bundle's qubits are associated with 1-cells of E, while checks correspond to 0- and 2-cells.
- Base notation: nB is the number of 1-cells in the base, while mB is the number of 0-cells.The base is represented by a bipartite graph whose right vertices are code bits and whose left vertices are checks.
- Fiber notation: nF = mF counts the fiber's 0-cells and, equally, its 1-cells.The fiber is specified here as a cycle graph.
- Notation: [n] denotes the integer set {1, 2, ..., n}, and 105 is a universal constant related to expansion bounds in Proposition 3.2.The constant is introduced as part of the paper's notation.
- Parameters: ℓ is chosen so that nF = mF = ℓ2, and all twists are integer multiples of ℓ.This parameterization links the fiber size to the allowed twist values.
- Parameters: ∆ is the base code's average check-degree and is ultimately chosen as Θ(log2 n), while k is the number of distinct twists and is chosen as Θ(log n).The shorthand n and m may refer to nB and mB.