Fault-tolerant weighted union-find decoding on the toric code
Open accessThe DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
Abstract
Quantum error correction requires decoders that are both accurate and efficient. To this end, union-find decoding has emerged as a promising candidate for error correction on the surface code. In this work, we benchmark a weighted variant of the union-find decoder on the toric code under circuit-level depolarizing noise. This variant preserves the almost-linear time complexity of the original while significantly increasing the performance in the fault-tolerance setting. In this noise model, weighting the union-find decoder increases the threshold from $0.38%$ to $0.62%$, compared to an increase from $0.65%$ to $0.72%$ when weighting a matching decoder. Further assuming quantum nondemolition measurements, weighted union-find decoding achieves a threshold of $0.76%$ compared to the $0.90%$ threshold when matching. We additionally provide comparisons of timing as well as low error rate behavior.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Surface codes: Towards practical large-scale quantum computation
Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012) · Physical Review A · doi:10.1103/physreva.86.032324 · Cited by 3,059
Dennis, E., Kitaev, A., Landahl, A., & Preskill, J. (2002) · Journal of Mathematical Physics · doi:10.1063/1.1499754 · Cited by 1,768
Fault-Tolerant Quantum Computation with High Threshold in Two Dimensions
Raussendorf, R., & Harrington, J. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.190504 · Cited by 812
High-threshold universal quantum computation on the surface code
Fowler, A. G., Stephens, A. M., & Groszkowski, P. (2009) · Physical Review A · doi:10.1103/physreva.80.052312 · Cited by 486
A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
Litinski, D. (2019) · Quantum · doi:10.22331/q-2019-03-05-128 · Cited by 408
Almost-linear time decoding algorithm for topological codes
Delfosse, N., & Nickerson, N. H. (2021) · Quantum · doi:10.22331/q-2021-12-02-595 · Cited by 242
Topological and Subsystem Codes on Low-Degree Graphs with Flag Qubits
Chamberland, C., Zhu, G., Yoder, T. J., Hertzberg, J. B., & Cross, A. W. (2020) · Physical Review X · doi:10.1103/physrevx.10.011022 · Cited by 223
Efficient algorithms for maximum likelihood decoding in the surface code
Bravyi, S., Suchara, M., & Vargo, A. (2014) · Physical Review A · doi:10.1103/physreva.90.032326 · Cited by 214
Efficient magic state factories with a catalyzed | C C Z ⟩ to 2 | T ⟩ transformation
Gidney, C., & Fowler, A. G. (2019) · Quantum · doi:10.22331/q-2019-04-30-135 · Cited by 152
Triangular color codes on trivalent graphs with flag qubits
Chamberland, C., Kubica, A., Yoder, T. J., & Zhu, G. (2020) · New Journal of Physics · doi:10.1088/1367-2630/ab68fd · Cited by 105
Cited by
Sparse blossom: correcting a million errors per core second with minimum-weight matching
Higgott, O., & Gidney, C. (2025) · Quantum · doi:10.22331/q-2025-01-20-1600 · Cited by 180
“The Union-Find decoder has an almost-linear worst-case running time [DN21; HNB20], and fast hardware implementations have been proposed [Das+22] and implemented [Liy+23].”
PyMatching: A Python Package for Decoding Quantum Codes with Minimum-Weight Perfect Matching
Higgott, O. (2022) · ACM Transactions on Quantum Computing · doi:10.1145/3505637 · Cited by 181
Sparse Blossom: correcting a million errors per core second with minimum-weight matching
Higgott, O., & Gidney, C. (2023) · arXiv · doi:10.48550/arxiv.2303.15933 · Cited by 148
A Fault-Tolerant Honeycomb Memory
Gidney, C., Newman, M., Fowler, A., & Broughton, M. (2021) · Quantum · doi:10.22331/q-2021-12-20-605 · Cited by 83
Self-citationDecoding algorithms for surface codes
deMarti iOlius, A., Fuentes, P., Orús, R., Crespo, P. M., & Etxezarreta Martinez, J. (2024) · Quantum · doi:10.22331/q-2024-10-10-1498 · Cited by 60
“Additionally, many physical implementations of these types of technologies like superconducting circuits (Huang et al., 2020a), iontraps (Häffner et al., 2008) or photons (Slussarenko and Pryde, 2019) are currently being investigated.”
BackgroundMethodInfluentialSubsystem codes with high thresholds by gauge fixing and reduced qubit overhead
Higgott, O., & Breuckmann, N. P. (2021) · Physical Review X · doi:10.1103/physrevx.11.031039 · Cited by 48
“decoders such as UNION-FIND [46,55], which has almost-”
BackgroundMethodInfluentialFusion Blossom: Fast MWPM Decoders for QEC
Wu, Y., & Zhong, L. (2023) · 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce57702.2023.00107 · Cited by 47
“Perhaps the most relevant is the (weighted) Union-Find (UF) decoder [23, 35] for which various design [5] and implementation [8] have been reported.”
BackgroundDecoder for the Triangular Color Code by Matching on a Möbius Strip
Sahay, K., & Brown, B. J. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.010310 · Cited by 38
FPGA-Based Distributed Union-Find Decoder for Surface Codes
(2024) · doi:10.1109/tqe.2024.3467271 · Cited by 36
Improving Threshold for Fault-Tolerant Color-Code Quantum Computing by Flagged Weight Optimization
Takada, Y., & Fujii, K. (2024) · PRX Quantum · doi:10.1103/prxquantum.5.030352 · Cited by 10
Practical Quantum Error Correction with the XZZX Code and Kerr-Cat Qubits
Darmawan, A. S., Brown, B. J., Grimsmo, A. L., Tuckett, D. K., & Puri, S. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.030345 · Cited by 2
Metadata
- Authors
- Huang, S., Newman, M., & Brown, K. R.
- Venue
- Physical Review A
- Publisher
- American Physical Society (APS)
- Published
- 2020-07-16
- Volume
- 102
- Issue
- 1
- ISSN
- 0556-2791 (ISSN-L)
- 2469-9926
- 2469-9934
- OpenAlex
- W3015998597
- Cited by
- 58
- References
- 12
- FWCI
- 2.56
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.