The Need for Structure in Quantum LDPC Codes
arXiv:1610.07478 · doi:10.1109/TIT.2019.2952366
Abstract
Existence of quantum low-density parity-check (LDPC) codes whose minimal distance scales linearly with the number of qubits is a major open problem in quantum information. Its practical interest stems from the need to protect information in a future quantum computer, and its theoretical appeal relates to a deep "global-to-local" notion in quantum mechanics: whether we can constrain long-range entanglement using local checks. Given the inability of lattice-based quantum LDPC codes to achieve linear distance, research has recently shifted to the other extreme end of topologies, so called high-dimensional expanders. In this work we show that trying to leverage the mere "random-like" property of these expanders to find good quantum codes may be futile: quantum CSS codes of quits built from -complexes that are -far from perfectly random, in a well-known sense called discrepancy, have a small minimal distance. Quantum codes aside, our work places a first upper-bound on the systole of high-dimensional expanders with small discrepancy, and a lower-bound on the discrepancy of skeletons of Ramanujan complexes due to Lubotzky.
References in corpus (9)
- Fault-tolerant quantum computation by anyons
- Good Quantum Error-Correcting Codes Exist
- Multiple Particle Interference and Quantum Error Correction
- Sparse Graph Codes for Quantum Error-Correction
- A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes
- Homological Error Correction: Classical and Quantum Codes
- Local Hamiltonians Whose Ground States are Hard to Approximate
- A Class of Quantum LDPC Codes Constructed From Finite Geometries
- Product-state Approximations to Quantum Ground States