Fast simulation of quantum algorithms using circuit optimization

Gian Giacomo Guerreschi

doi:10.22331/q-2022-05-03-706

Fast simulation of quantum algorithms using circuit optimization

Intel Labs, Intel Corporation, 2200 Mission College Blvd, Santa Clara, CA 95054

Published:	2022-05-03, volume 6, page 706
Eprint:	arXiv:2010.09746v3
Doi:	https://doi.org/10.22331/q-2022-05-03-706
Citation:	Quantum 6, 706 (2022).

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

Abstract

Classical simulators play a major role in the development and benchmark of quantum algorithms and practically any software framework for quantum computation provides the option of running the algorithms on simulators. However, the development of quantum simulators was substantially separated from the rest of the software frameworks which, instead, focus on usability and compilation. Here, we demonstrate the advantage of co-developing and integrating simulators and compilers by proposing a specialized compiler pass to reduce the simulation time for arbitrary circuits. While the concept is broadly applicable, we present a concrete implementation based on the Intel Quantum Simulator, a high-performance distributed simulator. As part of this work, we extend its implementation with additional functionalities related to the representation of quantum states. The communication overhead is reduced by changing the order in which state amplitudes are stored in the distributed memory, a concept analogous to the distinction between local and global qubits for distributed Schroedinger-type simulators. We then implement a compiler pass to exploit the novel functionalities by introducing special instructions governing data movement as part of the quantum circuit. Those instructions target unique capabilities of simulators and have no analogue in actual quantum devices. To quantify the advantage, we compare the time required to simulate random circuits with and without our optimization. The simulation time is typically halved.

Featured image: Effect of the compiler pass to optimize quantum circuits for simulation with Intel Quantum Simulator. The simulation time of random circuits on 35 qubits is reduced by about $40\%$. Datapoints represent the average over 20 random circuits and the vertical bars indicate one standard deviation.

Open-source repository of Intel Quantum Simulator: https://github.com/iqusoft/intel-qs

Popular summary

If you want to program a quantum computer, you do not need to be aware of its inner functioning since software frameworks will compile the code automatically. If you want to benchmark your quantum algorithm before actual execution, you can simulate it within the same software frameworks. To date, compilers and simulators have been implemented separately. Here, we propose an integrated approach that optimizes the circuit to speed-up its simulation. And you may save up to half of the simulation time without modifying your program.

We do so by extending both simulator and compiler: the former with a flexible way of representing quantum states, and the latter with a dedicated pass minimizing the communication overhead incurred during the simulation. Intel Quantum simulator is released open-source and the optimization algorithm provided as pseudocode.

With increasing interest in quantum computing technology, more time is spent running simulations. It is fundamental to reduce its footprint (time spent, and energy consumed), especially when no additional effort is required from the programmers. Expect backend-aware compiler passes becoming standard in your favorite software framework.

► BibTeX data

