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

#1. Introduction

Quantum error correction protects quantum information by encoding it redundantly, and the decoder maps noisy syndrome measurements back to a recovery operation. Under a stochastic Pauli noise model, in which each qubit independently suffers an $X$, $Y$, or $Z$ error with known probabilities, the maximum-likelihood decoder selects the logical equivalence class of faults with the largest total probability. This decoder minimizes the logical failure probability and is therefore the gold standard against which all practical decoders are measured. The obstacle is computational: 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],[10].

The Rank DP approach reframes the problem. Rather than exploiting treewidth, which controls the width of tensor-network contractions, it exploits rank-width, a width measure based on cut ranks of adjacency matrices over $\mathbb{F}_2$. Because the fault factors in the decoding partition function are local and independent, the partition function can be written as a quadratic sum of powers of small matrices, and dynamic programming over a rank decomposition evaluates it exactly with arithmetic cost exponential in rank-width alone. For code families whose Tanner graphs have bounded rank-width but unbounded treewidth — notably punctured quantum Reed–Muller codes and Steane-concatenated families with growing distance — this converts superpolynomial exact decoding into polynomial-time exact decoding [1],[10].

This paper is a structural analysis and independent appraisal of that result, reconciling three independent draft assessments. Our contributions are:

1. A self-contained restatement of the Rank DP decoding pipeline, with the quadratic-sum-of-powers form derived from first principles.
2. Fully explicit numerical derivations: exact logical-class probabilities for the three-qubit repetition code, a complexity gap computation for punctured Reed–Muller codes, and a floating-point error budget for a $1{,}023$-qubit instance.
3. A proof that $\mathrm{rw}(G) \le \mathrm{tw}(G) + 1$ for all graphs, establishing that Rank DP never loses asymptotically relative to tensor-network contraction.
4. A critical discussion connecting the result to the complexity theory of exact ML decoding [9], to algebraic classification programs for quantum codes [12],[13],[14], and to the broader literature on maximum-likelihood computation in statistics and coding theory [2]–[8],[11].

We write for an adjacent-field expert: a statistician, information theorist, or numerical analyst need not know stabilizer formalism in advance. Where jargon appears (stabilizer, Tanner graph, rank-width, logical class), it is defined once at first use.

#2. Background and Related Work

The target result. The paper under analysis [1] (circulated identically as [10]) introduces Rank DP for exact ML decoding of quantum codes. The authors express the decoding partition function — a sum over fault configurations of products of independent local fault factors — as a quadratic sum of powers, then apply dynamic programming over a rank decomposition of the Tanner graph with respect to the fault partition. The arithmetic complexity is polynomial in the input size and exponential in the rank-width, including the cost of constructing the decomposition. After Gaussian elimination over $\mathbb{F}_2$, this yields polynomial-time exact decoding for punctured quantum Reed–Muller codes and a Steane-concatenated family with growing distance, for which standard tensor-network contraction is superpolynomial. A nonnegative realization of the recursion gives relative floating-point error bounds under explicit arithmetic assumptions, and experiments show runtime advantages on code-capacity and circuit-level instances, with full likelihood evaluation for Reed–Muller codes up to $1{,}023$ qubits. Our analysis builds directly on this result and interrogates its scope.

Complexity of exact ML decoding. The foundational intractability result is that exact ML decoding of general linear codes is NP-hard, dating to Berlekamp, McEliece, and van Tilborg. Within the provided corpus, the work of [9] refines this picture: it shows that exact ML decoding over the binary symmetric channel is possible in polynomial time for expander codes, an asymptotically good class of low-density parity-check (LDPC) codes, despite the general hardness. This is conceptually the closest classical analogue of [1]: both results carve out structured families for which exact ML, normally intractable, becomes efficient — via expansion structure in [9] and via bounded rank-width in [1]. The parallel suggests a general program: identify the graph-algebraic invariant that governs the cost of exact inference for each code family.

Structured exact decoding in classical coding. Polar codes admit exact ML decoding over the binary erasure channel via a matrix triangulation of the sparse parity-check matrix followed by solving a small linear system over $\mathrm{GF}(2)$, with belief propagation used to implement the triangulation [6]. This is another instance of algebraic structure — the polar transform's recursive Kronecker form — collapsing an exponential search into polynomial algebra. Rank DP plays the analogous role for quantum codes whose Tanner graphs have low rank-width: the quadratic-sum-of-powers form is the structural invariant, as the Kronecker recursion is for polar codes [6].

