Entanglement-assisted quantum quasicyclic low-density parity-check codes

Min-Hsiu Hsieh, Todd A. Brun, Igor DevetakPhysical 2009 · DOI · arXiv

Abstract

We investigate the construction of quantum low-density parity-check (LDPC) codes from classical quasicyclic (QC) LDPC codes with girth greater than or equal to 6. We have shown that the classical codes in the generalized Calderbank-Skor-Steane construction do not need to satisfy the dual-containing property as long as preshared entanglement is available to both sender and receiver. We can use this to avoid the many four cycles which typically arise in dual-containing LDPC codes. The advantage of such quantum codes comes from the use of efficient decoding algorithms such as sum-product algorithm (SPA). It is well known that in the SPA, cycles of length 4 make successive decoding iterations highly correlated and hence limit the decoding performance. We show the principle of constructing quantum QC-LDPC codes which require only small amounts of initial shared entanglement.

Introduction

In classical communications, Low-Density Parity-Check (LDPC) codes are highly effective, performing close to the Shannon limit using the iterative Sum-Product Algorithm (SPA). However, adapting these to the quantum domain is challenging. Standard quantum codes, typically constructed via the Calderbank-Shor-Steane (CSS) method, require a "dual-containing" property where the parity-check matrix $H$ must satisfy $HH^T = 0$.

This algebraic constraint often necessitates the presence of many 4-cycles (short loops in the decoding graph). In SPA decoding, these short cycles cause iterative messages to become highly correlated, leading to poor error-correction performance. This paper proposes a method to bypass these constraints using the Entanglement-Assisted (EA) formalism.

Methodology: Bypassing the Dual-Containing Constraint

The researchers utilize the Entanglement-Assisted Quantum Error-Correcting Code (EAQECC) framework to decouple the code's graphical properties from its algebraic requirements.

  1. Relaxing Constraints: In the EA framework, the $HH^T = 0$ rule is no longer mandatory. Any classical linear code can be transformed into a quantum code, provided the sender and receiver share a specific number of entangled bits (ebits), $c = \text{rank}(HH^T)$.
  2. Quasi-Cyclic (QC) Construction: The focus is on QC-LDPC codes built from circulant matrices. These are hardware-friendly and mathematically tractable.
  3. Girth Optimization: By relaxing the dual-containing requirement, the authors can design codes with a girth of at least 6, effectively eliminating performance-degrading 4-cycles.
  4. Rank Minimization: To minimize the "entanglement tax," the paper proposes methods to keep the rank of $HH^T$ low while maintaining high girth.

Key Results and Performance

The performance of these new codes was evaluated using simulations over a depolarizing channel. The study compared two new entanglement-assisted codes (Ex1 and Ex2, $n=128$ qubits, girth 6, requiring 18 ebits) against standard benchmarks: the MacKay dual-containing code (known for 4-cycles) and the Ex-HI code (a dual-containing QC-LDPC code with girth 6).

Block Error Rate performance comparison between entanglement-assisted QC-LDPC codes (Ex1, Ex2) and standard quantum codes (Ex-MacKay, Ex-HI).

As shown in Figure 1, the EA-QC-LDPC codes (Ex1 and Ex2) significantly outperform both the MacKay benchmark and the Ex-HI code. The poor performance of the MacKay code is directly linked to its high density of 4-cycles, which cripples the SPA decoder. Even though Ex-HI has a girth of 6, the constraints imposed by the dual-containing property limit its effectiveness compared to the more flexible EA constructions.

Discussion and Insights

The core insight is that entanglement serves as a powerful design tool, allowing researchers to prioritize the graphical properties of a code (like girth) over rigid algebraic constraints. By removing the dual-containing barrier, decades of progress in classical LDPC design can be directly applied to quantum error correction.

While the "entanglement cost" (e.g., 18 ebits for a 128-qubit code) is a factor, the resulting jump in reliability and the ability to maintain competitive net rates make EA-QC-LDPC codes a promising avenue for practical quantum computing.

Future Work

Future research could explore "quantum-aware" decoding algorithms that account for quantum degeneracy, which might further improve performance beyond the classically-inspired SPA. Additionally, developing more systematic algorithms for finding optimal circulant matrices for various code lengths remains an open challenge.

Summary updated

Abstract

We investigate the construction of quantum low-density parity-check (LDPC) codes from classical quasicyclic (QC) LDPC codes with girth greater than or equal to 6. We have shown that the classical codes in the generalized Calderbank-Skor-Steane construction do not need to satisfy the dual-containing property as long as preshared entanglement is available to both sender and receiver. We can use this to avoid the many four cycles which typically arise in dual-containing LDPC codes. The advantage of such quantum codes comes from the use of efficient decoding algorithms such as sum-product algorithm (SPA). It is well known that in the SPA, cycles of length 4 make successive decoding iterations highly correlated and hence limit the decoding performance. We show the principle of constructing quantum QC-LDPC codes which require only small amounts of initial shared entanglement.
BibTeX
@inproceedings{hsieh2009entanglement,
  author = {Min-Hsiu Hsieh and Todd A. Brun and Igor Devetak},
  title = {{Entanglement-assisted quantum quasicyclic low-density parity-check codes}},
  booktitle = {Physical},
  year = {2009},
  doi = {10.1103/physreva.79.032340},
}
Figure