{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:09:57Z","timestamp":1784196597164,"version":"3.55.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T00:00:00Z","timestamp":1749772800000},"content-version":"vor","delay-in-days":3,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["2338773, 2427020"],"award-info":[{"award-number":["2338773, 2427020"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Department of Energy, Lawrence Berkeley National Laboratory","award":["MACH-Q"],"award-info":[{"award-number":["MACH-Q"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,6,10]]},"abstract":"<jats:p>Quantum Hamiltonian simulation, fundamental in quantum algorithm design, extends far beyond its foundational roots, powering diverse quantum computing applications. However, optimizing the compilation of quantum Hamiltonian simulation poses significant challenges. Existing approaches fall short in reconciling deterministic and randomized compilation, lack appropriate intermediate representations, and struggle to guarantee correctness. Addressing these challenges, we present MarQSim, a novel compilation framework. MarQSim leverages a Markov chain-based approach, encapsulated in the Hamiltonian Term Transition Graph, adeptly reconciling deterministic and randomized compilation benefits. Furthermore, we formulate a Minimum-Cost Flow model that can tune transition matrices to enforce correctness while accommodating various optimization objectives. Experimental results demonstrate MarQSim\u2019s superiority in generating more efficient quantum circuits for simulating various quantum Hamiltonians while maintaining precision.<\/jats:p>","DOI":"10.1145\/3729269","type":"journal-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T16:02:27Z","timestamp":1749830547000},"page":"576-600","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["MarQSim: Reconciling Determinism and Randomness in Compiler Optimization for Quantum Simulation"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5149-9871","authenticated-orcid":false,"given":"Xiuqi","family":"Cao","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-5564-8401","authenticated-orcid":false,"given":"Junyu","family":"Zhou","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-2822-0448","authenticated-orcid":false,"given":"Yuhao","family":"Liu","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0824-6107","authenticated-orcid":false,"given":"Yunong","family":"Shi","sequence":"additional","affiliation":[{"name":"AWS Quantum Technologies, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6233-0334","authenticated-orcid":false,"given":"Gushu","family":"Li","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.83.5162"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ab9359"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00220-006-0150-X"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_12"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.123.070503"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","unstructured":"Xiuqi Cao Junyu Zhou Yuhao Liu Yunong Shi and Gushu Li. 2025. MarQSim Artifact. (2025). doi:10.5281\/zenodo.15258728","DOI":"10.5281\/zenodo.15258728"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-023-39381-w"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-09-02-182"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.4204\/eptcs.318.13"},{"key":"e_1_3_2_11_2","unstructured":"Alexander Cowtan Will Simmons and Ross Duncan. 2020. A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz. arXiv preprint arXiv:2007.10515 (2020)."},{"key":"e_1_3_2_12_2","unstructured":"Andrew W Cross Lev S Bishop John A Smolin and Jay M Gambetta. 2017. Open quantum assembly language. arXiv preprint arXiv:1707.03429 (2017)."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-022-04940-6"},{"key":"e_1_3_2_14_2","unstructured":"Arianne Meijer\u2010van de Griend and Ross Duncan. 2020. Architecture-aware synthesis of phase polynomials for NISQ devices. arXivpreprint arXiv:2004.06052 (2020)."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature18648"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","unstructured":"The Qiskit Nature Developers. 2023. Qiskit Nature 0.6.0. doi:10.5281\/ZENODO.7828767","DOI":"10.5281\/ZENODO.7828767"},{"issue":"6","key":"e_1_3_2_17_2","article-title":"Simulating physics with computers","volume":"21","author":"Feynman Richard P.","year":"1982","unstructured":"Richard P. Feynman. 1982. Simulating physics with computers. Int.J. Theor. Phys 21, 6\/7 (1982).","journal-title":"Int.J. Theor. Phys"},{"key":"e_1_3_2_18_2","unstructured":"J Gambetta and S Sheldon. 2019. Cramming more power into a quantum device. IBM Research Blog (2019). https:\/\/www.ibm.com\/blogs\/research\/2019\/03\/power-quantum-device\/"},{"key":"e_1_3_2_19_2","unstructured":"Kaiwen Gui Teague Tomesh Pranav Gokhale Yunong Shi Frederic T Chong Margaret Martonosi and Martin Suchara. 2020. Term grouping and travelling salesperson for digital quantum simulation. arXiv preprint arXiv:2001.05983 (2020)."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.25080\/TCWV9851"},{"key":"e_1_3_2_21_2","unstructured":"Stav Haldar and Anthony J Brady. 2023. A numerical study of measurement-induced phase transitions in the Sachdev- Ye-Kitaev model. arXiv preprint arXiv:2301.05195 (2023)."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.l03.150502"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.5555\/2685188.2685189"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3434318"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3123939.3123949"},{"key":"e_1_3_2_26_2","unstructured":"Ali Javadi\u2013Abhari Matthew Treinish Kevin Krsulich Christopher J Wood Jake Lishman Julien Gacon Simon Martiel Paul D Nation Lev S Bishop Andrew W Cross Blake R Johnson and Jay M Gambetta. 2024. Quantum computing with Qiskit. arXiv preprint arXiv:2405.08810 (2024)."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/bf01331938"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3474222"},{"key":"e_1_3_2_29_2","unstructured":"Zolt\u00e2n Kir\u00e2ly and P\u00e9ter Kov\u00e2cs. 2012. Efficient implementations of minimum-cost flow algorithms. arXiv preprint arXiv:1207.6381 (2012)."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.4204\/eptcs.318.14"},{"key":"e_1_3_2_31_2","unstructured":"Adrian Lehmann Ben Caldwell and Robert Rand. 2022. VyZX: A Vision for Verifying the ZX Calculus. arXiv preprint arXiv:2205.05781 (2022)."},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3503222.3507715"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1618020114"},{"key":"e_1_3_2_34_2","doi-asserted-by":"crossref","unstructured":"Seth Lloyd. 1996. Universal quantum simulators. Science (1996) 1073\u20131078.","DOI":"10.1126\/science.273.5278.1073"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1038\/nphys3029"},{"key":"e_1_3_2_36_2","doi-asserted-by":"crossref","unstructured":"Dmitri Maslov. 2016. Optimal and asymptotically optimal NCT reversible circuits by the gate types. arXiv preprint arXiv:1602.02627 (2016).","DOI":"10.26421\/QIC16.13-14-2"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2007.911334"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/QCE52317.2021.00043"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.3.040302"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304075"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41534-018-0072-4"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511976667"},{"key":"e_1_3_2_43_2","volume-title":"Markov chains.","author":"Norris James R","year":"1998","unstructured":"James R Norris. 1998. Markov chains. Number 2. Cambridge university press."},{"key":"e_1_3_2_44_2","unstructured":"NVIDIA P\u00e9ter Vingelmann and Frank H.P. Fitzek. 2020. CUDA release: 10.2.89. https:\/\/developer.nvidia.com\/cuda-toolkit"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-02-27-235"},{"key":"e_1_3_2_46_2","first-page":"8024","volume-title":"Advances in Neural Information Processing Systems 32.","author":"Paszke Adam","year":"2019","unstructured":"Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In Advances in Neural Information Processing Systems 32. Curran Associates, Inc., 8024\u20138035. http:\/\/papers.neurips.cc\/paper\/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf"},{"key":"e_1_3_2_47_2","unstructured":"Yuxiang Peng Jacob Young Pengyu Liu and Xiaodi Wu. 2023. SimuQ: A Domain-Specific Language for Quantum Simulation with Analog Compilation. arXiv preprint arXiv:2303.02775 (March 2023)."},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.113.130503"},{"key":"e_1_3_2_49_2","volume-title":"A First Course in Stochastic Process.","author":"Taylor Howard M.","year":"1974","unstructured":"Howard M. TaylorSamuel Karlin. 1974. A First Course in Stochastic Process. ACADEMIC PRESS, INC. (LONDON) LTD., London."},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ab8e92"},{"key":"e_1_3_2_51_2","unstructured":"Robert S Smith Michael J Curtis and William J Zeng. 2016. A practical quantum instruction set architecture. arXiv preprint arXiv:1608.03355 (2016)."},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38986-3_16"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1002\/wcms.1340"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1016\/0375-9601(90)90962-N"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1063\/1.529425"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523431"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614369"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1959-0108732-6"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-09-12-322"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1080\/00268976.2011.552441"},{"key":"e_1_3_2_61_2","unstructured":"Wikipedia contributors. 2023. Minimum-cost flow problem \u2014 Wikipedia The Free Encyclopedia. https:\/\/en.wikipedia.org\/w\/index.php?title=Minimum-cost_flow_problem&oldid=1184915760 [Online; accessed 16-November-2023]."},{"key":"e_1_3_2_62_2","unstructured":"Yuxuan Zhang Roeland Wiersema Juan Carrasquilla Lukasz Cincio and Yong Baek Kim. 2024. Scalable quantum dynamics compilation via quantum machine learning. arXiv preprint arXiv:2409.16346 (2024)."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729269","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729269","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:02:26Z","timestamp":1784196146000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3729269"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,10]]},"references-count":61,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2025,6,10]]}},"alternative-id":["10.1145\/3729269"],"URL":"https:\/\/doi.org\/10.1145\/3729269","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,10]]},"assertion":[{"value":"2024-11-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}