@inproceedings{10ee3864d3a24f0eaf481b1e307e6e90,
title = "Optimized Quantum Program Execution Ordering to Mitigate Errors in Simulations of Quantum Systems",
abstract = "Simulating the time evolution of a physical system at quantum mechanical levels of detail - known as Hamiltonian Simulation (HS) - is an important and interesting problem across physics and chemistry. For this task, algorithms that run on quantum computers are known to be exponentially faster than classical algorithms; in fact, this application motivated Feynman to propose the construction of quantum computers. Nonetheless, there are challenges in reaching this performance potential. Prior work has focused on compiling circuits (quantum programs) for HS with the goal of maximizing either accuracy or gate cancellation. Our work proposes a compilation strategy that simultaneously advances both goals. At a high level, we use classical optimizations such as graph coloring and travelling salesperson to order the execution of quantum programs. Specifically, we group together mutually commuting terms in the Hamiltonian (a matrix characterizing the quantum mechanical system) to improve the accuracy of the simulation. We then rearrange the terms within each group to maximize gate cancellation in the final quantum circuit. These optimizations work together to improve HS performance and result in an average 40% reduction in circuit depth. This work advances the frontier of HS which in turn can advance physical and chemical modeling in both basic and applied sciences.",
keywords = "Hamiltonian simulation, compilation, program ordering, quantum computing",
author = "Teague Tomesh and Kaiwen Gui and Pranav Gokhale and Yunong Shi and Chong, {Frederic T.} and Margaret Martonosi and Martin Suchara",
note = "Funding Information: This work was funded in part by EPiQC, an NSF Expedition in Computing, under grants CCF-1730082 / 1730449 / 1730082, by the NSF STAQ project under grant NSF Phy-1818914, and by DOE grants DE-SC0020289 and DESC0020331; and in part by NSF OMA-2016136 and the Q-NEXT DOE NQI Center. Y.S. was also funded in part by the NSF QISE-NET fellowship under grant number 1747426. The work of K.G. and M.S. is based upon work supported by the U.S. Department of Energy, Office of Science, Office of Fusion Energy Sciences, under Award Number DE-SC0020249. This work was also funded by the US Department of Energy Office, Advanced Manufacturing Office (CRADA No. 2020-20099.) and by the NSF under Grant No. 2110860. Publisher Copyright: {\textcopyright} 2021 IEEE.; 2021 International Conference on Rebooting Computing, ICRC 2021 ; Conference date: 30-11-2021 Through 02-12-2021",
year = "2021",
doi = "10.1109/ICRC53822.2021.00013",
language = "English (US)",
series = "Proceedings - 2021 International Conference on Rebooting Computing, ICRC 2021",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "1--13",
booktitle = "Proceedings - 2021 International Conference on Rebooting Computing, ICRC 2021",
address = "United States",
}