Single-shot decoding of good quantum LDPC codes

Abstract

Quantum Tanner codes constitute a family of quantum low-density parity-check (LDPC) codes with good parameters, i.e., constant encoding rate and relative distance. In this article, we prove that quantum Tanner codes also facilitate single-shot quantum error correction (QEC) of adversarial noise, where one measurement round (consisting of constant-weight parity checks) suffices to perform reliable QEC even in the presence of measurement errors. We establish this result for both the sequential and parallel decoding algorithms introduced by Leverrier and Zémor. Furthermore, we show that in order to suppress errors over multiple repeated rounds of QEC, it suffices to run the parallel decoding algorithm for constant time in each round. Combined with good code parameters, the resulting constant-time overhead of QEC and robustness to (possibly time-correlated) adversarial noise make quantum Tanner codes alluring from the perspective of quantum fault-tolerant protocols.

36 pages, 3 figures, accepted in Communications in Mathematical Physics

References in corpus (10)

• Topological Quantum Distillation
• Quantum Low-Density Parity-Check Codes
• A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes
• Exact Topological Quantum Order in D=3 and Beyond: Branyons and Brane-Net Condensates
• Low-overhead fault-tolerant quantum computing using long-range connectivity
• Constant-overhead quantum error correction with thin planar connectivity
• NLTS Hamiltonians from good quantum codes
• Quantifying nonlocality: how outperforming local quantum codes is expensive
• Ability of stabilizer quantum error correction to protect itself from its own imperfection
• Lifting topological codes: Three-dimensional subsystem codes from two-dimensional anyon models

Cited by in corpus (8)

• Low-Overhead Transversal Fault Tolerance for Universal Quantum Computation
• Experiments with the 4D Surface Code on a QCCD Quantum Computer
• Quantum memory at nonzero temperature in a thermodynamically trivial system
• Stabilizer Entanglement Distillation and Efficient Fault-Tolerant Encoders
• Single-shot and measurement-based quantum error correction via fault complexes
• Single-shot preparation of hypergraph product codes via dimension jump
• Fault-tolerant quantum computation with constant overhead for general noise
• Almost Linear Decoder for Optimal Geometrically Local Quantum Codes