Efficient Algorithms for Maximum Likelihood Decoding in the Surface Code

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

18 pages, 12 figures

References in corpus (8)

• The density-matrix renormalization group in the age of matrix product states
• Surface codes: Towards practical large-scale quantum computation
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
• Quantum computing with nearest neighbor interactions and error rates over 1%
• Error Threshold for Color Codes and Random 3-Body Ising Models
• Optimal and Efficient Decoding of Concatenated Quantum Block Codes
• Surface code with decoherence: An analysis of three superconducting architectures