Exact Maximum Likelihood Decoding beyond Treewidth via Rank-Decomposition Dynamic Programming
Abstract
Maximum-likelihood decoding provides an optimal decoding strategy for quantum error correction under stochastic Pauli noise. However, computing logical-class probabilities is challenging, and the leading exact tensor-network contraction requires time exponential in treewidth. In this work, we introduce a new decoding algorithm based on rank-decomposition dynamic programming (Rank DP). We express decoding partition functions with independent local fault factors as quadratic sums of powers and apply Rank DP. The resulting exact evaluator has arithmetic complexity polynomial in the input size and exponential in the Tanner graph's rank-width with respect to the fault partition, including decomposition construction. After Gaussian elimination, it gives polynomial-time decoding for punctured quantum Reed-Muller codes and a Steane-concatenated family with growing distance under independent single-qubit Pauli noise. Standard contraction of the corresponding tensor networks requires superpolynomial time. A nonnegative realization gives relative floating-point error bounds under explicit arithmetic assumptions. Numerical experiments demonstrate runtime advantages over the tested tensor-network implementations on selected code-capacity and circuit-level instances, with full likelihood evaluation for Reed-Muller codes up to 1,023 qubits. We further use these likelihoods to learn circuit noise parameters from syndromes, evaluate rare postselection probabilities, and quantify decoder optimality gaps. Our work opens new avenues for exploiting algebraic structure in quantum decoding and noise characterization.
Related
- Approximate maximum-likelihood decoding via truncated free energies
- Certified Non-Degenerate Maximum-Likelihood Benchmarking of Quantum LDPC Decoders
- Maximum likelihood, neural networks and posterior mean for inferring fractional Brownian motion parameters
- Penalized Maximum Likelihood Inference of Core-Periphery Networks
- Maximum-Likelihood Joint Image Reconstruction/Motion Estimation in Attenuation-Corrected Respiratory Gated PET/CT Using a Single Attenuation Map
BibTeX
@misc{cheng2026exact,
title = {{Exact Maximum Likelihood Decoding beyond Treewidth via Rank-Decomposition Dynamic Programming}},
author = {Bin Cheng and Feng Pan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.39556},
eprint = {2609.39556},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39556},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exact Maximum Likelihood Decoding beyond Treewidth via Rank-Decomposition Dynamic Programming
AU - Bin Cheng
AU - Feng Pan
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.39556
UR - https://arxiv.org/abs/2609.39556
AB - Maximum-likelihood decoding provides an optimal decoding strategy for quantum error correction under stochastic Pauli noise. However, computing logical-class probabilities is challenging, and the leading exact tensor-network contraction requires time exponential in treewidth. In this work, we introduce a new decoding algorithm based on rank-decomposition dynamic programming (Rank DP). We express decoding partition functions with independent local fault factors as quadratic sums of powers and apply Rank DP. The resulting exact evaluator has arithmetic complexity polynomial in the input size and exponential in the Tanner graph's rank-width with respect to the fault partition, including decomposition construction. After Gaussian elimination, it gives polynomial-time decoding for punctured quantum Reed-Muller codes and a Steane-concatenated family with growing distance under independent single-qubit Pauli noise. Standard contraction of the corresponding tensor networks requires superpolynomial time. A nonnegative realization gives relative floating-point error bounds under explicit arithmetic assumptions. Numerical experiments demonstrate runtime advantages over the tested tensor-network implementations on selected code-capacity and circuit-level instances, with full likelihood evaluation for Reed-Muller codes up to 1,023 qubits. We further use these likelihoods to learn circuit noise parameters from syndromes, evaluate rare postselection probabilities, and quantify decoder optimality gaps. Our work opens new avenues for exploiting algebraic structure in quantum decoding and noise characterization.
ER -