Fast decoder for local quantum codes using Groebner basis
ORAL
Abstract
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.
*This work is supported in part by the Insitute for Quantum Information and Matter, an NSF Physics Frontier Center, and the Korea Foundation for Advanced Studies.
–