Actis: A Strictly Local Union–Find Decoder

Actis: A Strictly Local Union–Find Decoder

Time Stamp: November 14, 2023 6:58 AM
Source Node: 2382796

Tim Chan1 and Simon C. Benjamin1,2

1Department of Materials, University of Oxford, Parks Road, Oxford OX1 3PH, United Kingdom
2Quantum Motion, 9 Sterling Way, London N7 9HJ, United Kingdom

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

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.

Featured image: The network used for controller–node communication in Actis for a distance-3 surface code. This tree is similar to the decoding graph for circuit-level noise.

Popular summary

Quantum computers have the potential to offer groundbreaking computational power, but only if protected from noise. This is done via error correction: a way to exchange many noisy qubits (units of computation) for fewer but more perfect qubits. The crucial subtask of monitoring measurements from the quantum processor to deduce when errors have occurred is called decoding. This must be performed extremely quickly in order to keep pace with the quantum machine. Here we modify an existing decoding algorithm to make it local i.e. runnable on a grid of identical processing cells, each communicating only with their nearest neighbours. Locality has various practical benefits in speed, layout and robustness. We test our local design and find that its runtime indeed behaves more favourably than the original algorithm; we then suggest the use of ‘asynchronous’ hardware to maximise our design’s absolute performance.

► BibTeX data

► References

[1] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. “Topological quantum memory”. Journal of Mathematical Physics 43, 4452–4505 (2002).
https:/​/​doi.org/​10.1063/​1.1499754

[2] 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).
https:/​/​doi.org/​10.1103/​PhysRevA.86.032324

[3] Daniel Litinski. “A game of surface codes: Large-scale quantum computing with lattice surgery”. Quantum 3, 128 (2019).
https:/​/​doi.org/​10.22331/​q-2019-03-05-128

[4] Jack Edmonds. “Paths, trees, and flowers”. Canadian Journal of Mathematics 17, 449–467 (1965).
https:/​/​doi.org/​10.4153/​CJM-1965-045-4

[5] 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).
https:/​/​doi.org/​10.1103/​PhysRevLett.108.180501

[6] Guillaume Duclos-Cianci and David Poulin. “Fast decoders for topological quantum codes”. Physical Reviw Letters 104, 050504 (2010).
https:/​/​doi.org/​10.1103/​PhysRevLett.104.050504

[7] 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).
https:/​/​doi.org/​10.1109/​CIG.2010.5592866

[8] James R. Wootton and Daniel Loss. “High threshold error correction for the surface code”. Physical Review Letters 109, 160503 (2012).
https:/​/​doi.org/​10.1103/​PhysRevLett.109.160503

[9] Ben Criger and Imran Ashraf. “Multi-path summation for decoding 2D topological codes”. Quantum 2, 102 (2018).
https:/​/​doi.org/​10.22331/​q-2018-10-19-102

[10] 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).
https:/​/​doi.org/​10.1103/​PhysRevX.13.031007

[11] Oscar Higgott and Nikolas P. Breuckmann. “Improved single-shot decoding of higher-dimensional hypergraph-product codes”. PRX Quantum 4, 020332 (2023).
https:/​/​doi.org/​10.1103/​PRXQuantum.4.020332

[12] Kao-Yueh Kuo and Ching-Yi Lai. “Exploiting degeneracy in belief propagation decoding of quantum codes”. npj Quantum Information 8, 111 (2022).
https:/​/​doi.org/​10.1038/​s41534-022-00623-2

[13] Milap Sheth, Sara Zafar Jafarzadeh, and Vlad Gheorghiu. “Neural ensemble decoding for topological quantum error-correcting codes”. Physical Review A 101, 032338 (2020).
https:/​/​doi.org/​10.1103/​PhysRevA.101.032338

[14] 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).
https:/​/​doi.org/​10.1109/​TQE.2022.3174017

[15] Nicolas Delfosse. “Hierarchical decoding to reduce hardware requirements for quantum computing” (2020). arXiv:2001.11427.
arXiv:2001.11427

[16] Kai Meinerz, Chae-Yeun Park, and Simon Trebst. “Scalable neural decoder for topological surface codes”. Physical Review Letters 128, 080505 (2022).
https:/​/​doi.org/​10.1103/​PhysRevLett.128.080505

[17] 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.
https:/​/​doi.org/​10.1145/​3575693.3575733

[18] 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).
https:/​/​doi.org/​10.1103/​PhysRevApplied.19.034050

