Finite-rate sparse quantum codes aplenty

Maxime Tremblay, Guillaume Duclos-Cianci, and Stefanos Kourtis

Département de physique & Institut quantique, Université de Sherbrooke, Sherbrooke, Québec, Canada, J1K 2R1

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


We introduce a methodology for generating random multi-qubit stabilizer codes based on solving a constraint satisfaction problem (CSP) on random bipartite graphs. This framework allows us to enforce stabilizer commutation, $X/Z$ balancing, finite rate, sparsity, and maximum-degree constraints simultaneously in a CSP that we can then solve numerically. Using a state-of-the-art CSP solver, we obtain convincing evidence for the existence of a satisfiability threshold. Furthermore, the extent of the satisfiable phase increases with the number of qubits. In that phase, finding sparse codes becomes an easy problem. Moreover, we observe that the sparse codes found in the satisfiable phase practically achieve the channel capacity for erasure noise. Our results show that intermediate-size finite-rate sparse quantum codes are easy to find, while also demonstrating a flexible methodology for generating good codes with custom properties. We therefore establish a complete and customizable pipeline for random quantum code discovery.

Excellent quantum error-correcting codes are essential to achieve fault-tolerant quantum computing. In this work, we rephrase the search for error-correcting codes as a constraint satisfaction problem (CSP). The enable the use of state-of-the-art CSP solvers to construct codes. This strategy is flexible enough to consider constraints motivated by both theoretical arguments and restriction of physical implementations.

Our results show that intermediate-size finite-rate sparse quantum codes are easy to find, while also demonstrating a flexible methodology for generating good codes with custom properties. We therefore establish a complete and customizable pipeline for random quantum error-correcting code discovery.

► BibTeX data

► References

[1] MiniZinc - Challenge, a. URL https:/​/​​challenge.html.

[2] SAT Competitions, b. URL http:/​/​​.

[3] OR-Tools - Google Optimization Tools, March 2022a. URL https:/​/​​google/​or-tools.

[4] Stabilizer code generation from a CSP solver, June 2022b. URL https:/​/​​quicophy/​csp_code_gen.

[5] Dimitris Achlioptas and Cristopher Moore. Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold. SIAM Journal on Computing, 36 (3): 740–762, January 2006. ISSN 0097-5397. 10.1137/​S0097539703434231.

[6] Dimitris Achlioptas, Assaf Naor, and Yuval Peres. Rigorous location of phase transitions in hard optimization problems. Nature, 435 (7043): 759–764, June 2005. ISSN 1476-4687. 10.1038/​nature03602.

[7] Alexei Ashikhmin, Simon Litsyn, and Michael A. Tsfasman. Asymptotically good quantum codes. Physical Review A, 63 (3): 032311, February 2001. 10.1103/​PhysRevA.63.032311.

[8] Charles H. Bennett, David P. DiVincenzo, and John A. Smolin. Capacities of Quantum Erasure Channels. Physical Review Letters, 78 (16): 3217–3220, April 1997. 10.1103/​PhysRevLett.78.3217.

[9] B. Bollobás and A. G. Thomason. Threshold functions. Combinatorica, 7 (1): 35–38, March 1987. ISSN 1439-6912. 10.1007/​BF02579198.

[10] S. B. Bravyi and A. Yu Kitaev. Quantum codes on a lattice with boundary. arXiv:quant-ph/​9811052, November 1998. 10.48550/​arXiv.quant-ph/​9811052.

[11] Sergey Bravyi and Matthew B. Hastings. Homological product codes. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, STOC '14, pages 273–282, New York, NY, USA, May 2014. Association for Computing Machinery. ISBN 978-1-4503-2710-7. 10.1145/​2591796.2591870.

[12] Sergey Bravyi, David Poulin, and Barbara Terhal. Tradeoffs for Reliable Quantum Information Storage in 2D Systems. Physical Review Letters, 104 (5): 050503, February 2010. ISSN 0031-9007, 1079-7114. 10.1103/​PhysRevLett.104.050503.

[13] Winton Brown and Omar Fawzi. Short random circuits define good quantum error correcting codes. In 2013 IEEE International Symposium on Information Theory, pages 346–350, July 2013. 10.1109/​ISIT.2013.6620245.

[14] A. R. Calderbank and Peter W. Shor. Good quantum error-correcting codes exist. Physical Review A, 54 (2): 1098–1105, August 1996. 10.1103/​PhysRevA.54.1098.