@article{Guerreschi2022fastsimulationof,
  doi = {10.22331/q-2022-05-03-706},
  url = {https://doi.org/10.22331/q-2022-05-03-706},
  title = {Fast simulation of quantum algorithms using circuit optimization},
  author = {Guerreschi, Gian Giacomo},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {706},
  month = may,
  year = {2022}
}

► References

[1] Alexander S. Green, Peter LeFanu Lumsdaine, Neil J. Ross, Peter Selinger, and Benoit Valiron. ``Quipper: A scalable quantum programming language''. Proceedings PLDI 13 48, 333–342 (2013).
https://doi.org/10.1145/2491956.2462177

[2] David Wecker and Krysta M. Svore. ``LIQUi$|\rangle$: A software design architecture and domain-specific language for quantum computing'' (2014). arXiv:1402.4467.
arXiv:1402.4467

[3] Damian S. Steiger, Thomas Häner, and Matthias Troyer. ``ProjectQ: An Open Source Software Framework for Quantum Computing''. Quantum 2, 49 (2018).
https://doi.org/10.22331/q-2018-01-31-49

[4] The Qiskit Contributors. ``Qiskit: An open-source framework for quantum computing'' (2019). https://github.com/Qiskit/qiskit.
https://github.com/Qiskit/qiskit

[5] The Cirq Contributors. ``Cirq, a python framework for creating, editing, and invoking noisy intermediate scale quantum (NISQ) circuits''. https://github.com/quantumlib/Cirq.
https://github.com/quantumlib/Cirq

[6] Robert S. Smith, Michael J. Curtis, and William J. Zeng. ``A practical quantum instruction set architecture'' (2016).
arXiv:1608.03355

[7] Nathan Killoran, Josh Izaac, Nicolás Quesada, Ville Bergholm, Matthew Amy, and Christian Weedbrook. ``Strawberry Fields: A Software Platform for Photonic Quantum Computing''. Quantum 3, 129 (2019).
https://doi.org/10.22331/q-2019-03-11-129

[8] The Orquestra Contributors. ``Orquestra''. https://www.zapatacomputing.com/orquestra/.
https://www.zapatacomputing.com/orquestra/

[9] The Braket Contributors. ``Braket''. https://aws.amazon.com/braket/.
https://aws.amazon.com/braket/

[10] Ali Javadiabhari, Shruti Patil, Daniel Kudrow, Jeff Heckey, Alexey Lvov, Frederic T. Chong, and Margaret Martonosi. ``ScaffCC: A framework for compilation and analysis of quantum computing programs''. CF '14 Proceedings of the 11th ACM Conference on Computing Frontiers (2014).
https://doi.org/10.1145/2597917.2597939

[11] Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, and Seyon Sivarajah. ``On the qubit routing problem''. Leibniz International Proceedings in Informatics, LIPIcs 135, 5:1—-5:32 (2019).
https://doi.org/10.4230/LIPIcs.TQC.2019.5

[12] Andrew M. Childs, Eddie Schoute, and Cem M. Unsal. ``Circuit transformations for quantum architectures''. Leibniz International Proceedings in Informatics, LIPIcs 135, 1–24 (2019).
https://doi.org/10.4230/LIPIcs.TQC.2019.3

[13] Carmen G. Almudever, Lingling Lao, Robert Wille, and Gian G. Guerreschi. ``Realizing Quantum Algorithms on Real Quantum Computing Devices''. Proceedings of the 2020 Design, Automation and Test in Europe Conference and Exhibition, DATE 2020Pages 864–872 (2020).
https://doi.org/10.23919/DATE48585.2020.9116240

[14] Mikhail Smelyanskiy, Nicolas P. D. Sawaya, and Alán Aspuru-Guzik. ``qHiPSTER: The quantum high performance software testing environment'' (2016). arXiv:1601.07195.
arXiv:1601.07195

[15] Edwin Pednault, John A. Gunnels, Giacomo Nannicini, Lior Horesh, Thomas Magerlein, Edgar Solomonik, Erik W. Draeger, Eric T. Holland, and Robert Wisnieff. ``Breaking the 49-qubit barrier in the simulation of quantum circuits'' (2017). arXiv:1710.05867.
arXiv:1710.05867

[16] Hans De Raedt, Fengping Jin, Dennis Willsch, Madita Willsch, Naoki Yoshioka, Nobuyasu Ito, Shengjun Yuan, and Kristel Michielsen. ``Massively parallel quantum computer simulator, eleven years later''. Computer Physics Communications 237, 47–61 (2019).
https://doi.org/10.1016/j.cpc.2018.11.005

[17] Thomas Häner and Damian S. Steiger. ``0.5 petabyte simulation of a 45-qubit quantum circuit''. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis on - SC 17 (2017).
https://doi.org/10.1145/3126908.3126947

[18] N. Khammassi, I. Ashraf, X. Fu, C.G. Almudever, and K. Bertels. ``QX: A high-performance quantum computer simulation platform''. Design, Automation & Test in Europe Conference & Exhibition (DATE), 2017 (2017).
https://doi.org/10.23919/date.2017.7927034

[19] Tyson Jones, Anna Brown, Ian Bush, and Simon C. Benjamin. ``QuEST and high performance simulation of quantum computers''. Scientific Reports 9 (2019).
https://doi.org/10.1038/s41598-019-47174-9

[20] The Huawei HiQ Team. ``Huawei hiq: A high-performance quantum computing simulator and programming framework''. http://hiq.huaweicloud.com.
http://hiq.huaweicloud.com

[21] Benjamin Villalonga, Dmitry Lyakh, Sergio Boixo, Hartmut Neven, Travis S. Humble, Rupak Biswas, Eleanor G. Rieffel, Alan Ho, and Salvatore Mandrà. ``Establishing the quantum supremacy frontier with a 281 Pflop/s simulation''. Quantum Science and Technology 5, 034003 (2020).
https://doi.org/10.1088/2058-9565/ab7eeb

[22] Thomas E. O'Brien, B. Tarasinski, and Leo DiCarlo. ``Density-matrix simulation of small surface codes under current and projected experimental noise''. npj Quantum Information 3, 39 (2017).
https://doi.org/10.1038/s41534-017-0039-x

[23] Benjamin Villalonga, Sergio Boixo, Bron Nelson, Christopher Henze, Eleanor Rieffel, Rupak Biswas, and Salvatore Mandrà. ``A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware''. npj Quantum Information 5, 1–16 (2019).
https://doi.org/10.1038/s41534-019-0196-1

[24] Thomas Häner, Damian S. Steiger, Krysta M. Svore, and Matthias Troyer. ``A Software Methodology for Compiling Quantum Programs''. Quantum Science and Technology 3, 020501 (2018).
https://doi.org/10.1088/2058-9565/aaa5cc

[25] Gian Giacomo Guerreschi, Justin Hogaboam, Fabio Baruffa, and Nicolas P. D. Sawaya. ``Intel Quantum Simulator: A cloud-ready high-performance simulator of quantum circuits''. Quantum Science and Technology 5, 034007 (2020).
https://doi.org/10.1088/2058-9565/ab8505

[26] Chapman, Peter. ``Scaling IonQ's Quantum Computers: The Roadmap''. https://ionq.com/posts/december-09-2020-scaling-quantum-computer-roadmap/.
https://ionq.com/posts/december-09-2020-scaling-quantum-computer-roadmap/

[27] Santiago Rodrigo, Medina Bandic, Sergi Abadal, Hans van Someren, Eduard Alarcón, and Carmen G. Almudéver. ``Scaling of multi-core quantum architectures''. CF '21: Proceedings of the 18th ACM International Conference on Computing FrontiersPages 144–151 (2021).
https://doi.org/10.1145/3457388.3458674

[28] Thomas Häner, Damian S. Steiger, Torsten Hoefler, and Matthias Troyer. ``Distributed Quantum Computing with QMPI''. SC '21: Proceedings of the International Conference for High Performance Computing, Networking, Storage and AnalysisPage 16 (2021).
https://doi.org/10.1145/3458817.3476172

[29] Stephen Diadamo, Janis Nötzel, Benjamin Zanger, and Mehmet Mert Beşe. ``QuNetSim: A Software Framework for Quantum Networks''. IEEE Transactions on Quantum Engineering 2, 2502512 (2021).
https://doi.org/10.1109/TQE.2021.3092395

[30] Axel Dahlberg and Stephanie Wehner. ``SimulaQron - A simulator for developing quantum internet software''. Quantum Science and Technology 4, 015001 (2019).
https://doi.org/10.1088/2058-9565/aad56e

[31] K. De Raedt, K. Michielsen, H. De Raedt, B. Trieu, G. Arnold, M. Richter, Th. Lippert, H. Watanabe, and N. Ito. ``Massively parallel quantum computer simulator''. Computer Physics Communications 176, 121–136 (2007).
https://doi.org/10.1016/j.cpc.2006.08.007

[32] Yasunari Suzuki, Yoshiaki Kawase, Yuya Masumura, Yuria Hiraga, Masahiro Nakadai, Jiabao Chen, Ken M. Nakanishi, Kosuke Mitarai, Ryosuke Imai, Shiro Tamiya, Takahiro Yamamoto, Tennin Yan, Toru Kawakubo, Yuya O. Nakagawa, Yohei Ibe, Youyuan Zhang, Hirotsugu Yamashita, Hikaru Yoshimura, Akihiro Hayashi, and Keisuke Fujii. ``Qulacs: a fast and versatile quantum circuit simulator for research purpose''. Quantum 5, 559 (2021).
https://doi.org/10.22331/q-2021-10-06-559

[33] Frank et al. Arute. ``Quantum supremacy using a programmable superconducting processor''. Nature 574, 505–510 (2019).
https://doi.org/10.1038/s41586-019-1666-5

[34] Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi, and Jianxin Chen. ``Classical Simulation of Quantum Supremacy Circuits'' (2020). arXiv:2005.06787.
arXiv:2005.06787

[35] Edwin Pednault, John A. Gunnels, Giacomo Nannicini, Lior Horesh, and Robert Wisnieff. ``Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits'' (2019).
arXiv:1910.09534

[36] Xiu-Zhe Luo, Jin-Guo Liu, Pan Zhang, and Lei Wang. ``Yao.jl: Extensible, Efficient Framework for Quantum Algorithm Design''. Quantum 4, 341 (2020).
https://doi.org/10.22331/q-2020-10-11-341

[37] Gian Giacomo Guerreschi and Jongsoo Park. ``Two-step approach to scheduling quantum circuits''. Quantum Science and Technology 3, 045003 (2018).
https://doi.org/10.1088/2058-9565/aacf0b

[38] Lingling Lao, Hans Van Someren, Imran Ashraf, and Carmen G. Almudever. ``Timing and Resource-Aware Mapping of Quantum Circuits to Superconducting Processors''. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 41, 359–371 (2022).
https://doi.org/10.1109/TCAD.2021.3057583

[39] Toshinari Itoko, Rudy Raymond, Takashi Imamichi, and Atsushi Matsuo. ``Optimization of quantum circuit mapping using gate transformation and commutation''. Integration 70, 43–50 (2020).
https://doi.org/10.1016/j.vlsi.2019.10.004

[40] Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan. ``t$|$ket$\rangle$: A Retargetable Compiler for NISQ Devices''. Quantum Science and Technology 6, 014003 (2021).
https://doi.org/10.1088/2058-9565/ab8e92

[41] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A quantum approximate optimization algorithm'' (2014). arXiv:1411.4028.
arXiv:1411.4028

[42] Y. Salathé, M. Mondal, M. Oppliger, J. Heinsoo, P. Kurpiers, A. Potočnik, A. Mezzacapo, U. Las Heras, Lucas Lamata, Enrique Solano, S. Filipp, and Andreas Wallraff. ``Digital quantum simulation of spin models with circuit quantum electrodynamics''. Physical Review X 5, 021027 (2015).
https://doi.org/10.1103/PhysRevX.5.021027

Cited by

[1] Lakshita Aggarwal, Shelly Sachdeva, and Puneet Goswami, "Quantum healthcare computing using precision based granular approach", Applied Soft Computing 144, 110458 (2023).

[2] Tsung-Wei Huang, 2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS) 746 (2023) ISBN:979-8-3503-3766-2.

The above citations are from Crossref's cited-by service (last updated successfully 2023-09-21 13:29:55). The list may be incomplete as not all publishers provide suitable and complete citation data.

On SAO/NASA ADS no data on citing works was found (last attempt 2023-09-21 13:29:55).

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.