Towards practical classical processing for the surface code: Timing analysis

Topological quantum error-correction codes have high thresholds and are well suited to physical implementation. The minimum-weight perfect-matching algorithm can be used to efficiently handle errors in such codes. We perform a timing analysis of our current implementation of the minimum-weight perfect-matching algorithm. Our implementation performs the classical processing associated with an n x n lattice of qubits realizing a square surface code storing a single logical qubit of information in a fault-tolerant manner. We empirically demonstrate that our implementation requires only O(n(2)) average time per round of error correction for code distances ranging from 4 to 512 and a range of depolarizing error rates. We also describe tests we have performed to verify that it always obtains a true minimum-weight perfect matching.