Full-rank lossless expanders yield better quantum error-correcting codes
Full-Rank Constructions of Explicit Lossless Expanders and Good Small-Set qLTCs
Computational ComplexityData Structures and Algorithms
Summary
Building reliable quantum computers requires error-correcting codes that can detect and fix mistakes. The authors construct special mathematical graphs whose connections have a property called full rank, which helps improve the design of these codes. Their approach leads to quantum codes that perform well and last longer while keeping error checks effective on small parts of the data. This work also provides new kinds of graphs that may interest mathematicians working in network design. The resulting quantum memories show better predicted stability at low temperatures than previous constructions.
What this means in practice
- •For quantum hardware engineers: Use full-rank lossless expander graphs to design quantum LDPC codes with improved error-checking properties for more stable quantum memories.
- •For cryptography system designers: Explore new Ramanujan Cayley graphs on 2-groups as network topologies in secure communication and error-resilient coding schemes.
Authors
Yali Aharon-Holzman, Michael Ilan, Assaf Reiner, Amnon Ta-Shma
Abstract
We construct explicit two-sided lossless expanders whose binary adjacency matrices have full rank, and use them to obtain explicit asymptotically good quantum LDPC codes whose specified X- and Z-check matrices have full row rank and satisfy small-set soundness, or confinement, on a linear range. Our lossless expanders are a variant of those of Hsieh, Lubotzky, Mohanty, Reiner, and Zhang, with a free action of a finite 2-group. Under such an action, injectivity and surjectivity of the adjacency matrix are detected on a fixed-size matrix indexed by vertex orbits. Adding a sparse factor to the gadget at the middle vertices of a single type then enforces full rank, with a controlled loss in expansion. To obtain the 2-group action, we observe that reducing the generators of the Lubotzky-Phillips-Sarnak Ramanujan graphs modulo powers of 2, instead of modulo an odd prime, gives Ramanujan Cayley graphs on finite 2-groups. This construction may be of independent interest. Plugging two such expanders into the balanced product of Lin and Hsieh gives the quantum codes, since full rank of the input graphs is inherited by the check matrices. Our construction supplies the code family sought by Hong, Guo, and Lucas. Applying their analysis, within their framework and under their dynamical assumptions, gives quantum memories whose free-energy density is analytic at every positive temperature and whose guaranteed lifetime is $exp(Ω(N))$ at sufficiently low fixed positive temperature, where N is the blocklength. This improves the previously guaranteed stretched-exponential timescale.