Maximum likelihood in statistics: exactness versus approximation. The statistical literature offers a useful contrast class. Exact ML estimators for drift fractional Brownian motions, with consistency, strong consistency, and a central limit theorem proved via Malliavin calculus, demonstrate that exact likelihood theory can survive for models with long-range dependence [2]. Similarly, [7] establishes complete finite-sample exact ML inference for drifted multi-sub-fractional Brownian motion even when the increment covariance is not Toeplitz and no spectral density exists — the moral being that structural obstacles (non-stationary increments) need not preclude exact inference if one works with the right algebraic representation. Rank DP embodies the same moral for decoding: treewidth is the wrong invariant, and the right one (rank-width) restores tractability. On the approximate side, [3] accelerates ARMA maximum likelihood by replacing the exact likelihood with an AR approximation, reducing per-evaluation cost from $O(n)$ flops to $O(1)$ in repeated evaluations at the price of near-exactness; [4] approximates the ML estimator for $\alpha$-stable laws by projecting the score function onto trigonometric functions, making the approximated likelihood equation explicit through the characteristic function and its derivatives; and [8] reviews quasi-ML estimation of high-dimensional factor models, including Kalman-smoother and EM-based approaches, where the likelihood is maximized under a misspecified or simplified model. These works accept approximation to gain tractability; Rank DP's selling point is that it does not — it is exact, with certified floating-point error bounds, which matters because decoder optimality-gap quantification (one of the applications in [1]) requires a trustworthy exact baseline.

ML with latent or missing structure. Two further statistical works round out the context. [5] revisits the exact MLE for unit-root tests, deriving the asymptotic distribution of the test statistic more simply and directly and using response-surface regression for fast computation — a reminder that even "classical" exact ML problems benefit from algorithmic re-derivations, as Rank DP re-derives decoding partition functions. [11] studies ML estimation of sparse network connection probabilities under missing observations, bounding the risk of the MLE via stochastic-block-model proxies; the combinatorial-sum-over-latent-configurations structure there is formally akin to the sum over fault configurations in decoding, though [11] concerns statistical risk rather than computational complexity.

Algebraic classification of quantum codes. Within the QNFO program, [12] connects $p$-adic valuation theory, Mahler spectral expansions, Kodaira–Néron fiber classification, and the Amice transform to the classification of quantum error-correcting codes, with three conjectures, fourteen lemmas, and computational verification across four code families at $83\%$ classification coverage. [13] tests the Mahler spectral conjecture on eight additional stabilizer code families, confirming $v_p^{\max} = 28$ for the Golay CSS code while finding that other stabilizer codes cluster at a random baseline of $1$–$6$, thereby binding the conjecture to Golay-type self-dual codes. [14] argues that five independent QNFO research programs converge on the insight that ultrametric (non-Archimedean) mathematics provides the correct state-space geometry for fundamental physics, quantum computation, and optimization. Rank DP is architecturally consonant with this program: both replace metric-geometric invariants (treewidth, Euclidean distance) with algebraic ones (rank over $\mathbb{F}_2$, $p$-adic valuation), and both find that the algebraic invariant is the one that actually governs computational or classificatory behavior. The cut-rank function $\rho_G$ of Section 3.2 is a finite-field, hence non-Archimedean, object. We develop this connection — flagged as suggestive rather than theorem-level — in Section 6.

Collectively, these works illustrate a recurring theme: algebraic or structural reformulations — whether via rank-width, functional projection, matrix triangulation, or $p$-adic valuation — can convert an intractable exponential problem into a tractable polynomial one, provided the underlying assumptions hold.

#3. Methods

#3.1 Setting: stabilizer codes and logical classes

A stabilizer code encodes $k$ logical qubits into $n$ physical qubits using $n-k$ independent Pauli operators (the stabilizers) that all commute with the encoded state. A fault pattern $e \in \{0,1\}^{2n}$ (bits for the $X$ and $Z$ components on each qubit) produces a syndrome $s(e) \in \mathbb{F}_2^{n-k}$, computed as $s(e) = H e$ where $H$ is the parity-check matrix over $\mathbb{F}_2$. Under independent single-qubit Pauli noise with fault probability $p$, the likelihood of a fault pattern factorizes:

Two fault patterns with the same syndrome and the same logical action are equivalent. The decoder observes $s$ and must choose the logical class $L$ (an equivalence class of faults under multiplication by stabilizers) maximizing the class probability

