PaperlayerView exact revision on arXiv

Source-linked AI summary

Balanced Product Quantum Codes

Nikolas P. Breuckmann, Jens N. Eberhardt

arXiv:2012.09271v3quant-ph

TL;DR

LDPC quantum codes lack an established analogue of classical good codes. This work develops balanced product constructions and obtains explicit LDPC quantum-code families with strong asymptotic properties, while conjecturing that broader balanced products yield good codes.

  • Problem

    Classical good codes have constant encoding rate and linear distance, but no equivalent result is known for LDPC quantum codes.

  • Method

    The paper constructs balanced product codes by combining spaces with shared symmetries and introduces twists into hypergraph-product checks.

  • Results

    The construction gives explicit LDPC quantum-code families with strong asymptotic parameters, including X-distance DX ∈Ω(N 1 3 ) and Z-distance DZ ∈Θ(N).

  • Takeaways & Limitations

    Replacing cycle graphs with good classical codes is conjectured to yield good LDPC quantum codes with linear logical-qubit count and distance.

Abstract

from arXiv · show

This work provides the first explicit and non-random family of $[[N,K,D]]$ LDPC quantum codes which encode $K \in Θ(N^\frac{4}{5})$ logical qubits with distance $D \in Ω(N^\frac{3}{5})$. The family is constructed by amalgamating classical codes and Ramanujan graphs via an operation called balanced product. Recently, Hastings-Haah-O'Donnell and Panteleev-Kalachev were the first to show that there exist families of LDPC quantum codes which break the $\operatorname{polylog}(N)\sqrt{N}$ distance barrier. However, their constructions are based on probabilistic arguments which only guarantee the code parameters with high probability whereas our bounds hold unconditionally. Further, balanced products allow for non-abelian twisting of the check matrices, leading to a construction of LDPC quantum codes that can be shown to have $K\in Θ(N)$ and that we conjecture to have linear distance $D\in Θ(N)$.

I. INTRODUCTION

The paper introduces balanced product codes as an explicit, symmetric construction for LDPC quantum codes, obtaining strong asymptotic parameters and conjecturing good codes with linear rate and distance.

  • Motivation: LDPC quantum codes lack the classical combination of constant encoding rate and linear distance, and such distances were only recently shown to exceed the polylog(N)√N barrier.Earlier improved constructions were probabilistic rather than explicit, so their parameter guarantees held only with high probability.
  • Balanced product construction: Balanced product codes combine codes sharing a group symmetry, generalizing hypergraph products by twisting checks and potentially increasing relative distance.For trivial H they reduce to hypergraph product codes; nontrivial H can reduce physical qubits while preserving distance in certain cases.
  • Construction: The construction uses Sipser–Spielman expander codes, LPS Ramanujan graphs, and cyclic repetition codes with compatible cyclic symmetry.The LPS graphs provide the symmetry needed to form balanced products with repetition codes.
  • Main results: K ∈ Θ(N^(2/3)) logical qubits, X-distance D_X ∈ Ω(N^(1/3)), and Z-distance D_Z ∈ Θ(N) are achieved by an explicit LDPC family.The parameters result from carefully choosing the balanced-product factors.
  • Main results: Distance balancing yields an explicit [[N,K,D]] LDPC family, while the manuscript also reports improved distance bounds by a factor of polylog(N) over earlier fiber-bundle bounds.The balanced-product framework also provides a conceptual treatment of fiber-bundle and lifted-product constructions.
  • Outlook: The authors conjecture that replacing cycle graphs with good classical codes could produce good LDPC quantum codes with K ∈ Θ(N) and D ∈ Θ(N).They also note that some constructed members may be subsystem codes because of a technical condition, while retaining sparse stabilizer checks.

B. (Quantum) Codes from Complexes

