Check-Agnosia based Post-Processor for Message-Passing Decoding of Quantum LDPC Codes

Julien du Crest; Francisco Garcia-Herrero; Mehdi Mhalla; Valentin Savin; Javier Valls

doi:10.22331/q-2024-05-02-1334

Check-Agnosia based Post-Processor for Message-Passing Decoding of Quantum LDPC Codes

Julien du Crest¹, Francisco Garcia-Herrero², Mehdi Mhalla³, Valentin Savin⁴, and Javier Valls⁵

¹Université Grenoble Alpes, Grenoble INP, LIG, F-38000 Grenoble, France
²Department of Computer Architecture and Automatics, Complutense University of Madrid, Madrid, Spain
³Université Grenoble Alpes, CNRS, Grenoble INP, LIG, F-38000 Grenoble, France
⁴Université Grenoble Alpes, CEA-Léti, F-38054 Grenoble, France
⁵Instituto de Telecomunicaciones y Aplicaciones Multimedia, Universitat Politecnica de Valencia, Valencia, Spain

Published:	2024-05-02, volume 8, page 1334
Eprint:	arXiv:2310.15000v3
Doi:	https://doi.org/10.22331/q-2024-05-02-1334
Citation:	Quantum 8, 1334 (2024).

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

Abstract

The inherent degeneracy of quantum low-density parity-check codes poses a challenge to their decoding, as it significantly degrades the error-correction performance of classical message-passing decoders. To improve their performance, a post-processing algorithm is usually employed. To narrow the gap between algorithmic solutions and hardware limitations, we introduce a new post-processing algorithm with a hardware-friendly orientation, providing error correction performance competitive to the state-of-the-art techniques. The proposed post-processing, referred to as check-agnosia, is inspired by stabilizer-inactivation, while considerably reducing the required hardware resources, and providing enough flexibility to allow different message-passing schedules and hardware architectures. We carry out a detailed analysis for a set of Pareto architectures with different tradeoffs between latency and power consumption, derived from the results of implemented designs on an FPGA board. We show that latency values close to one microsecond can be obtained on the FPGA board, and provide evidence that much lower latency values can be obtained for ASIC implementations. In the process, we also demonstrate the practical implications of the recently introduced t-covering layers and random-order layered scheduling.

Featured image: Latency and power consumption of different designs for the post-processing.

Popular summary

In this work, we describe and analyse a new post-processing for message passing decoding of Quantum LDPC codes that can be run efficiently on parallel architectures.

► BibTeX data

@article{duCrest2024checkagnosiabased,
  doi = {10.22331/q-2024-05-02-1334},
  url = {https://doi.org/10.22331/q-2024-05-02-1334},
  title = {Check-{A}gnosia based {P}ost-{P}rocessor for {M}essage-{P}assing {D}ecoding of {Q}uantum {LDPC} {C}odes},
  author = {du Crest, Julien and Garcia-Herrero, Francisco and Mhalla, Mehdi and Savin, Valentin and Valls, Javier},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1334},
  month = may,
  year = {2024}
}

► References

[1] Z. Babar, P. Botsinis, D. Alanis, S. X. Ng, and L. Hanzo, ``Fifteen Years of Quantum LDPC Coding and Improved Decoding Strategies,'' IEEE Access, vol. 3, pp. 2492–2519, 2015. [Online]. Available: https://doi.org/10.1109/ACCESS.2015.2503267 0pt.
https://doi.org/10.1109/ACCESS.2015.2503267

[2] D. Gottesman, ``Fault-tolerant quantum computation with constant overhead,'' Quantum Information & Computation, vol. 14, no. 15-16, pp. 1338–1372, 2014. [Online]. Available: https://doi.org/10.48550/arXiv.1310.2984 0pt.
https://doi.org/10.48550/arXiv.1310.2984

[3] N. P. Breuckmann and J. N. Eberhardt, ``Quantum Low-Density Parity-Check Codes,'' PRX Quantum, vol. 2, p. 040101, Oct 2021. [Online]. Available: https://doi.org/10.1103/PRXQuantum.2.040101 0pt.
https://doi.org/10.1103/PRXQuantum.2.040101

[4] S. Bravyi, O. Dial, J. M. Gambetta, D. Gil, and Z. Nazario, ``The future of quantum computing with superconducting qubits,'' Journal of Applied Physics, vol. 132, no. 16, 2022. [Online]. Available: https://doi.org/10.1063/5.0082975 0pt.
https://doi.org/10.1063/5.0082975

