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.

Abstract

$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.

Featured image: Left: numerical data showing threshold behaviour for 500 cycles of decoding with the belief propagation decoder, which cannot correct any error equivalent to half of a stabiliser.
Right: numerical data showing threshold behaviour for a modified non-deterministic belief propagation decoder that can probabilistically correct half-stabiliser errors. Performance is improved relative to the performance of traditional BP.

Popular summary

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

@article{Scruby2023localprobabilistic, doi = {10.22331/q-2023-08-29-1093}, url = {https://doi.org/10.22331/q-2023-08-29-1093}, title = {Local {P}robabilistic {D}ecoding of a {Q}uantum {C}ode}, author = {Scruby, T. R. and Nemoto, K.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pages = {1093}, month = aug, year = {2023}<br /> }

► 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.
https://doi.org/10.48550/arXiv.quant-ph/9705052
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.
https://doi.org/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.
https://doi.org/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].
https://doi.org/10.1109/FOCS.2015.55
arXiv:1504.00822

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

[7] Antoine Grospellier and Anirudh Krishna. Numerical study of hypergraph product codes. 2019. 10.48550/arXiv.1810.03681.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1063/1.1499754

[17] URL https://github.com/tRowans/flip-gpu.
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.48550/arXiv.2111.03654

[31] Anthony Leverrier and Gilles Zémor. Quantum Tanner codes. 2022a. 10.48550/arXiv.2202.13641.
https://doi.org/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.
https://doi.org/10.48550/arXiv.2206.06557

[33] Anthony Leverrier and Gilles Zémor. Decoding quantum Tanner codes. 2022b. 10.48550/arXiv.2208.05537.
https://doi.org/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.
https://doi.org/10.48550/arXiv.2206.07750

Cited by

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

The above citations are from SAO/NASA ADS (last updated successfully 2023-08-30 11:21:05). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref’s cited-by service no data on citing works was found (last attempt 2023-08-30 11:21:03).

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.

SEO Powered Content & PR Distribution. Get Amplified Today.
PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
PlatoESG. Automotive / EVs, Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
ChartPrime. Elevate your Trading Game with ChartPrime. Access Here.
BlockOffsets. Modernizing Environmental Offset Ownership. Access Here.
Source: https://quantum-journal.org/papers/q-2023-08-29-1093/

Generative Data Intelligence

Local Probabilistic Decoding of a Quantum Code

Abstract

Popular summary

► BibTeX data

► References

Cited by

Shiba Inu Leads in Robinhood’s Crypto Performance

DOJ Disputes Roman Storm’s Characterization of Tornado Cash Operations in New Filing

Latest Intelligence

Top 5 Crypto Presales: BDAG Leads the Pack with 30,000x ROI Potential

Forbes Unveils 20 Crypto ‘Zombies,’ Declares Ripple And XRP Among The Undead

Consob, Italy’s Watchdog, Bans Additional Forex And Cryptocurrency Trading Websites – CryptoInfoNet

Fed’s Inflation Gauge Heats Up, Rate Cuts on Hold as Bitcoin and Stocks Slide

Explore Top 6 Cryptos for 2024: BlockDAG Leads with Unprecedented ROI Potential

Franklin Templeton’s Ethereum spot ETF listed on DTCC

Chat with us