I have been reading Delfosse's "Almost-linear time decoding algorithm for topological codes" and I understand how to perform syndrome validation and the posterior erasure decoding in toric codes. Nevertheless, I do not understand how this can work in non-periodic surface codes such as rotated planar codes. Since the Union-Find erasure decoder consists in using the information of the non-trivial syndrome elements in order to find the error-chains, if an error chain finishes on certain boundaries of the rotated planar code, one of the two error-chain boundaries can be missing.

An idea which comes to my mind is using the same tactic adopted by the Minimum Weight Perfect Matching decoder, which consists in considering additional checks adjacent to the boundary of the rotated planar code. These checks would be considered as additional non-trivial syndrome elements, thus affecting the parity of the clusters at which they are involved. Nevertheless, this consideration prevents the use of the erasure decoder.

Consider the plots of the slide:

(1) A rotated planar code experiences an error and, upon measurement, the code outcomes a syndrome.

(2-4) A cluster is produced and grows until it reaches even parity (recall that non-trivial syndrome elements have odd parity and so do the additional boundary checks).

Performing the erasure decoder on the final cluster (4) will not return the maximum likelihood error. I have been looking for a possible answer to this question but have not found anything. Is there an answer? Where could I read about it?

Thank you for your help in advance.

(1) An <span class=$X$-error affects a 3x3 rotated planar code." />

(2) First cluster growth from one of the triggered checks denoted with red lines.

(3)Second cluster growth, denoted with purple lines.

(4)Third and last cluster growth.


1 Answer 1


recall that non-trivial syndrome elements have odd parity and so do the additional boundary checks

This is your mistake. Boundary nodes are not excited nodes.

A cluster grows until it contains an even number of excitations or touches a boundary. As soon as a cluster touches a boundary, it is frozen forever. And anything that touches that cluster also becomes frozen forever. This is very different from treating the boundary nodes as being excited.

The decoding graph has three types of nodes: normal, excited, and boundary. Your goal is to find a set of edges E such that every normal node is adjacent to an even number of edges from E, every excited edge is adjacent to an odd number of edges from E, and boundary nodes can be adjacent to any number of edges from E. Boundary nodes behave very differently from excited nodes.

In picture form, from https://arxiv.org/abs/2303.15933:

enter image description here

  • $\begingroup$ Thank you for your help. Nevertheless I have an additional question, when you reach the cluster, which occurs when either the parity is even or it freezes, how do you decode it? The erasure decoder described in UnionFind does not consider boundary nodes. $\endgroup$ Commented Mar 31, 2023 at 20:40
  • $\begingroup$ Once all clusters have stopped growing, they are decoded by peeling their spanning trees. In this case you treat the boundary node to have odd parity if the net parity of the fully-grown cluster is odd. $\endgroup$
    – ChrisD
    Commented Mar 31, 2023 at 22:56
  • $\begingroup$ @AntonideMarti Use the method described in the appendix of the paper I linked in my answer. $\endgroup$ Commented Apr 1, 2023 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.