Local Probabilistic Decoding of a Quantum Code

T. R. Scruby and K. Nemoto

Okinawa Institute of Science and Technology, Okinawa, 904-0495, Japan

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


$\tt{flip}$ is an extremely simple and maximally local classical decoder which has been used to great effect in certain classes of classical codes. When applied to quantum codes there exist constant-weight errors (such as half of a stabiliser) which are uncorrectable for this decoder, so previous studies have considered modified versions of $\tt{flip}$, sometimes in conjunction with other decoders. We argue that this may not always be necessary, and present numerical evidence for the existence of a threshold for $\tt{flip}$ when applied to the looplike syndromes of a three-dimensional toric code on a cubic lattice. This result can be attributed to the fact that the lowest-weight uncorrectable errors for this decoder are closer (in terms of Hamming distance) to correctable errors than to other uncorrectable errors, and so they are likely to become correctable in future code cycles after transformation by additional noise. Introducing randomness into the decoder can allow it to correct these "uncorrectable" errors with finite probability, and for a decoding strategy that uses a combination of belief propagation and probabilistic $\tt{flip}$ we observe a threshold of $\sim5.5\%$ under phenomenological noise. This is comparable to the best known threshold for this code ($\sim7.1\%$) which was achieved using belief propagation and ordered statistics decoding [Higgott and Breuckmann, 2022], a strategy with a runtime of $O(n^3)$ as opposed to the $O(n)$ ($O(1)$ when parallelised) runtime of our local decoder. We expect that this strategy could be generalised to work well in other low-density parity check codes, and hope that these results will prompt investigation of other previously overlooked decoders.

Most quantum error correcting codes detect the presence of errors in a quantum system via the measurement of operators called stabilisers. The outcomes of these measurements are then passed to a classical algorithm called a decoder which uses this measurement data to calculate a correction that counteracts the effects of the errors. A common requirement for decoding algorithms is that they should be able to reliably calculate corrections for all errors under a certain size. In this work we examine the necessity of this requirement and study the performance of certain "bad" decoding algorithms which fail to correct some very small errors. We present numerical results which demonstrate that in some cases these decoders can perform very well despite their failings, and identify the reasons behind this. The algorithms we study in this work are very simple and efficient but nonetheless achieve performance competitive with the best known decoder for the same code, and so we argue that being less strict about what properties we require for decoders can lead to the discovery of more practically useful algorithms.

► BibTeX data

► References

[1] David J C MacKay. Information Theory, Inference, and Learning Algorithms. Cambridge University Press, 4th edition, 2005.

[2] Daniel Gottesman. Stabilizer Codes and Quantum Error Correction. arXiv:quant-ph/​9705052, May 1997. 10.48550/​arXiv.quant-ph/​9705052.

[3] A. R. Calderbank and Peter W. Shor. Good Quantum Error-Correcting Codes Exist. Physical Review A, 54 (2), 1996. 10.1103/​PhysRevA.54.1098.

[4] Andrew Steane. Multiple Particle Interference and Quantum Error Correction. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 452 (1954), 1996. 10.1098/​rspa.1996.0136.

[5] Anthony Leverrier, Jean-Pierre Tillich, and Gilles Zémor. Quantum Expander Codes. 2015. 10.1109/​FOCS.2015.55. arXiv:1504.00822 [quant-ph].

[6] David Poulin and Yeojin Chung. On the iterative decoding of sparse quantum codes. 2008. 10.48550/​arXiv.0801.1241.

[7] Antoine Grospellier and Anirudh Krishna. Numerical study of hypergraph product codes. 2019. 10.48550/​arXiv.1810.03681.

[8] Antoine Grospellier, Lucien Grouès, Anirudh Krishna, and Anthony Leverrier. Combining hard and soft decoders for hypergraph product codes. Quantum, 5, 2021. 10.22331/​q-2021-04-15-432.

[9] Muyuan Li and Theodore J. Yoder. A Numerical Study of Bravyi-Bacon-Shor and Subsystem Hypergraph Product Codes. 2020. 10.48550/​arXiv.2002.06257.

[10] Pavel Panteleev and Gleb Kalachev. Degenerate Quantum LDPC Codes With Good Finite Length Performance. Quantum, 5, 2021. 10.22331/​q-2021-11-22-585.

[11] Joschka Roffe, David R. White, Simon Burton, and Earl Campbell. Decoding across the quantum low-density parity-check code landscape. Physical Review Research, 2 (4), 2020. 10.1103/​PhysRevResearch.2.043423.

[12] Armanda O. Quintavalle, Michael Vasmer, Joschka Roffe, and Earl T. Campbell. Single-Shot Error Correction of Three-Dimensional Homological Product Codes. PRX Quantum, 2 (2), 2021. 10.1103/​PRXQuantum.2.020340.

[13] Oscar Higgott and Nikolas P. Breuckmann. Improved Single-Shot Decoding of Higher-Dimensional Hypergraph-Product Codes. PRX Quantum, 4, 2023. 10.1103/​PRXQuantum.4.020332.

