Viderman's Algorithm for Quantum LDPC Codes
summary
New Viderman-style decoder for hypergraph-product quantum LDPC codes gives a linear-time erasure conversion that outputs an envelope L guaranteed to contain all z-errors for errors up to a constant fraction of the code distance (distance is Θ(√n), rate is linear). It inspects a linear collection of local small subsets (subsets of each local view), scores them by a unique-neighborhood score, and grows L when the score falls below a threshold; performance depends on underlying vertex expansion (ε small, e.g. ~1/20) and degree ratio r = Δv/Δc. Envelope finding runs in linear time but full erasure correction is not yet linear.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:14Classical LDPC codes
- 3:45Vimman's decoding algorithm
- 6:43Hypergraph product codes
- 10:05Algorithm goals and overview
- 11:57High-level algorithm steps
- 16:04Score function and intuition
- 20:55Proof insights
- 25:11Decoding radius analysis
- 29:25Summary and open questions
- 30:23Q&A session
related talks
01h 03mQuantum LDPC Codes with Transversal CCZ Gates
34mExplicit Abelian Lifts and Quantum LDPC Codes
32mTowards local testability for quantum coding
44mNLTS Hamiltonians (and Strongly-Explicit SoS Lower Bounds) from Low-Rate Quantum LDPC Codes
01h 03mApproaching the Quantum Singleton Bound with Approximate Error Correction
49mCircuit lower bounds for low-energy states of quantum code Hamiltonians
39mExpansion of Higher-Dimensional Cubical Complexes With Application To Good ...
59mDawn in the age of quantum fault tolerance