{
  "id": "1405.4883",
  "version": "v1",
  "published": "2014-05-19T20:33:08.000Z",
  "updated": "2014-05-19T20:33:08.000Z",
  "title": "Efficient Algorithms for Maximum Likelihood Decoding in the Surface Code",
  "authors": [
    "Sergey Bravyi",
    "Martin Suchara",
    "Alexander Vargo"
  ],
  "comment": "18 pages, 12 figures",
  "categories": [
    "quant-ph"
  ],
  "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\\chi^3)$ where $\\chi$ 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 $\\chi$ 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 $\\chi\\ge 4$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-05-19T20:33:08.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03.67.Lx",
      "03.67.Pp"
    ],
    "keywords": [
      "surface code",
      "maximum likelihood decoding",
      "efficient algorithms",
      "weight matching decoder observing",
      "noise model"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "doi": "10.1103/PhysRevA.90.032326",
      "journal": "Physical Review A",
      "year": 2014,
      "month": "Sep",
      "volume": 90,
      "number": 3,
      "pages": "032326"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014PhRvA..90c2326B"
    }
  }
}