CoChat
Sign Up
PreprintCited by 1Quantum Computing Algorithms and ArchitectureError Correcting Code TechniquesCoding theory and cryptography

The DOI matches its DataCite record; 1 of the 1 references it cites were found in a registry or an index.

MaxSAT decoders for arbitrary CSS codes

Open access
Noormandipour, Mohammadreza, Haug, Tobias·2024·arXiv
DOI 10.48550/arxiv.2410.01673arXiv 2410.01673
Open this paper in CoChat — free accountOpen PDF

Abstract

Quantum error correction (QEC) is essential for operating quantum computers in the presence of noise. Here, we accurately decode arbitrary Calderbank-Shor-Steane (CSS) codes via the maximum satisfiability (MaxSAT) problem. We show how to map quantum maximum likelihood problem of CSS codes of arbitrary geometry and parity check weight into MaxSAT problems. We incorporate the syndrome measurements as hard clauses, while qubit and measurement error probabilities, including biased and non-uniform, are encoded as soft MaxSAT clauses. For the code capacity of color codes on a hexagonal lattice, our decoder has a higher threshold and superior scaling in noise suppression compared to belief propagation with ordered statistics post-processing (BP-OSD), while showing similar scaling in computational cost. Further, we decode surface codes and recently proposed bivariate quantum low-density parity check (QLDPC) codes where we find lower error rates than BP-OSD. Finally, we connect the complexity of MaxSAT decoding to a computational phase transition controlled by the clause density of the MaxSAT problem, where we show that our mapping is always in the computationally ''easy`` phase. Our MaxSAT decoder can be further parallelised or implemented on ASICs and FPGAs, promising potential further speedups of several orders of magnitude. Our work provides a flexible platform towards practical applications on quantum computers.

Overview

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

DataCite · 10.48550/arxiv.2410.01673

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

Verification

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?

  • The Max-SAT decoder maps MLE to the Max-SAT problem.

    “In particular, the Max-SAT decoder maps MLE to the Max-SAT problem: Max-SAT is an optimization problem in which one aims to find an assignment of binary variables that satisfies the maximum number of clauses [211, 212].”

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

Self-check

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

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

Citations

Cites

Flagged first, then by citations

