2017/09/30 by Ben Criger, Imran Ashraf
Computer Science · Engineering · Mathematics · Physics and Astronomy · #Advanced Memory and Neural Computing #Algorithm #Code (set theory) #Computer science #Decoding methods #Ferroelectric and Negative Capacitance Devices #Matching (statistics) #Mathematics #Quantum Computing Algorithms and Architecture #Statistics #quant-ph
paper · pdf · doi:10.22331/q-2018-10-19-102
published as Quantum 2, 102 (2018) · 19 pages, 13 figures, published in Quantum, available at https://quantum-journal.org/papers/q-2018-10-19-102/
openalex publication_date 2018/10/19 · arxiv created 2018/10/21 · arxiv updated 2018/10/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Fault tolerance is a prerequisite for scalable quantum computing. Architectures based on 2D topological codes are effective for near-term implementations of fault tolerance. To obtain high performance with these architectures, we require a decoder which can adapt to the wide variety of error models present in experiments. The typical approach to the problem of decoding the surface code is to reduce it to minimum-weight perfect matching in a way that provides a suboptimal threshold error rate, and is specialized to correct a specific error model. Recently, optimal threshold error rates for a variety of error models have been obtained by methods which do not use minimum-weight perfect matching, showing that such thresholds can be achieved in polynomial time. It is an open question whether these results can also be achieved by minimum-weight perfect matching. In this work, we use belief propagation and a novel algorithm for producing edge weights to increase the utility of minimum-weight perfect matching for decoding surface codes. This allows us to correct depolarizing errors using the rotated surface code, obtaining a threshold of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mn>17.76</mml:mn> <mml:mo>±</mml:mo> <mml:mn>0.02</mml:mn> <mml:mi mathvariant="normal">%</mml:mi> </mml:math> . This is larger than the threshold achieved by previous matching-based decoders ( <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mn>14.88</mml:mn> <mml:mo>±</mml:mo> <mml:mn>0.02</mml:mn> <mml:mi mathvariant="normal">%</mml:mi> </mml:math> ), though still below the known upper bound of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>∼</mml:mo> <mml:mn>18.9</mml:mn> <mml:mi mathvariant="normal">%</mml:mi> </mml:math> .