The paper represents classical and CSS quantum codes through chain complexes, using homology and cohomology to describe logical operators, distances, and code constructions.

  • Classical codes: A classical linear code is the kernel of a parity-check matrix and can be represented as the cycle space of a chain complex.The parity-check matrix is the differential, while codewords are 1-cycles.
  • Quantum codes: CSS quantum codes correspond to length-two chain complexes because commutation of X- and Z-checks is equivalent to H_Z^T H_X = 0.Boundary operators in the chain complex define the check matrices.
  • Quantum codes: The distance of the resulting CSS code is the minimum weight of a representative of a nontrivial homology or cohomology class.This connects quantum distance to homological representatives rather than ordinary codeword weight alone.
  • LDPC codes: LDPC families have stabilizer generators of bounded weight, with each qubit participating in only a bounded number of checks.This definition applies uniformly across the family.
  • Subsystem codes: Subsystem CSS codes retain selected logical qubits for information and treat the remaining logical degrees of freedom as gauge qubits.Their homology splits into logical and gauge parts, leading to bare and dressed distance notions.
  • Examples: The cycle graph C_ℓ yields the repetition code, while the ℓ×ℓ torus yields the toric code [[2ℓ^2, 2, ℓ]].These examples illustrate how cell complexes produce classical and quantum codes through their homology.

1) Total Complex:

Total complexes collapse double complexes by summing along diagonals, while tensor products provide a fundamental example. For 2×2 complexes, total-complex homology can be computed through successive vertical and horizontal homology, extending to fiber bundle codes under stated assumptions.

  • Total complexes: The total complex Tot(E) is formed by summing the vector spaces of a double complex along diagonals.This construction turns a double complex into an ordinary complex.
  • Tensor products: The tensor product double complex C ⊠D has the tensor product complex as its total complex.When both factors are 1-complexes, the construction is also called a hypergraph product.
  • 2×2 complexes: For a 2×2 complex, vertical homology followed by induced horizontal homology computes the homology of the total complex.The second-page spectral-sequence differentials vanish because their domains or codomains are zero.
  • Fiber bundle codes: A fiber bundle code twists horizontal tensor-product differentials using automorphisms assigned to incident base-cell pairs.With the trivial twist, the construction reduces to the usual tensor product complex.
  • Fiber bundle codes: Fiber bundle complexes satisfy a Künneth formula when the connection acts as the identity on fiber homology.The paper also assumes an augmentation isomorphism and vanishing zeroth homology of the base for a stated theorem.

III. EXPANDER CODES

Expander codes combine graph-based global constraints with small local codes. Their behavior is governed by graph expansion, quantified through boundary growth and spectral properties such as the second adjacency eigenvalue.

  • Tanner codes: A Tanner code is defined from an s-regular graph, a local [s,k,d] code, edge labels, and a boundary differential.The graph edges represent variables, while vertices represent checks.
  • Expander codes: Sipser–Spielman expander codes combine infinite families of expander graphs with fixed-size local codes to produce good classical codes.The Tanner-code construction replaces graph-vertex checks with parity checks from a local code.
  • Spectral expansion: Spectral expansion is measured by the second-largest adjacency eigenvalue λ2, with smaller λ2 indicating better expansion.Ramanujan graphs attain the optimal asymptotic eigenvalue bound for regular graphs.
  • Expansion properties: Expander graphs have large boundaries for vertex sets, and related lemmas control vertex and edge expansion for sufficiently small subsets.These expansion estimates support later distance analyses for Tanner and balanced-product codes.
  • Explicit constructions: Random regular graphs are expanders with high probability, whereas the paper turns to explicit expander constructions in the next section.The random-graph statement includes a high-probability eigenvalue bound near the Ramanujan threshold.

2) Properties of expanders:

Expander properties yield quantitative control over incident vertices, boundary structure, and induced subgraphs. Combined with local-code distance, these bounds produce lower bounds for expander-code distance.

  • Induced subgraphs: The induced subgraph on a vertex subset has an upper-bounded number of internal edges determined by the subset size and λ2.Negating this estimate gives lower bounds on the vertices incident to edge sets.
  • Edge-to-vertex expansion: A set of edges occupying an α fraction of graph edges is incident to more than a γ fraction of vertices.This converts edge weight into vertex support using spectral expansion.
  • Boundary refinement: The number of vertices with many edges leaving a small set can be lower-bounded from the graph’s expansion parameters.The proof partitions boundary edges according to their incident boundary degree.
  • Code parameters: Linear dependencies among local constraints can reduce the number of independent global checks.The all-ones vector can create such a dependency when it is a parity check of the local code.
  • Code distance: The expander-code distance lower bound depends on the local-code distance dL and the graph eigenvalue λ2.The bound is non-trivial when dL is strictly larger than λ2.

