Parallel window decoding enables scalable fault tolerant quantum computation
Open accessThe DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.
Abstract
Large-scale quantum computers have the potential to hold computational capabilities beyond conventional computers. However, the physical qubits are prone to noise which must be corrected in order to perform fault-tolerant quantum computations. Quantum Error Correction (QEC) provides the path for realizing such computations. QEC generates a continuous stream of data that decoders must process at the rate it is received, which can be as fast as 1 μ s per QEC round in superconducting quantum computers. If the decoder infrastructure cannot keep up, a data backlog problem is encountered and the computation runs exponentially slower. Today’s leading approaches to quantum error correction are not scalable as existing decoders typically run slower as the problem size is increased, inevitably hitting the backlog problem. Here, we show how to parallelize decoding to achieve almost arbitrary speed, removing this roadblock to scalability. Our parallelization requires some classical feed forward decisions to be delayed, slowing-down the logical clock speed. However, the slow-down is now only polynomial in the size of the QEC code, averting the exponential slowdown. We numerically demonstrate our parallel decoder for the surface code, showing no noticeable reduction in logical fidelity compared to previous decoders and demonstrating the predicted speedup.
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
Universal quantum computation with ideal Clifford gates and noisy ancillas
Bravyi, S., & Kitaev, A. (2005) · Physical Review A · doi:10.1103/physreva.71.022316 · Cited by 1,525 · cited 1×
“For instance, when performing T := diag(1, e) gates using teleportation and a magic state [2, 3], we must decide whether to apply a Clifford S := diag(1, e) correction before performing the next non-Clifford operation (see Fig.”
MethodQuantum error correction for quantum memories
Terhal, B. M. (2015) · Reviews of Modern Physics · doi:10.1103/revmodphys.87.307 · Cited by 1,354
Suppressing quantum errors by scaling a surface code logical qubit
Google Quantum, A. I., Acharya, R., Aleiner, I., Allen, R., Andersen, T. I., Ansmann, M., Arute, F., Arya, K., Asfaw, A., Atalaya, J., et al. (2023) · Nature · doi:10.1038/s41586-022-05434-1 · Cited by 1,103 · cited 1×
“Note that the additional space-time volume required for magic state distillation will depend only on the number of magic states produced and not on whether we use auto-corrected teleportation.”
BackgroundRealizing repeated quantum error correction in a distance-three surface code
Krinner, S., Lacroix, N., Remm, A., Di Paolo, A., Genois, E., Leroux, C., Hellings, C., Lazar, S., Swiadek, F., Herrmann, J., et al. (2022) · Nature · doi:10.1038/s41586-022-04566-8 · Cited by 686 · cited 1×
“Note that the additional space-time volume required for magic state distillation will depend only on the number of magic states produced and not on whether we use auto-corrected teleportation.”
BackgroundSurface code quantum computing by lattice surgery
Horsman, D., Fowler, A. G., Devitt, S., & Meter, R. V. (2012) · New Journal of Physics · doi:10.1088/1367-2630/14/12/123011 · Cited by 598 · cited 1×
“When performing computation by lattice surgery, during merge operations the code temporally has an extended size [6, 42, 48, 49], and windowing in the spatial direction will become necessary to prevent the window decode time τW from significantly increasing.”
MethodHigh-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 · cited 2×
“The majority of research and development of QEC techniques, on 2D surface codes, has resulted in a wealth of offline decoders such as minimum weight perfect matching [4, 23, 24], union-find [17, 25], renormalisation [26, 27], tensor-network [28–31] and variants of belief propagation [32–35].”
BackgroundStim: a fast stabilizer circuit simulator
Gidney, C. (2021) · Quantum · doi:10.22331/q-2021-07-06-497 · Cited by 415
Even More Efficient Quantum Computations of Chemistry Through Tensor Hypercontraction
Lee, J., Berry, D. W., Gidney, C., Huggins, W. J., McClean, J. R., Wiebe, N., & Babbush, R. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.030305 · Cited by 304
Building a Fault-Tolerant Quantum Computer Using Concatenated Cat Codes
Chamberland, C., Noh, K., Arrangoiz-Arriola, P., Campbell, E. T., Hann, C. T., Iverson, J., Putterman, H., Bohdanowicz, T. C., Flammia, S. T., Keller, A., et al. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.010329 · Cited by 281
Self-citationQuantum computing enhanced computational catalysis
von Burg, V., Low, G. H., Häner, T., Steiger, D. S., Reiher, M., Roetteler, M., & Troyer, M. (2020) · arXiv · doi:10.48550/arxiv.2007.14460 · Cited by 258
Research works printed but not linked: 31
- Litinski, D. A game of surface codes: Large-scale quantum computing with lattice surgery. Quantum 3, 128 (2019). · DOI · Paper page
- DiVincenzo, D. P. & Aliferis, P. Effective fault-tolerant quantum computation with slow measurements. Phys. Rev. Lett. 98, 020501 (2007). · DOI · Paper page
- Chamberland, C., Iyer, P. & Poulin, D. Fault-tolerant quantum computing in the Pauli or Clifford frame with slow error diagnostics. Quantum 2, 43 (2018). · DOI · Paper page
- Holmes, A. et al. Nisq+: Boosting quantum computing power by approximating quantum error correction, in 2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA) (IEEE, 2020) pp. 556–569. · DOI
- Chamberland, C., Goncalves, L., Sivarajah, P., Peterson, E. & Grimberg, S. Techniques for combining fast local decoders with global decoders under circuit-level noise. Quantum Sci. Technol. 8, 045011 (2023). · DOI
- Dennis, E., Kitaev, A., Landahl, A. & Preskill, J. Topological quantum memory. J. Math. Phys. 43, 4452 (2002). · DOI · Paper page
- Higgott, O., PyMatching: A python package for decoding quantum codes with minimum-weight perfect matching, arXiv preprint arXiv:2105.13082 (2021). · DOI · Paper page
- Delfosse, N. & Nickerson, N. H. Almost-linear time decoding algorithm for topological codes. Quantum 5, 595 (2021). · DOI · Paper page
- Das, P. et al. A scalable decoder micro-architecture for fault-tolerant quantum computing, arXiv preprint arXiv:2001.06598 (2020). · arXiv
- Huang, S. & Brown, K. R. Between shor and steane: A unifying construction for measuring error syndromes. Phys. Rev. Lett. 127, 090505 (2021). · DOI
- Iyengar, A. R. et al. Windowed decoding of protograph-based LDPC convolutional codes over erasure channels. IEEE Trans. Inf. Theory 58, 2303 (2012). · DOI · Paper page
- Tan, X., Zhang, F., Chao, R., Shi, Y., and Chen, J., Scalable surface code decoders with parallelization in time, arXiv preprint arXiv:2209.09219 (2022). · DOI · Paper page
- Bombín, H. Single-shot fault-tolerant quantum error correction. Phys. Rev. X 5, 031043 (2015).
- Brown, B. J., Nickerson, N. H. & Browne, D. E. Fault-tolerant error correction with the gauge color code. Nat. Commun. 7, 12302 (2016). · DOI · Paper page
- Quintavalle, A. O., Vasmer, M., Roffe, J. & Campbell, E. T. Single-shot error correction of three-dimensional homological product codes. PRX Quantum 2, 020340 (2021). · DOI
- Kubica, A. & Vasmer, M. Single-shot quantum error correction with the three-dimensional subsystem toric code. Nat. Commun. 13, 6272 (2022). · DOI
- Higgott, O. and Breuckmann, N. P., Improved single-shot decoding of higher dimensional hypergraph product codes, arXiv preprint arXiv:2206.03122 (2022). · DOI
- Gidney, C. and Fowler, A. G., Flexible layout of surface code computations using autoccz states, arXiv preprint arXiv:1905.08916 (2019). · arXiv
- Kivlichan, I. D. et al. Improved fault-tolerant quantum simulation of condensed-phase correlated electrons via trotterization. Quantum 4, 296 (2020). · DOI · Paper page
- Chamberland, C. & Campbell, E. T. Universal quantum computing with twist-free and temporally encoded lattice surgery. PRX Quantum 3, 010331 (2022). · DOI · Paper page
- Darmawan, A. S. & Poulin, D. Tensor-network simulations of the surface code under realistic noise. Phys. Rev. Lett. 119, 040502 (2017). · DOI · Paper page
- Higgott, O., Bohdanowicz, T. C., Kubica, A., Flammia, S. T., and Campbell, E. T., Fragile boundaries of tailored surface codes, arXiv preprint arXiv:2203.04948 (2022). · arXiv
- Chamberland, C. & Campbell, E. T. Circuit-level protocol and analysis for twist-based lattice surgery. Phys. Rev. Res. 4, 023090 (2022). · DOI
- Fawzi, O., Grospellier, A., and Leverrier, A., Constant overhead quantum fault-tolerance with quantum expander codes, in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2018) pp. 743–754. · doi:10.1109/focs.2018.00076 · Paper page
- Das, P., Locharla, A., and Jones, C., Lilliput: A lightweight low-latency lookup-table based decoder for near-term quantum error correction, arXiv preprint arXiv:2108.06569 (2021). · DOI
- Barber, B. et al. A real-time, scalable, fast and highly resource efficient decoder for a quantum computer, arXiv preprint arXiv:2309.05558 (2023). · arXiv
- Fowler, A. Minimum weight perfect matching of fault-tolerant topological quantum error correction in average o(1) parallel time. Quantum Inf. Comput. 15, 145 (2015).
- Anwar, H., Brown, B. J., Campbell, E. T. & Browne, D. E. Fast decoders for qudit topological codes. N. J. Phys. 16, 063038 (2014). · DOI · Paper page
- Ueno, Y., Kondo, M., Tanaka, M., Suzuki, Y., and Tabuchi, Y., Qecool: On-line quantum error correction with a superconducting decoder for surface code, in 2021 58th ACM/IEEE Design Automation Conference (DAC) (IEEE, 2021) pp. 451–456. · DOI
- Meinerz, K., Park, C.-Y. & Trebst, S. Scalable neural decoder for topological surface codes. Phys. Rev. Lett. 128, 080505 (2022). · DOI · Paper page
- Ueno, Y., Kondo, M., Tanaka, M., Suzuki, Y., and Tabuchi, Y., Neo-qec: Neural network enhanced online superconducting decoder for surface codes, arXiv preprint arXiv:2208.05758 (2022). · arXiv
Cited by
Quantum error correction below the surface code threshold
Collaborators, G. Q. A. A., Acharya, R., Abanin, D. A., Aghababaie-Beni, L., Aleiner, I., Andersen, T. I., Ansmann, M., Arute, F., Arya, K., Asfaw, A., et al. (2025) · Nature · doi:10.1038/s41586-024-08449-y · Cited by 778
“However, we do expect that many of our high-accuracy decoding methods can eventually be made real-time by introducing techniques like layered or win-dowed decoding [28, 44, 45].”
Self-citationSparse 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
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
Learning high-accuracy error decoding for quantum processors
Bausch, J., Senior, A. W., Heras, F. J. H., Edlich, T., Davies, A., Newman, M., Jones, C., Satzinger, K., Niu, M. Y., Blackwell, S., et al. (2024) · Nature · doi:10.1038/s41586-024-08148-8 · Cited by 106
“We also note that, in principle, it is possible to achieve unbounded throughput by decomposing the matching decoding problem in an extremely parallel fashion 55,56 .”
Decoding 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
Metadata
- Authors
- Skoric, L., Browne, D. E., Barnes, K. M., Gillespie, N. I., & Campbell, E. T.
- Venue
- Nature Communications
- Published
- 2023-11-03
- Volume
- 14
- Issue
- 1
- Pages
- 7040-7040
- ISSN
- 2041-1723 (ISSN-L)
- OpenAlex
- W4388284400
- Cited by
- 80
- References
- 19
- FWCI
- 6.94
- Type
- journal article
- Language
- en
- Open access
- gold
- Licence
- creativecommons.org/licenses/by/4.0 (tdm)
- creativecommons.org/licenses/by/4.0 (vor)
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Parallel window decoding enables scalable fault tolerant quantum computation. https://app.cochat.ai/papers/10.1038/s41467-023-42482-1
- The paper
- Skoric, L., Browne, D. E., Barnes, K. M., Gillespie, N. I., & Campbell, E. T. (2023). Parallel window decoding enables scalable fault tolerant quantum computation. Nature Communications. https://doi.org/10.1038/s41467-023-42482-1
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.