Adam Wills
Massachusetts Institute of Technology
Hon Hai Research Institute
arXiv:2603.04543 · FOCS 2026
Linear-Time
Encodable and
Decodable Quantum
Error-Correcting Codes
Min-Hsiu Hsieh
Hon Hai Research Institute2026 YITP QEC Workshop:
Fault-tolerant logical processing
Ting-Chun Lin
University of California San Diego
Hon Hai Research Institute
Rachel Yun Zhang
Massachusetts Institute of Technology
Min-Hsiu Hsieh
Hon Hai Research Institute
1 / 33
My Research Interest
Constructing
quantum
error-correcting codes
with different
properties.
2 / 33
Entanglement Removes the Constraint
Shared entanglement turns classical linear codes into quantum codes without the dual-containing constraint.
3 / 33
Protecting Classical and Quantum Information
Entanglement-assisted codes jointly encode and protect classical and quantum information.
4 / 33
Combining Entanglement and Passive Protection
Entanglement-assisted operator codes combine flexible code construction and passive error protection.
5 / 33
Good Quantum LDPC Codes with Fast Decoding
Quantum LDPC codes achieve constant rate and linear distance, with linear-time decoding.
6 / 33
Reducing Quantum Codes to Low Weight
Transform arbitrary quantum codes into low-weight codes with check weight 5 and qubit weight 6.
7 / 33
Almost Optimal Geometrically Local Quantum Codes
Turn good quantum LDPC codes into geometrically local codes with almost optimal dimension and distance.
8 / 33
Tradeoffs for Quantum Local Testability
Amplify soundness while preserving dimension and distance, at the cost of check locality.
9 / 33
Constant-Overhead Magic State Distillation
Good quantum codes with transversal non-Clifford gates enable constant-overhead magic state distillation.
10 / 33
Quantum Pseudorandom Error-Correcting Codes
Under a quantum LPN hardness assumption, quantum codes combine pseudorandom encodings with resilience to a constant fraction of local errors.
11 / 33
No QEC No QC
Timeline labels, from left to right:
- 2010 — Qubit Fidelity; Time
- 2020 — Gate Fidelity; 99.999%
- 2021–2024 — Logical Qubit Fidelity;
- Logical Gate Fidelity;
- FTQC
11 / 36
Today's Focus
Linear-Time
Encodable and Decodable
Quantum Codes
12 / 33
The Starting Point
STOC 1995, 388–397
IEEE TIT 42, 1723–1732 (1996)
Asymptotically good classical codes can be both encoded and decoded in linear time.
Can this construction be generalized to quantum error-correcting codes?
13 / 33
Quickly Encodable and Decodable Codes
Sender → Encoder → Channel → Decoder → Receiver
Errors/Noise enters the Channel.
Figure 1: Communication over a noisy channel.
Spielman: Asymptotically good codes, all operations have linear complexity and run in logarithmic depth.
12 / 34
Main Results
Asymptotically
Good Quantum Codes
Linear-Time and Log-Depth
Encoding / Unencoding / Decoding
Randomised and explicit constructions.
14 / 33
Spielman’s Approach
Efficient Error Reduction Codes
Recursion/Concatenation
15 / 33
Construction of Error Reduction Codes:
Start with a good expander code.
17 / 33
Properties of Error Reduction Codes
Property #1
Encodable in
Constant Time.
18 / 33
Properties of Error Reduction Codes
Property #2
Decodable in
Linear Time.
Sequential Error Reduction
- Flip a bit when unsatisfied checks outnumber satisfied checks.
- Repeat until no such bit remains.
19 / 33
Properties of Error Reduction Codes
Property #3
Expansion implies
Error Reduction
20 / 33
Error Reduction Codes
message bits; check bits.
- Take message bits, compute the check bits from them in constant depth.
→ This means they have constant distance!!
So what can they do?
16 / 34
Error Reduction Ability
message bits; check bits.
Suppose we get errors on message bits and errors on check bits.
Error Reduction if
17 / 34
Spielman’s Concatenation Structure
How Many Levels?
- Halve the block length at each step.
- Stop at the fixed-size base code.
- Decode it by brute force.
recursive steps
: original block length
: fixed base-code length
: number of recursive steps
Why Linear Time?
- Linear work at each level.
- Block length halves at the next.
total time
Recursion/Concatenation
21 / 33
Quantum Challenges
Challenge #1
Need
commuting stabilizers!
Challenge #2
Avoid
error propagation!
24 / 33
Toward a Solution
25 / 33
Error Syndromes and Residual Errors
X Syndrome
Residual X:
Residual Z:
Z Syndrome
26 / 33
Quantum Error Reduction: X Errors
Classical Error Reduction
- Reduce physical errors first.
. - Use to reduce .
- Then control the residual message error:
.
Reducing physical errors
controls the residual.
Reduction under must outweigh
amplification by .
27 / 33
Quantum Error Reduction: Z Errors
Classical Error Reduction
- Target the residual message error directly.
. - Rewrite the same syndrome:
.
Reduce the residual Z error
directly.
Use to reduce .
The residual Z error is a decoder variable.
28 / 33
The Need for Two-Way Expansion
Two-Way Expansion
- Both maps must provide classical error reduction:
. - Error reduction under must be strong enough to overcome the error amplification set by the sparsity of .
- A Z graph provides the required two-way expansion.
Z Graph
29 / 33
Two-Sided Lossless Expander and Z Graphs
FOCS 2025 Best paper
arXiv:2504.15087
Two-Sided Lossless Expander
Z Graph
30 / 33
MIT × UCSD × Stanford × UC Berkeley × HHRI
Thank you!
Linear-Time Encodable and Decodable
Quantum Error-Correcting Codes
Quantum Error-Correcting Codes
arXiv:2603.04543 · FOCS 2026
Adam Wills
MIT
Ting-Chun Lin
UCSD
→ Stanford
Rachel Yun Zhang
MIT
→ UC Berkeley
Min-Hsiu Hsieh
HHRI
33 / 33