where $Z(s) = \sum_{e : s(e)=s} \prod_i w_i(e_i)$ is the syndrome partition function. Because classes are cosets of the stabilizer, $Z_L = Z_{L_0} \cdot R_L$ where $R_L$ is a coset sum; computing all $Z_L$ reduces to computing base partition functions of quadratic-sum-of-powers form. The Tanner graph $G$ has one vertex per fault factor and one per check, with edges encoding dependence; its treewidth $\mathrm{tw}(G)$ governs tensor-network contraction cost, while its rank-width $\mathrm{rw}(G)$ will govern Rank DP.

#3.2 The quadratic-sum-of-powers form

The key rewriting of [1],[10]: because the factors $w_i$ are local and independent, the partition function restricted to a subset of factors can be written as a quadratic form in a vector of "boundary" monomials. Concretely, for a cut $(A, \bar{A})$ of the Tanner graph, define the cut adjacency matrix $M_A \in \mathbb{F}_2^{|A| \times |\bar{A}|}$ with $(M_A)_{ij} = 1$ iff factor $i \in A$ and check $j \in \bar{A}$ are adjacent. The number of distinct boundary interaction patterns across the cut is at most $2^{\operatorname{rank}_{\mathbb{F}_2}(M_A)}$, and the dynamic-programming state per decomposition bag is a vector of dimension $2^{b}$ where $b \le \mathrm{rw}(G) := \min_{\text{decompositions}} \max_{\text{cuts}} \operatorname{rank}_{\mathbb{F}_2}(M_A)$. The partition function becomes a quadratic sum of powers:

where each $Q_v(p)$ is a small matrix of polynomials in the local fault probabilities $p$, and the product is taken along the rank decomposition. Each multiplication is a matrix product of dimension at most $2^{\mathrm{rw}(G)}$.

#3.3 Complexity and the Rank DP pipeline

The pipeline of [1],[10] is: (i) build the Tanner graph with respect to the fault partition; (ii) compute a rank decomposition (via Gaussian elimination over $\mathbb{F}_2$ to compute cut ranks); (iii) run the DP over the decomposition, multiplying matrices of dimension $2^{\mathrm{rw}(G)}$; (iv) normalize by $Z(s)$ to obtain class probabilities and select the maximum-likelihood class. The arithmetic complexity is

where the $O(n^3)$ term covers Gaussian elimination for decomposition construction and cut-rank computation, and the $O(n \cdot 4^{\mathrm{rw}(G)})$ term covers $O(n)$ structured matrix products of dimension $2^{\mathrm{rw}(G)}$; we adopt the paper's stated bound (see Appendix A for the divergence concerning alternative per-node convolution counts). By contrast, tensor-network contraction costs $O(n \cdot 2^{\mathrm{tw}(G)})$.

#3.4 Nonnegative realization and floating-point bounds

All quantities in the DP are sums of products of probabilities, hence nonnegative. [1],[10] give a realization in which every intermediate value is nonnegative, so that relative floating-point errors accumulate multiplicatively rather than through cancellation. Under the standard assumption that each floating-point operation introduces relative error at most $u$ (the unit roundoff), a sequence of $N$ rounding operations on a running nonnegative value accumulates relative error at most $(1+u)^{N} - 1$, which is at most $N u$ when $N u \ll 1$. We make this quantitative in Section 4.3.

#3.5 Evaluation methodology

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],[10] (Section 4.2); and (c) floating-point error budgets derived from the standard unit-roundoff model (Section 4.3). We report no new empirical measurements; runtime comparisons are cited as reported in [1],[10] and labeled as such.

#4. Analysis

#4.1 Worked example: the three-qubit repetition code

The $[[3,1,3]]$ repetition code encodes one qubit with stabilizers $Z_1 Z_2$ and $Z_2 Z_3$. Under independent bit-flip noise with probability $p$ per qubit, a syndrome $s = 00$ (no triggers) arises from fault patterns with an even number of $X$ errors. The logical class $L_0$ (preserving the encoded state) contains patterns with an even number of faults; $L_1$ contains patterns with an odd number. We compute $P(L_0 \mid 00)$ exactly.

Input numbers: $n = 3$ qubits; per-qubit fault probability $p = 0.1$ (chosen illustrative value, standard in decoding benchmarks); hence $1 - p = 0.9$.

Step 1. Probability of exactly $j$ faults under independent noise:

Step 2. Class $L_0$ = even $j$:

Step 3. Arithmetic: $(0.9)^3 = 0.9 \times 0.9 = 0.81$; $0.81 \times 0.9 = 0.729$. Next, $(0.1)^2 = 0.01$; $0.01 \times 0.9 = 0.009$; $\binom{3}{2} = 3$; $3 \times 0.009 = 0.027$. Sum: $0.729 + 0.027 = 0.756$.

Step 4. Class $L_1$ = odd $j$: $\binom{3}{1}(0.1)(0.9)^2 = 3 \times 0.1 \times 0.81 = 0.243$; $\binom{3}{3}(0.1)^3 = 0.001$. Sum: $0.243 + 0.001 = 0.244$.

Step 5. Normalization check: $0.756 + 0.244 = 1.000$, as required since the classes partition all $2^{3} = 8$ fault configurations.

The ML decoder selects $L_0$ with class probability $0.756$. The minimum-weight decoder (which picks the single most likely pattern, the empty fault, and hence also $L_0$) agrees here; but the exact class probability $0.756$ versus the single-pattern probability $0.729$ shows the $0.027$ contribution of degenerate configurations that a suboptimal decoder's confidence estimate would miss. This gap — $0.756 - 0.729 = 0.027$, a relative underestimate of $0.027/0.756 \approx 0.035714$ — is precisely the optimality-gap information that exact likelihood evaluation exposes and that [1],[10] exploit for decoder benchmarking.

ML threshold. For the length-$n$ repetition code, $Z_0 = \sum_{j \text{ even}} \binom{n}{j} p^{j}(1-p)^{n-j}$ and $Z_1$ is the odd sum; both equal $\tfrac{1}{2}$ exactly when $p = \tfrac{1}{2}$, by the binomial symmetry $\binom{n}{j} = \binom{n}{n-j}$. Hence the exact ML threshold is $p^{\ast} = 0.5$, independent of $n$ — a trivial but fully verified instance of exact likelihood evaluation of the type Rank DP automates at scale.

#4.2 Rank-width versus treewidth, and the complexity gap

Claim. For any graph $G$, $\mathrm{rw}(G) \le \mathrm{tw}(G) + 1$.

Derivation. Let $(T, \mathcal{B})$ be a tree-decomposition of $G$ of width $\mathrm{tw}$, so every bag has $|\mathcal{B}_t| \le \mathrm{tw} + 1$ vertices. Construct a rank-decomposition whose decomposition tree is $T$ by attaching each vertex $v \in V$ to a leaf of $T$ corresponding to a bag containing $v$ (standard bag-to-leaf assignment). For an edge $e$ of $T$, the cut $(V_e, \bar{V}_e)$ separates leaf sets; every edge of $G$ crossing this cut has both endpoints in the bag(s) along the boundary, and the biadjacency matrix $A_G[V_e, \bar{V}_e]$ is a submatrix of the bag adjacency structure of size at most $(\mathrm{tw}+1) \times (\mathrm{tw}+1)$. The $\mathrm{GF}(2)$-rank of a matrix is at most its smaller dimension, so

Hence the induced rank-decomposition has width at most $\mathrm{tw} + 1$, i.e. $\mathrm{rw}(G) \le \mathrm{tw}(G) + 1$. $\blacksquare$

Consequence: the Rank DP complexity $n^{O(1)} \cdot 2^{O(\mathrm{rw})}$ never exceeds the tensor-network complexity $2^{O(\mathrm{tw})}$ up to polynomial factors, and strictly beats it on the families of [1] where $\mathrm{rw}$ is constant after Gaussian elimination but $\mathrm{tw} = \omega(1)$.

Complexity gap for punctured quantum Reed–Muller codes. Punctured quantum Reed–Muller codes have Tanner graphs of bounded rank-width but treewidth growing with code length; this is the structural claim of [1],[10]. For concreteness, take a family with $\mathrm{rw}(G_n) = 4$ and $\mathrm{tw}(G_n) = \Theta(n^{\alpha})$ with $\alpha = 1/2$ (a conservative polynomial growth rate consistent with the superpolynomial-contraction claim; the exact exponent is family-dependent and we state it as an assumption). Code length $n = 1{,}023$ (the largest Reed–Muller instance evaluated in [1],[10]).

Rank DP cost. With $\mathrm{rw} = 4$:

At $n = 1{,}023$: $n^2 = 1{,}046{,}529$; $n^3 = 1{,}046{,}529 \times 1{,}023 = 1{,}046{,}529{,}000 + 24{,}070{,}167 = 1{,}070{,}599{,}167 \approx 1.07 \times 10^{9}$ arithmetic operations. The DP term is $256 \times 1{,}023 = 261{,}888$, negligible. Total $\approx 1.07 \times 10^{9}$ operations.

Tensor-network cost. With $\mathrm{tw}(G_n) \approx n^{1/2}$ (assumed growth): at $n = 1{,}023$, $\sqrt{1{,}023} \approx 31.98$ (since $31^2 = 961$ and $32^2 = 1{,}024$). Then

Arithmetic: $2^{31.98} = 2^{31} \times 2^{0.98} \approx 2.147 \times 10^{9} \times 1.972 \approx 4.23 \times 10^{9}$; hence $T_{\text{TN}} \approx 1{,}023 \times 4.23 \times 10^{9} \approx 4.33 \times 10^{12}$ operations.

Gap. $T_{\text{TN}} / T_{\text{Rank DP}} \approx 4.33 \times 10^{12} / 1.07 \times 10^{9} \approx 4.05 \times 10^{3}$, i.e. roughly a four-thousand-fold separation at $n = 1{,}023$ under the stated assumption $\mathrm{tw} = \Theta(\sqrt{n})$. Moreover the separation grows: Rank DP stays at $O(n^3)$ while $T_{\text{TN}}$ grows superpolynomially, so the gap is unbounded in $n$. We emphasize that the exponent $\alpha = 1/2$ is an assumption; any $\alpha \gt 0$ preserves the qualitative conclusion (superpolynomial versus polynomial), and the numerical gap scales as $2^{n^{\alpha}} / n^{2}$.

#4.3 Floating-point error budget for a $1{,}023$-qubit instance

Input numbers (sources): IEEE double-precision unit roundoff $u = 2^{-53} \approx 1.1102 \times 10^{-16}$ (standard arithmetic model; exactly $2^{-53} = 1.1102230246251565 \times 10^{-16}$); DP depth $m = n = 1{,}023$ sequential matrix multiplications along the decomposition (the decomposition length equals the code length in the linear-order DP of [1],[10]).

Bound. For a nonnegative realization with at most two rounding operations per step on the running value, the relative error after $m$ steps satisfies

With $m = 1{,}023$, $2m = 2{,}046$. Using $\ln(1+u) \approx u$ for small $u$:

Compute: $2000 \times 1.1102 \times 10^{-16} = 2.2204 \times 10^{-13}$; $46 \times 1.1102 \times 10^{-16} = 5.107 \times 10^{-15}$; sum $= 2.2715 \times 10^{-13}$. The second-order correction is negligible: $\binom{2046}{2} u^2 \approx 2.09 \times 10^{6} \times 1.23 \times 10^{-32} \approx 2.6 \times 10^{-26}$, four orders below the linear term. Hence

i.e. approximately $13$ correct decimal digits — far below the precision needed for decoder selection or noise-parameter learning, where class probabilities differing by less than $10^{-6}$ are already operationally indistinguishable for syndrome sampling. This confirms the practical soundness of the nonnegative realization of [1],[10] at the $1{,}023$-qubit scale. For context, the same model with $N = 10^{6}$ accumulation steps gives $N u \approx 1.12 \times 10^{-10}$, and with $N = 10^{9}$ steps $N u \approx 1.12 \times 10^{-7}$; the bound degrades gracefully with operation count.

#4.4 Optimality-gap quantification

Given an exact class probability $P_{\text{ML}}(L \mid s)$ and a suboptimal decoder's effective class probability $P_{\text{dec}}(L \mid s)$, the optimality gap in log-likelihood is

From Section 4.1: if a minimum-weight-style confidence estimate reported only the dominant pattern, the gap is $\ln(0.756) - \ln(0.729)$. Arithmetic: $\ln(0.756) \approx -0.27971$ (since $\ln(0.75) = -0.28768$ and $\ln(1.008) \approx 0.00797$); $\ln(0.729) = 3\ln(0.9) = 3 \times (-0.10536) = -0.31608$. Gap: $-0.27971 - (-0.31608) = 0.03637$ nats per syndrome event. This is exactly the quantity that exact evaluation makes available and approximate methods cannot certify.

#5. Results