2) Expansion properties of Tanner codes:

Tanner-code expansion shows that small chains or cochains violate many checks when graph and local-code expansion parameters are suitable. The construction uses explicit, highly symmetric Ramanujan graphs to retain deterministic control.

  • Expansion properties of Tanner codes: Small edge-supported chains have boundary weight at least β times their weight, with β determined by graph and local-code expansion parameters.The theorem uses the local-code distance dL and the graph’s spectral expansion λ2.
  • Expansion properties of Tanner codes: Small vertex-supported cochains similarly have coboundary weight at least βy times their weight.The bound depends on the local code and its dual, together with the graph expansion.
  • Expansion properties of Tanner codes: The proof converts edge-to-vertex expansion into violated checks by identifying vertices whose incident boundary edges force nonzero local syndromes.At least one check is violated at every vertex in the relevant subset.
  • LPS expanders: Explicit expander families are required because the balanced-product construction needs full control over graph automorphism groups.This requirement excludes randomized expander constructions.
  • LPS expanders: LPS Cayley graphs of PSL(2,q) or PGL(2,q) are connected, (p+1)-regular expanders with λ2 < 2√p.They provide explicit Ramanujan-type graphs with group structure and known symmetry.
  • Hyperbolic constructions: Hyperbolic tessellations offer an alternative explicit route with flexible geometry and known symmetries.The Klein quartic is a genus-3 surface carrying the {3,7} tessellation and PSL(2,7) orientation-preserving symmetries.

2) Hyperbolic tessellations:

The paper constructs hyperbolic expander graphs from regular tessellations and finite quotients, with symmetry groups obtained through algebraic reduction. These graphs provide structured candidates for the code construction, although explicit bounds on their second eigenvalues are unavailable.

  • Regular hyperbolic tessellations are specified by the Schlӓfli symbol {r, s}, with r polygon sides and s polygons meeting at each vertex.
  • Infinite families of s-regular graphs arise as 1-skeleta of increasingly large closed hyperbolic surfaces obtained by quotienting tessellation symmetry groups.
  • Hyperbolic regular tessellations yield s-regular expander-graph families, but the paper notes that explicit bounds on their second eigenvalues are not known.
  • Matrix representations reduced modulo primes produce finite quotients whose images can be PSL(2, q) or PGL(2, q) with torsion-free kernels under stated arithmetic conditions.
  • The Klein quartic is a genus-3 hyperbolic surface tessellated by {3, 7}, with orientation-preserving symmetry group PSL(2, 7).
  • For local codes, the required conditions are rate kL/2 > 1/2 and distance dL > λ2, linking code quality to graph spectral expansion.

1) Goppa Codes:

The paper develops classical local codes for balanced products using Goppa, BCH, and expander-code constructions. It combines distance guarantees for codes and duals with cyclic symmetry requirements needed by the later quantum construction.

  • 1) Goppa Codes:: Binary Goppa codes encode at least s − mt bits and have distance at least 2t + 1.
  • 1) Goppa Codes:: The dual distance of a Goppa code also admits a lower bound when the defining polynomial has distinct roots.
  • 2) Cyclic codes and canonical labelings:: BCH codes offer a convenient cyclic Goppa-code choice, while LPS expanders require a doubling process because their degree is even but BCH code lengths are odd.
  • 2) Cyclic codes and canonical labelings:: A cyclic Hamming local code on a {3, 7} hyperbolic graph yields a [84, 12, 19] expander-code example with canonical symmetry-compatible labeling.
  • 3) Existence of good local codes:: For every n > 2/(1/2−H2(δ)) and δ ∈ (0, 0.11), there exists a binary linear code with kC > n/2 and both code and dual distances at least δn.

A. Motivation from Topology