[15] Nicolas Delfosse. Tradeoffs for reliable quantum information storage in surface codes and color codes. In 2013 IEEE International Symposium on Information Theory, pages 917–921, July 2013. 10.1109/​ISIT.2013.6620360.

[16] Nicolas Delfosse and Gilles Zémor. Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel. Physical Review Research, 2 (3): 033042, July 2020. 10.1103/​PhysRevResearch.2.033042.

[17] Paul Erdős and Alfréd Rényi. On random graphs. Publicationes Mathematicae, 6: 290–297, 1959. 10.5486/​PMD.1959.6.3-4.12.

[18] Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland. Surface codes: Towards practical large-scale quantum computation. Physical Review A, 86 (3): 032324, September 2012. 10.1103/​PhysRevA.86.032324.

[19] R. Gallager. Low-density parity-check codes. IRE Transactions on Information Theory, 8 (1): 21–28, January 1962. ISSN 2168-2712. 10.1109/​TIT.1962.1057683.

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

[21] Daniel Gottesman. Fault-Tolerant Quantum Computation with Constant Overhead. arXiv:1310.2984 [quant-ph], October 2013. 10.48550/​arXiv.1310.2984.

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

[23] Michael J. Gullans, Stefan Krastanov, David A. Huse, Liang Jiang, and Steven T. Flammia. Quantum Coding with Low-Depth Random Circuits. Physical Review X, 11 (3): 031066, September 2021. 10.1103/​PhysRevX.11.031066.

[24] Matthew B. Hastings, Jeongwan Haah, and Ryan O'Donnell. Fiber bundle codes: Breaking the n1/​2 polylog(n) barrier for quantum ldpc codes. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 1276–1288, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450380539. 10.1145/​3406325.3451005.

[25] Aleksander Kubica, Michael E. Beverland, Fernando Brandão, John Preskill, and Krysta M. Svore. Three-Dimensional Color Code Thresholds via Statistical- Mechanical Mapping. Physical Review Letters, 120 (18): 180501, May 2018. 10.1103/​PhysRevLett.120.180501.

[26] Andrew J. Landahl, Jonas T. Anderson, and Patrick R. Rice. Fault-tolerant quantum computing with color codes. arXiv:1108.5738 [quant-ph], August 2011. 10.48550/​arXiv.1108.5738.

[27] Pavel Panteleev and Gleb Kalachev. Asymptotically good quantum and locally testable classical ldpc codes. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 375–388, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450392648. 10.1145/​3519935.3520017.

[28] Tom Richardson and Ruediger Urbanke. Modern Coding Theory. Cambridge University Press, Cambridge, 2008. ISBN 978-0-511-79133-8. 10.1017/​CBO9780511791338.

[29] A. M. Steane. Simple quantum error-correcting codes. Physical Review A, 54 (6): 4741–4751, December 1996. 10.1103/​PhysRevA.54.4741.

[30] Ashley M. Stephens. Fault-tolerant thresholds for quantum error correction with the surface code. Physical Review A, 89 (2): 022321, February 2014. 10.1103/​PhysRevA.89.022321.

[31] Jean-Pierre Tillich and Gilles Zémor. Quantum LDPC Codes With Positive Rate and Minimum Distance Proportional to the Square Root of the Blocklength. IEEE Transactions on Information Theory, 60 (2): 1193–1202, February 2014. ISSN 1557-9654. 10.1109/​TIT.2013.2292061.

[32] Maxime Tremblay, Guillaume Duclos-Cianci, and Stefanos Kourtis. Data for threshold plot in "Finite-rate sparse quantum codes aplenty", February 2023. URL https:/​/​​10.5281/​zenodo.7658784.

[33] Maxime A. Tremblay, Nicolas Delfosse, and Michael E. Beverland. Constant-overhead quantum error correction with thin planar connectivity. Phys. Rev. Lett., 129: 050504, Jul 2022. 10.1103/​PhysRevLett.129.050504.

Cited by

[1] Diogo Cruz, Francisco A. Monteiro, and Bruno C. Coutinho, "Quantum Error Correction Via Noise Guessing Decoding", IEEE Access 11, 119446 (2023).

[2] Andrew S. Darmawan, Yoshifumi Nakata, Shiro Tamiya, and Hayata Yamasaki, "Low-depth random Clifford circuits for quantum coding against Pauli noise using a tensor-network decoder", arXiv:2212.05071, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2023-11-29 17:52:30) and SAO/NASA ADS (last updated successfully 2023-11-29 17:52:31). The list may be incomplete as not all publishers provide suitable and complete citation data.