# Efficient Algorithms for Maximum Likelihood Decoding in the Surface Code

@article{Bravyi2014EfficientAF, title={Efficient Algorithms for Maximum Likelihood Decoding in the Surface Code}, author={Sergey Bravyi and Martin Suchara and Alexander Vargo}, journal={Physical Review A}, year={2014}, volume={90} }

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… Expand

#### Figures and Tables from this paper

#### 82 Citations

Almost-linear time decoding algorithm for topological codes

- Mathematics, Physics
- 2017

In order to build a large scale quantum computer, one must be able to correct errors extremely fast. We design a fast decoding algorithm for topological codes to correct for Pauli errors and erasure… Expand

Analysing correlated noise on the surface code using adaptive decoding algorithms

- Computer Science, Physics
- Quantum
- 2019

New methods to analyse blue a particular class of spatially correlated errors by making use of parametrised families of decoding algorithms and it is shown that information can be learnt about the parameters of the noise model, and additionally that the logical error rates can be improved. Expand

General tensor network decoding of 2D Pauli codes

- Physics
- 2021

In this work we develop a general tensor network decoder for 2D codes. Specifically we propose a decoder which approximates maximally likelihood decoding for 2D stabiliser and subsystem codes subject… Expand

Statistical mechanical models for quantum codes with correlated noise

- Mathematics, Physics
- 2018

We give a broad generalisation of the mapping, originally due to Dennis, Kitaev, Landahl and Preskill, from quantum error correcting codes to statistical mechanical models. We show how the mapping… Expand

Multi-path Summation for Decoding 2D Topological Codes

- Physics, Computer Science
- Quantum
- 2018

This work uses belief propagation and a novel algorithm for producing edge weights to increase the utility of minimum-weight perfect matching for decoding surface codes, and obtains a threshold of 17.76±0.02%. Expand

The XZZX surface code

- Computer Science, Physics
- 2020

Focusing on the common situation where qubit dephasing is the dominant noise, a variant of the surface code—the XZZX code—is shown to have remarkable performance for fault-tolerant quantum computation and the error threshold matches what can be achieved with random codes for every single-qubit Pauli noise channel. Expand

Quantum error correction for the toric code using deep rein- forcement learning

- 2019

We implement a quantum error correction algorithm for bit-flip errors on the topological toric code using deep reinforcement learning. An action-value Q-function encodes the discounted value of… Expand

The surface code with a twist

- Computer Science, Physics
- 2016

A patch-based encoding involving a modified twist of defect-based logical encodings of a new variety called twists is investigated, and the smallest triangle code can demonstrate high-pseudothreshold fault-tolerance to depolarizing noise using just 13 physical qubits. Expand

Machine-learning-assisted correction of correlated qubit errors in a topological code

- Computer Science, Physics
- 2017

It is shown that a recurrent neural network can be trained, using only experimentally accessible data, to detect errors in a widely used topological code, the surface code, with a performance above that of the established minimum-weight perfect matching (or blossom) decoder. Expand

Ultrahigh Error Threshold for Surface Codes with Biased Noise.

- Physics, Medicine
- Physical review letters
- 2018

It is shown that a simple modification of the surface code can exhibit an enormous gain in the error correction threshold for a noise model in which Pauli Z errors occur more frequently than X or Y errors, and that large efficiency gains can be found by appropriately tailoring codes and decoders to realistic noise models, even under the locality constraints of topological codes. Expand

#### References

SHOWING 1-10 OF 35 REFERENCES

Threshold error rates for the toric and surface codes

- Mathematics, Physics
- 2009

The surface code scheme for quantum computation features a 2d array of nearest-neighbor coupled qubits yet claims a threshold error rate approaching 1% (NJoP 9:199, 2007). This result was obtained… Expand

Optimal and efficient decoding of concatenated quantum block codes

- Physics
- 2006

We consider the problem of optimally decoding a quantum error correction code—that is, to find the optimal recovery procedure given the outcomes of partial "check" measurements on the system. In… Expand

Efficient Markov chain Monte Carlo algorithm for the surface code

- Physics
- 2014

Minimum-weight perfect matching (MWPM) has been the primary classical algorithm for error correction in the surface code, since it is of low runtime complexity and achieves relatively low logical… Expand

Optimal complexity correction of correlated errors in the surface code

- Mathematics, Physics
- 2013

Centre for Quantum Computation and Communication Technology,School of Physics, The University of Melbourne, Victoria 3010, Australia(Dated: December 16, 2013)The surface code is designed to suppress… Expand

Simulation of rare events in quantum error correction

- Physics
- 2013

We consider the problem of calculating the logical error probability for a stabilizer quantum code subject to random Pauli errors. To access the regime of large code distances where logical errors… Expand

Topological quantum memory

- Physics
- 2002

We analyze surface codes, the topological quantum error-correcting codes introduced by Kitaev. In these codes, qubits are arranged in a two-dimensional array on a surface of nontrivial topology, and… Expand

Surface codes: Towards practical large-scale quantum computation

- Physics
- 2012

This article provides an introduction to surface code quantum computing. We first estimate the size and speed of a surface code quantum computer. We then introduce the concept of the stabilizer,… Expand

Fast decoders for topological quantum codes.

- Computer Science, Medicine
- Physical review letters
- 2010

A family of algorithms is presented, combining real-space renormalization methods and belief propagation, to estimate the free energy of a topologically ordered system in the presence of defects, which achieves a higher depolarizing error threshold. Expand

Implementing a strand of a scalable fault-tolerant quantum computing fabric.

- Physics, Medicine
- Nature communications
- 2014

High-fidelity parity detection of two code qubits via measurement of a third syndrome qubit is demonstrated and a measurement tomography protocol is developed to fully characterize this parity readout. Expand

Error threshold for color codes and random three-body Ising models.

- Physics, Medicine
- Physical review letters
- 2009

The error threshold of color codes, a class of topological quantum codes that allow a direct implementation of quantum Clifford gates suitable for entanglement distillation, teleportation, and fault-tolerant quantum computation, is studied, showing that enhanced computational capabilities do not necessarily imply lower resistance to noise. Expand