CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20220107-10356300

[img] PDF - Published Version
Creative Commons Attribution.

3MB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20220107-10356300

Abstract

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
https://doi.org/10.22331/q-2021-12-02-595DOIArticle
https://arxiv.org/abs/1709.06218arXivDiscussion Paper
ORCID:
AuthorORCID
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
Funders:
Funding AgencyGrant Number
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
NSFPHY-1125565
Gordon and Betty Moore FoundationGBMF-2644
DOI:10.22331/q-2021-12-02-595
Record Number:CaltechAUTHORS:20220107-14076800
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20220107-10356300
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:112789
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:09 Jan 2022 00:15
Last Modified:09 Jan 2022 22:07

Repository Staff Only: item control page