Balanced products originate from forming associated fiber bundles from spaces with compatible group actions. The same quotient-and-twist viewpoint extends to graphs, where connections encode how fibers are glued over quotient graphs.

  • A. Motivation from Topology: Given a right H-space X and a left H-space Y, the balanced product X ×H Y is the quotient of X × Y by an anti-diagonal H-action.
  • A. Motivation from Topology: The balanced product forms a fiber bundle over X/H with fiber Y, and its equivalence classes satisfy [x · h, y] = [x, h · y].
  • A. Motivation from Topology: For graphs with a free finite-group action satisfying the quotient condition, X → X/H is an |H|-fold covering and preserves regularity.
  • A. Motivation from Topology: Choosing representatives of vertex orbits defines a connection φR that records the group element needed to match lifted adjacent edges.
  • A. Motivation from Topology: The connection can be simplified locally but cannot be made globally trivial when X is connected.
  • A. Motivation from Topology: The balanced product of cyclic graphs produces the [[12, 2, 3]] twisted toric-code example, with edges as qubits and vertices and faces as X- and Z-checks.

D. Balanced Products of Chain Complexes

The paper lifts balanced products from spaces and graphs to vector spaces and chain complexes, then uses natural bases to define quantum codes. This framework generalizes tensor products and connects to fiber-bundle and lifted-product constructions.

  • D. Balanced Products of Chain Complexes: For chain complexes with compatible H-actions, the balanced product double complex yields a total complex whose natural basis defines a balanced product quantum code.
  • D. Balanced Products of Chain Complexes: If H acts on chosen bases, basis elements become anti-diagonal orbits [x, y], enabling explicit differential matrices after ordering those basis vectors.
  • D. Balanced Products of Chain Complexes: The trivial-group case reduces balanced products to tensor products, so the construction generalizes tensor and hypergraph products.
  • D. Balanced Products of Chain Complexes: When H has finite odd order, the balanced-product homology satisfies a Künneth-type isomorphism derived by identifying coinvariants with invariants.
  • D. Balanced Products of Chain Complexes: For suitable free abelian actions, balanced products specialize to fiber-bundle codes and lifted products, with the latter represented using matrices over the group algebra.
  • D. Balanced Products of Chain Complexes: Replacing group-algebra entries by regular-representation matrices produces an F2 chain complex agreeing with the balanced product complex.
  • D. Balanced Products of Chain Complexes: The construction combines a Tanner code C(X, L) with a graph complex C(Y) through C(X, L) ⊗H C(Y), using selected group, graph, local-code, and labeling choices.
  • D. Balanced Products of Chain Complexes: In the repetition-code example, the resulting twisted toric code has weight-4 X- and Z-checks, distance 3, and 12 qubits instead of 18.

2) Definition in terms of fiber bundles:

The fiber-bundle formulation identifies balanced product codes with constructions over the quotient graph and relates their homology to horizontal and vertical components. For cyclic fibers, the horizontal logical subspace is isomorphic to the corresponding Tanner-code homology.

  • Fiber-bundle construction: C(X, L) ⊗H C(Y ) is defined as the total complex of the corresponding balanced product bundle over X/H.The coordinatized construction uses the descended labeling on the quotient graph.
  • Fiber-bundle construction: The balanced product can also be interpreted as a lifted product code, linking the fiber-bundle and lifted-product perspectives.This equivalence is stated for C(X, L, Λ) ⊗H C(Y ).
  • Homology decomposition: H1(C(X, L) ⊗H C(Y )) decomposes into complementary horizontal and vertical homology classes represented by (u, 0) and (0, v).For a general representative, the Künneth formula supplies a homologous representative whose components are homology classes.
  • Cyclic fibers: For the cyclic fiber Cℓ with odd ℓ, the translation action induces a trivial action on H0(Cℓ) and H1(Cℓ).This supports the projection and inclusion maps used to identify the horizontal homology.
  • Cyclic fibers: The horizontal logical-bit count of the balanced product agrees with the logical-bit count of the Tanner code C(X/H, L).The result follows from isomorphisms between the relevant homology spaces and the quotient Tanner-code homology.

G. Balanced Product Subsystem Codes

