CoChat
Sign Up
Cited by 214Quantum Computing Algorithms and ArchitectureQuantum many-body systemsQuantum Information and Cryptography

Efficient algorithms for maximum likelihood decoding in the surface code

Open access
Bravyi, Sergey, Suchara, Martin, Vargo, Alexander·2014·Physical Review A
DOI 10.1103/physreva.90.032326
Open this paper in CoChat — free accountOpen PDF

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$.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1103/physreva.90.032326

Cites

3 of 3 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Tensor network (TN) decoders are among the most powerful known decoding methods, achieving very high accuracy by directly approximating DMLD.

    “Tensor network (TN) decoders are among the most powerful known decoding methods, achieving very high accuracy by directly approximating DMLD [199–201].”

    From Quantum error correction and fault tolerance: A comprehensive tutorial (2026) · cites this paper as [200]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 20

  1. [14]L. Valiant. Quantum circuits that can be simulated classically in polynomial time. SIAM J. on Comp. , 31(4):1229-1254, 2002.
  2. [15]L. Valiant. Holographic algorithms. SIAM J. on Comp. , 37(5):1565-1594, 2008.
  3. [16]J.-Y. Cai and V. Choudhary. Valiant's Holant theorem and matchgate tensors. In Theory and applications of models of computation , pages 248-261. Springer, 2006.
  4. [18]E. Knill. Fermionic linear optics and matchgates. arXiv preprint quant-ph/0108033 , 2001. · arXiv
  5. [19]B. M. Terhal and D. P. DiVincenzo. Classical simulation of noninteracting-fermion quantum circuits. Phys. Rev. A , 65(3):032325, 2002.
  6. [20]M. E. Fisher. Statistical mechanics of dimers on a plane lattice. Phys. Rev. , 124(6):1664, 1961.
  7. [21]P. W. Kasteleyn. The statistics of dimers on a lattice: I. the number of dimer arrangements on a quadratic lattice. Physica , 27(12):1209-1225, 1961.
  8. [22]H. Temperley and M. Fisher. Dimer problem in statistical mechanics - an exact result. Philosophical Magazine , 6(68):1061-1063, 1961.
  9. [23]S. Bravyi. Lagrangian representation for fermionic linear optics. Quant. Inf. and Comp. , 5(3):216-238, 2005.
  10. [24]F. Merz and J. Chalker. Two-dimensional random-bond Ising model, free fermions, and the network model. Phys. Rev. B , 65(5):054425, 2002.
  11. [25]G. Vidal. Efficient classical simulation of slightly entangled quantum computations. Phys. Rev. Lett. , 91(14):147902, 2003.
  12. [26]F. Verstraete and J. I. Cirac. Renormalization algorithms for quantum-many body systems in two and higher dimensions. arXiv preprint cond-mat/0407066 , 2004. · arXiv
  13. [27]V. Murg, F. Verstraete, and J.I. Cirac. Variational study of hard-core bosons in a two-dimensional optical lattice using projected entangled pair states. Phys. Rev. A , 75(3):033605, 2007.
  14. [28]F. Verstraete, V. Murg, and J. I. Cirac. Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems. Adv. Phys. , 57(2):143-224, 2008.
  15. [29]U. Schollw¨ ock. The density-matrix renormalization group in the age of matrix product states. Ann. of Phys. , 326(1):96-192, 2011.
  16. [31]D. Wang, A. Fowler, and L. Hollenberg. Surface code quantum computing with error rates over 1%. Phys. Rev. A , 83(2):020302, 2011.
  17. [32]T. Stace and S. Barrett. Error correction and degeneracy in surface codes suffering loss. Phys. Rev. A , 81(2):022317, 2010.
  18. [33]A. Fowler. Optimal complexity correction of correlated errors in the surface code. arXiv preprint arXiv:1310.0863 , 2013. · arXiv
  19. [34]S. Bravyi and A. Vargo. Simulation of rare events in quantum error correction. Phys. Rev. A , 88(6):062308, 2013.
  20. [35]C. Wang, J. Harrington, and J. Preskill. ConfinementHiggs transition in a disordered gauge theory and the accuracy threshold for quantum memory. Ann. of Phys. , 303(1):31-58, 2003.

Cited by

Sorted by citations

Authors
Bravyi, S., Suchara, M., & Vargo, A.
Affiliations
IBM Research - Thomas J. Watson Research Center (US)
ORCID
Venue
Physical Review A
Publisher
American Physical Society (APS)
Published
2014-09-25
Volume
90
Issue
3
ISSN
  • 0556-2791 (ISSN-L)
  • 1050-2947
  • 1094-1622
DOI
10.1103/physreva.90.032326
OpenAlex
W2075431083
Cited by
214
References
3
Citations by year
2026: 14 · 2025: 39 · 2024: 31 · 2023: 21 · 2022: 24 · 2021: 21 · 2020: 19 · 2019: 16 · 2018: 10 · 2017: 9 · 2016: 3 · 2015: 5 · 2014: 2
FWCI
6.31
Type
journal article
Language
en
Open access
Licence
link.aps.org/licenses/aps-default-license (vor)
Locations
  • Physical Review A (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
National Science Foundation (CCF-1110941)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
Keywords
maximum likelihood decoding, surface code, quantum error correction, matrix product states, tensor network contraction, density matrix renormalization group, bond dimension

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review