Union-find quantum decoding without union-find
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 i...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2024-02-01
|
| Series: | Physical Review Research |
| Online Access: | http://doi.org/10.1103/PhysRevResearch.6.013154 |
| _version_ | 1797210266914521088 |
|---|---|
| author | Sam J. Griffiths Dan E. Browne |
| author_facet | Sam J. Griffiths Dan E. Browne |
| author_sort | Sam J. Griffiths |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-24T10:07:52Z |
| format | Article |
| id | doaj.art-d45dbc9d112a464eaaec882af9386eda |
| institution | Directory Open Access Journal |
| issn | 2643-1564 |
| language | English |
| last_indexed | 2024-04-24T10:07:52Z |
| publishDate | 2024-02-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | Physical Review Research |
| spelling | doaj.art-d45dbc9d112a464eaaec882af9386eda2024-04-12T17:39:03ZengAmerican Physical SocietyPhysical Review Research2643-15642024-02-016101315410.1103/PhysRevResearch.6.013154Union-find quantum decoding without union-findSam J. GriffithsDan E. BrowneThe 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.http://doi.org/10.1103/PhysRevResearch.6.013154 |
| spellingShingle | Sam J. Griffiths Dan E. Browne Union-find quantum decoding without union-find Physical Review Research |
| title | Union-find quantum decoding without union-find |
| title_full | Union-find quantum decoding without union-find |
| title_fullStr | Union-find quantum decoding without union-find |
| title_full_unstemmed | Union-find quantum decoding without union-find |
| title_short | Union-find quantum decoding without union-find |
| title_sort | union find quantum decoding without union find |
| url | http://doi.org/10.1103/PhysRevResearch.6.013154 |
| work_keys_str_mv | AT samjgriffiths unionfindquantumdecodingwithoutunionfind AT danebrowne unionfindquantumdecodingwithoutunionfind |