Quantum circuit costs for Reed–Solomon decoding
Follow the latest progress by email.
Can Reed–Solomon syndrome decoding run coherently with fewer gates and peak qubits? The studied decoder is a subroutine of decoded quantum interferometry rather than an ordinary irreversible decoder.
Why it matters and what counts as progress
Why it matters: Reversible decoding is a major resource cost in the specified quantum optimization circuit.
What counts as progress: A lower-cost decoder for the same syndrome and error parameters, retaining the stated input-distribution failure allowance and all cleanup costs.
How the problem developed
- 15 Oct 2026 · Circuit optimization [1]
Andi Gu, Alek H. Kemeny, Susanne F. Yelin and Mikhail D. Lukin, using LLM-guided search Reported a Reed–Solomon decoder using 440,000 Toffolis and 1,837 qubits, versus a 5.1-million-Toffoli and 1,938-qubit baseline, a 12× reduction in the Toffoli–qubit product.
AI contribution
Discovering state-of-the-art quantum circuits with large language models
Gu, Kemeny, Yelin and Lukin report lower Toffoli and peak-qubit counts in seven specified circuit benchmarks, plus a new prime-field modular-inversion architecture. For fixed-point Gaussian evaluation, their stated benchmark falls from about 24,000 Toffolis and 362 qubits to 1,583 Toffolis and 139 qubits; the reported worst-case error is 9.99×10⁻⁸.
Sources
Website timeline
Publication dates and editorial changes.
LLM-discovered quantum circuits reduce Toffoli and qubit costs