The horizontal subsystem balanced product code retains selected horizontal logical operators while treating vertical degrees of freedom as gauge qubits. Its distance bounds follow from expansion assumptions and lifted-product results.

  • Subsystem construction: The horizontal subsystem balanced product code stores information in horizontal homology while disregarding vertical gauge qubits.The construction uses subsystem-code formalism to focus on the horizontal part because stronger distance bounds are available there.
  • Distance bounds: |x| = |u| + |v| ≥ ℓ min {αho/(4s), αhoβho/(4s)} for a representative with non-trivial horizontal homology.This bound is the horizontal case used in the distance analysis.
  • Code parameters: The physical-qubit count is dim(C(X, L) ⊗Zℓ C(Cℓ))1 = |X1| + s|X0| = 3|X1|.This expression gives the number of physical qubits for the balanced product with the cycle graph.
  • Logical-qubit count: The horizontal subsystem encodes as many logical qubits as the Tanner code C(X/Zℓ, L), with the count bounded using the quotient graph.The quotient has |X1|/ℓ edges when Zℓ acts freely on X.
  • Distance bounds: The horizontal homological distance DX is bounded by combining the horizontal and vertical cases of the lifted-product distance theorem.The code is identified with a lifted product LP(A, 1 + x), allowing Panteleev–Kalachev bounds to apply.

I. Concrete Example of a Balanced Product Code

The section presents explicit balanced-product LDPC quantum-code constructions, including a concrete finite example and asymptotic families with strong encoding and distance guarantees. It also identifies linear-rate constructions and linear-distance questions that remain open.

  • Concrete example: 78 encoded bits arise in the underlying expander code, which has 546 bits and 468 checks of weight 4.The example uses a degree-7 graph and the Hamming code, but the available bound gives no nontrivial distance lower bound.
  • Concrete example: N = 1014 qubits and K = 6 logical qubits in the concrete balanced product using a cyclic group of order 13.The X-stabilizers have weight 6, while Z-stabilizer weights range from 4 to 8.
  • Asymptotic construction: K ∈ Θ(N^(2/3)), with X-distance D_X ∈ Ω(N^(1/3)) and Z-distance D_Z ∈ Θ(N), for an explicit LDPC family.The construction uses LPS expanders and cyclic subgroups satisfying freeness and quotient conditions.
  • Asymptotic construction: K ∈ Θ(N^(4/5)) and D ∈ Ω(N^(3/5)) for an explicit [[N, K, D]] LDPC family after distance balancing.The authors obtain this family from classical codes with parameters Θ(N^(2/3)), Θ(N^(2/3)), and Θ(N^(2/3)).
  • Open directions: Balanced products can produce good LDPC quantum codes with constant encoding rate, but linear distance remains an open problem for the associated subsystem family.The construction’s sparse Kronecker-product checks imply the LDPC property, while efficient decoding is left for future work.

APPENDIX A SPECTRAL SEQUENCES

The appendix explains spectral sequences as an iterative method for computing homology of a double complex and reviews the hyperbolic geometry and symmetries underlying the paper’s graph constructions. It also connects regular tessellations to graph families with linear encoding rate.

  • Spectral sequences: A spectral sequence iteratively replaces pages of vector-space arrays by homology along page-specific differentials, approximating the homology of the total complex.The r-th page carries differentials whose homology defines the next page.
  • Spectral sequences: A spectral sequence degenerates on page r0 when all later differentials vanish, making subsequent pages identical.The resulting pages are then isomorphic for all r ≥ r0.
  • Spectral sequences: The 0-th page is the double complex itself, while later pages are obtained by successive vertical and horizontal homology operations.The second page first takes vertical and then horizontal homology.
  • Hyperbolic geometry: In the Poincaré disc model, hyperbolic geodesics are circular arcs meeting the unit circle orthogonally, while angles are represented faithfully despite distorted lengths.The appendix uses this model to describe hyperbolic tessellations and their symmetries.
  • Tessellations and codes: Regular hyperbolic tessellations are specified by the Schlӓfli symbol {r, s}, and their symmetry groups generate highly structured graph families.Taking 1-skeleta after quotienting by normal subgroups yields infinite graph families; such surfaces give quantum codes with linear encoding rate.
Loading 2012.09271v3…