[5] P. Panteleev and G. Kalachev, ``Degenerate Quantum LDPC Codes With Good Finite Length Performance,'' Quantum, vol. 5, p. 585, nov 2021. [Online]. Available: https://doi.org/10.22331/q-2021-11-22-585 0pt.
https://doi.org/10.22331/q-2021-11-22-585

[6] N. P. Breuckmann and J. N. Eberhardt, ``Balanced Product Quantum Codes,'' IEEE Transactions on Information Theory, vol. 67, no. 10, pp. 6653–6674, oct 2021. [Online]. Available: https://doi.org/10.1109/TIT.2021.3097347 0pt.
https://doi.org/10.1109/TIT.2021.3097347

[7] A. Leverrier and G. Zémor, ``Quantum Tanner codes,'' in 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022, pp. 872–883. [Online]. Available: https://doi.org/10.1109/FOCS54457.2022.00117 0pt.
https://doi.org/10.1109/FOCS54457.2022.00117

[8] N. P. Breuckmann and V. Londe, ``Single-Shot Decoding of Linear Rate LDPC Quantum Codes With High Performance,'' IEEE Transactions on Information Theory, vol. 68, no. 1, pp. 272–286, 2022. [Online]. Available: https://doi.org/10.1109/TIT.2021.3122352 0pt.
https://doi.org/10.1109/TIT.2021.3122352

[9] S. Bravyi, A. W. Cross, J. M. Gambetta, D. Maslov, P. Rall, and T. J. Yoder, ``High-threshold and low-overhead fault-tolerant quantum memory,'' preprint arXiv:2308.07915, 2023. [Online]. Available: https://doi.org/10.48550/arXiv.2308.07915 0pt.
https://doi.org/10.48550/arXiv.2308.07915
arXiv:2308.07915

[10] J. Roffe, ``Towards practical quantum LDPC codes,'' Quantum Views, vol. 5, p. 63, 2021. [Online]. Available: https://doi.org/10.22331/qv-2021-11-30-63 0pt.
https://doi.org/10.22331/qv-2021-11-30-63

[11] N. Raveendran and B. Vasić , ``Trapping Sets of Quantum LDPC Codes,'' Quantum, vol. 5, p. 562, oct 2021. [Online]. Available: https://doi.org/10.22331/q-2021-10-14-562 0pt.
https://doi.org/10.22331/q-2021-10-14-562

[12] F. Battistel, C. Chamberland, K. Johar, R. W. J. Overwater, F. Sebastiano, L. Skoric, Y. Ueno, and M. Usman, ``Real-Time Decoding for Fault-Tolerant Quantum Computing: Progress, Challenges and Outlook,'' 2023. [Online]. Available: https://doi.org/10.1088/2399-1984/aceba6 0pt.
https://doi.org/10.1088/2399-1984/aceba6

[13] N. Raveendran, E. Boutillon, and B. Vasic, ``Turbo-XZ Algorithm: Low-Latency Decoders for Quantum LDPC Codes,'' in International Symposium on Topics in Coding, 2023. [Online]. Available: https://doi.org/10.1109/ISTC57237.2023.10273490 0pt.
https://doi.org/10.1109/ISTC57237.2023.10273490

[14] N. Delfosse and N. H. Nickerson, ``Almost-linear time decoding algorithm for topological codes,'' Quantum, vol. 5, p. 595, Dec. 2021. [Online]. Available: https://doi.org/10.22331/q-2021-12-02-595 0pt.
https://doi.org/10.22331/q-2021-12-02-595

[15] Y.-H. Liu and D. Poulin, ``Neural Belief-Propagation Decoders for Quantum Error-Correcting Codes,'' Phys. Rev. Lett., vol. 122, p. 200501, May 2019. [Online]. Available: https://doi.org/10.1103/PhysRevLett.122.200501 0pt.
https://doi.org/10.1103/PhysRevLett.122.200501

[16] J. D. Crest, M. Mhalla, and V. Savin, ``Stabilizer Inactivation for Message-Passing Decoding of Quantum LDPC Codes,'' in 2022 IEEE Information Theory Workshop (ITW), 2022, pp. 488–493. [Online]. Available: https://doi.org/10.1109/ITW54588.2022.9965902 0pt.
https://doi.org/10.1109/ITW54588.2022.9965902

