PaperlayerView exact revision on arXiv

Source-linked AI summary

Degenerate Quantum LDPC Codes With Good Finite Length Performance

Pavel Panteleev, Gleb Kalachev

arXiv:1904.02703v3quant-phcs.IT

TL;DR

The paper asks how medium-length degenerate QLDPC codes perform in practice and develops BP-OSD decoding plus new code families to address this question. It finds strong performance across several code classes, including a constructed code that surpasses a larger surface code decoded near-optimally.

  • Problem

    The practical error-correcting performance of degenerate QLDPC codes at relatively small lengths is largely unexplored, and their competitiveness with topological codes is unclear.

  • Method

    The paper combines OSD-like post-processing for BP decoding with constructions based on generalized bicycle and generalized hypergraph product QLDPC codes.

  • Results

    BP-OSD improves decoding on many degenerate QLDPC codes, and some constructed codes outperform a relatively large surface code under a near-optimal decoder.

  • Takeaways & Limitations

    BP-OSD and the proposed code constructions provide practical finite-length QLDPC performance that can exceed the reported surface-code comparison.

  • Takeaways & Limitations

    The study considers the depolarizing channel, and the proposed code family lacks a nontrivial general lower bound on minimum distance.

Abstract

from arXiv · show

We study the performance of medium-length quantum LDPC (QLDPC) codes in the depolarizing channel. Only degenerate codes with the maximal stabilizer weight much smaller than their minimum distance are considered. It is shown that with the help of OSD-like post-processing the performance of the standard belief propagation (BP) decoder on many QLDPC codes can be improved by several orders of magnitude. Using this new BP-OSD decoder we study the performance of several known classes of degenerate QLDPC codes including hypergraph product codes, hyperbicycle codes, homological product codes, and Haah's cubic codes. We also construct several interesting examples of short generalized bicycle codes. Some of them have an additional property that their syndromes are protected by small BCH codes, which may be useful for the fault-tolerant syndrome measurement. We also propose a new large family of QLDPC codes that contains the class of hypergraph product codes, where one of the used parity-check matrices is square. It is shown that in some cases such codes have better performance than hypergraph product codes. Finally, we demonstrate that the performance of the proposed BP-OSD decoder for some of the constructed codes is better than for a relatively large surface code decoded by a near-optimal decoder.

1 Introduction

The paper targets the poorly understood practical performance of medium-length degenerate QLDPC codes and addresses this through BP-OSD decoding and new code constructions. It reports strong decoding results across established and newly proposed code families, including performance exceeding that of a larger surface code under near-optimal decoding.

  • Motivation: Medium-length degenerate QLDPC codes have good asymptotic parameters, but their practical performance below n < 1000 and competitiveness with topological codes remain unclear.The paper identifies finite-length construction quality and decoder performance as the main difficulties.
  • Method: The proposed BP-OSD decoder enhances standard BP with OSD-like post-processing when BP fails to find a recovery operator with the correct syndrome.The method is presented for binary and non-binary QLDPC decoding using a binary parity-check representation.
  • Code constructions: New generalized bicycle and generalized hypergraph product code families are constructed, including codes with BCH-protected syndromes and potentially improved performance over hypergraph product codes.The GHP family contains generalized bicycle codes and hypergraph product codes when one product matrix is square.
  • Evaluation: The decoder is evaluated on hypergraph product, hyperbicycle, homological product, and Haah’s cubic codes, alongside newly constructed codes and alternative BP modifications.The comparisons include random perturbation, enhanced feedback, and matrix augmentation.
  • Results: The [[1270, 28]] GHP code performs significantly better under BP-OSD than the compared BP modifications and outperforms the [[1201, 1, 25]] surface code under near-optimal MPS decoding.The paper also reports good BP-OSD performance for one Haah’s cubic code.

2 Basic facts and definitions

