Fast decoder for local quantum codes using Groebner basis*

Based on arXiv:1204.1063. A local translation-invariant quantum code has a description in terms of Laurent polynomials. As an application of this observation, we present a fast decoding algorithm for translation-invariant local quantum codes in {\em any} spatial dimensions using the straightforward division algorithm for multivariate polynomials. The running time is $O(n \log n)$ on average, or $O(n^2 \log n)$ on worst cases, where $n$ is the number of physical qubits. The algorithm improves a subroutine of the renormalization-group decoder by Bravyi and Haah (arXiv:1112.3252) in the translation-invariant case.