PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum "hyperbicycle" low-density parity check codes with finite rate

Alexey A. Kovalev, Leonid P. Pryadko

arXiv:1212.6703v2quant-ph

TL;DR

Quantum LDPC codes seek low-overhead protection despite stringent commutativity constraints and the absence of known asymptotically good families. The paper introduces hyperbicycle codes, a broad construction encompassing hypergraph-product and generalized bicycle codes as limiting cases. It obtains finite-rate families with square-root distance scaling, explicit distance bounds, and potentially higher rates while preserving the estimated error threshold.

  • Problem

    Quantum LDPC codes can reduce syndrome-measurement overhead, but commutativity constraints leave asymptotically good families unknown.

  • Method

    The paper constructs hyperbicycle codes as a larger family whose limiting cases include hypergraph-product and generalized bicycle codes.

  • Results

    Hyperbicycle families have finite rates and distances scaling as a square root of block length, with explicit upper and lower distance bounds.

  • Takeaways & Limitations

    Hyperbicycle codes broaden the parameter range and can improve hypergraph-product rates while preserving the estimated error threshold.

Abstract

from arXiv · show

We introduce a "hyperbicycle" ansatz for quantum codes which gives the hypergraph-product (generalized toric) codes by Tillich and Zémor and generalized bicycle codes by MacKay et al. as limiting cases. The construction allows for both the lower and the upper bounds on the minimum distance; they scale as a square root of the block length. Many of thus defined codes have finite rate and a limited-weight stabilizer generators, an analog of classical low-density parity check (LDPC) codes. Compared to the hypergraph-product codes, hyperbicycle codes generally have wider range of parameters; in particular, they can have higher rate while preserving the (estimated) error threshold.

I. INTRODUCTION

Quantum error correction needs codes that protect fragile information while reducing measurement overhead. Quantum LDPC codes address this goal, but commutativity constraints leave their achievable asymptotic parameters largely unresolved.

  • Motivation: Quantum error correction protects fragile quantum information from environmental coupling but can require many auxiliary qubits and difficult technology.Simpler syndrome measurements could reduce overhead and enable parallel error correction.
  • Open problem: No asymptotically good quantum LDPC families or existence bounds are known, motivating explicit designs with controlled K, D, and stabilizer-generator weight.The code rate is K/N, where N is the block length.
  • Prior constructions: Hypergraph-product constructions provide finite-rate quantum LDPC codes whose distances scale as a square root of block length.They generalize toric codes through products of hypergraphs associated with classical binary codes.
  • Prior constructions: Bicycle codes show good numerical decoding behavior but have unknown minimum distance, whereas hypergraph-product codes have known parameters but potentially difficult decoding.Finite noise thresholds have been established for limited-stabilizer-weight hypergraph-product codes.
  • Contribution: Hyperbicycle codes form a larger family that contains generalized bicycle and hypergraph-product codes as limiting cases, with finite rates, square-root distance scaling, and potentially higher rate at preserved estimated threshold.The construction broadens the available parameter range relative to hypergraph-product codes.
  • Motivation: Quantum LDPC codes use limited-weight stabilizer generators, analogous to sparse parity-check matrices in classical LDPC codes.For limited quantum LDPC codes, stabilizer-matrix row and column weights are bounded above.

C. Bicycle codes

Bicycle and hypergraph-product constructions motivate a broader product-based framework. The resulting hypergraph-product parameters are determined by four classical codes and obey explicit rate and distance relations.

  • Bicycle codes: Bicycle codes use a CSS block construction based on a binary circulant matrix and have numerically good error-correction capabilities but unknown distance.Some generator-matrix rows are deleted to obtain bicycle codes.
  • Hypergraph-product codes: Hypergraph-product codes construct quantum generators from the Kronecker products of parity-check matrices for two classical binary codes.The associated X- and Z-generator matrices commute because of the Kronecker-product structure.
  • Hypergraph-product codes: N = r2n1 + r1n2 gives the quantum block length, with generator matrices having r1r2 and n1n2 rows and N columns.The rows need not all be linearly independent.
  • Hypergraph-product codes: The quantum parameters [[N, K, D]] depend on four classical codes associated with H1, H2, H1^T, and H2^T.The construction permits linearly dependent rows or columns in the classical matrices.
  • Hypergraph-product codes: D ≥ min(d1, d2, ed1, ed2), while upper bounds include D ≤ d1 when k1 > 0 and ek2 > 0, or D ≤ d2 when k2 > 0 and ek1 > 0.These conditions provide explicit lower and upper constraints on the quantum distance.

III. TWO-SUBLATTICE CODES

