Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1405.4883 · Physical Review A

Efficient algorithms for maximum likelihood decoding in the surface code

Sergey B. Bravyi, Martin Suchara, Alexander Vargo

Published Sep 25, 2014• 214 citations
arXivHTMLPDF

Abstract

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(n^2)$, 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 $χ\ge 4$.

DOI
10.1103/physreva.90.032326

Related papers

Maximum Likelihood Decoding of Quantum Error Correction Codes

Hanyan Cao, Ge Yan, Yuxuan Du +1 more

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.

quant-pharXiv:2605.17230•May 19, 2026•0 citations

Approximate maximum-likelihood decoding with K minimum weight matchings

Mao Lin

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.

arXiv:2510.06531•Physical Review A•Oct 6, 2025•0 citations

Tensor Network decoding under inter-qubit correlated errors

Yue Yan, SiYing Wang, ZhiXin Xia +3 more

The maximum likelihood decoder based on tensor networks has proven highly successful for the 2D surface code, achieving the optimal decoding success rate. However, existing tensor network decoders are typically designed for independent single-qubit error models, and their performance under inter-qubit correlated error models remains unexplored. This is due to two major challenges. The first challenge lies in constructing the tensor network for correlated errors, since the same final Pauli error can arise from many different combinations of independent and correlated errors, preventing a direct factorization of the error probability. The second challenge is that even after a tensor network is constructed, it generally contains huge-dimensional tensors and is therefore not efficiently contractible. In this work, to address the first difficulty, we introduce additional binary indices and two transformations to construct a multi-index tensor network for maximum-likelihood decoding with correlated errors. To address the second difficulty, we use reparametrization, elimination, and index classification to decompose the huge-dimensional tensors into lower-dimensional tensors. This yields an efficiently contractible tensor network for error models satisfying the tractability conditions derived in this work. We perform numerical simulations for a representative correlated error model and show that the maximum-likelihood decoder implemented with our multi-index tensor network construction achieves a higher finite-size threshold than the widely used MWPM decoder.

quant-pharXiv:2607.13570•Jul 16, 2026•0 citations

General tensor network decoding of 2D Pauli codes

Christopher T. Chubb

In this work we develop a general tensor network decoder for 2D codes. Specifically, we propose a decoder that approximates maximally likelihood decoding for 2D stabiliser and subsystem codes subject to Pauli noise. For a code consisting of $n$ qubits our decoder has a runtime of $O(n\log n+nχ^3)$, where $χ$ is an approximation parameter. We numerically demonstrate the power of this decoder by studying four classes of codes under three noise models, namely regular surface codes, irregular surface codes, subsystem surface codes and colour codes, under bit-flip, phase-flip and depolarising noise. We show that the thresholds yielded by our decoder are state-of-the-art, and numerically consistent with optimal thresholds where available, suggesting that the tensor network decoder well approximates optimal decoding in all these cases. Novel to our decoder is an efficient and effective approximate contraction scheme for arbitrary 2D tensor networks, which may be of independent interest. We have also released an implementation of this algorithm as a stand-alone Julia package: SweepContractor.jl.

arXiv:2101.04125•Jan 11, 2021•20 citations

Differentiable Maximum Likelihood Noise Estimation for Quantum Error Correction

Hanyan Cao, Dongyang Feng, Zixuan Lu +2 more

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.

quant-pharXiv:2602.19722•Feb 24, 2026•0 citations

Hypergraph-based approximate maximum likelihood decoding for quantum codes under circuit-level noise

Ke Chen, Mingzheng Zhu, H. Y. Song +2 more

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.

Physical Review Research•Apr 12, 2026•0 citations
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)O(n^2)O(n2), where nnn 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)O(nχ^3)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χ\ge 4χ≥4.
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.
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 KKK 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 KKK MWMs by systematically modifying the original decoding graph followed by finding the MWMs of the modified graphs. For the case where the XXX and ZZZ 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 KKK MWMs in the XXX and ZZZ 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 KKK increases.
The maximum likelihood decoder based on tensor networks has proven highly successful for the 2D surface code, achieving the optimal decoding success rate. However, existing tensor network decoders are typically designed for independent single-qubit error models, and their performance under inter-qubit correlated error models remains unexplored. This is due to two major challenges. The first challenge lies in constructing the tensor network for correlated errors, since the same final Pauli error can arise from many different combinations of independent and correlated errors, preventing a direct factorization of the error probability. The second challenge is that even after a tensor network is constructed, it generally contains huge-dimensional tensors and is therefore not efficiently contractible. In this work, to address the first difficulty, we introduce additional binary indices and two transformations to construct a multi-index tensor network for maximum-likelihood decoding with correlated errors. To address the second difficulty, we use reparametrization, elimination, and index classification to decompose the huge-dimensional tensors into lower-dimensional tensors. This yields an efficiently contractible tensor network for error models satisfying the tractability conditions derived in this work. We perform numerical simulations for a representative correlated error model and show that the maximum-likelihood decoder implemented with our multi-index tensor network construction achieves a higher finite-size threshold than the widely used MWPM decoder.
In this work we develop a general tensor network decoder for 2D codes. Specifically, we propose a decoder that approximates maximally likelihood decoding for 2D stabiliser and subsystem codes subject to Pauli noise. For a code consisting of nnn qubits our decoder has a runtime of O(nlog⁡n+nχ3)O(n\log n+nχ^3)O(nlogn+nχ3), where χχχ is an approximation parameter. We numerically demonstrate the power of this decoder by studying four classes of codes under three noise models, namely regular surface codes, irregular surface codes, subsystem surface codes and colour codes, under bit-flip, phase-flip and depolarising noise. We show that the thresholds yielded by our decoder are state-of-the-art, and numerically consistent with optimal thresholds where available, suggesting that the tensor network decoder well approximates optimal decoding in all these cases. Novel to our decoder is an efficient and effective approximate contraction scheme for arbitrary 2D tensor networks, which may be of independent interest. We have also released an implementation of this algorithm as a stand-alone Julia package: SweepContractor.jl.
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.
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.