Finite-rate Sparse Quantum Codes Aplenty

Republished By Plato

Followers: 0

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.

Abstract

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.

Finite-rate sparse quantum codes aplenty PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Featured image: (Left) Graphical representation of the commutation constraints for a pair of stabilizers sharing three qubits. (Right) Phase diagram for quantum error-correcting code generation. Blue pixels represent parameters for which there is a high probability to find a solution.

Popular summary

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

@article{Tremblay2023finiteratesparse, doi = {10.22331/q-2023-04-20-985}, url = {https://doi.org/10.22331/q-2023-04-20-985}, title = {Finite-rate sparse quantum codes aplenty}, author = {Tremblay, Maxime and Duclos-Cianci, Guillaume and Kourtis, Stefanos}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pages = {985}, month = apr, year = {2023}<br /> }

► References

[1] MiniZinc – Challenge, a. URL https://www.minizinc.org/challenge.html.
https://www.minizinc.org/challenge.html

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

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

[4] Stabilizer code generation from a CSP solver, June 2022b. URL https://github.com/quicophy/csp_code_gen.
https://github.com/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.48550/arXiv.quant-ph/9811052
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1109/TIT.1962.1057683

[20] Daniel Gottesman. Stabilizer Codes and Quantum Error Correction. 1997. 10.48550/arXiv.quant-ph/9705052.
https://doi.org/10.48550/arXiv.quant-ph/9705052
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.
https://doi.org/10.48550/arXiv.1310.2984
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.48550/arXiv.1108.5738
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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://doi.org/10.5281/zenodo.7658784.
https://doi.org/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.
https://doi.org/10.1103/PhysRevLett.129.050504

Cited by

[1] 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 SAO/NASA ADS (last updated successfully 2023-04-21 00:27:43). 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-04-21 00:27:40).

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.