Jet: Fast quantum circuit simulations with parallel task-based tensor-network contraction
1Xanadu, 777 Bay Street, Toronto, Canada
2Institute of Theoretical Physics and IQST, Ulm University, Albert-Einstein-Allee 11, 89081 Ulm, Germany
Published: | 2022-05-09, volume 6, page 709 |
Eprint: | arXiv:2107.09793v3 |
Doi: | https://doi.org/10.22331/q-2022-05-09-709 |
Citation: | Quantum 6, 709 (2022). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
We introduce a new open-source software library $Jet$, which uses task-based parallelism to obtain speed-ups in classical tensor-network simulations of quantum circuits. These speed-ups result from i) the increased parallelism introduced by mapping the tensor-network simulation to a task-based framework, ii) a novel method of reusing shared work between tensor-network contraction tasks, and iii) the concurrent contraction of tensor networks on all available hardware. We demonstrate the advantages of our method by benchmarking our code on several Sycamore-53 and Gaussian boson sampling (GBS) supremacy circuits against other simulators. We also provide and compare theoretical performance estimates for tensor-network simulations of Sycamore-53 and GBS supremacy circuits for the first time.
![](https://quantum-journal.org/wp-content/uploads/2022/05/tensornetworks.png)
Featured image: Left: A plot of the tensor-network for the Sycamore-53 $m=20$ circuit. The only two qubit gate is fSim. Right: A 4x4x4 GBS circuit with beam splitters (BS) which act as two-qudit gates and squeezers (S), which act as one-qudit gates. Both tensor networks have similar computational complexity.
Popular summary
► BibTeX data
► References
[1] S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, Nature Physics 14, 595 (2018).
https://doi.org/10.1038/s41567-018-0124-x
[2] B. Villalonga, D. Lyakh, S. Boixo, H. Neven, T. S. Humble, R. Biswas, E. G. Rieffel, A. Ho, and S. Mandrà, Quantum Science and Technology 5, 034003 (2020).
https://doi.org/10.1088/2058-9565/ab7eeb
[3] J. Gray and S. Kourtis, Quantum 5, 410 (2021).
https://doi.org/10.22331/q-2021-03-15-410
[4] E. Pednault, J. A. Gunnels, G. Nannicini, L. Horesh, T. Magerlein, E. Solomonik, E. W. Draeger, E. T. Holland, and R. Wisnieff, arXiv preprint (2017), 10.48550/ARXIV.1710.05867.
https://doi.org/10.48550/ARXIV.1710.05867
[5] C. Huang, F. Zhang, M. Newman, J. Cai, X. Gao, Z. Tian, J. Wu, H. Xu, H. Yu, B. Yuan, M. Szegedy, Y. Shi, and J. Chen, arXiv preprint (2020a), 10.48550/ARXIV.2005.06787.
https://doi.org/10.48550/ARXIV.2005.06787
[6] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, et al., Nature 574, 505 (2019).
https://doi.org/10.1038/s41586-019-1666-5
[7] E. Pednault, J. A. Gunnels, G. Nannicini, L. Horesh, and R. Wisnieff, arXiv preprint (2019), 10.48550/ARXIV.1910.09534.
https://doi.org/10.48550/ARXIV.1910.09534
[8] A. Deshpande, A. Mehta, T. Vincent, N. Quesada, M. Hinsche, M. Ioannou, L. Madsen, J. Lavoie, H. Qi, J. Eisert, D. Hangleiter, B. Fefferman, and I. Dhand, Science Advances 8, eabi7894 (2022).
https://doi.org/10.1126/sciadv.abi7894
[9] K. Bergman, S. Borkar, D. Campbell, W. Carlson, W. Dally, M. Denneau, P. Franzon, W. Harrod, K. Hill, J. Hiller, et al., Defense Advanced Research Projects Agency Information Processing Techniques Office (DARPA IPTO), Tech. Rep 15 (2008).
[10] S. Heldens, P. Hijma, B. V. Werkhoven, J. Maassen, A. S. Belloum, and R. V. Van Nieuwpoort, ACM Computing Surveys (CSUR) 53, 1 (2020).
https://doi.org/10.1145/3372390
[11] J. Dongarra, J. Hittinger, J. Bell, L. Chacon, R. Falgout, M. Heroux, P. Hovland, E. Ng, C. Webster, and S. Wild, Applied mathematics research for exascale computing, Tech. Rep. (Lawrence Livermore National Lab.(LLNL), Livermore, CA (United States), 2014).
https://doi.org/10.2172/1149042
[12] ``Top500 Benchmark,'' https://www.top500.org (2021).
https://www.top500.org
[13] J. Dongarra, University of Tennessee-Knoxville Innovative Computing Laboratory, Tech. Rep. ICLUT-20-06 (2020).
[14] P. Thoman, K. Dichev, T. Heller, R. Iakymchuk, X. Aguilar, K. Hasanov, P. Gschwandtner, P. Lemarinier, S. Markidis, H. Jordan, et al., The Journal of Supercomputing 74, 1422 (2018).
https://doi.org/10.1007/s11227-018-2238-4
[15] S. R. Paul, A. Hayashi, N. Slattengren, H. Kolla, M. Whitlock, S. Bak, K. Teranishi, J. Mayo, and V. Sarkar, in European Conference on Parallel Processing (Springer, 2019) pp. 346–360.
https://doi.org/10.1007/978-3-030-29400-7_25
[16] T.-W. Huang, Y. Lin, C.-X. Lin, G. Guo, and M. D. Wong, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (2020b), 10.1109/TCAD.2020.3025075.
https://doi.org/10.1109/TCAD.2020.3025075
[17] L. V. Kale and S. Krishnan, in Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications (1993) pp. 91–108.
https://doi.org/10.1145/165854.165874
[18] H. Kaiser, P. Diehl, A. S. Lemoine, B. A. Lelbach, P. Amini, A. Berge, J. Biddiscombe, S. R. Brandt, N. Gupta, T. Heller, et al., Journal of Open Source Software 5, 2352 (2020).
https://doi.org/10.21105/joss.02352
[19] H. C. Edwards, C. R. Trott, and D. Sunderland, Journal of Parallel and Distributed Computing 74, 3202 (2014).
https://doi.org/10.1016/j.jpdc.2014.07.003
[20] J. C. Bridgeman and C. T. Chubb, Journal of Physics A: Mathematical and Theoretical 50, 223001 (2017).
https://doi.org/10.1088/1751-8121/aa6dc3
[21] C. Damm, M. Holzer, and P. McKenzie, Computational Complexity 11, 54 (2002).
https://doi.org/10.1007/s00037-000-0170-4
[22] F. Schindler and A. Jermyn, Machine Learning: Science and Technology (2020), 10.1088/2632-2153/ab94c5.
https://doi.org/10.1088/2632-2153/ab94c5
[23] L. Chi-Chung, P. Sadayappan, and R. Wenger, Parallel Processing Letters 7, 157 (1997).
https://doi.org/10.1142/S0129626497000176
[24] I. L. Markov and Y. Shi, SIAM Journal on Computing 38, 963 (2008).
https://doi.org/10.1137/050644756
[25] S. Boixo, S. V. Isakov, V. N. Smelyanskiy, and H. Neven, arXiv preprint (2017), 10.48550/ARXIV.1712.05384.
https://doi.org/10.48550/ARXIV.1712.05384
[26] D. Lykov, R. Schutski, A. Galda, V. Vinokur, and Y. Alexeev, arXiv preprint (2020), 10.48550/ARXIV.2012.02430.
https://doi.org/10.48550/ARXIV.2012.02430
[27] S. Kourtis, C. Chamon, E. R. Mucciolo, and A. E. Ruckenstein, SciPost Phys. 7, 60 (2019).
https://doi.org/10.21468/SciPostPhys.7.5.060
[28] B. Villalonga, S. Boixo, B. Nelson, C. Henze, E. Rieffel, R. Biswas, and S. Mandrà, npj Quantum Information 5, 1 (2019).
https://doi.org/10.1038/s41534-019-0196-1
[29] J. Chen, F. Zhang, C. Huang, M. Newman, and Y. Shi, arXiv preprint (2018), 10.48550/ARXIV.1805.01450.
https://doi.org/10.48550/ARXIV.1805.01450
[30] T. G. Mattson, R. Cledat, V. Cavé, V. Sarkar, Z. Budimlić, S. Chatterjee, J. Fryman, I. Ganev, R. Knauerhase, M. Lee, et al., in 2016 IEEE High Performance Extreme Computing Conference (HPEC) (IEEE, 2016) pp. 1–7.
https://doi.org/10.1109/HPEC.2016.7761580
[31] J. Dongarra, L. Grigori, and N. J. Higham, Philosophical Transactions of the Royal Society A 378, 20190066 (2020).
https://doi.org/10.1098/rsta.2019.0066
[32] T. Heller, B. A. Lelbach, K. A. Huck, J. Biddiscombe, P. Grubel, A. E. Koniges, M. Kretz, D. Marcello, D. Pfander, A. Serio, et al., The International Journal of High Performance Computing Applications 33, 699 (2019).
https://doi.org/10.1177/1094342018819744
[33] L. E. Kidder, S. E. Field, F. Foucart, E. Schnetter, S. A. Teukolsky, A. Bohn, N. Deppe, P. Diener, F. Hébert, J. Lippuner, et al., Journal of Computational Physics 335, 84 (2017).
https://doi.org/10.1016/j.jcp.2016.12.059
[34] T.-W. Huang, G. Guo, C.-X. Lin, and M. D. F. Wong, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 40, 776 (2021).
https://doi.org/10.1109/TCAD.2020.3007319
[35] J. C. Phillips, D. J. Hardy, J. D. Maia, J. E. Stone, J. V. Ribeiro, R. C. Bernardi, R. Buch, G. Fiorin, J. Hénin, W. Jiang, et al., The Journal of chemical physics 153, 044130 (2020).
https://doi.org/10.1063/5.0014475
[36] P. Jetley, F. Gioachin, C. Mendes, L. V. Kale, and T. Quinn, in 2008 IEEE International Symposium on Parallel and Distributed Processing (2008) pp. 1–12.
https://doi.org/10.1109/IPDPS.2008.4536319
[37] D. C. Marcello, S. Shiber, O. De Marco, J. Frank, G. C. Clayton, P. M. Motl, P. Diehl, and H. Kaiser, Monthly Notices of the Royal Astronomical Society 504, 5345 (2021).
https://doi.org/10.1093/mnras/stab937
[38] A. Alpay and V. Heuveline, in Proceedings of the International Workshop on OpenCL (2020) pp. 1–1.
https://doi.org/10.1145/3388333.3388658
[39] https://github.com/jcmgray/cotengra (2021).
https://github.com/jcmgray/cotengra
[40] https://blogs.nvidia.com/blog/2021/04/12/what-is-quantum-computing/ (2021).
https://blogs.nvidia.com/blog/2021/04/12/what-is-quantum-computing/
[41] T. Nguyen, D. Lyakh, E. Dumitrescu, D. Clark, J. Larkin, and A. McCaskey, arXiv preprint (2021), 10.48550/ARXIV.2104.10523.
https://doi.org/10.48550/ARXIV.2104.10523
[42] D. I. Lyakh, Computer Physics Communications 189, 84 (2015).
https://doi.org/10.1016/j.cpc.2014.12.013
[43] https://github.com/ngnrsaa/qflex (2021).
https://github.com/ngnrsaa/qflex
[44] https://developer.nvidia.com/cutensor (2021).
https://developer.nvidia.com/cutensor
[45] https://github.com/XanaduAI/jet (2021).
https://github.com/XanaduAI/jet
[46] S. Schlag, V. Henne, T. Heuer, H. Meyerhenke, P. Sanders, and C. Schulz, in 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX) (SIAM, 2016) pp. 53–67.
https://doi.org/10.1137/1.9781611974317.5
[47] C. Loken, D. Gruner, L. Groer, R. Peltier, N. Bunn, M. Craig, T. Henriques, J. Dempsey, C.-H. Yu, J. Chen, et al., in Journal of Physics: Conference Series, Vol. 256 (IOP Publishing, 2010) p. 012026.
https://doi.org/10.1088/1742-6596/256/1/012026
[48] https://docs.scinet.utoronto.ca/index.php/Niagara_Quickstart (2019).
https://docs.scinet.utoronto.ca/index.php/Niagara_Quickstart
[49] M. Ponce, R. van Zon, S. Northrup, D. Gruner, J. Chen, F. Ertinaz, A. Fedoseev, L. Groer, F. Mao, B. C. Mundim, et al., Proceedings of the Practice and Experience in Advanced Research Computing on Rise of the Machines (learning) , 1 (2019).
https://doi.org/10.1145/3332186.3332195
[50] https://docs.scinet.utoronto.ca/index.php/Rouge (2021).
https://docs.scinet.utoronto.ca/index.php/Rouge
[51] B. Gupt, J. Izaac, and N. Quesada, Journal of Open Source Software 4, 1705 (2019).
https://doi.org/10.21105/joss.01705
[52] M. Lubasch, A. A. Valido, J. J. Renema, W. S. Kolthammer, D. Jaksch, M. S. Kim, I. Walmsley, and R. García-Patrón, Phys. Rev. A 97, 062304 (2018).
https://doi.org/10.1103/PhysRevA.97.062304
[53] R. García-Patrón, J. J. Renema, and V. Shchesnovich, Quantum 3, 169 (2019).
https://doi.org/10.22331/q-2019-08-05-169
Cited by
[1] Jin Lee, Zheng Zhang, Sofía González-García, and Haewon Jeong, 2024 IEEE International Symposium on Information Theory (ISIT) 3095 (2024) ISBN:979-8-3503-8284-6.
[2] Ryutaro Nagai and Takao Tomono, 2022 IEEE International Conference on Quantum Computing and Engineering (QCE) 818 (2022) ISBN:978-1-6654-9113-6.
[3] Glen Evenbly, "A Practical Guide to the Numerical Implementation of Tensor Networks I: Contractions, Decompositions, and Gauge Freedom", Frontiers in Applied Mathematics and Statistics 8, 806549 (2022).
[4] Alon Kukliansky, Ed Younis, Lukasz Cincio, and Costin Iancu, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 814 (2023) ISBN:979-8-3503-4323-6.
[5] Deborah Volpe, Nils Quetschlich, Mariagrazia Graziano, Giovanna Turvani, and Robert Wille, 2024 IEEE International Conference on Quantum Software (QSW) 46 (2024) ISBN:979-8-3503-6847-5.
[6] Akihiro Hayashi, Austin Adams, Jeffrey Young, Alexander McCaskey, Eugene Dumitrescu, Vivek Sarkar, and Thomas M. Conte, 2023 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) 509 (2023) ISBN:979-8-3503-1199-0.
[7] Shi-Ju Ran and Gang Su, "Tensor Networks for Interpretable and Efficient Quantum-Inspired Machine Learning", Intelligent Computing 2, 0061 (2023).
[8] Teppei Suzuki, Tsubasa Miyazaki, Toshiki Inaritai, and Takahiro Otsuka, "Quantum AI simulator using a hybrid CPU–FPGA approach", Scientific Reports 13 1, 7735 (2023).
[9] Tsung-Wei Huang, 2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS) 746 (2023) ISBN:979-8-3503-3766-2.
[10] Robert Wille and Lukas Burgholzer, Handbook of Computer Architecture 1 (2022) ISBN:978-981-15-6401-7.
[11] Diego Guala, Shaoming Zhang, Esther Cruz, Carlos A. Riofrío, Johannes Klepsch, and Juan Miguel Arrazola, "Practical overview of image classification with tensor-network quantum circuits", Scientific Reports 13 1, 4427 (2023).
[12] Florian J. Kiwit, Marwa Marso, Philipp Ross, Carlos A. Riofrío, Johannes Klepsch, and Andre Luckow, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 475 (2023) ISBN:979-8-3503-4323-6.
[13] Thien Nguyen, Dmitry Lyakh, Eugene Dumitrescu, David Clark, Jeff Larkin, and Alexander McCaskey, "Tensor Network Quantum Virtual Machine for Simulating Quantum Circuits at Exascale", ACM Transactions on Quantum Computing 4 1, 1 (2023).
[14] Nishant Saurabh, Shantenu Jha, and Andre Luckow, 2023 IEEE International Conference on Quantum Software (QSW) 116 (2023) ISBN:979-8-3503-0479-4.
[15] Robert Wille, Lucas Berent, Tobias Forster, Jagatheesan Kunasaikaran, Kevin Mato, Tom Peham, Nils Quetschlich, Damian Rovara, Aaron Sander, Ludwig Schmid, Daniel Schönberger, Yannick Stade, and Lukas Burgholzer, 2024 IEEE International Conference on Quantum Software (QSW) 1 (2024) ISBN:979-8-3503-6847-5.
[16] Daniel Strano, Benn Bollay, Aryan Blaauw, Nathan Shammah, William J. Zeng, and Andrea Mari, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 949 (2023) ISBN:979-8-3503-4323-6.
[17] Anurag Dwivedi, Miguel Angel Lopez-Ruiz, and Srinivasan S. Iyengar, "Resource Optimization for Quantum Dynamics with Tensor Networks: Quantum and Classical Algorithms", The Journal of Physical Chemistry A 128 32, 6774 (2024).
[18] Nils Quetschlich, Lukas Burgholzer, and Robert Wille, "MQT Bench: Benchmarking Software and Design Automation Tools for Quantum Computing", Quantum 7, 1062 (2023).
[19] Amit Jamadagni, Andreas M. Läuchli, and Cornelius Hempel, "Benchmarking Quantum Computer Simulation Software Packages: State Vector Simulators", arXiv:2401.09076, (2024).
[20] Alan Morningstar, Markus Hauru, Jackson Beall, Martin Ganahl, Adam G. M. Lewis, Vedika Khemani, and Guifre Vidal, "Simulation of Quantum Many-Body Dynamics with Tensor Processing Units: Floquet Prethermalization", PRX Quantum 3 2, 020331 (2022).
[21] Deborah Volpe, Nils Quetschlich, Mariagrazia Graziano, Giovanna Turvani, and Robert Wille, "A Predictive Approach for Selecting the Best Quantum Solver for an Optimization Problem", arXiv:2408.03613, (2024).
[22] Robert Wille, Lucas Berent, Tobias Forster, Jagatheesan Kunasaikaran, Kevin Mato, Tom Peham, Nils Quetschlich, Damian Rovara, Aaron Sander, Ludwig Schmid, Daniel Schönberger, Yannick Stade, and Lukas Burgholzer, "The MQT Handbook: A Summary of Design Automation Tools and Software for Quantum Computing", arXiv:2405.17543, (2024).
[23] Glen Evenbly, "A Practical Guide to the Numerical Implementation of Tensor Networks I: Contractions, Decompositions and Gauge Freedom", arXiv:2202.02138, (2022).
[24] John Brennan, Lee O'Riordan, Kenneth Hanley, Myles Doyle, Momme Allalen, David Brayford, Luigi Iapichino, and Niall Moran, "QXTools: A Julia framework for distributed quantum circuit simulation", The Journal of Open Source Software 7 70, 3711 (2022).
[25] Lukas Burgholzer, Alexander Ploier, and Robert Wille, "Tensor Networks or Decision Diagrams? Guidelines for Classical Quantum Circuit Simulation", arXiv:2302.06616, (2023).
[26] Nils Quetschlich, Lukas Burgholzer, and Robert Wille, "Towards an Automated Framework for Realizing Quantum Computing Solutions", arXiv:2210.14928, (2022).
[27] Kieran Young, Marcus Scese, and Ali Ebnenasir, "Simulating Quantum Computations on Classical Machines: A Survey", arXiv:2311.16505, (2023).
[28] Akihiro Hayashi, Austin Adams, Jeffrey Young, Alexander McCaskey, Eugene Dumitrescu, Vivek Sarkar, and Thomas M. Conte, "Enabling Multi-threading in Heterogeneous Quantum-Classical Programming Models", arXiv:2301.11559, (2023).
[29] Sergio Sánchez-Ramírez, Javier Conejero, Francesc Lordan, Anna Queralt, Toni Cortes, Rosa M Badia, and Artur Garcia-Saez, "RosneT: A Block Tensor Algebra Library for Out-of-Core Quantum Computing Simulation", arXiv:2201.06620, (2022).
[30] Lukas Burgholzer, Alexander Ploier, and Robert Wille, "Simulation Paths for Quantum Circuit Simulation with Decision Diagrams", arXiv:2203.00703, (2022).
[31] Deborah Volpe, Nils Quetschlich, Mariagrazia Graziano, Giovanna Turvani, and Robert Wille, "Towards an Automatic Framework for Solving Optimization Problems with Quantum Computers", arXiv:2406.12840, (2024).
[32] Nils Quetschlich, Tobias Forster, Adrian Osterwind, Domenik Helms, and Robert Wille, "Towards Equivalence Checking of Classical Circuits Using Quantum Computing", arXiv:2408.14539, (2024).
The above citations are from Crossref's cited-by service (last updated successfully 2024-09-07 21:21:10) and SAO/NASA ADS (last updated successfully 2024-09-07 21:21:11). The list may be incomplete as not all publishers provide suitable and complete citation data.
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.