Approximate maximum-likelihood decoding via truncated free energies
Abstract
Maximum-likelihood decoding (MLD) achieves the minimum logical error rate of stabilizer codes under known i.i.d. Pauli noise, but its exact evaluation is \#P-hard. Practical pipelines therefore approximate MLD by minimum-weight decoding (MWD), retaining only the lowest-weight recovery per syndrome and discarding the coset degeneracy. The minimum-weight search is in turn implemented by stochastic solvers. We introduce approximate maximum-likelihood decoding (AMLD), a black-box framework that recycles the candidate samples discarded by stochastic inner decoders into a per-class truncated free-energy estimator. For every logical class represented in the candidate pool, the estimator is provably bounded below by the exact free energy and above by the empirical minimum weight. AMLD returns the logical class minimizing the estimated free energy with linear classical overhead. In SA-based Ising-decoder benchmarks, AMLD closes up to 83% of the MWD--MLD threshold gap across the toric and color codes under bit-flip and depolarizing noise. The largest threshold improvement, from 17.28% to 18.62%, occurs on the $6.6.6$ color code under depolarizing noise. We further demonstrate AMLD on the $[[144,12,12]]$ bivariate-bicycle code, whose bit-flip decoding problem has a hypergraph structure. This application requires neither matching-based enumeration nor code-specific tensor-network contraction. At p=0.05, AMLD reduces the logical error rate by 13% relative to MWD evaluated on the same BP-OSD candidate pool.
Related
- Exact Maximum Likelihood Decoding beyond Treewidth via Rank-Decomposition Dynamic Programming
- Certified Non-Degenerate Maximum-Likelihood Benchmarking of Quantum LDPC Decoders
- A dS4 maximum in M-theory from Casimir energies on Riemann-flat manifolds
- Maximum likelihood, neural networks and posterior mean for inferring fractional Brownian motion parameters
- Penalized Maximum Likelihood Inference of Core-Periphery Networks
BibTeX
@misc{liu2026approximate,
title = {{Approximate maximum-likelihood decoding via truncated free energies}},
author = {Yuanqi Liu and Weilei Zeng and Junjie Wu and Lingling Lao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.03928},
eprint = {2609.03928},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.03928},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Approximate maximum-likelihood decoding via truncated free energies
AU - Yuanqi Liu
AU - Weilei Zeng
AU - Junjie Wu
AU - Lingling Lao
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.03928
UR - https://arxiv.org/abs/2609.03928
AB - Maximum-likelihood decoding (MLD) achieves the minimum logical error rate of stabilizer codes under known i.i.d. Pauli noise, but its exact evaluation is \#P-hard. Practical pipelines therefore approximate MLD by minimum-weight decoding (MWD), retaining only the lowest-weight recovery per syndrome and discarding the coset degeneracy. The minimum-weight search is in turn implemented by stochastic solvers. We introduce approximate maximum-likelihood decoding (AMLD), a black-box framework that recycles the candidate samples discarded by stochastic inner decoders into a per-class truncated free-energy estimator. For every logical class represented in the candidate pool, the estimator is provably bounded below by the exact free energy and above by the empirical minimum weight. AMLD returns the logical class minimizing the estimated free energy with linear classical overhead. In SA-based Ising-decoder benchmarks, AMLD closes up to 83% of the MWD--MLD threshold gap across the toric and color codes under bit-flip and depolarizing noise. The largest threshold improvement, from 17.28% to 18.62%, occurs on the $6.6.6$ color code under depolarizing noise. We further demonstrate AMLD on the $[[144,12,12]]$ bivariate-bicycle code, whose bit-flip decoding problem has a hypergraph structure. This application requires neither matching-based enumeration nor code-specific tensor-network contraction. At p=0.05, AMLD reduces the logical error rate by 13% relative to MWD evaluated on the same BP-OSD candidate pool.
ER -