⚛️ quantum physics

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

This paper introduces a rank-decomposition dynamic programming algorithm that achieves exact maximum-likelihood decoding for quantum error correction with arithmetic complexity polynomial in input size and exponential in rank-width, thereby enabling efficient decoding of specific code families like punctured quantum Reed-Muller codes where traditional treewidth-based tensor network methods fail.

Original authors: Bin Cheng, Feng Pan

Published 2026-10-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Bin Cheng, Feng Pan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Quantum computers hold the promise of solving problems that would take today's machines millennia to crack, but they are incredibly fragile. The slightest disturbance from the environment can corrupt the information they hold. To protect this delicate data, scientists use quantum error correction, a system that spreads a single piece of information across many physical particles. As the computer runs, it constantly checks for signs of damage, much like a security system monitoring for intruders. When an error is detected, a classical computer must decide how to fix it. The most reliable way to make this decision is to calculate the probability of every possible way the error could have happened and choose the most likely scenario. This process, known as maximum-likelihood decoding, is the gold standard for keeping quantum information safe, but it has been notoriously difficult to perform because the number of possibilities grows so fast that it quickly overwhelms even the most powerful supercomputers.

For years, researchers have relied on a method called tensor-network contraction to tackle this problem. This approach treats the error-correction puzzle as a complex web of connections, trying to simplify the web step by step to find the answer. While effective for some types of codes, this method hits a hard wall when the connections become too tangled. The time required to solve the puzzle grows exponentially with the complexity of the web, meaning that for many promising quantum codes, the calculation would take longer than the age of the universe. This limitation has left a gap between the theoretical power of quantum error correction and the practical ability to decode it efficiently.

In a new study, researchers Bin Cheng and Feng Pan have found a way to bypass this wall. They developed a fresh algorithm that approaches the decoding problem from a different angle, using a technique called rank-decomposition dynamic programming. Instead of trying to untangle the entire web at once, their method breaks the problem down into smaller, manageable pieces based on the underlying algebraic structure of the code. They realized that the complex calculations required to find the most likely error could be rewritten as a specific type of sum, which their new algorithm can evaluate with surprising speed. The key insight is that for certain families of quantum codes, the complexity of the problem depends on a different measure of structure than the one that stumps the old methods. While the traditional approach gets stuck on the sheer number of connections, the new method navigates the problem by focusing on the independent patterns within those connections.

The results of this work are striking. The researchers demonstrated that for specific types of quantum codes, including punctured quantum Reed-Muller codes and a family of codes built by combining smaller codes together, their new algorithm can find the exact answer in a reasonable amount of time. In contrast, the standard tensor-network methods would require an impossibly long time to do the same job. For instance, they successfully calculated the full likelihood for a code with 1,023 physical qubits, a scale where the old methods would have failed completely. The new approach does not just offer a theoretical advantage; in direct computer tests, it ran significantly faster than the best existing implementations of the older methods, even when those older methods were given extra help to simplify their calculations.

Beyond simply decoding errors faster, this new tool opens up entirely new possibilities for understanding how quantum computers behave. Because the algorithm can calculate exact probabilities so efficiently, it allows scientists to learn the specific characteristics of the noise affecting a quantum computer directly from the error signals it produces. This is like being able to diagnose the exact nature of a disease by observing a patient's symptoms with perfect clarity, rather than guessing based on averages. The researchers used their tool to estimate noise parameters, evaluate the chances of rare events that could cause a system to fail, and measure how close practical decoders come to the theoretical ideal. They found that by using the exact probabilities provided by their algorithm, they could quantify exactly how much better a perfect decoder would be compared to the ones currently used in experiments.

The study also addresses a common problem in high-precision computing: the loss of accuracy due to rounding errors. When computers perform billions of calculations, tiny mistakes can accumulate and distort the final result. The researchers created a version of their algorithm that uses only positive numbers, avoiding the cancellation effects that often cause these errors. This ensures that the probabilities they calculate are not just fast, but also mathematically trustworthy. They proved that the error in their results stays within strict, predictable bounds, giving them the confidence to use these numbers for critical decisions.

This work represents a significant step forward in making quantum error correction practical. By showing that exact decoding is possible for important classes of codes where it was previously thought to be intractable, the researchers have removed a major bottleneck. Their method provides a new way to exploit the hidden algebraic structure of quantum codes, turning problems that were once considered too hard into ones that can be solved efficiently. As quantum computers grow larger and more complex, the ability to decode errors with both speed and precision will be essential. This new approach offers a powerful tool for that task, helping to bridge the gap between the fragile nature of quantum information and the robust systems needed to protect it. The findings suggest that with the right mathematical tools, the challenge of decoding quantum errors is not an insurmountable barrier, but a solvable puzzle.

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

Problem Statement

Maximum-likelihood decoding (MLD) is the optimal strategy for quantum error correction under stochastic Pauli noise, as it minimizes the probability of selecting an incorrect logical class. However, implementing MLD is computationally challenging due to the degeneracy of quantum codes: errors in the same logical class differ by stabilizers and share the same syndrome. Calculating the total probability of a logical class requires summing over an exponentially large space of error configurations, a task known to be #P-hard.

