A Caltech Library Service

Almost-linear time decoding algorithm for topological codes

Delfosse, Nicolas and Nickerson, Naomi H. (2021) Almost-linear time decoding algorithm for topological codes. Quantum, 5 . Art. No. 595. ISSN 2521-327X. doi:10.22331/q-2021-12-02-595.

[img] PDF - Published Version
Creative Commons Attribution.


Use this Persistent URL to link to this item:


In order to build a large scale quantum computer, one must be able to correct errors extremely fast. We design a fast decoding algorithm for topological codes to correct for Pauli errors and erasure and combination of both errors and erasure. Our algorithm has a worst case complexity of O(nα(n)), where n is the number of physical qubits and αα is the inverse of Ackermann's function, which is very slowly growing. For all practical purposes, α(n) ≤ 3. We prove that our algorithm performs optimally for errors of weight up to (d−1)/2 and for loss of up to d−1 qubits, where d is the minimum distance of the code. Numerically, we obtain a threshold of 9.9% for the 2d-toric code with perfect syndrome measurements and 2.6% with faulty measurements.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Delfosse, Nicolas0000-0002-3949-981X
Additional Information:© 2021. This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. Published: 2021-12-02. The authors would like to thank Eric Johnson and Chris Dawson for valuable discussions, and Terry Rudolph for first introducing them to the question of error correction in photonic devices. The authors would like to thank Aleksander Kubica for his comments on a preliminary version of this paper. ND acknowledges funding provided by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-2644).
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Gordon and Betty Moore FoundationGBMF-2644
Record Number:CaltechAUTHORS:20220107-10356300
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:112789
Deposited By: Tony Diaz
Deposited On:09 Jan 2022 00:15
Last Modified:25 Jul 2022 23:14

Repository Staff Only: item control page