This section introduces classical and quantum code representations, stabilizer and CSS codes, LDPC sparsity, Tanner graphs, and belief propagation decoding. It also explains degeneracy, commutativity, code distance, and how graph cycles affect BP performance.

  • Classical codes: A classical linear [n, k]_q code is a k-dimensional subspace, with rate k/n and minimum distance defined by the smallest nonzero codeword weight.Such codes can be represented by a generator matrix or a parity-check matrix.
  • Binary and CSS representations: Binary representations map Pauli operators to vectors (x|z), while the parity-check matrix H records stabilizer generators and must satisfy a commutativity condition.For CSS codes, H is represented using separate HX and HZ matrices with n columns.
  • Quantum stabilizer codes: A quantum stabilizer [[n, k, d]] code is a 2^k-dimensional subspace defined as the common +1 eigenspace of commuting stabilizer generators.Its minimum distance is the smallest weight of a non-stabilizer Pauli operator commuting with every stabilizer.
  • Degeneracy: A Pauli error is degenerate when it acts trivially on every code state, whereas the minimum distance measures the smallest weight of a non-degenerate commuting Pauli error.Stabilizer-group elements are precisely the degenerate Pauli errors.
  • LDPC decoding: LDPC codes use sparse parity-check matrices, and their Tanner graphs connect variable nodes to check nodes wherever the matrix has a one.Belief propagation iteratively updates bitwise probability distributions, while short cycles such as 4-cycles degrade decoder performance.
  • Quantum LDPC codes: A QLDPC code is a stabilizer code with a sparse parity-check matrix, whose Tanner graph has qubit nodes and stabilizer-generator nodes.This extends the classical LDPC graph representation to quantum stabilizer codes.

3 OSD-like post-processing for BP

The paper develops syndrome-based OSD post-processing for BP decoding of QLDPC codes, using reliability-ranked information sets and testing nearby error patterns. The method can substantially improve decoding performance, often with order-0 complexity O(n^3).

  • Syndrome OSD: The syndrome OSD algorithm post-processes BP output when the estimated error fails to satisfy the observed syndrome.It uses syndrome decoding to search for a recovery error consistent with the parity-check equations.
  • Information sets: Reliability estimates rank positions so the decoder can select a most reliable information set and recover an error vector from the syndrome.A greedy algorithm finds the corresponding least-reliable basis of the parity-check matrix.
  • OSD order: Order-w OSD examines 2^w candidate error vectors formed by flipping up to w least reliable positions, then selects the minimum-weight candidate.For depolarizing noise, the weight is the weight of the corresponding Pauli operator.
  • Performance: In many QLDPC cases, OSD-0 already radically improves BP decoding while requiring computational cost O(n^3).Higher order can help particular codes, but its impact is often small across the authors’ experiments.
  • Performance: For code B1, BP-OSD improves WER over BP by up to 5 orders of magnitude, whereas the gain is small for code A1.The authors attribute A1’s small gain to its high parity-check column weight, which makes BP effective without post-processing.
  • Performance: The 8-limited Haah’s [[1024,30]] code performs well with BP-OSD, and long runs found no non-degenerate codewords below weight 32.The paper presents this as a demonstration on the depolarizing channel and as suggestive evidence about minimum distance.

4 New generalized bicycle codes

The paper develops generalized bicycle codes through commuting binary circulant matrices and polynomial representations, derives dimension and syndrome-code formulas, and constructs short examples with competitive performance.

  • Construction: Generalized bicycle codes use binary circulant matrices A and B, whose commutation guarantees the CSS commutativity condition.Bicycle codes are the special case B = A^T.
  • Construction: The circulant-matrix representation identifies matrices with polynomials in F2[x]/(x^ℓ−1), turning matrix products into cyclic convolution.This representation also supports matrix-vector products through cyclic convolution.
  • Dimension formula: The generalized bicycle [[2ℓ, k]] code dimension is determined by g(x) = gcd(a(x), b(x), x^ℓ−1) through the ranks of HX and HZ.The proof establishes rk HX = rk HZ = n − deg g(x) and applies the CSS dimension formula.
  • Code design: High-dimensional codes can be designed by selecting factors g(x) of x^ℓ−1 and finding low-weight polynomial codewords a(x) and b(x) in the resulting cyclic syndrome code.The paper lists exhaustive and randomized searches, followed by performance simulation.
  • Syndrome protection: Cyclic syndrome codes generated by g(x) and g*(x) can protect the syndromes of HX and HZ, while constraining the polynomial weights by their minimum distance d.The paper notes that this protection may improve reliability under faulty syndrome measurement.
  • Comparison with other codes: The 10-limited [[254, 28]] generalized bicycle code performs almost like the 10-limited [[7938, 578, 16]] hypergraph product code and also performs similarly under classical BP without OSD.Both codes have no 4-cycles in HX and HZ and the same stabilizer weight; the generalized bicycle code has syndrome-code minimum distance 5.
  • Comparison with other codes: The new 8-limited generalized bicycle codes have performance similar to the 8-limited [[49, 1, 9]] homological product code while having higher rates.The comparison uses BP with OSD-like post-processing.
  • Comparison with other codes: The generalized bicycle [[180, 10, d]] code, 15 ⩽ d ⩽ 18, performs similarly to the hyperbicycle [[900, 50, 14]] code with the same stabilizer weight and one-fifth its length.The comparison uses the BP-OSD-10 decoder.

