{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,20]],"date-time":"2026-10-20T16:25:52Z","timestamp":1792513552609,"version":"4.5.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"8","license":[{"start":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T00:00:00Z","timestamp":1784246400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Softw. Eng. Methodol."],"published-print":{"date-parts":[[2026,8,31]]},"abstract":"<jats:p>Due to the scarcity of quantum computing resources, researchers and developers have very limited access to real quantum computers. Therefore, judicious planning and utilization of quantum computer runtime are essential to ensure smooth execution and completion of projects. Accurate estimation of a quantum circuit\u2019s execution time is thus necessary to prevent unexpectedly exceeding the anticipated runtime or the maximum capacity of the quantum computers; it also allows quantum computing platforms to make precisely informed provisioning and prioritization of quantum computing jobs. In this article, we first study the characteristics of quantum circuits\u2019 runtime on simulators and real quantum computers. Then, we introduce an innovative method that employs a graph transformer-based model, utilizing the graph information and global information of quantum circuits to estimate their execution time. We selected a benchmark dataset comprising over 1,510 quantum circuits, initially predicting their execution times on simulators, which yielded promising results with an R-squared value greater than 95%. Subsequently, we applied active learning to select 340 circuit samples with a confidence level of 95% to build and evaluate our approach for the estimation of circuit execution times on quantum computers, achieving an average R-squared value exceeding 90%. Our approach can be integrated into quantum computing platforms to provide an accurate estimation of quantum execution time and be used as a reference for prioritizing quantum execution jobs. In addition, our findings provide insights for quantum program developers to optimize their circuits for reduced execution time.<\/jats:p>","DOI":"10.1145\/3778031","type":"journal-article","created":{"date-parts":[[2025,11,27]],"date-time":"2025-11-27T09:19:29Z","timestamp":1764235169000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Understanding and Estimating the Execution Time of Quantum Circuits"],"prefix":"10.1145","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-3148-7021","authenticated-orcid":false,"given":"Ning","family":"Ma","sequence":"first","affiliation":[{"name":"Computer Engineering and Software Engineering Department, Polytechnique Montr\u00e9al, Montreal, Quebec, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5441-6763","authenticated-orcid":false,"given":"Heng","family":"Li","sequence":"additional","affiliation":[{"name":"Computer Engineering and Software Engineering Department, Polytechnique Montr\u00e9al, Montreal, Quebec, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,7,17]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"Michael E. Beverland Prakash Murali Matthias Troyer Krysta M. Svore Torsten Hoefler Vadym Kliuchnikov Guang Hao Low Mathias Soeken Aarthi Sundaram and Alexander Vaschillo. 2022. Assessing requirements to scale to practical quantum advantage. arXiv:2211.07629. Retrieved from https:\/\/arxiv.org\/abs\/2211.07629"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10586-022-03774-1"},{"key":"e_1_3_3_4_2","first-page":"189","volume-title":"Advances in Computers","author":"Black Paul E.","year":"2002","unstructured":"Paul E. Black, D. Richard Kuhn, and Carl J. Williams. 2002. Quantum computing and communication. In Advances in Computers. Vol. 56. Elsevier, 189\u2013244."},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2021-06-01-463"},{"key":"e_1_3_3_6_2","doi-asserted-by":"crossref","unstructured":"Ferhat Erata Chuanqi Xu Ruzica Piskac and Jakub Szefer. 2024. Quantum circuit reconstruction from power side-channel attacks on quantum computer controllers. arXiv:2401.15869. Retrieved from https:\/\/arxiv.org\/abs\/2401.15869","DOI":"10.46586\/tches.v2024.i2.735-768"},{"key":"e_1_3_3_7_2","unstructured":"Andr\u00e1s Gily\u00e9n and Alexander Poremba. 2022. Improved quantum algorithms for fidelity estimation. arXiv:2203.15993. Retrieved from https:\/\/arxiv.org\/abs\/2203.15993"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physleta.2004.02.043"},{"key":"e_1_3_3_9_2","article-title":"Predicting execution time of computer programs using sparse polynomial regression","volume":"23","author":"Huang Ling","year":"2010","unstructured":"Ling Huang, Jinzhu Jia, Bin Yu, Byung-Gon Chun, Petros Maniatis, and Mayur Naik. 2010. Predicting execution time of computer programs using sparse polynomial regression. In Advances in Neural Information Processing Systems Vol. 23.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_3_10_2","volume-title":"The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling","author":"Jain Raj","year":"1991","unstructured":"Raj Jain. 1991. The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling. Wiley, NY."},{"key":"e_1_3_3_11_2","unstructured":"Ali Javadi-Abhari Matthew Treinish Kevin Krsulich Christopher J. Wood Jake Lishman Julien Gacon Simon Martiel Paul D. Nation Lev S. Bishop Andrew W. Cross et al. 2024. Quantum computing with Qiskit. arXiv:2405.08810. Retrieved from https:\/\/arxiv.org\/abs\/2405.08810"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2014.2374153"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304023"},{"key":"e_1_3_3_14_2","article-title":"A unified approach to interpreting model predictions","volume":"30","author":"Lundberg Scott M.","year":"2017","unstructured":"Scott M. Lundberg and Su-In Lee. 2017. A unified approach to interpreting model predictions. In Advances in Neural Information Processing Systems, Vol. 30.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10586-016-0606-5"},{"key":"e_1_3_3_16_2","unstructured":"Prakash Murali Ali Javadiabhari and David C. McKay. 2021. Instruction scheduling facilitating mitigation of crosstalk in a quantum computing system. US Patent 11 121 725."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04898-2_615"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.1896.0007"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/DAC56929.2023.10248002"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2023-07-20-1062"},{"key":"e_1_3_3_21_2","unstructured":"Nils Quetschlich Lukas Burgholzer and Robert Wille. 2023. MQT predictor: Automatic device selection with device-specific circuit compilation for quantum computing. arXiv:2310.06889. Retrieved from https:\/\/arxiv.org\/abs\/2310.06889"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/QSW59989.2023.00015"},{"key":"e_1_3_3_23_2","doi-asserted-by":"crossref","unstructured":"Nils Quetschlich Mathias Soeken Prakash Murali and Robert Wille. 2024. Utilizing resource estimation for the development of quantum computing applications. arXiv:2402.12434. Retrieved from https:\/\/arxiv.org\/abs\/2402.12434","DOI":"10.1109\/QCE60285.2024.00036"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/TQE.2022.3140376"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-87568-8_4"},{"key":"e_1_3_3_26_2","unstructured":"Burr Settles. 2009. Active learning literature survey. Technical Report University of Wisconsin-Madison Department of Computer Sciences. Retrieved from https:\/\/minds.wisconsin.edu\/handle\/1793\/60660"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/52.3-4.591"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ab8e92"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.2307\/1422689"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD.2013.6657074"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA53966.2022.00050"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s42484-023-00121-4"},{"key":"e_1_3_3_33_2","volume-title":"Advances in Neural Information Processing Systems","volume":"30","author":"Vaswani Ashish","year":"2017","unstructured":"Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, \u0141ukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in Neural Information Processing Systems, Vol. 30."},{"issue":"20","key":"e_1_3_3_34_2","first-page":"10","article-title":"Graph attention networks","volume":"1050","author":"Velickovic Petar","year":"2017","unstructured":"Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017. Graph attention networks. stat 1050, 20 (2017), 10\u201348550.","journal-title":"stat"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.82.2417"},{"key":"e_1_3_3_36_2","unstructured":"Hanrui Wang Pengyu Liu Jinglei Cheng Zhiding Liang Jiaqi Gu Zirui Li Yongshan Ding Weiwen Jiang Yiyu Shi Xuehai Qian et al. 2022. Quest: Graph transformer for quantum circuit reliability estimation. arXiv:2210.16724. Retrieved from https:\/\/arxiv.org\/abs\/2210.16724"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/ASE51524.2021.9678792"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1038\/299802a0"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2018.09.060"},{"key":"e_1_3_3_40_2","article-title":"Graph transformer networks","volume":"32","author":"Yun Seongjun","year":"2019","unstructured":"Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J. Kim. 2019. Graph transformer networks. In Advances in Neural Information Processing Systems, Vol. 32.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.abe8770"}],"container-title":["ACM Transactions on Software Engineering and Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3778031","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T16:04:07Z","timestamp":1784304247000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3778031"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,17]]},"references-count":40,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2026,8,31]]}},"alternative-id":["10.1145\/3778031"],"URL":"https:\/\/doi.org\/10.1145\/3778031","relation":{},"ISSN":["1049-331X","1557-7392"],"issn-type":[{"value":"1049-331X","type":"print"},{"value":"1557-7392","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,17]]},"assertion":[{"value":"2024-10-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-02","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-07-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}