[19] 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).
https:/​/​doi.org/​10.1103/​PhysRevResearch.2.033042

[20] Nicolas Delfosse and Naomi H. Nickerson. “Almost-linear time decoding algorithm for topological codes”. Quantum 5, 595 (2021).
https:/​/​doi.org/​10.22331/​q-2021-12-02-595

[21] Namitha Liyanage, Yue Wu, Alexander Deters, and Lin Zhong. “Scalable quantum error correction for surface codes using FPGA” (2023). arXiv:2301.08419.
arXiv:2301.08419

[22] Alexei Yu Kitaev. “Fault-tolerant quantum computation by anyons”. Annals of Physics 303, 2–30 (2003).
https:/​/​doi.org/​10.1016/​S0003-4916(02)00018-0

[23] Tim Chan (2023). code: timchan0/​localuf.
https:/​/​github.com/​timchan0/​localuf

[24] Tim Chan. “Data for `Actis: A Strictly Local Union–Find Decoder”’ (2023).
https:/​/​doi.org/​10.5281/​zenodo.10075207

[25] Michael A. Nielsen and Isaac L. Chuang. “Quantum computation and quantum information: 10th anniversary edition”. Cambridge University Press. (2010).
https:/​/​doi.org/​10.1017/​CBO9780511976667

[26] Xinyu Tan, Fang Zhang, Rui Chao, Yaoyun Shi, and Jianxin Chen. “Scalable surface code decoders with parallelization in time” (2022). arXiv:2209.09219.
arXiv:2209.09219

[27] 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).
https:/​/​doi.org/​10.1038/​s41467-023-42482-1

[28] Shui Hu. “Quasilinear time decoding algorithm for topological codes with high error threshold”. Master’s thesis. Delft University of Technology. (2020).
https:/​/​doi.org/​10.13140/​RG.2.2.13495.96162

[29] Oscar Higgott. “PyMatching: A Python package for decoding quantum codes with minimum-weight perfect matching”. ACM Transactions on Quantum Computing 3, 1–16 (2022).
https:/​/​doi.org/​10.1145/​3505637

[30] Yue Wu, Namitha Liyanage, and Lin Zhong. “An interpretation of Union-Find decoder on weighted graphs” (2022). arXiv:2211.03288.
arXiv:2211.03288

[31] Robert Endre Tarjan. “Efficiency of a good but not linear set union algorithm”. Journal of the ACM 22, 215–225 (1975).
https:/​/​doi.org/​10.1145/​321879.321884

[32] Shilin Huang, Michael Newman, and Kenneth R. Brown. “Fault-tolerant weighted union-find decoding on the toric code”. Physical Review A 102, 012419 (2020).
https:/​/​doi.org/​10.1103/​PhysRevA.102.012419

[33] 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).
https:/​/​doi.org/​10.1038/​s41534-017-0038-y

[34] Andrew Richards. “University of Oxford Advanced Research Computing”. (2015).
https:/​/​doi.org/​10.5281/​zenodo.22558

[35] Sam J. Griffiths and Dan E. Browne. “Union–find quantum decoding without union–find” (2023). arXiv:2306.09767.
arXiv:2306.09767

[36] 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.
arXiv:2309.05558

[37] 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).
https:/​/​doi.org/​10.1103/​PhysRevA.83.020302

[38] Emanuel Knill. “Quantum computing with realistically noisy devices”. Nature 434, 39–44 (2005).
https:/​/​doi.org/​10.1038/​nature03350

[39] Oscar Higgott and Craig Gidney. “Sparse Blossom: correcting a million errors per core second with minimum-weight matching” (2023). arXiv:2303.15933.
arXiv:2303.15933

[40] 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).
https:/​/​doi.org/​10.1103/​PhysRevA.86.042313

[41] Yue Wu and Lin Zhong. “Fusion Blossom: Fast MWPM decoders for QEC” (2023). arXiv:2305.08307.
arXiv:2305.08307

Cited by

[1] Sam J. Griffiths and Dan E. Browne, “Union-find quantum decoding without union-find”, arXiv:2306.09767, (2023).

[2] Asmae Benhemou, Kaavya Sahay, Lingling Lao, and Benjamin J. Brown, “Minimising surface-code failures using a color-code decoder”, arXiv:2306.16476, (2023).

The above citations are from SAO/NASA ADS (last updated successfully 2023-11-15 01:29:45). 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-11-15 01:29:44).

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.

Time Stamp:

More from Quantum Journal