Quantum LDPC codes reach near optimal error correction limits
Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound
Information Theory
Summary
Quantum computers need special error-correcting codes to protect their fragile data. This paper shows that there are families of these quantum codes, called QLDPC codes, that can get very close to the best possible theoretical limits for correcting errors. The authors create these codes using a new construction that carefully manages tricky properties called degeneracy, allowing them to perform well in important quantum noise situations. Their methods combine existing good codes with a process to improve distance and add randomness in a clever way.
What this means in practice
- •For quantum hardware engineers: Implement error correction that approaches quantum channel capacity for more reliable quantum communication channels.
- •For quantum network designers: Design quantum communication protocols with error-correcting codes that perform well under realistic noise like erasures and depolarizing errors.
Authors
Tushant Mittal, Shashank Srivastava, Madhur Tulsiani, Mary Wootters
Abstract
We show that for any $R,ε>0$ and any prime $p\geq 2$, there exists an infinite family of $p$-ary quantum low-density parity-check (QLDPC) codes, rate $R$, checks of weight $O_ε(1)$, and normalized distance at least $δ_{\mathrm{GV}}(p,R)-ε$. Here, $δ_{\mathrm{GV}}(p,R)$ denotes the quantum Gilbert-Varshamov (GV) bound for $p$-ary stabilizer codes. In fact, we construct an ensemble of such QLDPC codes, such that a random code from this ensemble is close to the GV bound with high probability. Moreover, this ensemble matches the performance of random stabilizer codes on several quantum channels. Specifically, it approaches the quantum capacity of the erasure channel and the hashing bound for memoryless Pauli channels, including the depolarizing channel. A significant challenge in working with QLDPC codes is that they are necessarily \emph{degenerate}, i.e., contain many low-weight stabilizers. A key contribution of our work is a construction of QLDPC codes with quantitative control on their degeneracy. These codes are obtained by combining known constructions of asymptotically good QLDPC codes with the expander-based distance amplification procedure of Alon, Edmonds, and Luby [FOCS'95]. Our random ensemble is constructed by starting with these low-degeneracy QLDPC codes near the quantum Singleton bound and concatenating each coordinate with a random inner code. This can be viewed as a quantum analogue of Thommesen's construction, and as an LDPC version of a result of Ouyang, with an appropriately designed outer code.