[challenge]: Decode 20× faster than Tesseract at matched accuracy (p = 0.001)

Released by

Jinguo Liu, Hong Kong University of Science and Technology (Guangzhou)

Contact email

cacate0129@gmail.com

Method

Other

Challenge issue

Background

Tesseract (Google Quantum AI, arXiv:2503.10988) is a search-based most-likely-error decoder for quantum LDPC codes: it runs A* search with pruning heuristics through the exponentially large graph of error subsets, and achieves near-MLE accuracy at moderate physical error rates on an open benchmark suite of Stim circuits — surface codes, color codes, three bivariate-bicycle code families, and transversal-CX surface-code protocols — shipped in testdata/ of quantumlib/tesseract-decoder.

Decoding speed is a first-order bottleneck for fault-tolerant quantum computing: decoders must eventually keep up with μs-scale syndrome cycles, and accuracy bought by slow search is accuracy you cannot use online. A follow-up by the Tesseract authors (arXiv:2602.02985) accelerated the decoder by ~2–2.5× (peak >5× on the hardest bivariate-bicycle configurations) using purely low-level optimizations — data structures, cache layout, bit-twiddling — with no algorithmic change. That strongly suggests the algorithmic headroom above A*-with-current-heuristics is untapped.

Research objective

Build a decoder that is ~20× more efficient than Tesseract on its own benchmark suite — while losing nothing in accuracy at physical error rate p = 0.001.

Concretely:

1. Baseline: quantumlib/tesseract-decoder at commit 9c73ca0 (main, 2026-07-27), which already contains the published low-level accelerations — the 20× is measured on top of them. Same machine, matched parallelism (like-for-like single-thread comparison; a multi-threaded comparison may be reported additionally).
2. Speed gate: ≥20× wall-clock speedup per shot on at least 80% of the benchmark configurations in testdata/ at p = 0.001.
3. Accuracy gate: logical error rate equal or better on every benchmark configuration at p = 0.001 — no accuracy may be traded away anywhere, and improvements count in your favor.
4. The search space is open: smarter search heuristics and pruning bounds, hierarchical/predecoding hybrids (e.g., matching or BP+OSD prefilters with search fallback on hard shots), learned cost-to-go guidance, batch/SIMD/GPU decoding, ensembling — anything goes, as long as the gates pass. Note that hybrid designs must beat Tesseract on aggregate wall-clock including their fallback path.

Verification plan

The benchmark is fully deterministic and self-contained, so every claim is machine-checkable:

• Fixed dataset: the Stim circuits and detector error models shipped at the pinned commit; syndrome shots sampled with fixed, published seeds, plus a held-out freshly-seeded re-run to rule out overfitting to specific shots.
• Timing protocol: wall-clock per shot averaged over a stated number of shots on one documented machine, warm-up excluded, baseline and challenger measured back-to-back by a published harness script; speedup reported per configuration.
• Accuracy protocol: logical error rates with confidence intervals (e.g., Clopper–Pearson) at p = 0.001; "equal or better" means the challenger's rate is not worse beyond statistical uncertainty on any configuration, with enough shots that the comparison is meaningful at the observed error rates.
• One-command reproduction: open source code plus a script that re-runs baseline and challenger on the full suite and regenerates the speedup/accuracy tables.

Why this may lead to research output

Each step in this lineage has been its own paper — the Tesseract decoder itself, and its 2.5× low-level acceleration. A verified order-of-magnitude jump at matched MLE-grade accuracy would be a strong QEC-software result with direct relevance to real-time decoding budgets for surface and bivariate-bicycle codes (the leading candidates for early fault-tolerant machines), and the winning ideas — learned search guidance, hard-shot triage, hybrid fallback architectures — would transfer to other decoders. The fully closed, deterministic evaluation loop also makes this an ideal autoresearch target: an autonomous agent can iterate decoder variants against the exact same gate indefinitely.

References

1. L. Aghababaie Beni, N. Shutty, et al., Tesseract: a search-based decoder for quantum error correction, arXiv:2503.10988 (2025).
2. D. Grbic, L. Aghababaie Beni, N. Shutty, Accelerating the Tesseract decoder for quantum error correction, arXiv:2602.02985 (2026) — the low-level 2–2.5× baseline improvements, included in the pinned commit.
3. Benchmark suite: https://github.com/quantumlib/tesseract-decoder (testdata/: surface codes, color codes, bivariate-bicycle codes ×3, transversal-CX circuits), pinned at 9c73ca0.
4. O. Higgott, C. Gidney, Sparse Blossom: correcting a million errors per core second with minimum-weight matching, arXiv:2303.15933 — the speed reference point for matching-based decoding.
5. J. Roffe et al., Decoding across the quantum LDPC code landscape, Phys. Rev. Research 2, 043423 (2020) — BP+OSD, the standard QLDPC baseline family.

Start by inspecting the benchmark suite in quantumlib/tesseract-decoder at commit 9c73ca0, especially the configurations under testdata/. Establish a reproducible single-thread baseline at p = 0.001, then evaluate a decoder approach against the stated speed and accuracy gates. Done means at least 20× speedup on 80% of configurations, no accuracy regression, and an open one-command reproduction of the results.