Griffiths, Sam J;
Browne, Dan E;
(2024)
Union-find quantum decoding without union-find.
Physical Review Research
, 6
(1)
, Article 013154. 10.1103/physrevresearch.6.013154.
Preview |
PDF
PhysRevResearch.6.013154.pdf - Published Version Download (857kB) | Preview |
Abstract
The union-find decoder is a leading algorithmic approach to the correction of quantum errors on the surface code, achieving code thresholds comparable to minimum-weight perfect matching (MWPM) with amortized computational time scaling near-linearly in the number of physical qubits. This complexity is achieved via optimizations provided by the disjoint-set data structure. We demonstrate, however, that the behavior of the decoder at scale underutilizes this data structure for twofold analytic and algorithmic reasons, and that improvements and simplifications can be made to architectural designs to reduce resource overhead in practice. To reinforce this, we model the behavior of erasure clusters formed by the decoder and show that there does not exist a percolation threshold within the data structure for any mode of operation. This yields a linear-time worst-case complexity for the decoder at scale, even with a naive implementation omitting popular optimizations.
| Type: | Article |
|---|---|
| Title: | Union-find quantum decoding without union-find |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1103/physrevresearch.6.013154 |
| Publisher version: | http://dx.doi.org/10.1103/physrevresearch.6.013154 |
| Language: | English |
| Additional information: | Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Physics and Astronomy |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10187885 |
Archive Staff Only
 |
View Item |
