Decoding the Toric Code

Topological codes have been used in recent years in an attemp to build fault-tolerant quantum memories. Decoding this code, i.e. determining the optimal recovery operation given the error syndrome, is a computationally difficult task. During this talk I will suggest a new classical algorithm to decode the toric code. Up until now, the best algorithm was accepted to be the Edmond algorithm wich finds the most likely physical error, i.e. ignoring the code's degeneracy. The new approach is to approximate the most likely logical error. This new algorithm has been inspired by generalized belief propagation techniques and renormalisation-like techniques. The threshold of this algorithm on the depolarizing channel was established at around 11% against 15.5% for Edmond's. However, the main advantage of this technique is that the computational cost scales like nlog n (n is the number of qubits in the code) parallelizable down to log n while Edmond's scales like n^3.