2014/05/19 by Sergey Bravyi, Martin Suchara, Alexander Vargo · 3 citations
Physics and Astronomy · #quant-ph
paper · pdf · doi:10.1103/physreva.90.032326
published as Phys. Rev. A 90, 032326 (2014) · 18 pages, 12 figures
arxiv created 2014/05/19 · arxiv updated 2014/10/01
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), 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 χ≥ 4.