Exact Maximum-Likelihood Quantum Decoding beyond Treewidth: A Structural Analysis of Rank-Decomposition Dynamic Programming

In the paper's words

Maximum-likelihood (ML) decoding is the optimal decoding rule for quantum error correction under stochastic Pauli noise, but exact evaluation of logical-class probabilities has required tensor-network contraction whose cost grows exponentially in the treewidth of the syndrome graph, blocking certified decoder benchmarking and noise learning at scale. The specific gap is a width parameter that better matches the structure of decoding partition functions: treewidth controls contraction cost, yet the fault factors in the decoding sum are local and independent, suggesting that a rank-based invariant should govern the true complexity. We analyze the rank-decomposition dynamic programming (Rank DP) paradigm, in which decoding partition functions with independent local fault factors are written as quadratic sums of powers and evaluated by dynamic programming over a rank decomposition of the Tanner graph.

The abstract, verbatim; every line below is quoted from the text.

What it claims

For any graph G, rw(G) ≤ tw(G) + 1.

Numbers it reports

1. We give a fully explicit worked derivation of logical-class probabilities for the three-qubit repetition code ($P(L_0 \mid 00) = 0.756$ at $p = 0.1$, versus $0.729$ for the dominant pattern alone), a complexity comparison at $n = 1{,}023$ qubits showing an $\approx 4.05 \times 10^{3}$-fold operation-count separation under a stated treewidth-growth assumption, a floating-point error budget of $\lesssim 2.3 \times 10^{-13}$ relative error for the nonnegative realization, and a proof that $\mathrm{rw}(G) \le \mathrm{tw}(G) + 1$, so Rank DP is never asymptotically worse than contraction.

   from Abstract

2. Fully explicit numerical derivations: exact logical-class probabilities and the ML threshold for the three-qubit repetition code, a complexity-gap computation for punctured Reed–Muller codes at $n = 1{,}023$, a floating-point error budget for the nonnegative realization, and a projected operation-count separation for the Steane-concatenated family (Sections 4.1–4.4).

   from 1. Introduction

3. Theorem 1.1 of [1] defines the input size $N := m + d + \sum_B 2^{|B|}$ for explicitly given local weight tables and states that the arithmetic complexity is polynomial in the input size and exponential in the Tanner graph's rank-width, including decomposition construction; in Section 4.2 we adopt the specific form $O(N + n\,4^{\mathrm{rw}})$ as our own working convention for this qualitative bound.

   from 2. Background and Related Work

4. For decoding, the analogue is benign — the decoding partition function is a finite sum of nonnegative terms and always exists — but the practical recommendations of [11] for detecting and handling degenerate fits are a reminder that any likelihood-based pipeline needs existence and conditioning diagnostics; for Rank DP the relevant diagnostic is the floating-point error budget of Section 4.3.

   from 2. Background and Related Work

5. Within the QNFO program, the reconciled structural analysis of [12] documents the same Rank DP result at the level of a prior appraisal: it derives the three-qubit repetition-code class probabilities $P(L_0 \mid 00) = 0.756$ and $P(L_1 \mid 00) = 0.244$ at $p = 0.1$, proves the parameter dominance $\mathrm{rw}(G) \le \mathrm{tw}(G) + 1$, computes the complexity separation at $n = 1{,}023$ ($\approx 1.07 \times 10^9$ versus $\approx 4.33 \times 10^{12}$ operations, ratio $\approx 4.05 \times 10^3$), and catalogs failure modes including unbounded rank-width and decomposition-construction overhead [12].

   from 2. Background and Related Work

6. Hence the exact ML threshold is $p^{\ast} = 0.5$, independent of $n$ — a small but fully verified instance of the exact likelihood evaluation that Rank DP automates at scale.

   from 4.1 Worked example: the three-qubit repetition code

How it is done

1. We give a fully explicit worked derivation of logical-class probabilities for the three-qubit repetition code ($P(L_0 \mid 00) = 0.756$ at $p = 0.1$, versus $0.729$ for the dominant pattern alone), a complexity comparison at $n = 1{,}023$ qubits showing an $\approx 4.05 \times 10^{3}$-fold operation-count separation under a stated treewidth-growth assumption, a floating-point error budget of $\lesssim 2.3 \times 10^{-13}$ relative error for the nonnegative realization, and a proof that $\mathrm{rw}(G) \le \mathrm{tw}(G) + 1$, so Rank DP is never asymptotically worse than contraction.

   from Abstract

2. The probability of a logical class is a partition function, a sum over exponentially many fault configurations, and the leading exact method contracts a tensor network whose cost is exponential in the treewidth of the interaction graph [1],[7].

   from 1. Introduction

3. Theorem 1.1 of [1] defines the input size $N := m + d + \sum_B 2^{|B|}$ for explicitly given local weight tables and states that the arithmetic complexity is polynomial in the input size and exponential in the Tanner graph's rank-width, including decomposition construction; in Section 4.2 we adopt the specific form $O(N + n\,4^{\mathrm{rw}})$ as our own working convention for this qualitative bound.

   from 2. Background and Related Work

4. Because this is an analysis paper, our quantitative claims are of three kinds, each clearly labeled: (a) exact closed-form computations for small codes (Section 4.1), performed by hand with every arithmetic step shown; (b) complexity arithmetic derived from the stated bounds of [1],[7] (Section 4.2); and (c) floating-point error budgets derived from the standard unit-roundoff model (Section 4.3).

   from 3.5 Evaluation methodology

What would falsify it

1. A critical discussion of failure modes, falsification criteria, and open questions, situating the result within the classical literature on exact and approximate maximum-likelihood computation [2]–[6],[8]–[11] and within the algebraic classification program for quantum codes [12] (Sections 2, 6, 7).

   from 1. Introduction

2. The analysis makes falsifiable commitments.

   from 6. Discussion

3. Each criterion is checkable by construction of a single counterexample instance.

   from 6. Discussion

Where the claim stops

1. Rank DP can fail to deliver its advertised advantage under at least four conditions.

   from 6. Discussion

2. (F3) Degeneracy handling: the reduction of class probabilities to base partition functions assumes the fault partition aligns with the stabilizer structure; misaligned partitions inflate the boundary dimension beyond $2^{\mathrm{rw}}$.

   from 6. Discussion

3. (F4) Arithmetic-model violation: the relative error bound of Section 4.3 requires the strictly nonnegative realization; any implementation that reuses a cancellation-prone recurrence voids the $Nu$ bound, and near-degenerate class probabilities (differences below $u$ itself) cannot be resolved at any fixed precision.

   from 6. Discussion

Where to read

1. Abstract236 words · 1 min
2. 1. Introduction658 words · 3 min
3. 2. Background and Related Work1,692 words · 7 min
4. 3. Methods827 words · 4 min
5. 4. Analysis1,268 words · 6 min
6. 5. Results552 words · 2 min
7. 6. Discussion729 words · 3 min
8. 7. Practical Implications and Engineering Pathways579 words · 3 min
9. 8. Conclusion186 words · 1 min
10. Provenance and AI Involvement225 words · 1 min