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.
AI Summary
Exact quantum maximum-likelihood decoding requires summing fault probabilities within logical classes. This paper asks whether algebraic parity structure can make these sums tractable beyond the treewidth limits of standard exact tensor-network contraction.
For code-capacity and circuit-level stochastic Pauli models with independent local fault blocks, it expresses likelihoods as weighted quadratic sums of powers and adapts an existing rank-decomposition dynamic program (Rank DP). Evaluation costs $\mathrm{poly}(N)2^{O(r)}$ arithmetic operations, including decomposition construction, where $r$ is Tanner-graph rank-width with fault blocks kept intact. Gaussian elimination produces a reduced graph without increasing decomposition width. A nonnegative, Fourier-equivalent recurrence avoids cancellation and supports relative floating-point error bounds under explicit arithmetic assumptions.
Explicit width constructions give polynomial-time decoding for punctured $[[2^m-1,1,3]]$ Reed–Muller codes and a Steane-concatenated family with polynomially growing distance. Separator arguments establish superpolynomial dense-contraction costs for the specified original tensor networks, including $2^{\Omega(\sqrt n/(\log n)^{3/2})}$ for the growing-distance family. This separation depends on representation and check elimination; it does not exclude efficient algebraically reformulated tensor networks.
Numerical comparisons include algebraically preprocessed tensor-network controls. At $1{,}023$ Reed–Muller qubits, four-sector evaluation takes median times of $9.24$ versus $26.14$ seconds. Applications demonstrate syndrome-only noise fitting, rare postselection probabilities, and decoder-risk gaps. Practical gains are instance-dependent, decomposition width remains exponential in the cost, and enumerating logical classes adds an exponential factor in encoded-qubit count. Numerical certificates concern stored weights under stated range and roundoff assumptions, not noise-model uncertainty.
Little sign of AI-generated textAI use disclosed
We used GPT 5.6 Sol and GPT 6 Astra to assist with literature searches, proof development, mathematical checks, numerical experiments, and manuscript preparation.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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.
Exact quantum maximum-likelihood decoding requires summing fault probabilities within logical classes. This paper asks whether algebraic parity structure can make these sums tractable beyond the treewidth limits of standard exact tensor-network contraction.
For code-capacity and circuit-level stochastic Pauli models with independent local fault blocks, it expresses likelihoods as weighted quadratic sums of powers and adapts an existing rank-decomposition dynamic program (Rank DP). Evaluation costs poly(N)2O(r) arithmetic operations, including decomposition construction, where r is Tanner-graph rank-width with fault blocks kept intact. Gaussian elimination produces a reduced graph without increasing decomposition width. A nonnegative, Fourier-equivalent recurrence avoids cancellation and supports relative floating-point error bounds under explicit arithmetic assumptions.
Explicit width constructions give polynomial-time decoding for punctured [[2m−1,1,3]] Reed–Muller codes and a Steane-concatenated family with polynomially growing distance. Separator arguments establish superpolynomial dense-contraction costs for the specified original tensor networks, including 2Ω(n/(logn)3/2) for the growing-distance family. This separation depends on representation and check elimination; it does not exclude efficient algebraically reformulated tensor networks.
Numerical comparisons include algebraically preprocessed tensor-network controls. At 1,023 Reed–Muller qubits, four-sector evaluation takes median times of 9.24 versus 26.14 seconds. Applications demonstrate syndrome-only noise fitting, rare postselection probabilities, and decoder-risk gaps. Practical gains are instance-dependent, decomposition width remains exponential in the cost, and enumerating logical classes adds an exponential factor in encoded-qubit count. Numerical certificates concern stored weights under stated range and roundoff assumptions, not noise-model uncertainty.
Quantum error correction (QEC) is indispensable for realizing fault-tolerant quantum computation, yet its effectiveness hinges critically on the classical decoding algorithm that interprets noisy syndrome measurements. Among all possible decoding strategies, maximum likelihood decoding (MLD) is provably optimal, since it identifies the logical group with largest likelihood by summing over all possible errors within logical class consistent with the observed syndrome. Despite its optimality, MLD is computationally intractable in general (#P-hard), motivating a rich landscape of exact and approximate algorithms. In this topical review, we provide a unified perspective on MLD by surveying recent advances through three complementary lenses: statistical mechanics, tensor networks, and artificial intelligence. From the statistical mechanics viewpoint, the MLD problem maps onto evaluating partition functions of disordered spin models, enabling exact solutions for certain codes and noise models as well as threshold estimation via phase-transition analysis. From the tensor network perspective, approximate contraction of tensor networks on the code's factor graph yields decoders that closely approach MLD accuracy with polynomial computational cost. From the artificial intelligence perspective, neural-network-based decoders, including autoregressive generative models and recurrent transformers, learn to approximate the MLD distribution from data, achieving high accuracy with the parallelism afforded by modern hardware accelerators. We discuss the connections among these three approaches, review their application to both simulated and experimental quantum hardware, and outline open challenges including real-time decoding, scalability to large code distances, and generalization to high-rate quantum low-density parity-check codes.
The maximum likelihood decoder based on tensor networks has proven highly successful for the 2D surface code, achieving the optimal decoding success rate. However, existing tensor network decoders are typically designed for independent single-qubit error models, and their performance under inter-qubit correlated error models remains unexplored. This is due to two major challenges. The first challenge lies in constructing the tensor network for correlated errors, since the same final Pauli error can arise from many different combinations of independent and correlated errors, preventing a direct factorization of the error probability. The second challenge is that even after a tensor network is constructed, it generally contains huge-dimensional tensors and is therefore not efficiently contractible. In this work, to address the first difficulty, we introduce additional binary indices and two transformations to construct a multi-index tensor network for maximum-likelihood decoding with correlated errors. To address the second difficulty, we use reparametrization, elimination, and index classification to decompose the huge-dimensional tensors into lower-dimensional tensors. This yields an efficiently contractible tensor network for error models satisfying the tractability conditions derived in this work. We perform numerical simulations for a representative correlated error model and show that the maximum-likelihood decoder implemented with our multi-index tensor network construction achieves a higher finite-size threshold than the widely used MWPM decoder.
We study the exact maximum-likelihood decoding of quantum error-correcting codes. Our primary focus is on the repetition code under circuit-level noise, which serves as a fundamental basis for quantum error correction experiments and is the only code that has achieved large distances and extremely low error rates. We uncover that the repetition code under circuit-level noise has an exact solution and propose an optimal maximum-likelihood decoding algorithm called "planar." This algorithm is based on the exact solution of the spin-glass partition function on planar graphs and has polynomial computational complexity. Through extensive numerical experiments, we demonstrate that our algorithm uncovers the exact threshold for depolarizing noise and realistic superconductor SI1000 noise. Furthermore, we apply our method to analyze data from recent quantum memory experiments conducted by Google Quantum AI, revealing that part of the error floor was attributed to the decoding algorithm used by Google. Finally, we implemented the repetition code quantum memory on superconducting systems using a 72-qubit quantum chip lacking reset gates, demonstrating that even with an unknown error model, the proposed algorithm achieves a significantly lower logical error rate than the matching-based algorithm. We also discuss the application of our approach to quantum codes whose maximum-likelihood decoding problem corresponds to a spin-glass problem, including the surface code under independent code-capacity noise.
Quantum low-density parity-check (qLDPC) codes reduce the qubit overhead of fault-tolerant quantum computation by an order of magnitude, but their decoding is harder than its classical counterpart: because many physical errors are equivalent up to stabilizers, the degenerate maximum-likelihood (ML) decoder must compare the probabilities of entire equivalence classes of errors, that is, partition functions, rather than single errors. The workhorse decoder BP+OSD sidesteps degeneracy heuristically and offers no guarantees. We treat degenerate decoding as probabilistic inference in an undirected graphical model: the probability of each logical class is the partition function of an unconstrained, strictly positive Markov random field over the code's check variables, a construction that generalizes the random-bond Ising mapping of the surface code to arbitrary CSS codes and to spacetime decoding with measurement errors and circuit-level noise. On this model we build two decoders. The first estimates all class partition functions by annealed importance sampling with common random numbers and attaches to every decision a certificate of optimality: a paired bootstrap test, or, composed with constant-factor estimators such as WISH, an exact optimality proof. The second is region-based: the Bethe free energy, whose bias cancels between classes, reproduces exact ML decoding on every tested surface-code instance at millisecond cost, and enlarging the regions to elimination clusters makes exact degenerate ML decoding of the [[72,12,6]] bivariate bicycle code feasible. Across surface codes and the bivariate bicycle codes [[72,12,6]] and [[144,12,12]], under code-capacity, phenomenological, and circuit-level noise, the sampling decoder matches or exceeds BP+OSD while certifying the bulk of its decisions, and the certificate flags exactly the syndromes on which any fast decoder should be distrusted.
The maximum-likelihood decoding (MLD), which is optimal for any error-correcting code, is known to be NP-hard. The standard technique for solving such MLD problems for quantum states is typically done using a mixed-integer program (MIP). In this work, we develop a faster decoding method than the MIP for graph codes, a class of stabilizer quantum error-correcting codes constructed from graph states. Our proposed decoder exploits the structural properties of the underlying graph states. Although different error patterns may yield the same syndrome, we demonstrate that the post-measurement state follows a well-defined structure determined by the projective syndrome measurement. Building on this idea, we introduce a hierarchical decoder in which each level can be solved in polynomial time. Additionally, this decoder achieves optimal decoding performance at the lower levels of the hierarchy. This strategy avoids the need to perform full maximum-likelihood decoding of graph codes. Numerical results illustrate the effectiveness of the proposed approach.
Accurate noise estimation is essential for fault-tolerant quantum computing, since decoding per formance depends critically on the fidelity of circuit-level noise parameters. We introduce a differ entiable Maximum Likelihood Estimation (dMLE) framework that learns these parameters directly from experimental syndrome data using likelihood gradients, with no decoder in the training loop. Mapping syndrome likelihoods to statistical-mechanical models enables exact and efficient evalua tion via planar solvers for repetition codes and tensor networks (TNs) for surface codes, extending the exact treatment to code distance d = 5 with a small number of rounds, and, via spatial subsam pling combined with time-translation symmetry, to larger codes and larger round counts. Across four experimental superconducting datasets, dMLE reduces logical error rates by up to 30.6% for repetition codes. On the Sycamore d = 3 surface code, a TN decoder using the dMLE prior attains a logical error rate comparable to that reported for state-of-the-art AlphaQubit, using standard syndromes alone without auxiliary leakage data. On the larger d = 5 surface code the dMLE prior lowers the logical error rate of the TN and Tesseract decoders by 7.18% and 5.23% relative to a prior optimized by reinforcement learning; at d = 7 it lowers that of Tesseract by 4.56% and 4.83% in the X and Z bases.