Union-find quantum decoding without union-find Article Swipe
Sam J. Griffiths
,
Dan E. Browne
·
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.1103/physrevresearch.6.013154
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.1103/physrevresearch.6.013154
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. Published by the American Physical Society 2024
Related Topics
Concepts
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://doi.org/10.1103/physrevresearch.6.013154
- http://link.aps.org/pdf/10.1103/PhysRevResearch.6.013154
- OA Status
- gold
- Cited By
- 4
- References
- 22
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4391684658
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4391684658Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.1103/physrevresearch.6.013154Digital Object Identifier
- Title
-
Union-find quantum decoding without union-findWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2024Year of publication
- Publication date
-
2024-02-09Full publication date if available
- Authors
-
Sam J. Griffiths, Dan E. BrowneList of authors in order
- Landing page
-
https://doi.org/10.1103/physrevresearch.6.013154Publisher landing page
- PDF URL
-
https://link.aps.org/pdf/10.1103/PhysRevResearch.6.013154Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
goldOpen access status per OpenAlex
- OA URL
-
https://link.aps.org/pdf/10.1103/PhysRevResearch.6.013154Direct OA link when available
- Concepts
-
Decoding methods, Quantum, Political science, Computer science, Physics, Quantum mechanics, TelecommunicationsTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
4Total citation count in OpenAlex
- Citations by year (recent)
-
2025: 4Per-year citation counts (last 5 years)
- References (count)
-
22Number of works referenced by this work
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4391684658 |
|---|---|
| doi | https://doi.org/10.1103/physrevresearch.6.013154 |
| ids.doi | https://doi.org/10.1103/physrevresearch.6.013154 |
| ids.openalex | https://openalex.org/W4391684658 |
| fwci | 2.5551142 |
| type | article |
| title | Union-find quantum decoding without union-find |
| awards[0].id | https://openalex.org/G6706090731 |
| awards[0].funder_id | https://openalex.org/F4320334627 |
| awards[0].display_name | |
| awards[0].funder_award_id | EP/R043647/1 |
| awards[0].funder_display_name | Engineering and Physical Sciences Research Council |
| awards[1].id | https://openalex.org/G6174183273 |
| awards[1].funder_id | https://openalex.org/F4320334627 |
| awards[1].display_name | |
| awards[1].funder_award_id | EP/T001062/1 |
| awards[1].funder_display_name | Engineering and Physical Sciences Research Council |
| awards[2].id | https://openalex.org/G2324702809 |
| awards[2].funder_id | https://openalex.org/F4320334627 |
| awards[2].display_name | |
| awards[2].funder_award_id | EP/S021582/1 |
| awards[2].funder_display_name | Engineering and Physical Sciences Research Council |
| biblio.issue | 1 |
| biblio.volume | 6 |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10682 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9998999834060669 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1702 |
| topics[0].subfield.display_name | Artificial Intelligence |
| topics[0].display_name | Quantum Computing Algorithms and Architecture |
| topics[1].id | https://openalex.org/T10020 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9994000196456909 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1702 |
| topics[1].subfield.display_name | Artificial Intelligence |
| topics[1].display_name | Quantum Information and Cryptography |
| topics[2].id | https://openalex.org/T10622 |
| topics[2].field.id | https://openalex.org/fields/31 |
| topics[2].field.display_name | Physics and Astronomy |
| topics[2].score | 0.9919000267982483 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/3107 |
| topics[2].subfield.display_name | Atomic and Molecular Physics, and Optics |
| topics[2].display_name | Quantum Mechanics and Applications |
| funders[0].id | https://openalex.org/F4320320286 |
| funders[0].ror | https://ror.org/02jx3x895 |
| funders[0].display_name | University College London |
| funders[1].id | https://openalex.org/F4320334627 |
| funders[1].ror | https://ror.org/0439y7842 |
| funders[1].display_name | Engineering and Physical Sciences Research Council |
| is_xpac | False |
| apc_list.value | 2625 |
| apc_list.currency | USD |
| apc_list.value_usd | 2625 |
| apc_paid.value | 2625 |
| apc_paid.currency | USD |
| apc_paid.value_usd | 2625 |
| concepts[0].id | https://openalex.org/C57273362 |
| concepts[0].level | 2 |
| concepts[0].score | 0.5668565034866333 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q576722 |
| concepts[0].display_name | Decoding methods |
| concepts[1].id | https://openalex.org/C84114770 |
| concepts[1].level | 2 |
| concepts[1].score | 0.4176270067691803 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q46344 |
| concepts[1].display_name | Quantum |
| concepts[2].id | https://openalex.org/C17744445 |
| concepts[2].level | 0 |
| concepts[2].score | 0.33367133140563965 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q36442 |
| concepts[2].display_name | Political science |
| concepts[3].id | https://openalex.org/C41008148 |
| concepts[3].level | 0 |
| concepts[3].score | 0.32244741916656494 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[3].display_name | Computer science |
| concepts[4].id | https://openalex.org/C121332964 |
| concepts[4].level | 0 |
| concepts[4].score | 0.2802005410194397 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q413 |
| concepts[4].display_name | Physics |
| concepts[5].id | https://openalex.org/C62520636 |
| concepts[5].level | 1 |
| concepts[5].score | 0.18126732110977173 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q944 |
| concepts[5].display_name | Quantum mechanics |
| concepts[6].id | https://openalex.org/C76155785 |
| concepts[6].level | 1 |
| concepts[6].score | 0.14322134852409363 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q418 |
| concepts[6].display_name | Telecommunications |
| keywords[0].id | https://openalex.org/keywords/decoding-methods |
| keywords[0].score | 0.5668565034866333 |
| keywords[0].display_name | Decoding methods |
| keywords[1].id | https://openalex.org/keywords/quantum |
| keywords[1].score | 0.4176270067691803 |
| keywords[1].display_name | Quantum |
| keywords[2].id | https://openalex.org/keywords/political-science |
| keywords[2].score | 0.33367133140563965 |
| keywords[2].display_name | Political science |
| keywords[3].id | https://openalex.org/keywords/computer-science |
| keywords[3].score | 0.32244741916656494 |
| keywords[3].display_name | Computer science |
| keywords[4].id | https://openalex.org/keywords/physics |
| keywords[4].score | 0.2802005410194397 |
| keywords[4].display_name | Physics |
| keywords[5].id | https://openalex.org/keywords/quantum-mechanics |
| keywords[5].score | 0.18126732110977173 |
| keywords[5].display_name | Quantum mechanics |
| keywords[6].id | https://openalex.org/keywords/telecommunications |
| keywords[6].score | 0.14322134852409363 |
| keywords[6].display_name | Telecommunications |
| language | en |
| locations[0].id | doi:10.1103/physrevresearch.6.013154 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4210240247 |
| locations[0].source.issn | 2643-1564 |
| locations[0].source.type | journal |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | 2643-1564 |
| locations[0].source.is_core | True |
| locations[0].source.is_in_doaj | True |
| locations[0].source.display_name | Physical Review Research |
| locations[0].source.host_organization | https://openalex.org/P4310320261 |
| locations[0].source.host_organization_name | American Physical Society |
| locations[0].source.host_organization_lineage | https://openalex.org/P4310320261 |
| locations[0].source.host_organization_lineage_names | American Physical Society |
| locations[0].license | cc-by |
| locations[0].pdf_url | http://link.aps.org/pdf/10.1103/PhysRevResearch.6.013154 |
| locations[0].version | publishedVersion |
| locations[0].raw_type | journal-article |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | Physical Review Research |
| locations[0].landing_page_url | https://doi.org/10.1103/physrevresearch.6.013154 |
| locations[1].id | pmh:oai:doaj.org/article:d45dbc9d112a464eaaec882af9386eda |
| locations[1].is_oa | False |
| locations[1].source.id | https://openalex.org/S4306401280 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | False |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | DOAJ (DOAJ: Directory of Open Access Journals) |
| locations[1].source.host_organization | |
| locations[1].source.host_organization_name | |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | submittedVersion |
| locations[1].raw_type | article |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | False |
| locations[1].raw_source_name | Physical Review Research, Vol 6, Iss 1, p 013154 (2024) |
| locations[1].landing_page_url | https://doaj.org/article/d45dbc9d112a464eaaec882af9386eda |
| indexed_in | crossref, doaj |
| authorships[0].author.id | https://openalex.org/A5049081900 |
| authorships[0].author.orcid | https://orcid.org/0000-0001-7211-4339 |
| authorships[0].author.display_name | Sam J. Griffiths |
| authorships[0].countries | GB |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I45129253 |
| authorships[0].affiliations[0].raw_affiliation_string | Department of Physics and Astronomy, University College London, London WC1E 6BT, United Kingdom |
| authorships[0].institutions[0].id | https://openalex.org/I45129253 |
| authorships[0].institutions[0].ror | https://ror.org/02jx3x895 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I124357947, https://openalex.org/I45129253 |
| authorships[0].institutions[0].country_code | GB |
| authorships[0].institutions[0].display_name | University College London |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Sam J. Griffiths |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | Department of Physics and Astronomy, University College London, London WC1E 6BT, United Kingdom |
| authorships[1].author.id | https://openalex.org/A5058916700 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-3001-158X |
| authorships[1].author.display_name | Dan E. Browne |
| authorships[1].countries | GB |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I45129253 |
| authorships[1].affiliations[0].raw_affiliation_string | Department of Physics and Astronomy, University College London, London WC1E 6BT, United Kingdom |
| authorships[1].institutions[0].id | https://openalex.org/I45129253 |
| authorships[1].institutions[0].ror | https://ror.org/02jx3x895 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I124357947, https://openalex.org/I45129253 |
| authorships[1].institutions[0].country_code | GB |
| authorships[1].institutions[0].display_name | University College London |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Dan E. Browne |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | Department of Physics and Astronomy, University College London, London WC1E 6BT, United Kingdom |
| has_content.pdf | True |
| has_content.grobid_xml | True |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | http://link.aps.org/pdf/10.1103/PhysRevResearch.6.013154 |
| open_access.oa_status | gold |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Union-find quantum decoding without union-find |
| has_fulltext | True |
| is_retracted | False |
| updated_date | 2025-11-06T03:46:38.306776 |
| primary_topic.id | https://openalex.org/T10682 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9998999834060669 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1702 |
| primary_topic.subfield.display_name | Artificial Intelligence |
| primary_topic.display_name | Quantum Computing Algorithms and Architecture |
| related_works | https://openalex.org/W2748952813, https://openalex.org/W2390279801, https://openalex.org/W2358668433, https://openalex.org/W2376932109, https://openalex.org/W2001405890, https://openalex.org/W2382290278, https://openalex.org/W3203142394, https://openalex.org/W2478288626, https://openalex.org/W2350741829, https://openalex.org/W2530322880 |
| cited_by_count | 4 |
| counts_by_year[0].year | 2025 |
| counts_by_year[0].cited_by_count | 4 |
| locations_count | 2 |
| best_oa_location.id | doi:10.1103/physrevresearch.6.013154 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4210240247 |
| best_oa_location.source.issn | 2643-1564 |
| best_oa_location.source.type | journal |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | 2643-1564 |
| best_oa_location.source.is_core | True |
| best_oa_location.source.is_in_doaj | True |
| best_oa_location.source.display_name | Physical Review Research |
| best_oa_location.source.host_organization | https://openalex.org/P4310320261 |
| best_oa_location.source.host_organization_name | American Physical Society |
| best_oa_location.source.host_organization_lineage | https://openalex.org/P4310320261 |
| best_oa_location.source.host_organization_lineage_names | American Physical Society |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | http://link.aps.org/pdf/10.1103/PhysRevResearch.6.013154 |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | journal-article |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | Physical Review Research |
| best_oa_location.landing_page_url | https://doi.org/10.1103/physrevresearch.6.013154 |
| primary_location.id | doi:10.1103/physrevresearch.6.013154 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4210240247 |
| primary_location.source.issn | 2643-1564 |
| primary_location.source.type | journal |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | 2643-1564 |
| primary_location.source.is_core | True |
| primary_location.source.is_in_doaj | True |
| primary_location.source.display_name | Physical Review Research |
| primary_location.source.host_organization | https://openalex.org/P4310320261 |
| primary_location.source.host_organization_name | American Physical Society |
| primary_location.source.host_organization_lineage | https://openalex.org/P4310320261 |
| primary_location.source.host_organization_lineage_names | American Physical Society |
| primary_location.license | cc-by |
| primary_location.pdf_url | http://link.aps.org/pdf/10.1103/PhysRevResearch.6.013154 |
| primary_location.version | publishedVersion |
| primary_location.raw_type | journal-article |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | Physical Review Research |
| primary_location.landing_page_url | https://doi.org/10.1103/physrevresearch.6.013154 |
| publication_date | 2024-02-09 |
| publication_year | 2024 |
| referenced_works | https://openalex.org/W2088636071, https://openalex.org/W2030867075, https://openalex.org/W3041260181, https://openalex.org/W3217173135, https://openalex.org/W2044146725, https://openalex.org/W2114207424, https://openalex.org/W2131690084, https://openalex.org/W2135273380, https://openalex.org/W2107453273, https://openalex.org/W4233756358, https://openalex.org/W2164424155, https://openalex.org/W3015998597, https://openalex.org/W4206182345, https://openalex.org/W4213451376, https://openalex.org/W4388664054, https://openalex.org/W4388284400, https://openalex.org/W2890292748, https://openalex.org/W2102532141, https://openalex.org/W1606480398, https://openalex.org/W3100736866, https://openalex.org/W4220688022, https://openalex.org/W2764347725 |
| referenced_works_count | 22 |
| abstract_inverted_index.a | 4, 110, 124, 135 |
| abstract_inverted_index.To | 89 |
| abstract_inverted_index.We | 51 |
| abstract_inverted_index.at | 60, 131 |
| abstract_inverted_index.be | 78 |
| abstract_inverted_index.by | 46, 100, 142 |
| abstract_inverted_index.in | 33, 87 |
| abstract_inverted_index.is | 3, 41 |
| abstract_inverted_index.of | 11, 36, 57, 96, 120 |
| abstract_inverted_index.on | 14 |
| abstract_inverted_index.to | 8, 22, 80, 83 |
| abstract_inverted_index.we | 92 |
| abstract_inverted_index.The | 0 |
| abstract_inverted_index.and | 69, 72, 75, 103 |
| abstract_inverted_index.any | 118 |
| abstract_inverted_index.can | 77 |
| abstract_inverted_index.for | 66, 117, 128 |
| abstract_inverted_index.not | 108 |
| abstract_inverted_index.the | 9, 15, 34, 47, 55, 58, 94, 101, 114, 129, 143 |
| abstract_inverted_index.via | 43 |
| abstract_inverted_index.2024 | 147 |
| abstract_inverted_index.This | 39, 122 |
| abstract_inverted_index.code | 19 |
| abstract_inverted_index.data | 49, 64, 115 |
| abstract_inverted_index.does | 107 |
| abstract_inverted_index.even | 133 |
| abstract_inverted_index.made | 79 |
| abstract_inverted_index.mode | 119 |
| abstract_inverted_index.show | 104 |
| abstract_inverted_index.that | 54, 73, 105 |
| abstract_inverted_index.this | 63 |
| abstract_inverted_index.time | 30 |
| abstract_inverted_index.with | 27, 134 |
| abstract_inverted_index.code, | 17 |
| abstract_inverted_index.exist | 109 |
| abstract_inverted_index.model | 93 |
| abstract_inverted_index.naive | 136 |
| abstract_inverted_index.scale | 61 |
| abstract_inverted_index.there | 106 |
| abstract_inverted_index.this, | 91 |
| abstract_inverted_index.(MWPM) | 26 |
| abstract_inverted_index.errors | 13 |
| abstract_inverted_index.formed | 99 |
| abstract_inverted_index.number | 35 |
| abstract_inverted_index.reduce | 84 |
| abstract_inverted_index.scale, | 132 |
| abstract_inverted_index.within | 113 |
| abstract_inverted_index.yields | 123 |
| abstract_inverted_index.Society | 146 |
| abstract_inverted_index.decoder | 2, 59, 102, 130 |
| abstract_inverted_index.designs | 82 |
| abstract_inverted_index.erasure | 97 |
| abstract_inverted_index.leading | 5 |
| abstract_inverted_index.perfect | 24 |
| abstract_inverted_index.popular | 139 |
| abstract_inverted_index.quantum | 12 |
| abstract_inverted_index.qubits. | 38 |
| abstract_inverted_index.scaling | 31 |
| abstract_inverted_index.surface | 16 |
| abstract_inverted_index.twofold | 67 |
| abstract_inverted_index.American | 144 |
| abstract_inverted_index.Physical | 145 |
| abstract_inverted_index.achieved | 42 |
| abstract_inverted_index.analytic | 68 |
| abstract_inverted_index.approach | 7 |
| abstract_inverted_index.behavior | 56, 95 |
| abstract_inverted_index.clusters | 98 |
| abstract_inverted_index.however, | 53 |
| abstract_inverted_index.matching | 25 |
| abstract_inverted_index.omitting | 138 |
| abstract_inverted_index.overhead | 86 |
| abstract_inverted_index.physical | 37 |
| abstract_inverted_index.provided | 45 |
| abstract_inverted_index.reasons, | 71 |
| abstract_inverted_index.resource | 85 |
| abstract_inverted_index.Published | 141 |
| abstract_inverted_index.achieving | 18 |
| abstract_inverted_index.amortized | 28 |
| abstract_inverted_index.practice. | 88 |
| abstract_inverted_index.reinforce | 90 |
| abstract_inverted_index.structure | 65, 116 |
| abstract_inverted_index.threshold | 112 |
| abstract_inverted_index.comparable | 21 |
| abstract_inverted_index.complexity | 40, 127 |
| abstract_inverted_index.correction | 10 |
| abstract_inverted_index.operation. | 121 |
| abstract_inverted_index.structure. | 50 |
| abstract_inverted_index.thresholds | 20 |
| abstract_inverted_index.union-find | 1 |
| abstract_inverted_index.worst-case | 126 |
| abstract_inverted_index.algorithmic | 6, 70 |
| abstract_inverted_index.linear-time | 125 |
| abstract_inverted_index.percolation | 111 |
| abstract_inverted_index.demonstrate, | 52 |
| abstract_inverted_index.disjoint-set | 48 |
| abstract_inverted_index.improvements | 74 |
| abstract_inverted_index.architectural | 81 |
| abstract_inverted_index.computational | 29 |
| abstract_inverted_index.near-linearly | 32 |
| abstract_inverted_index.optimizations | 44 |
| abstract_inverted_index.underutilizes | 62 |
| abstract_inverted_index.implementation | 137 |
| abstract_inverted_index.minimum-weight | 23 |
| abstract_inverted_index.optimizations. | 140 |
| abstract_inverted_index.simplifications | 76 |
| cited_by_percentile_year.max | 98 |
| cited_by_percentile_year.min | 97 |
| countries_distinct_count | 1 |
| institutions_distinct_count | 2 |
| citation_normalized_percentile.value | 0.86290221 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | True |