Exact Maximum Likelihood Decoding beyond Treewidth via Rank-Decomposition Dynamic Programming

AI summary

Overview

• Research area: Quantum error correction, specifically classical decoding algorithms for quantum codes, and the computational complexity of exact maximum-likelihood decoding.
• Technical level: Advanced. The paper is a theory paper built on stabilizer formalism, binary symplectic representation, rank-width of graphs, sums-of-powers (SOP) representations, and dynamic programming, with numerical experiments as a secondary component.
• Scope (one sentence): The paper shows that exact maximum-likelihood decoding of quantum codes under independent local Pauli noise can be reduced to a quadratic sum-of-powers and evaluated exactly by rank-decomposition dynamic programming, with runtime exponential in the rank-width of the Tanner graph rather than in its treewidth.

What This Paper Is About

Maximum-likelihood decoding (MLD) is the optimal decoding rule under a correctly specified stochastic Pauli noise model, because it picks the logical class with the largest total error probability, properly accounting for degeneracy. Its bottleneck is computing those logical-class probabilities, which are partition functions, and exact degenerate MLD is #P-hard under polynomial-time Turing reductions. The leading exact approach, tensor-network contraction, costs time exponential in the treewidth of the underlying graph; this paper asks whether exact MLD can escape that treewidth barrier by exploiting the algebraic structure of the parity constraints instead of the graph's connectivity.

Key Contributions

1. A decoding-to-SOP reduction. The authors show (Lemma 4.1) that the decoding partition function with independent local fault factors equals, up to a factor of 2^{-m}, a quadratic sum-of-powers on the Tanner graph T(M) of the constraint matrix, with the partition formed from the fault blocks plus singleton check nodes.
2. An exact evaluator via rank-decomposition dynamic programming. Applying the Rank DP of de Colnet et al. gives an exact algorithm using poly(N)·2^{O(rw(T(M); C))} arithmetic operations, where N := m + d + Σ_{B∈ℬ} 2^{|B|} and rw is rank-width with respect to the partition into fault blocks and singleton checks — with decomposition construction included in the bound.
3. Explicit tractable code families and a separation from tensor networks. After Gaussian elimination (which does not increase the decomposition width), punctured quantum Reed-Muller codes and a Steane-concatenated family with growing distance get polynomial-time MLD under independent single-qubit Pauli noise, while dense pairwise contraction of the corresponding tensor networks requires 2^{Ω(√n/(log n)^{3/2})} time.
4. A nonnegative realization and numerical evidence. Proposition 4.5 gives a nonnegative variant preserving table sizes and arithmetic complexity, admitting relative floating-point error bounds under explicit arithmetic assumptions; experiments show 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.

Main Findings

• Rank-width replaces treewidth as the governing parameter. Given an optimal rank decomposition of the decoding tensor-network graph G, Rank DP evaluates the likelihood in poly(N)·2^{O(rw(G))} arithmetic operations, whereas dense pairwise contraction of G requires 2^{Ω(tw(G))} time (Theorem 1.2, informal).
• Logarithmic rank-width plus polynomially many logical classes implies polynomial-time MLD in the arithmetic model, per the informal Theorem 1.1.
• Concrete superpolynomial separations exist. For punctured quantum Reed-Muller codes and a Steane concatenation, the reduced representation yields polynomial-time MLD under independent single-qubit Pauli noise, while dense pairwise contraction needs 2^{Ω(√n/(log n)^{3/2})} time.
• Gaussian elimination helps without hurting the bound. The SOP graph can be reduced by Gaussian elimination without increasing the decomposition width (Corollary 4.4), which is what produces the explicit separations.
• Numerical error control is available. The nonnegative realization uses only nonnegative sums and products, avoiding cancellation, and gives relative floating-point error bounds under explicit assumptions (Supplemental Appendix C).
• Practical runtime wins on tested instances. Rank DP ran faster than the tested tensor-network implementations on selected code-capacity and circuit-level decoding instances; the tensor-network implementations were allowed extra algebraic optimizations, while Rank DP used the general algorithm without code-specific algebraic optimization.
• Scale demonstrated. Full likelihood evaluation for Reed-Muller codes up to 1,023 qubits, illustrating the gap between decomposition widths after reduction and treewidth lower bounds for the original graphs.
• Downstream uses of the likelihoods. The computed likelihoods support learning circuit noise parameters from syndromes, evaluating rare postselection probabilities, and quantifying decoder optimality gaps; on color-code memory circuits the method computes both logical-observable sector probabilities with certified relative accuracy and determines the maximum-likelihood label.
• Enumeration cost context. Direct enumeration would require 4^k candidate classes for full-Pauli code-capacity decoding (2^k for a binary component) and at most 2^q flip vectors for the circuit-level task; the paper notes a single likelihood value does not in general determine the maximizing label, so approximate likelihoods only suffice when their error bounds pin down the maximizer.

