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: | , |
|---|---|
| Formato: | Journal article |
| Idioma: | English |
| Publicado em: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2023
|
| _version_ | 1826311788567724032 |
|---|---|
| author | Chan, T Benjamin, SC |
| author_facet | Chan, T Benjamin, SC |
| author_sort | Chan, T |
| collection | OXFORD |
| 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 <i>O</i>(<i>d</i><sup>3</sup>) and mean runtime subquadratic in the surface code distance <i>d</i>. 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-07T08:16:24Z |
| format | Journal article |
| id | oxford-uuid:f1d2111e-8655-4881-901b-06c1326f19ed |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:16:24Z |
| publishDate | 2023 |
| publisher | Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften |
| record_format | dspace |
| spelling | oxford-uuid:f1d2111e-8655-4881-901b-06c1326f19ed2023-12-22T17:13:38ZActis: a strictly local Union–Find decoderJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:f1d2111e-8655-4881-901b-06c1326f19edEnglishSymplectic ElementsVerein zur Förderung des Open Access Publizierens in den Quantenwissenschaften2023Chan, TBenjamin, SCFault-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 <i>O</i>(<i>d</i><sup>3</sup>) and mean runtime subquadratic in the surface code distance <i>d</i>. 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. |
| spellingShingle | Chan, T Benjamin, SC Actis: a strictly local Union–Find decoder |
| 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 |
| work_keys_str_mv | AT chant actisastrictlylocalunionfinddecoder AT benjaminsc actisastrictlylocalunionfinddecoder |