CoChat
Sign Up
Cited by 192Quantum Computing Algorithms and ArchitectureError Correcting Code TechniquesQuantum many-body systems

Decoding across the quantum low-density parity-check code landscape

Open access
Roffe, Joschka, White, David R., Burton, Simon, Campbell, Earl·2020·Physical Review Research
DOI 10.1103/physrevresearch.2.043423
Open this paper in CoChat — free accountOpen PDF

Abstract

We show that belief propagation combined with ordered statistics post-processing is a general decoder for quantum low-density parity-check codes constructed from the hypergraph product.To this end, we run numerical simulations of the decoder applied to three families of hypergraph product code: topological codes, fixed-rate random codes, and a new class of codes that we call semitopological codes.Our new code families share properties of both topological and random hypergraph product codes, with a construction that allows for a finely controlled trade-off between code threshold and stabilizer locality.Our results indicate thresholds across all three families of hypergraph product code, and provide evidence of exponential suppression in the low error regime.For the toric code, we observe a threshold in the range 9.9% ± 0.2%.This result improves upon previous quantum decoders based on belief propagation, and approaches the performance of the minimum-weight perfectmatching algorithm.We expect semitopological codes to have the same threshold as toric codes, as they are identical in the bulk, and we present numerical evidence supporting this observation.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1103/physrevresearch.2.043423

Cites

