Decoders for Good Quantum LDPC Codes
summary
Constructs linear-time and parallel decoders for quantum Tanner LDPC codes built on a left-right Cayley complex and local classical codes, proving they correct adversarial errors up to linear weight and succeed with probability exponentially close to 1 under i.i.d. noise. Uses a potential-based / mismatch-decomposition greedy algorithm tied to expansion properties; sequential decoder is linear-time, parallel decoder runs in constant rounds and gives single-shot (sequential and parallel) guarantees with residual error bounded by alpha, beta parameters, enabling constant-time decoding during computation.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 2:11Quantum LDPC codes overview
- 5:47Good code constructions
- 7:58Decoding problem setup
- 11:11Quantum Tanner codes
- 14:52Potential-based decoder
- 17:46Decoding results
- 19:00Single-shot QEC intro
- 24:05Mismatch-decomposition decoder
- 27:29Single-shot decoder theorems
- 28:33Stochastic setting and noise
- 30:01Constant-time overhead
- 31:47Summary and future
- 33:32Q&A
related talks
01h 03mQuantum LDPC Codes with Transversal CCZ Gates
44mNLTS Hamiltonians (and Strongly-Explicit SoS Lower Bounds) from Low-Rate Quantum LDPC Codes
32mTowards local testability for quantum coding
39mExpansion of Higher-Dimensional Cubical Complexes With Application To Good ...
34mExplicit Abelian Lifts and Quantum LDPC Codes
01h 03mApproaching the Quantum Singleton Bound with Approximate Error Correction
03mQuantum Algorithms, Complexity, and Fault Tolerance
18mConcurrent Quantum Separation Logic for Fine-Grained Parallelism