Current state-of-the-art approaches utilize tensor-network (TN) contraction to evaluate these partition functions. While effective, exact TN contraction has a time complexity exponential in the treewidth of the underlying graph. For many important code families, such as those with growing distance or specific algebraic structures, the treewidth is large, rendering exact MLD superpolynomial in time. This paper addresses the question: Can exact maximum-likelihood decoding go beyond tensor-network contraction by exploiting algebraic structure rather than just graph connectivity?

Methodology

The authors propose a new decoding algorithm based on Rank-Decomposition Dynamic Programming (Rank DP). The core methodology involves three main steps:

Partition Function Formulation:
The decoding likelihoods for both code-capacity and circuit-level noise models are formulated as partition functions $Z_M(t; w)$ with binary linear constraints. These functions sum the weights of local fault blocks over configurations satisfying syndrome and logical constraints.
Reduction to Quadratic Sums of Powers (SOP):
Using the binary Fourier identity, the partition function is transformed into a quadratic sum of powers (SOP). This representation expresses the likelihood as a sum over binary variables involving local weights and edge interactions defined by the Tanner graph of the constraint matrix.
Rank-Decomposition Dynamic Programming:
Instead of contracting tensors based on graph treewidth, the authors apply a dynamic program parameterized by the rank-width of the Tanner graph.
- The algorithm utilizes a rank-decomposition tree of the graph.
- It maintains tables of partial sums indexed by "boundary signatures" (linear functionals of the cut).
- The complexity is exponential in the rank-width ($rw$) rather than the treewidth ($tw$).
- Gaussian Elimination: A key step involves reducing the Tanner graph by Gaussian elimination to a smaller graph (the fundamental graph of the binary matroid) without increasing the decomposition width. This reduction is crucial for achieving polynomial-time results for specific code families.
- Nonnegative Realization: To ensure numerical stability and avoid cancellation errors inherent in signed arithmetic, the authors present a nonnegative realization of the DP. This version uses only nonnegative sums and products, preserving table sizes and arithmetic complexity while providing rigorous relative floating-point error bounds.

Key Contributions

Theoretical Framework: The paper establishes that exact MLD can be performed in time polynomial in the input size and exponential in the rank-width of the Tanner graph (with respect to the fault block partition), rather than the treewidth.
Complexity Separation: The authors prove an exponential separation between Rank DP and standard dense pairwise TN contraction. Specifically, they identify code families where Rank DP runs in polynomial time while TN contraction requires superpolynomial time.
Explicit Code Families: The paper demonstrates that punctured quantum Reed-Muller codes and a Steane-concatenated family with growing distance admit polynomial-time MLD under independent single-qubit Pauli noise after Gaussian elimination. For these families, the rank-width of the reduced Tanner graph is $O(m)$ (where $m$ is the parameter such that $n \approx 2^m$ ), whereas the treewidth of the original tensor-network graph scales superpolynomially.
Numerical Robustness: The nonnegative realization provides certified relative error bounds under explicit arithmetic assumptions, enabling reliable inference even for rare events.
Empirical Validation: Extensive numerical experiments show that Rank DP outperforms tested TN implementations (including those with algebraic preprocessing) on selected code-capacity and circuit-level instances, achieving full likelihood evaluation for Reed-Muller codes up to 1,023 qubits.

Results

Runtime Performance: On Reed-Muller codes ( $n=1023$ ), Rank DP was approximately 2.83 times faster than the best-performing preprocessed TN implementation. On 3D surface codes and color codes, Rank DP showed speedups ranging from 1.5x to 7.7x depending on the circuit parameters.
Structural Bounds: For the punctured Reed-Muller codes, the reduced Tanner graph has a rank-width of $O(m)$ (which is $O(\log n)$ ), while the original tensor-network graph has a treewidth lower bound of $\Omega(n / (\log n)^{3/2})$ .
Applications: The authors successfully used the exact likelihoods to:
- Learn circuit noise parameters from syndrome data via gradient-based optimization.
- Evaluate rare postselection probabilities (e.g., conditional logical failure probabilities as low as $10^{-26}$ ) with certified accuracy.
- Quantify the optimality gaps of practical decoders (e.g., BP+OSD) relative to the exact MLD benchmark.

Significance and Claims

The paper claims to open new avenues for exploiting algebraic structure in quantum decoding and noise characterization. By shifting the complexity parameter from treewidth to rank-width, the authors demonstrate that exact MLD is feasible for code families previously considered intractable for exact methods.

The authors are modest in their scope, noting that the polynomial-time guarantee relies on specific structural conditions (small rank-width after Gaussian elimination) and that the method is currently limited to independent local fault factors. They do not claim to solve MLD for all quantum codes but rather provide a new, efficient exact evaluator for a significant class of codes and a tool for precise noise characterization. The work highlights that the "algebraic structure" of constraints (captured by rank-width) can be more succinct than the "connectivity" of the tensor network (captured by treewidth), offering a path to efficient exact decoding beyond the limitations of standard tensor-network contraction.