# Efficient algorithms for maximum likelihood decoding in the surface code

Article · Sergey B. Bravyi, Martin Suchara, Alexander Vargo

- Archive id: arxiv:1405.4883
- Published: 2014-09-25
- Venue: Physical Review A
- DOI: https://doi.org/10.1103/physreva.90.032326
- arXiv: https://arxiv.org/abs/1405.4883
- Citations: 214
- Source URL: https://doi.org/10.1103/physreva.90.032326
- PDF: https://arxiv.org/pdf/1405.4883
- Provenance: openalex+arxiv

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

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Quantum Error Correction & Fault Tolerance](https://space-kitty.com/topics/quantum-error-correction)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.