Methodology in Plain English

The authors first write the decoding problem in binary form: Pauli faults become bit vectors, and the syndrome and logical constraints become linear equations over 𝔽₂. The probability of a given logical class is then a partition function — a sum over all fault configurations consistent with the observed syndrome and a candidate logical label, weighted by the product of independent local fault probabilities.

Their key move is a Fourier-type identity over 𝔽₂ that turns the hard constraint "M e = t" into an alternating sum over auxiliary binary variables, one per check. The result is a "sum of powers" expression: a sum over all binary assignments to the vertices of the Tanner graph of (-1) raised to a sum of products over graph edges, times local weight tables. Because the sign structure is quadratic (edge-wise), it can be handled by a dynamic program that follows a rank decomposition of the graph: a binary tree whose cuts have small rank over 𝔽₂. At each cut, instead of keeping a dense tensor over all boundary variables, the program keeps a table indexed by the span of the cut — the linear-algebraic information that actually crosses the partition — which is why rank-width, not treewidth, controls the cost.

They then apply Gaussian elimination to shrink the graph further without increasing the decomposition width, which is what makes the Reed-Muller and concatenated-Steane families provably polynomial-time. To address floating-point concerns, they give a nonnegative variant of the dynamic program that never subtracts, so relative error can be bounded. Finally, they run experiments comparing against tensor-network implementations and use the resulting exact likelihoods for noise learning and rare-event estimation.

Why This Matters

• Research impact: The work identifies a structural parameter (rank-width of the Tanner graph with respect to the fault partition) that can be exponentially smaller than treewidth, giving the first application, to the authors' knowledge, of the quadratic SOP / Rank DP framework to exact quantum MLD. It suggests that algebraic rank, not just connectivity, is the right currency for exact decoding complexity.
• Benchmarking decoders: Because MLD is the optimal rule, exact likelihoods provide ground truth for measuring how far practical decoders fall short, which the paper does via decoder optimality gaps (Eq. 16 defines excess conditional failure probability relative to MLD).
• Noise characterization: Exact likelihoods can be optimized over noise parameters to learn circuit noise models directly from syndrome data, an alternative exact evaluator for the syndrome-only estimation objective used in prior differentiable-likelihood work.
• Rare-event and postselection analysis: The method evaluates low-probability postselection probabilities that are hard to sample.

Real-world applications implied by the paper's results:

• Calibrating and validating quantum processor noise models from measured syndrome/detector data, reducing reliance on separate tomographic experiments.
• Providing a certified-accurate reference decoder for benchmarking fast heuristic or neural decoders deployed on hardware.
• Estimating the cost and usefulness of postselection and magic-state-style protocols where rare, low-probability events determine overhead.
• Assessing whether a given hardware noise budget is compatible with a target logical error rate by computing exact likelihood ratios.

Industry relevance: The results target fault-tolerant quantum computing stacks, where decoders sit in the real-time control loop and where characterizing device noise is a recurring engineering task. The paper does not claim real-time decoding capability; it offers an exact offline analysis tool and a complexity-theoretic alternative to tensor-network methods, with a nonnegative implementation suitable for floating-point use.

Future Directions

• Extending beyond the demonstrated code families. The polynomial-time guarantees are established for punctured quantum Reed-Muller codes and a specific Steane-concatenated family; broadening the class of codes with small rank-width relative to their fault partition is a natural open question.
• Decomposition construction in practice. The complexity bound includes building the rank decomposition, but the experiments do not report how the decomposition is found or how its width compares to the optimum on the tested instances; practical heuristics for finding good rank decompositions would matter for larger circuits.
• Approximate and truncated variants. The paper contrasts exact Rank DP with approximate tensor-network contraction, which uses truncation but does not preserve exact likelihoods; a controlled approximation scheme for Rank DP with error guarantees is a logical extension.
• Closing the decoder-optimality and noise-learning loop. The likelihood machinery is used for noise learning, postselection, and optimality gaps; integrating it into iterative calibration workflows and scaling to larger circuit-level instances are the obvious next engineering steps.

Target Audience

Researchers in quantum error correction and fault-tolerant quantum computing, especially those working on decoders, tensor-network methods, or the computational complexity of decoding; theoretical computer scientists interested in rank-width, sum-of-powers representations, and dynamic programming over linear structure; and quantum-hardware teams who need exact reference likelihoods for noise characterization and decoder benchmarking. Readers should be comfortable with the stabilizer formalism, binary linear algebra over 𝔽₂, and basic graph parameters; the numerical experiments are secondary to the theory.

Authors’ 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.