R1 (exact, Section 4.1). For the $[[3,1,3]]$ repetition code at $p = 0.1$: $P(L_0 \mid 00) = 0.756$, $P(L_1 \mid 00) = 0.244$, normalized to $1.000$. The dominant-pattern-only estimate is $0.729$, underestimating the true class probability by $0.027$ (relative $3.5714\%$). The exact ML threshold is $p^{\ast} = 0.5$ for all lengths $n$, proved by binomial symmetry.

R2 (parameter dominance, Section 4.2). $\mathrm{rw}(G) \le \mathrm{tw}(G) + 1$ for all graphs $G$. Consequently Rank DP [1] is never asymptotically worse than tensor-network contraction and is strictly superior (exponential in a constant versus exponential in a growing parameter) on the punctured Reed–Muller and Steane-concatenated families.

R3 (complexity arithmetic, Section 4.2). At $n = 1{,}023$ with assumed $\mathrm{rw} = 4$ and $\mathrm{tw} = \Theta(\sqrt{n})$: Rank DP costs $\approx 1.07 \times 10^{9}$ operations; tensor-network contraction costs $\approx 4.33 \times 10^{12}$ operations; ratio $\approx 4.05 \times 10^{3}$. The gap grows without bound in $n$ because one side is polynomial and the other superpolynomial. These are derived projections from the stated bounds of [1],[10], with the treewidth growth exponent $\alpha = 1/2$ as an explicit assumption; the qualitative conclusion (polynomial vs. superpolynomial) is assumption-free for the families identified in [1],[10].

R4 (error budget, Section 4.3). Under the IEEE double-precision model with $u = 2^{-53} \approx 1.11 \times 10^{-16}$ and $m = 1{,}023$ DP steps, the nonnegative realization guarantees relative error $\lesssim 2.3 \times 10^{-13}$, i.e. about $13$ significant decimal digits. This is a derived bound under the stated arithmetic assumptions, not an empirical measurement.

R5 (optimality gap, Section 4.4). For the Section 4.1 instance, the log-likelihood gap between the exact class probability and the dominant-pattern estimate is $\approx 0.0364$ nats per syndrome event.

R6 (projected operation counts for the Steane-concatenated family; labeled projection). The Steane $[[7,1,3]]$ code concatenated $t$ times has $n = 7^{t}$ qubits and distance $d = 3^{t}$. Assume (as in [1]) that after Gaussian elimination on the fault partition the rank-width is bounded by a constant $k_{\ast}$ independent of $t$, and that the Rank DP constant-factor cost is $c \cdot n \cdot 4^{k_{\ast}}$ per syndrome evaluation. Tensor-network contraction on the same instance costs $O(n \cdot 2^{\mathrm{tw}})$, and the treewidth of the concatenated Tanner graph grows with the distance, at least $\mathrm{tw}(G_n) = \Omega(d) = \Omega(3^{t})$ for this family. As a concrete projection, take $t = 3$ (so $n = 343$, $d = 27$), $k_{\ast} = 4$, and $c = 10$: Rank DP costs $10 \times 343 \times 4^{4} = 10 \times 343 \times 256 = 878{,}080 \approx 8.8 \times 10^{5}$ operations, while tensor-network contraction costs $343 \times 2^{27} = 343 \times 134{,}217{,}728 \approx 4.60 \times 10^{10}$ operations, a separation of roughly $5.2 \times 10^{4}$-fold at $t = 3$ that grows without bound in $t$ since one side is $O(n)$ in the DP exponent and the other is exponential in $3^{t}$. These are derived projections under the stated assumptions of [1],[10], not measurements; the qualitative conclusion (linear-in-$n$ versus exponential-in-distance) holds for any constant $k_{\ast}$ and any $c$.

Summary of Results. R1–R6 jointly establish: (i) exact class probabilities and thresholds are computable in closed form on small instances and expose decoder optimality gaps invisible to single-pattern estimates (R1, R5); (ii) Rank DP is never asymptotically worse than tensor-network contraction and is strictly superior on the identified families (R2, R3, R6); and (iii) the nonnegative realization certifies about $13$ significant decimal digits at the $1{,}023$-qubit scale (R4). All quantitative claims beyond Section 4.1 are labeled as derived projections or bounds, not empirical measurements.

#6. Discussion, Failure Modes, and Falsification

Relation to algebraic classification programs. As flagged in Section 2, the cut-rank function $\rho_G$ is a finite-field, hence non-Archimedean, object, and the QNFO program of [12],[13],[14] likewise finds that algebraic invariants ($p$-adic valuations, ultrametric geometry) rather than metric ones govern classificatory and computational behavior. We emphasize that this connection is suggestive rather than theorem-level: no formal correspondence between rank-width decompositions and Mahler spectral expansions is established here, and we offer it as a direction rather than a result.

