Fault-tolerant quantum computing requires classical hardware to perform the decoding necessary for error correction. The Union–Find decoder is one of the best candidates for this. It has remarkably organic characteristics, involving the growth and merger of data structures through nearest-neighbour steps; this naturally suggests the possibility of its realisation using a lattice of simple processors with nearest-neighbour links. In this way the computational load can be distributed with near-ideal parallelism. Here we show for the first time that this strict (rather than partial) locality is practical, with a worst-case runtime $\mathcal O(d^3)$ and mean runtime subquadratic in the surface code distance $d$. A novel parity-calculation scheme is employed which can simplify previously proposed architectures, and our approach is optimised for circuit-level noise. We compare our local realisation with one augmented by long-range links; while the latter is of course faster, we note that local asynchronous logic could negate the difference.
 Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland. ``Surface codes: Towards practical large-scale quantum computation''. Physical Review A 86, 032324 (2012).
 Austin G. Fowler, Adam C. Whiteside, and Lloyd C. L. Hollenberg. ``Towards practical classical processing for the surface code''. Physical Review Letters 108, 180501 (2012).
 Guillaume Duclos-Cianci and David Poulin. ``Fast decoders for topological quantum codes''. Physical Reviw Letters 104, 050504 (2010).
 Guillaume Duclos-Cianci and David Poulin. ``A renormalization group decoding algorithm for topological quantum codes''. In 2010 IEEE Information Theory Workshop. Pages 1–5. (2010).
 James R. Wootton and Daniel Loss. ``High threshold error correction for the surface code''. Physical Review Letters 109, 160503 (2012).
 Oscar Higgott, Thomas C. Bohdanowicz, Aleksander Kubica, Steven T. Flammia, and Earl T. Campbell. ``Improved decoding of circuit noise and fragile boundaries of tailored surface codes''. Physical Review X 13, 031007 (2023).
 Oscar Higgott and Nikolas P. Breuckmann. ``Improved single-shot decoding of higher-dimensional hypergraph-product codes''. PRX Quantum 4, 020332 (2023).
 Milap Sheth, Sara Zafar Jafarzadeh, and Vlad Gheorghiu. ``Neural ensemble decoding for topological quantum error-correcting codes''. Physical Review A 101, 032338 (2020).
 Ramon W. J. Overwater, Masoud Babaie, and Fabio Sebastiano. ``Neural-network decoders for quantum error correction using surface codes: A space exploration of the hardware cost-performance tradeoffs''. IEEE Transactions on Quantum Engineering 3, 1–19 (2022).
 Kai Meinerz, Chae-Yeun Park, and Simon Trebst. ``Scalable neural decoder for topological surface codes''. Physical Review Letters 128, 080505 (2022).
 Gokul Subramanian Ravi, Jonathan M. Baker, Arash Fayyazi, Sophia Fuhui Lin, Ali Javadi-Abhari, Massoud Pedram, and Frederic T. Chong. ``Better than worst-case decoding for quantum error correction''. In Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2. Pages 88–102. New York, NY, USA (2023). Association for Computing Machinery.
 Samuel C. Smith, Benjamin J. Brown, and Stephen D. Bartlett. ``Local predecoder to reduce the bandwidth and latency of quantum error correction''. Physical Review Applied 19, 034050 (2023).
 Nicolas Delfosse and Gilles Zémor. ``Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel''. Physical Review Research 2, 033042 (2020).
 Michael A. Nielsen and Isaac L. Chuang. ``Quantum computation and quantum information: 10th anniversary edition''. Cambridge University Press. (2010).
 Luka Skoric, Dan E. Browne, Kenton M. Barnes, Neil I. Gillespie, and Earl T. Campbell. ``Parallel window decoding enables scalable fault tolerant quantum computation''. Nature Communications 14, 7040 (2023).
 Shui Hu. ``Quasilinear time decoding algorithm for topological codes with high error threshold''. Master's thesis. Delft University of Technology. (2020).
 Oscar Higgott. ``PyMatching: A Python package for decoding quantum codes with minimum-weight perfect matching''. ACM Transactions on Quantum Computing 3, 1–16 (2022).
 Shilin Huang, Michael Newman, and Kenneth R. Brown. ``Fault-tolerant weighted union-find decoding on the toric code''. Physical Review A 102, 012419 (2020).
 L. M. K. Vandersypen, H. Bluhm, J. S. Clarke, A. S. Dzurak, R. Ishihara, A. Morello, D. J. Reilly, L. R. Schreiber, and M. Veldhorst. ``Interfacing spin qubits in quantum dots and donors—–hot, dense, and coherent''. npj Quantum Information 3, 34 (2017).
 Ben Barber, Kenton M. Barnes, Tomasz Bialas, Okan Buğdaycı, Earl T. Campbell, Neil I. Gillespie, Kauser Johar, Ram Rajan, Adam W. Richardson, Luka Skoric, Canberk Topal, Mark L. Turner, and Abbas B. Ziad. ``A real-time, scalable, fast and highly resource efficient decoder for a quantum computer'' (2023). arXiv:2309.05558.
 David S. Wang, Austin G. Fowler, and Lloyd C. L. Hollenberg. ``Surface code quantum computing with error rates over 1%''. Physical Review A 83, 020302 (2011).
 Austin G. Fowler, Adam C. Whiteside, and Lloyd C. L. Hollenberg. ``Towards practical classical processing for the surface code: Timing analysis''. Physical Review A 86, 042313 (2012).
The above citations are from SAO/NASA ADS (last updated successfully 2023-12-07 02:47:22). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref's cited-by service no data on citing works was found (last attempt 2023-12-07 02:47:19).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.