Wednesday, February 13, 2013

1302.2669 (Adrian Hutter et al.)

An efficient decoding algorithm for stabilizer codes    [PDF]

Adrian Hutter, James R. Wootton, Daniel Loss
To date, the best classical algorithm for performing error correction in the surface code has been minimum-weight perfect matching. However, in this work we present a Markov chain Monte Carlo algorithm that achieves significantly lower logical error rates. It therefore allows any target logical error rate to be obtained using a significantly smaller code. This increase in performance does come at the cost of an increased runtime complexity, but only by a polynomial factor $O(L^\eps)$ for $\eps<2$. Our algorithm is based on an analytically exact rewriting of the probability of each logical equivalence class, which also suggests that for arbitrary stabilizer codes error correction can be performed to arbitrary accuracy in a runtime $O(\m{poly}(L))$. It is applicable to any stabilizer code, allows for parallelization, and can be used to correct in the case of imperfect stabilizer measurements.
View original: http://arxiv.org/abs/1302.2669

No comments:

Post a Comment