Failure modes. Rank DP can fail to deliver its advertised advantage under at least four conditions. (F1) Unbounded rank-width: if the Tanner graph has rank-width growing with $n$ — as for random LDPC-like stabilizer codes with no product structure — the $4^{\mathrm{rw}}$ factor is exponential and Rank DP offers no advantage over contraction, whose $2^{\mathrm{tw}}$ may in fact be smaller since $\mathrm{rw}$ can exceed useful treewidth regimes on dense-ish graphs. (F2) Decomposition-construction cost: the $O(n^3)$ Gaussian-elimination term dominates for small or moderate $n$; for codes where tensor contraction is already cheap, the preprocessing overhead can make Rank DP slower in practice despite the asymptotic bound. (F3) Degeneracy handling: the coset reduction $Z_L = Z_{L_0} \cdot R_L$ assumes the fault partition aligns with the stabilizer structure; misaligned partitions inflate the boundary dimension beyond $2^{\mathrm{rw}}$. (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 $N u$ bound, and near-degenerate class probabilities (differences below $u$ itself) cannot be resolved at any fixed precision.

Falsification criteria. The analysis makes falsifiable commitments. (C1) If a graph family is produced with $\mathrm{rw}(G) \gt \mathrm{tw}(G) + 1$, the Theorem of Section 4.2 is false. (C2) If the punctured Reed–Muller or Steane-concatenated families of [1],[10] are shown to have treewidth $O(1)$ or rank-width $\omega(1)$, the claimed separation collapses. (C3) If a nonnegative implementation at the stated scale exhibits relative error exceeding $(1+u)^{2m}-1$, the error model of Section 3.4 is wrong. (C4) If exact ML decoding of a bounded-rank-width family is shown NP-hard, the polynomial bound $T_{\text{Rank DP}}$ is misstated. Each criterion is checkable by construction of a single counterexample instance.

Open questions. (Q1) What is the exact per-node convolution count in the DP of [1],[10] — see the divergence documented in Appendix A — and can the $O(n \cdot 4^{\mathrm{rw}})$ term be tightened? (Q2) Do the QNFO valuation invariants of [12],[13] correlate with rank-width across code families, in the way treewidth correlates with contraction cost? (Q3) Can the decomposition-construction step be improved below $O(n^3)$, e.g. via sparsity-aware elimination? (Q4) Does the expander-code tractability of [9] admit a rank-width interpretation, unifying the two structural escapes from ML hardness?

#Appendix A: Divergences Among the Source Drafts

All divergences among the three source drafts reconciled in this paper are documented here.

A.1 Complexity-bound divergence (cited from Section 3.3). One draft states the DP term as $O(n \cdot 4^{\mathrm{rw}})$, counting one $2^{\mathrm{rw}} \times 2^{\mathrm{rw}}$ matrix product per decomposition node in a linear-order traversal; a second draft counts $O(n \cdot \mathrm{rw} \cdot 4^{\mathrm{rw}})$, charging a per-node convolution over boundary patterns. The two agree when $\mathrm{rw} = O(1)$, which covers all families for which the separation is claimed; this paper adopts the first (smaller) bound as stated in [1],[10] and flags the discrepancy.

A.2 Decomposition-construction cost. One draft includes decomposition construction inside the complexity statement (yielding the $O(n^3)$ term retained here); another reports the DP cost alone and treats construction as preprocessing. We follow [1],[10] in including it.

A.3 Error-bound assumptions. One draft assumes at most one rounding operation per DP step (giving $m\,u$ with $m = 1{,}023$); another assumes two (giving $2m\,u$, the bound adopted in Section 4.3, which is the more conservative of the two). The difference ($1.14 \times 10^{-13}$ versus $2.27 \times 10^{-13}$) is immaterial at the reported precision.

A.4 Threshold-statement scope. One draft states the $p^{\ast} = 0.5$ repetition-code threshold for the three-qubit instance only; another generalizes to all $n$ via binomial symmetry. This paper adopts the general statement (Section 4.1), which is the more general result applicable to repetition codes of any length.

#References

[1] TITLE: arXiv Query: search_query=&id_list=2609.39556&start=0&max_results=1 [2] Exact maximum likelihood estimators for drift fractional Brownian motions. arXiv:0904.4186v1. https://arxiv.org/abs/0904.4186v1 [3] Faster ARMA maximum likelihood estimation. arXiv:1611.00965v1. https://arxiv.org/abs/1611.00965v1 [4] Trigonometrically approximated maximum likelihood estimation for stable law. arXiv:2209.08980v1. https://arxiv.org/abs/2209.08980v1 [5] Developments in Maximum Likelihood Unit Root Tests. arXiv:1611.00819v1. https://arxiv.org/abs/1611.00819v1 [6] Efficient Maximum Likelihood Decoding of Polar Codes Over the Binary Erasure Channel. arXiv:2106.14753v1. https://arxiv.org/abs/2106.14753v1 [7] Exact maximum likelihood inference for drifted multi-sub-fractional Brownian motion at discrete observation. arXiv:2609.22617v1. https://arxiv.org/abs/2609.22617v1 [8] Quasi Maximum Likelihood Estimation of High-Dimensional Factor Models: A Critical Review. arXiv:2303.11777v5. https://arxiv.org/abs/2303.11777v5 [9] On the Complexity of Exact Maximum-Likelihood Decoding for Asymptotically Good Low Density Parity Check Codes. arXiv:cs/0702147v1. https://arxiv.org/abs/cs/0702147v1 [10] Exact Maximum Likelihood Decoding beyond Treewidth via Rank-Decomposition Dynamic Programming. arXiv:2609.39556v1. https://arxiv.org/abs/2609.39556v1 [11] Maximum Likelihood Estimation of Sparse Networks with Missing Observations. arXiv:1902.10605v2. https://arxiv.org/abs/1902.10605v2 [12] DOI 10.5281/zenodo.21193487. QNFO: Number-Theoretic Ultrametric Foundations: A Unified p-adic Framework for Error-Correcting Code Classification. [13] DOI 10.5281/zenodo.21754148. QNFO: Extending $v_{p}^{\max}$ Code Classification: Testing the Mahler Spectral Conjecture on Additional Stabilizer Code Families. [14] DOI 10.5281/zenodo.21603374. QNFO: Five Pillars, One Structure: Consilient Convergence in QNFO Research.

#References

[1] TITLE: arXiv Query: search_query=&id_list=2609.39556&start=0&max_results=1 [2] Exact maximum likelihood estimators for drift fractional Brownian motions. arXiv:0904.4186v1. https://arxiv.org/abs/0904.4186v1 [3] Faster ARMA maximum likelihood estimation. arXiv:1611.00965v1. https://arxiv.org/abs/1611.00965v1 [4] Trigonometrically approximated maximum likelihood estimation for stable law. arXiv:2209.08980v1. https://arxiv.org/abs/2209.08980v1 [5] Developments in Maximum Likelihood Unit Root Tests. arXiv:1611.00819v1. https://arxiv.org/abs/1611.00819v1 [6] Efficient Maximum Likelihood Decoding of Polar Codes Over the Binary Erasure Channel. arXiv:2106.14753v1. https://arxiv.org/abs/2106.14753v1 [7] Exact maximum likelihood inference for drifted multi-sub-fractional Brownian motion at discrete observation. arXiv:2609.22617v1. https://arxiv.org/abs/2609.22617v1 [8] Quasi Maximum Likelihood Estimation of High-Dimensional Factor Models: A Critical Review. arXiv:2303.11777v5. https://arxiv.org/abs/2303.11777v5 [9] On the Complexity of Exact Maximum-Likelihood Decoding for Asymptotically Good Low Density Parity Check Codes. arXiv:cs/0702147v1. https://arxiv.org/abs/cs/0702147v1 [10] Exact Maximum Likelihood Decoding beyond Treewidth via Rank-Decomposition Dynamic Programming. arXiv:2609.39556v1. https://arxiv.org/abs/2609.39556v1 [11] Maximum Likelihood Estimation of Sparse Networks with Missing Observations. arXiv:1902.10605v2. https://arxiv.org/abs/1902.10605v2 [12] DOI 10.5281/zenodo.21193487. QNFO: Number-Theoretic Ultrametric Foundations: A Unified p-adic Framework for Error-Correcting Code Classification. [13] DOI 10.5281/zenodo.21754148. QNFO: Extending $v_{p}^{\max}$ Code Classification: Testing the Mahler Spectral Conjecture on Additional Stabilizer Code Families. [14] DOI 10.5281/zenodo.21603374. QNFO: Five Pillars, One Structure: Consilient Convergence in QNFO Research.