Approximate maximum-likelihood decoding via truncated free energies

• URL: http://arxiv.org/abs/2609.03928v1
• Date: Thu, 03 Sep 2026 14:40:22 GMT
• Title: Approximate maximum-likelihood decoding via truncated free energies
• Abstract summary: Maximum-likelihood decoding (MLD) achieves the minimum logical error rate of stabilizer codes under known i.i.d. Pauli noise.<n>We introduce approximate maximum-likelihood decoding (AMLD), a black-box framework that recycles the candidate samples discarded by inner decoders into a per-class truncated free-energy estimator.
• Score: 3.4237938456166304
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Maximum-likelihood decoding (MLD) achieves the minimum logical error rate of stabilizer codes under known i.i.d. Pauli noise, but its exact evaluation is \#P-hard. Practical pipelines therefore approximate MLD by minimum-weight decoding (MWD), retaining only the lowest-weight recovery per syndrome and discarding the coset degeneracy. The minimum-weight search is in turn implemented by stochastic solvers. We introduce approximate maximum-likelihood decoding (AMLD), a black-box framework that recycles the candidate samples discarded by stochastic inner decoders into a per-class truncated free-energy estimator. For every logical class represented in the candidate pool, the estimator is provably bounded below by the exact free energy and above by the empirical minimum weight. AMLD returns the logical class minimizing the estimated free energy with linear classical overhead. In SA-based Ising-decoder benchmarks, AMLD closes up to $83\%$ of the MWD--MLD threshold gap across the toric and color codes under bit-flip and depolarizing noise. The largest threshold improvement, from $17.28\%$ to $18.62\%$, occurs on the $6.6.6$ color code under depolarizing noise. We further demonstrate AMLD on the $[[144,12,12]]$ bivariate-bicycle code, whose bit-flip decoding problem has a hypergraph structure. This application requires neither matching-based enumeration nor code-specific tensor-network contraction. At $p=0.05$, AMLD reduces the logical error rate by $13\%$ relative to MWD evaluated on the same BP-OSD candidate pool.

Related papers

• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty.<n>We study how many samples are necessary and sufficient to learn an $varepsilon$-optimal robust policy under the average-reward criterion.
  arXiv  Detail & Related papers  (2026-08-06T19:49:48Z)
• Towards Worst-case Hardness for Low-Noise LPN [6.6603865098703805]
  Existing worst-case-to-average-case reductions for [BLVW19, YZ21] rely on statistical smoothing of linear codes.<n>We show that any efficient solver can be transformed into a pair of efficient algorithms.
  arXiv  Detail & Related papers  (2026-06-04T08:11:23Z)
• Fair Decoder Baselines and Rigorous Finite-Size Scaling for Bivariate Bicycle Codes on the Quantum Erasure Channel [0.14323566945483496]
  We run both uninformed and empherasure-aware surface code baselines alongside BP-OSD decoding of BB codes.<n>With standard depolarizing-weight MWPM and no erasure information, performance matches random guessing on the erasure channel.<n>BB at $N=1296$ has a modest edge in threshold over the surface code at twice the qubit count, and a 12$times$ lower normalized overhead.
  arXiv  Detail & Related papers  (2026-03-19T15:53:51Z)
• Decoder Performance in Hybrid CV-Discrete Surface-Code Threshold Estimation Using LiDMaS+ [3.833542530785707]
  Threshold estimation is central to faulttolerant quantum computing, but the reported threshold depends not only on the code and noise model, but also on the decoder used to interpret syndrome data.<n>We study this dependence for surface-code threshold estimation under both a standard Pauli noise model and a hybrid continuous-variable/discrete model motivated by GKP-style digitization.
  arXiv  Detail & Related papers  (2026-03-06T03:33:00Z)
• Enhancing Fault-Tolerant Surface Code Decoding with Iterative Lattice Reweighting [12.330043396100635]
  We introduce the Iterative Reweighting Minimum-Weight Perfect Matching (IRMWPM) decoder.<n>We show that IRMWPM reduces logical error rates by over 20x with only a few distances.<n>It also raises the accuracy threshold from 1% to 1.16%, making it practical for near-term real-time decoding.
  arXiv  Detail & Related papers  (2025-09-08T14:45:59Z)
• $ε$-Softmax: Approximating One-Hot Vectors for Mitigating Label Noise [99.91399796174602]
  Noisy labels pose a common challenge for training accurate deep neural networks.<n>We propose $epsilon$-softmax, which modifies the outputs of the softmax layer to approximate one-hot vectors with a controllable error.<n>We prove theoretically that $epsilon$-softmax can achieve noise-tolerant learning with controllable excess risk bound for almost any loss function.
  arXiv  Detail & Related papers  (2025-08-04T13:10:48Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [84.0257274213152]
  We propose a new technique to provide accurate estimates of the DFR of a two-iterations (parallel) bit flipping decoder.<n>We validate our results, providing comparisons of the modeled and simulated weight of the syndrome, incorrectly-guessed error bit distribution at the end of the first iteration, and two-itcrypteration Decoding Failure Rates (DFR)
  arXiv  Detail & Related papers  (2024-01-30T11:40:24Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP) We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
  arXiv  Detail & Related papers  (2022-12-01T15:57:58Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Deep Q-learning decoder for depolarizing noise on the toric code [0.0]
  We present an AI-based decoding agent for quantum error correction of depolarizing noise on the toric code. The agent is trained using deep reinforcement learning (DRL), where an artificial neural network encodes the state-action Q-values of error-correcting $X$, $Y$, and $Z$ Pauli operations. We argue that the DRL-type decoder provides a promising framework for future practical error correction of topological codes.
  arXiv  Detail & Related papers  (2019-12-30T13:27:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.