The two-sublattice ansatz maps stabilizer codes to CSS codes and supports sparse constructions, including generalized bicycle codes with explicit parameter formulas and examples.

  • A. Two-sublattice CSS code from a generic stabilizer code: A stabilizer code [[N, K, D]] maps reversibly to a two-sublattice CSS code [[2N, 2K, D′]] with D ≤ D′ ≤ 2D.
  • A. Two-sublattice CSS code from a generic stabilizer code: The mapping preserves sparsity, keeping column weight unchanged while increasing row weight by at most a factor of two.
  • B. Generalized bicycle codes: For commuting circulant matrices, the construction yields generalized bicycle codes represented by additive cyclic codes over F4.
  • B. Generalized bicycle codes: Generalized bicycle codes have block length N = 2n, encoded-qubit count K = 2 deg p(x) + 2 deg r(x) − 2n, and distance at least that of an associated classical F4 code.
  • B. Generalized bicycle codes: The distance estimate is tight only for pure codes because degeneracy is not included.
  • B. Generalized bicycle codes: Rotated toric-code families provide explicit examples, including CSS parameters [[2t^2 + 2(t + 1)^2, 2, 2t + 1]] and non-CSS parameters [[t^2 + (t + 1)^2, 1, 2t + 1]].
  • B. Generalized bicycle codes: Some examples exceed the lower distance bound because of degeneracy.

C. Tensor-product constructions and Haah’s codes

Tensor-product constructions generalize the hypergraph-product and bicycle limits through commuting matrix blocks, while preserving CSS commutativity and enabling reduced hypergraph interpretations.

  • Tensor-product constructions: Combining tensor products with commuting matrices produces a general two-sublattice tensor-product code family.
  • Haah’s codes: Haah’s codes instantiate the two-sublattice tensor-product structure and are built essentially from a repetition code.
  • Tensor-product constructions: The construction uses binary matrix blocks a_i and b_i, unit matrices, and permutation matrices governed by coprime integers c and χ.
  • Tensor-product constructions: The resulting generator matrices satisfy GXGZ^T = 0 because the permutation matrices commute.
  • Tensor-product constructions: Setting c = 1 and χ = 1 recovers hypergraph-product codes, while scalar block matrices recover generalized bicycle codes.
  • Tensor-product constructions: For c > 1, the codes can be viewed as reduced hypergraph codes because the identity blocks are reduced by a factor of 1/c.

B. CSS hyperbicycle codes: dimension

The dimension analysis classifies quasicyclic constituent codes by circulant symmetry and uses those classes to count independent generator rows and encoded qubits.

  • Dimension analysis: The dimensions k_i and distances d_i of constituent codes provide the parameters needed to characterize the quantum hyperbicycle code.
  • Dimension analysis: The constituent binary codes are quasicyclic, with cycle length c determined by the cyclic permutation matrices.
  • Symmetry classification: Vectors are classified by symmetry classes associated with binary factors p(x) of x^c − 1, including a no-symmetry class.
  • Symmetry classification: A vector shared by the relevant constituent codes must belong to the same symmetry class for both codes.
  • Rank counting: Lemma 3 counts the linearly independent rows of the generator matrices by summing contributions from compatible polynomial symmetry classes.
  • Encoded dimension: The encoded-qubit formula depends on the constituent dimensions, factor dimensions k(p), and factors p_l(x) of x^c − 1.
  • Encoded dimension: A positive encoded dimension requires at least one constituent binary code defined by the parity-check matrices to be non-empty.

C. CSS hyperbicycle codes: general distance bounds

The section establishes lower and upper bounds on hyperbicycle-code minimum distance using symmetry classes and subset distances. The bounds are derived by relating nontrivial logical operators to classical-code structures.

  • Theorem 5 gives a lower bound on the minimum distance for codes generated by Eq. (19).
  • Subset distances d_i^(p) characterize classical-code vectors with the exact symmetry of p(x).
  • The upper-bound proof constructs nontrivial logical vectors from classical codewords associated with the relevant symmetry class.
  • Every term contributing nonzero encoded-qubit dimension K also supplies an upper bound on the quantum minimum distance.

D. Codes with finite rate and distance scaling as square root of block length

The construction yields quantum LDPC families with finite rate and minimum distance proportional to the square root of block length. These families arise from finite-rate classical LDPC codes with finite relative distance.

  • D ∝ √N for finite-rate (v, h+v)-limited quantum LDPC families derived from finite-rate classical LDPC codes.
  • Random (h,v)-regular classical LDPC parity-check matrices provide the starting point, with h < v.
  • Removing dependent rows produces a full-rank parity-check matrix a_1 used in the hyperbicycle construction.
  • The classical-code rate satisfies R_c = k_c/n_c ≥ 1−h/v, and its relative distance is expected to remain finite at large block length.

E. Codes with repeated codewords