Research works printed but not linked: 46

  1. P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM review 41, 303 (1999).
  2. M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information, Vol. 2 (Cambridge university press Cam- bridge, 2001).
  3. M. Noormandipour and H. Wang, Matching point sets with quantum circuit learning, in ICASSP 2022 -2022 IEEE Interna- tional Conference on Acoustics, Speech and Signal Processing (ICASSP) (2022) pp. 8607-8611. · DOI
  4. P. W. Shor, Fault-tolerant quantum computation, in Proceedings of 37th conference on foundations of computer science (IEEE, 1996) pp. 56-65.
  5. D. J. MacKay and R. M. Neal, Near Shannon limit performance of low density parity check codes, Electronics letters 33, 457 (1997).
  6. S. Resch and U. R. Karpuzcu, Benchmarking quantum comput- ers and the impact of quantum noise, ACM Computing Surveys (CSUR) 54, 1 (2021).
  7. A. Steane, Multiple-particle interference and quantum error correction, Proceedings of the Royal Society of London. Se- ries A: Mathematical, Physical and Engineering Sciences 452, 2551 (1996).
  8. A. R. Calderbank and P. W. Shor, Good quantum error- correcting codes exist, Physical Review A 54, 1098 (1996).
  9. S. B. Bravyi and A. Y. Kitaev, Quantum codes on a lattice with boundary, arXiv preprint quant-ph/9811052 (1998). · arXiv
  10. H. Bombin and M. A. Martin-Delgado, Topological quantum distillation, Physical review letters 97, 180501 (2006).
  11. A. A. Kovalev and L. P. Pryadko, Quantum kronecker sum- product low-density parity-check codes with finite rate, Phys- ical Review A 88, 012311 (2013).
  12. 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, Nature 627, 778 (2024).
  13. L. Voss, S. J. Xian, T. Haug, and K. Bharti, Trivari- ate bicycle codes, arXiv preprint arXiv:2406.19151 10.48550/arXiv.2406.19151 (2024). · DOI
  14. R. Acharya, L. Aghababaie-Beni, I. Aleiner, T. I. Andersen, M. Ansmann, F. Arute, K. Arya, A. Asfaw, N. Astrakhantsev, J. Atalaya, et al., Quantum error correction below the surface code threshold, arXiv preprint arXiv:2408.13687 (2024). · arXiv
  15. G. Q. AI, Suppressing quantum errors by scaling a surface code logical qubit, Nature 614, 676 (2023).
  16. D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kalinowski, D. Hangleiter, et al., Logical quantum processor based on reconfigurable atom arrays, Nature 626, 58 (2024).
  17. P. Iyer and D. Poulin, Hardness of decoding quantum stabi- lizer codes, IEEE Transactions on Information Theory 61, 5209 (2015).
  18. A. J. Ferris and D. Poulin, Tensor networks and quantum error correction, Physical review letters 113, 030501 (2014).
  19. C. T. Chubb and S. T. Flammia, Statistical mechanical models for quantum codes with correlated noise, Annales de l'Institut Henri Poincaré D 8, 269 (2021).
  20. A. Kaufmann and I. Arad, A blockbp decoder for the surface code, arXiv preprint arXiv:2402.04834 (2024). · arXiv
  21. G. Torlai and R. G. Melko, Neural decoder for topological codes, Physical review letters 119, 030501 (2017).
  22. J. Fujisaki, H. Oshima, S. Sato, and K. Fujii, Practical and scal- able decoder for topological quantum error correction with an ising machine, Physical Review Research 4, 043086 (2022).
  23. Y. Takeuchi, Y. Takada, T. Sakashita, J. Fujisaki, H. Oshima, S. Sato, and K. Fujii, Comparative study of decoding the sur- face code using simulated annealing under depolarizing noise, arXiv:2311.07973 (2023). · arXiv
  24. Y. Takada, Y. Takeuchi, and K. Fujii, Ising model formula- tion for highly accurate topological color codes decoding, Phys. Rev. Res. 6, 013092 (2024). · DOI · Paper page
  25. J. Roffe, D. R. White, S. Burton, and E. Campbell, Decoding across the quantum low-density parity-check code landscape, Physical Review Research 2, 043423 (2020).
  26. P. Panteleev and G. Kalachev, Degenerate quantum ldpc codes with good finite length performance, Quantum 5, 585 (2021).
  27. E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Topological quantum memory, Journal of Mathematical Physics 43, 4452 (2002).
  28. A. G. Fowler, Minimum weight perfect matching of fault- tolerant topological quantum error correction in average o(1) parallel time, arXiv preprint arXiv:1307.1740 (2013). · arXiv
  29. O. Higgott and C. Gidney, Sparse blossom: correcting a mil- lion errors per core second with minimum-weight matching, arXiv:2303.15933 (2023). · arXiv
  30. G. Duclos-Cianci and D. Poulin, Fast decoders for topological quantum codes, Physical review letters 104, 050504 (2010).
  31. N. Delfosse and N. H. Nickerson, Almost-linear time decoding algorithm for topological codes, Quantum 5, 595 (2021).
  32. L. Berent, L. Burgholzer, P.-J. H. Derks, J. Eisert, and R. Wille, Decoding quantum color codes with maxsat, arXiv:2303.14237 (2023). · arXiv
  33. I. P. Gent, T. Walsh, and A. Cohn, The sat phase transition (1994) pp. 105-109, proc European Conference on Artificial Intelligence 94. John Wiley and Sons.
  34. V. Chvátal and E. Szemerédi, Many hard examples for resolu- tion, J. ACM 35, 759-768 (1988). · DOI
  35. G. Bresler and B. Huang, The algorithmic phase transi- tion of random k-sat for low degree polynomials (2021), arXiv:2106.02129 [cs.CC]. · arXiv
  36. D. Coppersmith, D. Gamarnik, M. Hajiaghayi, and G. B. Sorkin, Random max sat, random max cut, and their phase transitions, Random Structures & Algorithms 24, 502 (2004), https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.20015. · DOI
  37. S. Bravyi and A. Vargo, Simulation of rare events in quantum error correction, Physical Review A 88, 062308 (2013).
  38. O. Higgott and N. P. Breuckmann, Improved single-shot de- coding of higher-dimensional hypergraph-product codes, PRX Quantum 4, 020332 (2023).
  39. A. A. Sohanghpurwala, M. W. Hassan, and P. Athanas, Hard- ware accelerated sat solvers-a survey, Journal of Parallel and Distributed Computing 106, 170 (2017).
  40. C. T. Chubb, General tensor network decoding of 2d pauli codes, arXiv preprint arXiv:2101.04125 (2021). · arXiv
  41. H. Bombín and M. A. Martin-Delgado, Optimal resources for topological two-dimensional stabilizer codes: Comparative study, Physical Review A-Atomic, Molecular, and Optical Physics 76, 012305 (2007).
  42. O. Higgott, Pymatching: A python package for decoding quantum codes with minimum-weight perfect matching, ACM Transactions on Quantum Computing 3, 1 (2022).
  43. K. Sahay and B. J. Brown, Decoder for the triangular color code by matching on a möbius strip, PRX Quantum 3, 010310 (2022).
  44. C. Gidney and C. Jones, New circuits and an open source decoder for the color code, arXiv preprint arXiv:2312.08813 (2023). · arXiv
  45. D. S. Wang, A. G. Fowler, C. D. Hill, and L. C. Hollenberg, Graphical algorithms and threshold error rates for the 2d colour code, arXiv preprint arXiv:0907.1708 (2009). · arXiv
  46. T. Schubert, M. Lewis, and B. Becker, Pamiraxt: Parallel sat solving with threads and message passing, Journal on Satisfia- bility, Boolean Modeling and Computation 6, 203 (2010).

Cited by

Sorted by citations

Metadata

Authors
Noormandipour, M., & Haug, T.
Affiliations
  • University of Cambridge (GB)
  • Technology Innovation Institute (AE)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2024
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2410.01673
arXiv
2410.01673
OpenAlex
W4403852007
Cited by
1
References
1
Citations by year
2026: 1
Type
posted content
Language
en
Open access
Licence
Locations
  • arXiv (Cornell University) (submittedVersion, cc-by-nc-sa)
  • arXiv (Cornell University)
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 › Mathematics › Discrete Mathematics and Combinatorics › Coding theory and cryptography
Keywords
CSS codes, quantum error correction, maximum likelihood decoding, color codes, surface code, syndrome measurement, computational phase transition, clause density, threshold decoding, hexagonal lattice, FPGA implementation

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