Actis: A Strictly Local Union–Find Decoder
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2023-11-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2023-11-14-1183/pdf/ |
| _version_ | 1797628026323730432 |
|---|---|
| author | Tim Chan Simon C. Benjamin |
| author_facet | Tim Chan Simon C. Benjamin |
| author_sort | Tim Chan |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-11T10:32:41Z |
| format | Article |
| id | doaj.art-7dd2ebfdd12247c0a57cd30d43cfaa92 |
| institution | Directory Open Access Journal |
| issn | 2521-327X |
| language | English |
| last_indexed | 2024-03-11T10:32:41Z |
| publishDate | 2023-11-01 |
| publisher | Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften |
| record_format | Article |
| series | Quantum |
| spelling | doaj.art-7dd2ebfdd12247c0a57cd30d43cfaa922023-11-14T13:34:38ZengVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenQuantum2521-327X2023-11-017118310.22331/q-2023-11-14-118310.22331/q-2023-11-14-1183Actis: A Strictly Local Union–Find DecoderTim ChanSimon C. BenjaminFault-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.https://quantum-journal.org/papers/q-2023-11-14-1183/pdf/ |
| spellingShingle | Tim Chan Simon C. Benjamin Actis: A Strictly Local Union–Find Decoder Quantum |
| title | Actis: A Strictly Local Union–Find Decoder |
| title_full | Actis: A Strictly Local Union–Find Decoder |
| title_fullStr | Actis: A Strictly Local Union–Find Decoder |
| title_full_unstemmed | Actis: A Strictly Local Union–Find Decoder |
| title_short | Actis: A Strictly Local Union–Find Decoder |
| title_sort | actis a strictly local union find decoder |
| url | https://quantum-journal.org/papers/q-2023-11-14-1183/pdf/ |
| work_keys_str_mv | AT timchan actisastrictlylocalunionfinddecoder AT simoncbenjamin actisastrictlylocalunionfinddecoder |