[17] X. Ni, ``Neural Network Decoders for Large-Distance 2D Toric Codes,'' Quantum, vol. 4, p. 310, Aug 2020. [Online]. Available: http://doi.org/10.22331/q-2020-08-24-310 0pt.
https://doi.org/10.22331/q-2020-08-24-310

[18] C. Chamberland and P. Ronagh, ``Deep neural decoders for near term fault-tolerant experiments,'' Quantum Science and Technology, vol. 3, no. 4, p. 044002, jul 2018. [Online]. Available: https://doi.org/10.1088/2058-9565/aad1f7 0pt.
https://doi.org/10.1088/2058-9565/aad1f7

[19] P. Murali, N. M. Linke, M. Martonosi, A. J. Abhari, N. H. Nguyen, and C. H. Alderete, ``Full-Stack, Real-System Quantum Computer Studies: Architectural Comparisons and Design Insights,'' in Proceedings of the 46th International Symposium on Computer Architecture, ser. ISCA '19. New York, NY, USA: Association for Computing Machinery, 2019, p. 527–540. [Online]. Available: https://doi.org/10.1145/3307650.3322273 0pt.
https://doi.org/10.1145/3307650.3322273

[20] J. Roffe, D. R. White, S. Burton, and E. Campbell, ``Decoding across the quantum low-density parity-check code landscape,'' Physical Review Research, vol. 2, no. 4, dec 2020. [Online]. Available: https://doi.org/10.1103/PhysRevResearch.2.043423 0pt.
https://doi.org/10.1103/PhysRevResearch.2.043423

[21] J. Valls, F. Garcia-Herrero, N. Raveendran, and B. Vasić, ``Syndrome-Based Min-Sum vs OSD-0 Decoders: FPGA Implementation and Analysis for Quantum LDPC Codes,'' IEEE Access, vol. 9, pp. 138 734–138 743, 2021. [Online]. Available: https://doi.org/10.1109/ACCESS.2021.3118544 0pt.
https://doi.org/10.1109/ACCESS.2021.3118544

[22] Y. Ueno, M. Kondo, M. Tanaka, Y. Suzuki, and Y. Tabuchi, ``QECOOL: On-line quantum error correction with a superconducting decoder for surface code,'' in 2021 58th ACM/IEEE Design Automation Conference (DAC). IEEE, dec 2021. [Online]. Available: https://doi.org/10.1109/dac18074.2021.9586326 0pt.
https://doi.org/10.1109/dac18074.2021.9586326

[23] S. S. Tannu, Z. A. Myers, P. J. Nair, D. M. Carmean, and M. K. Qureshi, ``Taming the Instruction Bandwidth of Quantum Computers via Hardware-Managed Error Correction,'' in Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture, ser. MICRO-50 '17. New York, NY, USA: Association for Computing Machinery, 2017, p. 679–691. [Online]. Available: https://doi.org/10.1145/3123939.3123940 0pt.
https://doi.org/10.1145/3123939.3123940

[24] E. Sharon, S. Litsyn, and J. Goldberger, ``An efficient message-passing schedule for LDPC decoding,'' in 2004 23rd IEEE Convention of Electrical and Electronics Engineers in Israel, 2004, pp. 223–226. [Online]. Available: https://doi.org/10.1109/EEEI.2004.1361130 0pt.
https://doi.org/10.1109/EEEI.2004.1361130

[25] M. Mansour and N. Shanbhag, ``VLSI architectures for SISO-APP decoders,'' IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 11, no. 4, pp. 627–650, 2003. [Online]. Available: https://doi.org/10.1109/TVLSI.2003.816136 0pt.
https://doi.org/10.1109/TVLSI.2003.816136

[26] E. Boutillon and G. Masera, ``Hardware design and realization for iteratively decodable codes,'' in Channel coding: Theory, algorithms, and applications, D. Declercq, M. Fossorier, and E. Biglieri, Eds. Elsevier, 2014, pp. 583–642. [Online]. Available: https://doi.org/10.1016/B978-0-12-396499-1.00013-3 0pt.
https://doi.org/10.1016/B978-0-12-396499-1.00013-3

[27] V. Savin, ``LDPC decoders,'' in Channel coding: Theory, algorithms, and applications, D. Declercq, M. Fossorier, and E. Biglieri, Eds. Elsevier, 2014, pp. 211–260. [Online]. Available: https://doi.org/10.1016/C2011-0-07211-3 0pt.
https://doi.org/10.1016/C2011-0-07211-3