[14] M. Sipser and D.A. Spielman. Expander codes. IEEE Transactions on Information Theory, 42 (6), 1996. 10.1109/​18.556667.

[15] Héctor Bombín. Single-Shot Fault-Tolerant Quantum Error Correction. Physical Review X, 5 (3), 2015. 10.1103/​PhysRevX.5.031043.

[16] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. Topological quantum memory. Journal of Mathematical Physics, 43 (9), 2002. 10.1063/​1.1499754.

[17] URL https:/​/​github.com/​tRowans/​flip-gpu.

[18] A. Yu. Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303 (1), 2003. 10.1016/​S0003-4916(02)00018-0.

[19] Benjamin J. Brown, Naomi H. Nickerson, and Dan E. Browne. Fault-tolerant error correction with the gauge color code. Nature Communications, 7 (1), 2016. 10.1038/​ncomms12302.

[20] Chenyang Wang, Jim Harrington, and John Preskill. Confinement-Higgs transition in a disordered gauge theory and the accuracy threshold for quantum memory. Annals of Physics, 303 (1): 31–58, 2003. 10.1016/​S0003-4916(02)00019-2.

[21] Joschka Roffe, Lawrence Z. Cohen, Armanda O. Quintavalle, Daryus Chandra, and Earl T. Campbell. Bias-tailored quantum LDPC codes. 2022. 10.48550/​arXiv.2202.01702.

[22] Jinghu Chen, A. Dholakia, E. Eleftheriou, M.P.C. Fossorier, and Xiao-Yu Hu. Reduced-complexity decoding of LDPC codes. IEEE Transactions on Communications, 53 (8), 2005. 10.1109/​TCOMM.2005.852852.

[23] Barbara M. Terhal. Quantum error correction for quantum memories. Reviews of Modern Physics, 87 (2), 2015. 10.1103/​RevModPhys.87.307.

[24] Poulami Das, Christopher A. Pattison, Srilatha Manne, Douglas Carmean, Krysta Svore, Moinuddin Qureshi, and Nicolas Delfosse. A Scalable Decoder Micro-architecture for Fault-Tolerant Quantum Computing. 2020. 10.48550/​arXiv.2001.06598.

[25] Christopher Chamberland, Luis Goncalves, Prasahnt Sivarajah, Eric Peterson, and Sebastian Grimberg. Techniques for combining fast local decoders with global decoders under circuit-level noise. 2022. 10.48550/​arXiv.2208.01178.

[26] Luka Skoric, Dan E. Browne, Kenton M. Barnes, Neil I. Gillespie, and Earl T. Campbell. Parallel window decoding enables scalable fault tolerant quantum computation. 2022. 10.48550/​arXiv.2209.08552.

[27] Thomas R. Scruby, Michael Vasmer, and Dan E. Browne. Non-Pauli errors in the three-dimensional surface code. Physical Review Research, 4 (4), 2022. 10.1103/​PhysRevResearch.4.043052.

[28] Aleksander Kubica and John Preskill. Cellular-Automaton Decoders with Provable Thresholds for Topological Codes. Physical Review Letters, 123 (2), 2019. 10.1103/​PhysRevLett.123.020501.

[29] Michael Vasmer, Dan E. Browne, and Aleksander Kubica. Cellular automaton decoders for topological quantum codes with noisy measurements and beyond. Scientific Reports, 11 (1), 2021. 10.1038/​s41598-021-81138-2.

[30] Pavel Panteleev and Gleb Kalachev. Asymptotically Good Quantum and Locally Testable Classical LDPC Codes. 2022. 10.48550/​arXiv.2111.03654.

[31] Anthony Leverrier and Gilles Zémor. Quantum Tanner codes. 2022a. 10.48550/​arXiv.2202.13641.

[32] Shouzhen Gu, Christopher A. Pattison, and Eugene Tang. An efficient decoder for a linear distance quantum LDPC code. 2022. 10.48550/​arXiv.2206.06557.

[33] Anthony Leverrier and Gilles Zémor. Decoding quantum Tanner codes. 2022b. 10.48550/​arXiv.2208.05537.

[34] Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, and Thomas Vidick. Good Quantum LDPC Codes with Linear Time Decoders. 2022. 10.48550/​arXiv.2206.07750.

Cited by

[1] Lucas Berent, Timo Hillmann, Jens Eisert, Robert Wille, and Joschka Roffe, "Analog Information Decoding of Bosonic Quantum Low-Density Parity-Check Codes", PRX Quantum 5 2, 020349 (2024).

[2] Joschka Roffe, Lawrence Z. Cohen, Armanda O. Quintavalle, Daryus Chandra, and Earl T. Campbell, "Bias-tailored quantum LDPC codes", Quantum 7, 1005 (2023).

[3] Nithin Raveendran, Emmanuel Boutillon, and Bane Vasić, 2023 12th International Symposium on Topics in Coding (ISTC) 1 (2023) ISBN:979-8-3503-2611-6.

The above citations are from Crossref's cited-by service (last updated successfully 2024-06-22 09:24:16) and SAO/NASA ADS (last updated successfully 2024-06-22 09:24:17). The list may be incomplete as not all publishers provide suitable and complete citation data.