Repeated-codeword constructions provide exact or bounded distance formulas for important hyperbicycle families. Repetition can improve distance-related behavior while introducing a factor-of-c lower-bound issue for general vectors.

  • For the CSS repeated-code family, N = 2cn_1n_2, K = 2k_1k_2, and ⌊d/c⌋ ≤ D ≤ d.
  • For fully symmetric vectors, nontrivial sublattice weights are either zero or at least d, yielding the exact distance D = d under the stated conditions.
  • When c = 2, the CSS code has parameters [[4n_1n_2, 2k_1k_2, d]] with d = min(d_1,d_2,e d_1,e d_2).
  • For even c, the distance satisfies (2/c)d ≤ D ≤ d, where d = min(d_1,d_2,e d_1,e d_2).
  • Using two small cyclic codes yields hypergraph-product, repeated even-c, and large-code hypergraph-product constructions with different block lengths and distance bounds.
  • A [[294,18,4 ≤ D ≤ 12]] example with c = 3 exhibits tripled logical operators and repeated overlap structure.

F. Planar qubit layout of hyperbicycle codes and encoding

Hyperbicycle codes admit planar block layouts built from two sublattices with shifted periodic boundaries. In selected CSS cases, logical operators retain a line-like form and can support encoding through a physical-to-logical correspondence.

  • The planar construction uses rectangular sublattices stitched with a boundary shift χ across c blocks.
  • For c = 1, logical operators can be represented by vertical and horizontal lines in shaded regions containing k_1k̃_2 + k̃_1k_2 logical qubits.
  • The toric example [[90,2,9]] uses c = 5 and χ = 3, producing shifted periodic boundaries and the family [[2n^2c,2,nχ]].
  • For c > 1, logical operators generally have complicated structure, although a specific odd-c CSS case recovers the c = 1 form.
  • A CSS [[900,50,14]] and a non-CSS [[289,81,5]] example illustrate distinct stabilizer layouts, while repeated logical operators can aid encoding.

G. Codes from two circulant matrices

Using two circulant matrices, the hyperbicycle construction produces CSS codes whose parameters depend on the choice of χ, with χ ≠ 1 often increasing distance and sometimes increasing rate relative to corresponding hypergraph-product codes.

  • Distance effects of χ: For χ ≠ 1, rearranging the toric-code surface changes the boundary geometry and can increase the code distance.For toric codes, the construction gives D = χd/c, and numerical examples often reach the upper distance bound.
  • Distance effects of χ: The rotated toric family has parameters [[2n^2c, 2, nχ]], including [[40, 2, 6]] and [[90, 2, 9]] for n = 2 and n = 3, respectively.The same family also yields [[104, 2, 10]] and [[234, 2, 15]] for larger values of t.
  • Examples: χ = 3 gives [[180, 16, 8]], whereas χ = 1 gives [[180, 16, 6]] for the same underlying classical cyclic code.Thus, changing χ increases the listed distance without changing the block length or number of encoded qubits in this example.
  • Rate comparison: In many cases, the code rate increases relative to the hypergraph-product code built from the same cyclic codes.The construction can also apply when the corresponding construction from the small cyclic codes is unavailable.

H. Non-CSS versions of hyperbicycle codes

The non-CSS construction maps suitable CSS hyperbicycle codes to non-CSS codes, often reducing the number of physical and encoded qubits while retaining related distance bounds.

  • Construction: When H1 = eH1 and H2 = eH2, the CSS construction can be mapped to non-CSS hyperbicycle codes that often have the same distance with half as many encoded and physical qubits.The stated special case includes χ = 1 with symmetric H1 and H2.
  • Distance bounds: For the non-CSS construction, the distance is bounded by D ≥ ⌊d/c⌋, where d = min(d1, d2).The bound follows because every codeword must have support on at least one sublattice with weight exceeding ⌊d/c⌋.
  • Distance bounds: Under the conditions of Theorem 11, the non-CSS code has parameters [[n1n2c, k1k2, ≥(2/c)d]], with d = min(d1, d2).The theorem assumes even c and distance-at-least-two conditions for the associated binary codes.
  • Distance bounds: The upper distance bound from Theorem 6 also applies to non-CSS hyperbicycle codes.This remains true because the bound depends only on one sublattice.
  • Construction: For χ = 1, palindromic check polynomials can be used to construct the symmetric circulant matrices required by the mapping.The polynomial condition is paired with a parity condition on c − deg h(x).

V. CONCLUSIONS

The paper presents hyperbicycle codes as a broad LDPC-code family with explicit distance bounds, finite-rate families, and square-root distance scaling. Their cyclic-code and translationally invariant structure is especially useful for relatively small block lengths and implementation-oriented designs.

  • Conclusions: Hyperbicycle codes include subclasses of the best known LDPC codes and provide explicit upper and lower bounds on code distance.The construction also yields new finite-rate LDPC families with distances scaling as a square root of block length.
  • Conclusions: The construction can use well-studied classical cyclic codes, producing good parameters up to limited but relatively large block lengths.The authors note that cyclic codes with asymptotic rates below one can have poor asymptotic parameters.
  • Conclusions: The planar layout has translationally invariant stabilizer generators, which may simplify implementation.This implementation relevance is stated as an advantage of the cyclic-code-based construction.
  • Scope: The discussed quantum LDPC codes have been shown to possess a finite noise threshold.The conclusion passage states the threshold result without specifying a numerical value.
Loading 1212.6703v2…