## 3 The Decoding Algorithm  
The job of a decoding algorithm is to find a correction operator to neutralize the syndrome. This means that it must return the state of the code to one with trivial syndrome. In addition, the correction operator should also undo the effects of errors on the stored logical information. It is not possible to do this with unit probability. It can be done with high probability, with an exponential decay of failure rate with system size, but the success will depend greatly on the design of the decoder.  
Ideally a decoder will perform a global optimization process to find the correction operator that is most likely to succeed, given the syndrome. However, such methods are never simple. An alternative is to start looking for patches of syndrome at small length scales that can be neutralized independently of the rest. Once all of the syndrome that can be dealt with at this scale is corrected, higher and higher scales can be considered until all of the syndrome is neutralized. Decoders that use this kind of iterative method are called HDRG decoders. See [5] for a general definition, and discussion of examples.  
For the planar code, the syndrome is made up of anyons. These are created in pairs by strings of bit flip errors. Any pair of anyons can therefore be neutralized independently of the rest of the syndrome, with a string of bit flips serving as the required correction operator. Single anyons can also be neutralized by pairing them with an edge. Ideally the pairing used by correction is the same as that for creation, with the anyons annihilated in the pairs they were created in. It is not possible to do this perfectly, due to ambiguities in the syndrome information. However, we can instead aim to do it with high probability. As long as this results in the right parity (odd or even) for the number of anyons pairing with each edge, the correction of the logical information will succeed.  
The decoder is designed to find pairs of anyons are likely to have been created by the same error string. The probability of this decays exponentially with their separation. As such, anyons that are mutual nearest neighbours will be a good candidate. The decoder therefore finds and pairs such mutual nearest neighbours. The method used to do this is as follows.  
1. Loop through all plaquettes to find anyons.
2. For each anyon, search through all plaquettes at a Manhattan distance of \(k\), using \(k=1\) initially.  
3. If either an anyon or the edge is found at this distance, pair them. Annihilate the anyons by performing bit flips on the connecting qubits. If there are multiple possibilities at this distance, pair with the first found.
4. If there are still anyons present, repeat the process for \(k=k+1\).  
Once all the anyons are removed, the total pattern of bit flips used to remove them is considered. The correction procedure is a success if this belongs to the same equivalence class as the pattern of bit flips that occurred in error. Otherwise, the correction procedure results in a logical error.  
An upper bound for the run time in the worst case scenario can be easily determined. The \(k\)-th iteration requires \(O(k)\) plaquettes to be searched per anyon. The number of anyons present during each iteration is at most \(O(L^{2})\). There will be no more than \(L\) iterations since no anyon is more than this distance from the edge. The total complexity is then never more than \(O(\sum_{k=1}^{L}kL^{2})=O(L^{4})\). This upper bound on the complexity is clearly polynomial with system size, and a moderately low ordered polynomial also. The algorithm therefore allows for fast and efficient decoding.