High dimensional lossless cubical complexes enable better quantum error correction codes
Good Quantum Locally Testable Codes from Lossless Cubical Complexes
Computational ComplexityInformation Theory
Summary
Quantum computers need special codes to protect information from errors. This paper studies how certain complex geometric structures, called lossless cubical complexes, could help build better quantum error-correcting codes that are easier to check and fix. The authors prove a key connection between local properties of these complexes and their global behavior, which could make these improved codes possible if such complexes exist. Their work opens a new direction for creating reliable quantum computing tools.
What this means in practice
- •For quantum hardware developers: Design quantum error correction protocols that might use high-dimensional expansion structures for better fault tolerance.
- •For coding theory engineers: Explore new classes of locally testable quantum codes based on lossless cubical complexes to improve code efficiency and verification.
A theory result. No direct application yet.
Authors
Itay Cohen, Itai Leigh, Assaf Reiner, Amnon Ta-Shma, Elad Tzalik
Abstract
Sipser and Spielman constructed LDPC codes from either bipartite \emph{spectral} expanders or one-sided \emph{lossless} expanders. In higher dimensions, \emph{spectral} expansion similarly played a central role in the constructions of asymptotically good classical LTCs and qLDPC codes by Dinur, Evra, Livne, Lubotzky, and Mozes and by Panteleev and Kalachev. Alternatively, Lin and Hsieh constructed classical LTCs and qLDPC codes from two-dimensional \emph{lossless} cubical complexes. In this work we develop the higher-dimensional \emph{lossless} approach. We do not construct the required high-dimensional lossless cubical complexes; rather, we investigate what their existence would imply. We associate with a high-dimensional cubical complex a \emph{level chain complex}, whose chain groups are supported on the level sets of the Boolean cube rather than on its cells. Our main technical contribution is a clean local-to-global theorem for this structure: suitable one-dimensional lossless expansion in the directional graphs implies small-set coboundary expansion of the global level complex. As a consequence, sufficiently imbalanced, two-sided lossless four-dimensional cubical complexes give rise to asymptotically good quantum locally testable codes. We expect the local-to-global principle developed here to have further applications.