9 of 9 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Enhancing BP with classical decoding techniques such as ordered statistics decoding (OSD) or localized statistics decoding (LSD) significantly improves performance.

    “Also, one can enhance BP with classical decoding techniques such as ordered statistics decoding (OSD) [197] or localized statistics decoding (LSD) [198]. These approaches significantly improve performance.”

    From Quantum error correction and fault tolerance: A comprehensive tutorial (2026) · cites this paper as [197]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 51

  1. P. W. Shor, Scheme for reducing decoherence in quantum com- puter memory, Phys. Rev. A 52, R2493 (1995). · DOI · Paper page
  2. D. Gottesman, An introduction to quantum error correction and fault-tolerant quantum computation, arXiv:0904.2557. · arXiv
  3. S. J. Devitt, W. J. Munro, and K. Nemoto, Quantum error correction for beginners, Rep. Prog. Phys. 76, 076001 (2013). · DOI
  4. J. Roffe, Quantum error correction: An introductory guide, Contemp. Phys. 60, 226 (2019). · DOI
  5. N. Delfosse, Hierarchical decoding to reduce hardware require- ments for quantum computing, arXiv:2001.11427. · arXiv
  6. Z. Babar, P. Botsinis, D. Alanis, S. X. Ng, and Lajos Hanzo, Fifteen years of quantum LDPC coding and improved decoding strategies, IEEE Access 3, 2492 (2015). · DOI
  7. R. Gallager, Low-density parity-check codes, IRE Trans. Inf. Theory 8, 21 (1962). · DOI
  8. J. H. Bae, A. Abotabl, H.-P. Lin, K.-B. Song, and J. Lee, An overview of channel coding for 5G NR cellular commu- nications, APSIPA Transactions on Signal and Information Processing 8, E17 (2019). · DOI
  9. J. Pearl, Reverend Bayes on inference engines: A distributed hierarchical approach, in Proceedings of the National Confer- ence on Artificial Intelligence, Carnegie Mellon University and the University of Pittsburgh, Pittsburgh, Pennsylvania (AAAI, 1982), pp. 133-136.
  10. C. E. Shannon, A mathematical theory of communication, Bell System Tech. J 27, 379 (1948). · DOI · Paper page
  11. D. J. C. MacKay and R. M. Neal, Near Shannon limit perfor- mance of low density parity check codes, Electron. Lett. 33, 457 (1997). · DOI
  12. J.-P. Tillich and G. Zémor, Quantum LDPC codes with pos- itive rate and minimum distance proportional to the square root of the blocklength, IEEE Trans. Inf. Theory 60, 1193 (2013). · DOI
  13. B. Criger and I. Ashraf, Multi-path summation for decoding 2D topological codes, Quantum 2, 102 (2018). · DOI
  14. E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Topological quantum memory, J. Math. Phys. 43, 4452 (2002). · DOI · Paper page
  15. A. Leverrier, J.-P. Tillich, and G. Zémor, Quantum expander codes, in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (IEEE, 2015), pp. 810-824.
  16. O. Fawzi, A. Grospellier, and A. Leverrier, Efficient decoding of random errors for quantum expander codes, in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (ACM, 2018), pp. 521-534.
  17. A. Grospellier and A. Krishna, Numerical study of hypergraph product codes, arXiv:1810.03681. · arXiv
  18. A. Grospellier, Lucien Grouès, A. Krishna, and A. Leverrier, Combining hard and soft decoders for hypergraph product codes, arXiv:2004.11199. · arXiv
  19. P. Panteleev and G. Kalachev, Degenerate quantum LDPC codes with good finite length performance, arXiv:1904.02703. · arXiv
  20. M. P. C. Fossorier and S. Lin, Soft-decision decoding of linear block codes based on ordered statistics, IEEE Trans. Inf. Theory 41, 1379 (1995). · DOI
  21. M. P. C. Fossorier, Iterative reliability-based decoding of low- density parity check codes, IEEE J. Select. Areas Commun. 19, 908 (2001). · DOI
  22. A. Yu. Kitaev, Fault-tolerant quantum computation by anyons, Ann. Phys. 303, 2 (2003). · DOI · Paper page
  23. J. Kelly, R. Barends, A. G. Fowler, A. Megrant, E. Jeffrey, T. C. White, D. Sank, J. Y. Mutus, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, E. Lucero, M. Neeley, C. Neill, P. J. J. O'Malley, C. Quintana, P. Roushan, A. Vainsencher, J. Wenner, and J. M. Martinis, Scalable in situ qubit calibration during repetitive error detection, Phys. Rev. A 94, 032321 (2016). · DOI
  24. E. A. Sete, W. J. Zeng, and C. T. Rigetti, A functional architecture for scalable quantum computing, in 2016 IEEE In- ternational Conference on Rebooting Computing (ICRC) (IEEE, 2016), pp. 1-6.
  25. J. Randall, S. Weidt, E. D. Standing, K. Lake, S. C. Webster, D. F. Murgia, T. Navickas, K. Roth, and W. K. Hensinger, Efficient preparation and detection of microwave dressed-state qubits and qutrits with trapped ions, Phys. Rev. A 91, 012322 (2015). · DOI
  26. S. Debnath, N. M. Linke, C. Figgatt, K. A. Landsman, K. Wright, and C. Monroe, Demonstration of a small pro- grammable quantum computer with atomic qubits, Nature (London) 536, 63 (2016). · DOI · Paper page
  27. M. F. Brandl, M. W. van Mourik, L. Postler, A. Nolf, K. Lakhmanskiy, R. R. Paiva, S. Möller, N. Daniilidis, H. Häffner, V. Kaushal, T. Ruster, C. Warschburger, H. Kaufmann, U. G. Poschinger, F. Schmidt-Kaler, P. Schindler, T. Monz, and R. Blatt, Cryogenic setup for trapped ion quantum computing, Rev. Sci. Instrum. 87, 113103 (2016). · DOI
  28. C. J. Ballance, T. P. Harty, N. M. Linke, M. A. Sepiol, and D. M. Lucas, High-Fidelity Quantum Logic Gates Using Trapped-Ion Hyperfine Qubits, Phys. Rev. Lett. 117, 060504 (2016). · DOI · Paper page
  29. X. Qiang, X. Zhou, J. Wang, Callum M. Wilkes, T. Loke, Sean O'Gara, L. Kling, Graham D. Marshall, R. Santagati, Timothy C. Ralph, Jingbo B. Wang, Jeremy L. O'Brien, Mark G. Thompson, and J. C. F. Matthews, Large-scale silicon quantum photonics implementing arbitrary two-qubit process- ing, Nat. Photonics 12, 534 (2018). · DOI
  30. X.-L. Wang, L.-K. Chen, W. Li, H.-L. Huang, C. Liu, C. Chen, Y.-H. Luo, Z.-E. Su, D. Wu, Z.-D. Li, H. Lu, Y. Hu, X. Jiang, C.-Z. Peng, L. Li, N.-L. Liu, Yu.-A. Chen, C.-Y. Lu, and J.-W. Pan, Experimental Ten-Photon Entanglement, Phys. Rev. Lett. 117, 210502 (2016). · DOI
  31. Y. Wu, Y. Wang, X. Qin, X. Rong, and J. Du, A programmable two-qubit solid-state quantum processor under ambient condi- tions, npj Quantum Inf. 5, 1 (2019). · DOI
  32. A. A. Kovalev, S. Prabhakar, I. Dumer, L. P. Pryadko, Nu- merical and analytical bounds on threshold error rates for hypergraph-product codes, Phys. Rev. A 97, 062320 (2018). · DOI
  33. Y.-H. Liu and D. Poulin, Neural Belief-Propagation Decoders for Quantum Error-Correcting Codes, Phys. Rev. Lett. 122, 200501 (2019). · DOI
  34. N. H. Nickerson, J. F. Fitzsimons, and S. C. Benjamin, Freely Scalable Quantum Technologies Using Cells of 5-to-50 Qubits with Very Lossy and Noisy Photonic Links, Phys. Rev. X 4, 041041 (2014). · DOI
  35. V. Kolmogorov, Blossom V: A new implementation of a mini- mum cost perfect matching algorithm, Math. Program. Comput. 1, 43 (2009). · DOI
  36. R. Tanner, A recursive approach to low complexity codes, IEEE Trans. Inf. Theory 27, 533 (1981). · DOI
  37. J. Roffe, S. Zohren, D. Horsman, and N. Chancellor, Quantum codes from classical graphical models, IEEE Trans. Inf. Theory 66, 130 (2020). · DOI
  38. Emanuel Knill and R. Laflamme, Theory of quantum error- correcting codes, Phys. Rev. A 55, 900 (1997). · DOI · Paper page
  39. D. Gottesman, The Heisenberg representation of quantum com- puters, in Group22: Proceedings of the XXII International Colloquium on Group Theoretical Methods in Physics (Inter- national Press, Cambridge, MA, 1999), pp. 32-43.
  40. A. M. Steane, Error Correcting Codes in Quantum Theory, Phys. Rev. Lett. 77, 793 (1996). · DOI · Paper page
  41. A. M. Steane, Active Stabilization, Quantum Computation, and Quantum State Synthesis, Phys. Rev. Lett. 78, 2252 (1997). · DOI
  42. D. J. C. MacKay, G. Mitchison, and P. L McFadden, Sparse- graph codes for quantum error correction, IEEE Trans. Inf. Theory 50, 2315 (2004). · DOI
  43. D. J. C. MacKay, Good error-correcting codes based on very sparse matrices, IEEE Trans. Inf. Theory 45, 399 (1999). · DOI
  44. A. A. Emran and M. Elsabrouty, Simplified variable-scaled min-sum LDPC decoder for irregular LDPC codes, in 2014 IEEE 11th Consumer Communications and Networking Con- ference (CCNC) (IEEE, 2014), pp. 518-523.
  45. A. O. Quintavalle, M. Vasmer, J. Roffe, and E. T. Campbell, Single-shot error correction of three-dimensional homological product codes, arXiv:2009.11790. · arXiv
  46. H. Bombín, Single-Shot Fault-Tolerant Quantum Error Correc- tion, Phys. Rev. X 5, 031043 (2015). · DOI
  47. M. Vasmer and D. E. Browne, Three-dimensional surface codes: Transversal gates and fault-tolerant architectures, Phys. Rev. A 100, 012312 (2019). · DOI
  48. E. Campbell, A theory of single-shot error correction for adver- sarial noise, Quantum Sci. Technol. 4, 025006 (2019). · DOI
  49. S. Vijay, J. Haah, and L. Fu, Fracton topological order, general- ized lattice gauge theory, and duality, Phys. Rev. B 94, 235157 (2016). · DOI
  50. M. Hagiwara, K. Kasai, H. Imai, and K. Sakaniwa, Spatially coupled quasi-cyclic quantum LDPC codes, in 2011 IEEE Inter- national Symposium on Information Theory Proceedings (IEEE, 2011), pp. 638-642.
  51. S. van der Walt, S. C. Colbert, and G. Varoquaux, The NumPy array: A structure for efficient numerical computation, Comput. Sci. Eng. 13, 22 (2011). · DOI

Cited by

Sorted by citations

Authors
Roffe, J., White, D. R., Burton, S., & Campbell, E.
Affiliations
  • University of Sheffield (GB)
  • University College London (GB)
ORCID
Venue
Physical Review Research
Publisher
American Physical Society (APS)
Published
2020-12-28
Volume
2
Issue
4
ISSN
2643-1564 (ISSN-L)
DOI
10.1103/physrevresearch.2.043423
OpenAlex
W3025282692
Cited by
192
References
9
Citations by year
2026: 41 · 2025: 64 · 2024: 36 · 2023: 21 · 2022: 18 · 2021: 11 · 2017: 1
FWCI
4.83
Type
journal article
Language
en
Open access
Licence
Locations
  • Physical Review Research (publishedVersion, cc-by)
  • White Rose Research Online (University of Leeds, The University of Sheffield, University of York) (acceptedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • Horizon 2020 (EP/R043825/1)
  • Engineering and Physical Sciences Research Council (EP/M024261/1)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Computer Networks and Communications › Error Correcting Code Techniques
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
Keywords
quantum low-density parity-check codes, hypergraph product codes, belief propagation decoding, quantum error correction threshold, toric code, topological codes, minimum-weight perfect matching

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review