{
  "id": "oai:papers.qnfo.org:exact-maximum-likelihood-quantum-decoding-beyond-treewidth-a-reconciled-structur",
  "slug": "exact-maximum-likelihood-quantum-decoding-beyond-treewidth-a-reconciled-structur",
  "title": "Exact Maximum-Likelihood Quantum Decoding beyond Treewidth: A Structural Analysis of Rank-Decomposition Dynamic Programming",
  "authors": [
    "Rowan Brad Quni-Gudzinas"
  ],
  "abstract": "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. We give a fully explicit worked derivation of logical-class probabilities for the three-qubit repetition code (P(L₀ 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 ≈ 4.05 × 10³-fold operation-count separation under a stated treewidth-growth assumption, a floating-point error budget of lesssim 2.3 × 10^-13 relative error for the nonnegative realization, and a proof that rw(G) ≤ tw(G) + 1, so Rank DP is never asymptotically worse than contraction. This converts superpolynomial exact decoding into polynomial-time exact decoding for punctured quantum Reed–Muller and Steane-concatenated families, and gives decoder designers a certified exact baseline.",
  "abstract_markdown": "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. 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. This converts superpolynomial exact decoding into polynomial-time exact decoding for punctured quantum Reed–Muller and Steane-concatenated families, and gives decoder designers a certified exact baseline.",
  "date": "2026-10-09",
  "first_published": "2026-10-09",
  "last_revised": "2026-10-13T19:31:04Z",
  "modified": "2026-10-13T19:31:04Z",
  "version": "2.0.0",
  "version_count": 2,
  "language": "en",
  "keywords": [],
  "quality_tags": [
    "High-quality scholarly research",
    "open-access scholarly work",
    "versioned research publication"
  ],
  "quality_label": "High-quality scholarly research",
  "quality_basis": "QNFO publisher classification for open-access, versioned research with a public revision history and reader correction channel; this is not a claim of independent peer review.",
  "quality_evidence_url": "https://qnfo.org/about",
  "peer_review_status": "Not independently peer-reviewed",
  "resource_type": "ScholarlyArticle",
  "doi": null,
  "doi_url": null,
  "url": "https://papers.qnfo.org/papers/exact-maximum-likelihood-quantum-decoding-beyond-treewidth-a-reconciled-structur",
  "license_url": "https://legal.qnfo.org/",
  "license_spdx": null,
  "sha256": "46efefc139375f44145bce02a943e1ad45535eeb69a28701f22efbba80d68086",
  "version_url": "https://papers.qnfo.org/papers/exact-maximum-likelihood-quantum-decoding-beyond-treewidth-a-reconciled-structur/v/2.0.0",
  "datacite": {
    "schemaVersion": "http://datacite.org/schema/kernel-4",
    "identifiers": [
      {
        "identifier": "https://papers.qnfo.org/papers/exact-maximum-likelihood-quantum-decoding-beyond-treewidth-a-reconciled-structur",
        "identifierType": "URL"
      }
    ],
    "creators": [
      {
        "name": "Rowan Brad Quni-Gudzinas",
        "nameType": "Personal",
        "nameIdentifiers": [
          {
            "nameIdentifier": "https://orcid.org/0009-0002-4317-5604",
            "nameIdentifierScheme": "ORCID",
            "schemeUri": "https://orcid.org"
          }
        ]
      }
    ],
    "titles": [
      {
        "title": "Exact Maximum-Likelihood Quantum Decoding beyond Treewidth: A Structural Analysis of Rank-Decomposition Dynamic Programming"
      }
    ],
    "publisher": "QNFO",
    "publicationYear": "2026",
    "resourceType": {
      "resourceTypeGeneral": "Text",
      "resourceType": "ScholarlyArticle"
    },
    "subjects": [
      {
        "subject": "High-quality scholarly research",
        "subjectScheme": "QNFO publisher classification",
        "schemeUri": "https://qnfo.org/about"
      },
      {
        "subject": "open-access scholarly work",
        "subjectScheme": "QNFO publisher classification",
        "schemeUri": "https://qnfo.org/about"
      },
      {
        "subject": "versioned research publication",
        "subjectScheme": "QNFO publisher classification",
        "schemeUri": "https://qnfo.org/about"
      }
    ],
    "dates": [
      {
        "date": "2026-10-09",
        "dateType": "Issued"
      },
      {
        "date": "2026-10-13",
        "dateType": "Updated"
      }
    ],
    "language": "en",
    "version": "2.0.0",
    "rightsList": [
      {
        "rightsUri": "https://legal.qnfo.org/"
      }
    ],
    "descriptions": [
      {
        "description": "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. We give a fully explicit worked derivation of logical-class probabilities for the three-qubit repetition code (P(L₀ 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 ≈ 4.05 × 10³-fold operation-count separation under a stated treewidth-growth assumption, a floating-point error budget of lesssim 2.3 × 10^-13 relative error for the nonnegative realization, and a proof that rw(G) ≤ tw(G) + 1, so Rank DP is never asymptotically worse than contraction. This converts superpolynomial exact decoding into polynomial-time exact decoding for punctured quantum Reed–Muller and Steane-concatenated families, and gives decoder designers a certified exact baseline.",
        "descriptionType": "Abstract"
      },
      {
        "description": "Publisher quality classification: High-quality scholarly research. QNFO publisher classification for open-access, versioned research with a public revision history and reader correction channel; this is not a claim of independent peer review.",
        "descriptionType": "Other"
      },
      {
        "description": "Peer review status: Not independently peer-reviewed",
        "descriptionType": "Other"
      }
    ],
    "formats": [
      "text/html"
    ]
  }
}