Maximum likelihood decoding (MLD) achieves optimal accuracy but is computationally infeasible for large-distance codes. Tensor-network-based MLD (TN-MLD) improves efficiency but has so far only been shown to work for small-distance surface codes. We introduce a hypergraph-based approximate MLD (HAMLD) that enables more efficient decoding of more general codes under circuit-level noise. Unlike TN-MLD, our HAMLD employs syndrome-guided hyperedge selection and probability-based truncation to reduce redundant computation. We benchmarked our approach on surface codes, color codes, and bivariate-bicycle (BB) codes under a circuit-level noise model. Numerical results demonstrate that HAMLD can decode BB codes with hundreds of qubits, which MLD and TN-MLD cannot handle. For a surface code with distance and repetition rounds both equal to 3, HAMLD achieves optimal decoding accuracy while being about 323 × faster than MLD and about 551 × faster than TN-MLD. HAMLD also achieves higher accuracy than common decoders—minimum-weight perfect matching, Chromobius, and BP + OSD —in the two smallest parameter settings we considered, reducing logical error rates by an average of 27.8% for surface codes, 58.5% for color codes, and 74.4% for BB codes through degeneracy-aware and precise hypergraph selection.
Maximum likelihood decoding (MLD) achieves optimal accuracy but is computationally infeasible for large-distance codes. Tensor-network-based MLD (TN-MLD) improves efficiency but has so far only been shown to work for small-distance surface codes. We introduce a hypergraph-based approximate MLD (HAMLD) that enables more efficient decoding of more general codes under circuit-level noise. Unlike TN-MLD, our HAMLD employs syndrome-guided hyperedge selection and probability-based truncation to reduce redundant computation. We benchmarked our approach on surface codes, color codes, and bivariate-bicycle (BB) codes under a circuit-level noise model. Numerical results demonstrate that HAMLD can decode BB codes with hundreds of qubits, which MLD and TN-MLD cannot handle. For a surface code with distance and repetition rounds both equal to 3, HAMLD achieves optimal decoding accuracy while being about 323 × faster than MLD and about 551 × faster than TN-MLD. HAMLD also achieves higher accuracy than common decoders—minimum-weight perfect matching, Chromobius, and BP + OSD —in the two smallest parameter settings we considered, reducing logical error rates by an average of 27.8% for surface codes, 58.5% for color codes, and 74.4% for BB codes through degeneracy-aware and precise hypergraph selection.
We describe two implementations of the optimal error correction algorithm known as the maximum likelihood decoder (MLD) for the 2D surface code with a noiseless syndrome extraction. First, we show how to implement MLD exactly in time O(n2), where n is the number of code qubits. Our implementation uses a reduction from MLD to simulation of matchgate quantum circuits. This reduction however requires a special noise model with independent bit-flip and phase-flip errors. Secondly, we show how to implement MLD approximately for more general noise models using matrix product states (MPS). Our implementation has running time O(nχ3) where χ is a parameter that controls the approximation precision. The key step of our algorithm, borrowed from the DMRG method, is a subroutine for contracting a tensor network on the two-dimensional grid. The subroutine uses MPS with a bond dimension χ to approximate the sequence of tensors arising in the course of contraction. We benchmark the MPS-based decoder against the standard minimum weight matching decoder observing a significant reduction of the logical error probability for χ≥4.
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.
Accurate and efficient decoding is a crucial component for achieving fault-tolerant quantum computing. Realistic circuit-level noise introduces temporal correlations and degeneracy, making optimal (maximum-likelihood) decoding computationally intractable in general. As a result, practical decoders rely on heuristic approximations, and it is generally difficult to quantify how suboptimal they are, as this strongly depends on the code and noise model considered. In this work, we study the accuracy of practical decoding algorithms under circuit-level noise by comparing them against a maximum likelihood decoding benchmark. Our approach propagates the density matrix through the full memory experiment and computes the optimal decoding decision for each syndrome history. We introduce pruning techniques with rigorous bounds, allowing us to access larger numbers of syndrome-extraction rounds. We apply this framework to small instances of the repetition code and a cellular automaton code, and benchmark minimum-weight perfect matching (MWPM), belief propagation with ordered statistics decoding (BP+OSD), Tesseract, and Planar decoders against optimal decoding. While standard decoders remain close to optimal for the repetition code, we find significant deviations for the cellular automaton code, with BP+OSD deteriorating already in experimentally relevant noise regimes. Moreover, the pruning method developed here highlights that, at low physical error rates, only a narrow fraction of syndrome histories contributes significantly to the logical error rate.
Accurate noise estimation is essential for fault-tolerant quantum computing, since decoding per formance depends critically on the fidelity of circuit-level noise parameters. We introduce a differ entiable Maximum Likelihood Estimation (dMLE) framework that learns these parameters directly from experimental syndrome data using likelihood gradients, with no decoder in the training loop. Mapping syndrome likelihoods to statistical-mechanical models enables exact and efficient evalua tion via planar solvers for repetition codes and tensor networks (TNs) for surface codes, extending the exact treatment to code distance d = 5 with a small number of rounds, and, via spatial subsam pling combined with time-translation symmetry, to larger codes and larger round counts. Across four experimental superconducting datasets, dMLE reduces logical error rates by up to 30.6% for repetition codes. On the Sycamore d = 3 surface code, a TN decoder using the dMLE prior attains a logical error rate comparable to that reported for state-of-the-art AlphaQubit, using standard syndromes alone without auxiliary leakage data. On the larger d = 5 surface code the dMLE prior lowers the logical error rate of the TN and Tesseract decoders by 7.18% and 5.23% relative to a prior optimized by reinforcement learning; at d = 7 it lowers that of Tesseract by 4.56% and 4.83% in the X and Z bases.
Minimum weight matching (MWM) and maximum likelihood decoding (MLD) are two widely used and distinct decoding strategies for quantum error correction. For a given syndrome, the MWM decoder finds the most probable physical error corresponding to the MWM of the decoding graph, whereas MLD aims to find the most probable logical error. Although MLD is the optimal error correction strategy, it is typically more computationally expensive compared to the MWM decoder. In this work, we introduce an algorithm that approximates MLD with K MWMs from the decoding graph. Taking the surface code subject to graphlike errors as an example, we show that it is possible to efficiently find the first K MWMs by systematically modifying the original decoding graph followed by finding the MWMs of the modified graphs. For the case where the X and Z errors are correlated, despite the fact that the MWM of the decoding hypergraph cannot be found efficiently, we present a heuristic approach to approximate the MLD by finding the K MWMs in the X and Z subgraphs. We benchmark the efficacy of our algorithm for the surface code subject to graphlike errors as well as the surface-square Gottesman-Kitaev-Preskill (GKP) code and surface-hexagonal GKP code subject to the Gaussian random displacement errors, showing that the fidelity approaches that of the exact MLD (for the first two cases) or the tensor-network decoder (for the last case) as K increases.
Quantum error correction (QEC) is indispensable for realizing fault-tolerant quantum computation, yet its effectiveness hinges critically on the classical decoding algorithm that interprets noisy syndrome measurements. Among all possible decoding strategies, maximum likelihood decoding (MLD) is provably optimal, since it identifies the logical group with largest likelihood by summing over all possible errors within logical class consistent with the observed syndrome. Despite its optimality, MLD is computationally intractable in general (#P-hard), motivating a rich landscape of exact and approximate algorithms. In this topical review, we provide a unified perspective on MLD by surveying recent advances through three complementary lenses: statistical mechanics, tensor networks, and artificial intelligence. From the statistical mechanics viewpoint, the MLD problem maps onto evaluating partition functions of disordered spin models, enabling exact solutions for certain codes and noise models as well as threshold estimation via phase-transition analysis. From the tensor network perspective, approximate contraction of tensor networks on the code's factor graph yields decoders that closely approach MLD accuracy with polynomial computational cost. From the artificial intelligence perspective, neural-network-based decoders, including autoregressive generative models and recurrent transformers, learn to approximate the MLD distribution from data, achieving high accuracy with the parallelism afforded by modern hardware accelerators. We discuss the connections among these three approaches, review their application to both simulated and experimental quantum hardware, and outline open challenges including real-time decoding, scalability to large code distances, and generalization to high-rate quantum low-density parity-check codes.