5 Generalization of HP codes

The paper generalizes hypergraph product codes to a broader family based on a square parity-check matrix, encompassing HP and generalized bicycle constructions. QC specializations yield explicit length formulas and favorable simulated performance for some codes.

  • Generalized construction: The generalized hypergraph product construction extends HP codes when one parity-check matrix is square.The family also contains generalized bicycle codes.
  • QC specialization: Commuting circulant matrices produce quasi-cyclic GHP codes represented by block matrices over circulants.The polynomial-matrix representation is used for sparse random QC examples.
  • Code parameters: The CSS code C(A, b) has length N = (m + n)ℓ.
  • Relation to HP codes: Taking R = {0, I} recovers a hypergraph product code from the block matrix A and the binary matrix b.
  • Performance: The [[882,24]] and [[1270,28]] QC GHP codes show no error floor down to WER = 10^-10 under BP-OSD-0.The comparison includes a [[1201,1,25]] surface code decoded with an MPS-based decoder.

6 Conclusion

The conclusion highlights improved BP decoding through OSD-like post-processing, strong performance from newly constructed codes, and a new CSS-code family with unresolved general distance guarantees.

  • OSD-like post-processing improves BP performance on some codes over the modifications known to the authors.
  • New generalized bicycle codes show very good performance compared with known codes having similar parameters.
  • The new CSS-code ansatz admits dimension estimates in special cases but lacks a nontrivial general lower bound on minimum distance.The paper identifies finding such a bound as an open problem.
  • One constructed code outperforms a relatively large surface code of similar length despite the surface code using a near-optimal decoder.

B Matrices used for simulations

The simulation set comprises generalized bicycle, generalized hypergraph product, hypergraph product, Haah cubic, and hyperbicycle codes, specified primarily through quasi-cyclic matrices and listed code parameters.

  • Matrix representation: All simulated GB and GHP codes use HX = [A, B] and HZ = [B^T, A^T] with quasi-cyclic A and B.The matrices are specified in polynomial form over the circulant ring.
  • Generalized bicycle codes: GB examples use scalar polynomial matrices A = (a(x)) and B = (b(x)) with a specified circulant size ℓ.
  • Generalized hypergraph product codes: GHP examples use diagonal B = b(x)I_n, including a [[882,48,16]] code with column weights 3 and 5 and row weight 8.
  • Hypergraph product codes: HP simulations include a [[1922,50,16]] code with (3,6)-regular parity-check matrices and a [[7938,578,16]] code with (5,10)-regular matrices.
  • Other code families: The dataset also includes Haah’s [[1024,30,d]] cubic code with 13 ≤ d ≤ 32 and a [[900,50,14]] hyperbicycle code.

F. Homological product (HMP) codes. We used

The homological-product-code examples consist of one randomly constructed [[49,1,9]] code, alongside a table summarizing code parameters.

  • The simulations include one randomly constructed [[49,1,9]] homological product code.
  • Table 1 is presented as a summary of code parameters.

C Additional Simulations

Additional simulations show strong BP-OSD-0 performance on short generalized bicycle codes and a cyclic non-CSS code, including a threshold close to that of surface codes and a multi-order-of-magnitude gain from OSD-0 post-processing.

  • Simulation scope: The additional results concern BP-OSD decoding on the depolarizing channel.They include simulations for generalized bicycle codes and a cyclic non-CSS code.
  • Generalized bicycle codes: 15% threshold for five 6-limited generalized bicycle codes is close to the 18% threshold of corresponding 4-limited surface codes.The comparison is made under BP-OSD-0 on the depolarizing channel.
  • Generalized bicycle codes: The tested 6-limited generalized bicycle codes have parameters [[2s+1 −2, 2s]], with s ∈ N.Their syndrome codes are cyclic Hamming [2s −1, s, 3] codes defined by irreducible degree-s polynomials.
  • Cyclic non-CSS code: OSD-0 post-processing provides at least three orders of magnitude WER gain for the 5-limited cyclic non-CSS [[126,2,12]] code.The code uses 126 × 126 circulant matrices defined by 1 + x^71 + x^55 and 1 + x^40 + x^86.
Loading 1904.02703v3…