[28] J. Zhang, Y. Wang, M. P. C. Fossorier, and J. S. Yedidia, ``Iterative decoding with replicas,'' IEEE Transactions on Information Theory, vol. 53, no. 5, pp. 1644–1663, 2007. [Online]. Available: https://doi.org/10.1109/TIT.2007.894683 0pt.
https://doi.org/10.1109/TIT.2007.894683

[29] J. du Crest, F. Garcia-Herrero, M. Mhalla, V. Savin, and J. Valls, ``Layered decoding of quantum LDPC codes,'' in International Symposium on Topics in Coding, 2023, arXiv:2308.13377. [Online]. Available: https://doi.org/10.1109/ISTC57237.2023.10273477 0pt.
https://doi.org/10.1109/ISTC57237.2023.10273477
arXiv:2308.13377

[30] G. Liva, E. Paolini, B. Matuz, and M. Chiani, ``A decoding algorithm for LDPC codes over erasure channels with sporadic errors,'' in 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2010, pp. 458–465. [Online]. Available: https://doi.org/10.1109/ALLERTON.2010.5706942 0pt.
https://doi.org/10.1109/ALLERTON.2010.5706942

[31] A. D. Kumar and A. Dukkipati, ``A two stage selective averaging LDPC decoding,'' in 2012 IEEE International Symposium on Information Theory Proceedings, 2012, pp. 2866–2870. [Online]. Available: https://doi.org/10.1109/ISIT.2012.6284048 0pt.
https://doi.org/10.1109/ISIT.2012.6284048

[32] M. Luby, M. Mitzenmacher, M. Shokrollahi, and D. Spielman, ``Efficient erasure correcting codes,'' IEEE Trans. on Information Theory, vol. 47, no. 2, pp. 569–584, 2001. [Online]. Available: https://doi.org/10.1109/18.910575 0pt.
https://doi.org/10.1109/18.910575

[33] O. Boncalo, G. Kolumban-Antal, A. Amaricai, V. Savin, and D. Declercq, ``Layered LDPC decoders with efficient memory access scheduling and mapping and built-in support for pipeline hazards mitigation,'' IEEE Transactions on Circuits and Systems I: Regular Papers, pp. 1643–1656, December 2018. [Online]. Available: https://doi.org/10.1109/TCSI.2018.2884252 0pt.
https://doi.org/10.1109/TCSI.2018.2884252

[34] O. Boncalo, G. Kolumban-Antal, D. Declercq, and V. Savin, ``Code-design for efficient pipelined layered LDPC decoders with bank memory organization,'' Microprocessors and Microsystems, vol. 63, pp. 216–225, September 2018. [Online]. Available: https://doi.org/10.1016/j.micpro.2018.09.011 0pt.
https://doi.org/10.1016/j.micpro.2018.09.011

[35] T. T. Nguyen-Ly, V. Savin, K. Le, D. Declercq, F. Ghaffari, and O. Boncalo, ``Analysis and design of cost-effective, high-throughput LDPC decoders,'' IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 26, no. 3, pp. 508–521, March 2018. [Online]. Available: https://doi.org/10.1109/TVLSI.2017.2776561 0pt.
https://doi.org/10.1109/TVLSI.2017.2776561

[36] J. R. Hauser, ``MOSFET device scaling,'' in Handbook of Semiconductor Manufacturing Technology. Boca Raton, FL: CRC Press, 2008. [Online]. Available: https://doi.org/10.1201/9781420017663 0pt.
https://doi.org/10.1201/9781420017663

[37] A. Rupp, J. Pelzl, C. Paar, M. Mertens, and A. Bogdanov, ``A parallel hardware architecture for fast gaussian elimination over gf(2),'' in 2006 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 2006, pp. 237–248. [Online]. Available: https://doi.org/10.1109/FCCM.2006.12 0pt.
https://doi.org/10.1109/FCCM.2006.12

[38] B. Hochet, P. Quinton, and Y. Robert, ``Systolic solution of linear systems over gf(p) with partial pivoting,'' in 1987 IEEE 8th Symposium on Computer Arithmetic (ARITH), 1987, pp. 161–168. [Online]. Available: https://doi.org/10.1109/ARITH.1987.6158700 0pt.
https://doi.org/10.1109/ARITH.1987.6158700

Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2024-05-17 02:37:02). On SAO/NASA ADS no data on citing works was found (last attempt 2024-05-17 02:37:02).

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.