{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T14:50:10Z","timestamp":1776783010046,"version":"3.51.2"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2024,6,4]],"date-time":"2024-06-04T00:00:00Z","timestamp":1717459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Australian Research","award":["No. DP210101348, No. FT220100391, and No. DP220102059"],"award-info":[{"award-number":["No. DP210101348, No. FT220100391, and No. DP220102059"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Softw. Eng. Methodol."],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>\n            Many existing static analysis algorithms suffer from cubic bottlenecks because of the need to compute a dynamic transitive closure (DTC). For the first time, this article studies the quantum speedups on searching subtasks in DTC-based static analysis algorithms using quantum search (e.g., Grover\u2019s algorithm). We first introduce our oracle implementation in Grover\u2019s algorithm for DTC-based static analysis and illustrate our quantum search subroutine. Then, we take two typical DTC-based analysis algorithms: context-free-language reachability and set constraint-based analysis, and show that our quantum approach can reduce the time complexity of these two algorithms to truly subcubic (\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(N^2\\sqrt {N}{\\it polylog}(N))\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            ), yielding better results than the upper bound (\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>N<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            \/log\n            <jats:italic>N<\/jats:italic>\n            )) of existing classical algorithms. Finally, we conducted a classical simulation of Grover\u2019s search to validate our theoretical approach, due to the current quantum hardware limitation of lacking a practical, large-scale, noise-free quantum machine. We evaluated the correctness and efficiency of our approach using IBM\n            <jats:sans-serif>Qiskit<\/jats:sans-serif>\n            on nine open-source projects and randomly generated edge-labeled graphs\/constraints. The results demonstrate the effectiveness of our approach and shed light on the promising direction of applying quantum algorithms to address the general challenges in static analysis.\n          <\/jats:p>","DOI":"10.1145\/3644389","type":"journal-article","created":{"date-parts":[[2024,2,6]],"date-time":"2024-02-06T07:03:40Z","timestamp":1707203020000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Dynamic Transitive Closure-based Static Analysis through the Lens of Quantum Search"],"prefix":"10.1145","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7635-468X","authenticated-orcid":false,"given":"Jiawei","family":"Ren","sequence":"first","affiliation":[{"name":"University of New South Wales, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9510-6574","authenticated-orcid":false,"given":"Yulei","family":"Sui","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5456-3827","authenticated-orcid":false,"given":"Xiao","family":"Cheng","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3097-3896","authenticated-orcid":false,"given":"Yuan","family":"Feng","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8083-4352","authenticated-orcid":false,"given":"Jianjun","family":"Zhao","sequence":"additional","affiliation":[{"name":"Kyushu University, Fukuoka, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,4]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"Jiawei Ren. 2024. Artifact: \u201cDynamic Transitive Closure-based Static Analysis through the Lens of Quantum Search.\u201d GitHub. Retrieved from https:\/\/github.com\/jiawei-95\/tosem-QDTCSA-artifact."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(68)91087-5"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1992.185545"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.2562111"},{"key":"e_1_3_2_6_2","unstructured":"Andris Ambainis. 2005. Quantum Search Algorithms. Retrieved from https:\/\/arxiv.org\/abs\/quant-ph\/0504012"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.107"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_13"},{"key":"e_1_3_2_9_2","unstructured":"Lars Ole Andersen. 1994. Program analysis and specialization for the c programming language. Retrieved from https:\/\/www.cs.cornell.edu\/courses\/cs711\/2005fa\/papers\/andersen-thesis94.pdf"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature23474"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/268946.268966"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5%3C493::AID-PROP493%3E3.0.CO;2-P"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814607"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1021\/acs.chemrev.8b00803"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3158118"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1328438.1328460"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2022.3192419"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3436877"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3533767.3534371"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.101.060401"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3498702"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","unstructured":"John Cortese and Timothy Braje. 2018. Loading classical data into a quantum computer. Retrieved from https:\/\/arxiv.org\/abs\/1803.0195810.48550\/arXiv.1803.01958","DOI":"10.48550\/arXiv.1803.01958"},{"key":"e_1_3_2_23_2","unstructured":"Sebastian D\u00f6rn. 2008. Quantum complexity of graph and algebraic problems. Retrieved from https:\/\/www.uni-ulm.de\/fileadmin\/website_uni_ulm\/iui.inst.190\/Mitarbeiter\/doern\/Dissertation.pdf"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/050644719"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2021.3"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","unstructured":"Edward Farhi Jeffrey Goldstone and Sam Gutmann. 2014. A quantum approximate optimization algorithm. Retrieved from https:\/\/arxiv.org\/abs\/1411.4028. 10.48550\/arXiv.1411.4028","DOI":"10.48550\/arXiv.1411.4028"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/24039.24041"},{"key":"e_1_3_2_28_2","article-title":"Quantum-centric supercomputing: The next wave of computing","author":"Gambetta Jay","year":"2022","unstructured":"Jay Gambetta. 2022. Quantum-centric supercomputing: The next wave of computing. IBM Research Blog. Retrieved from https:\/\/research.ibm.com\/blog\/next-wave-quantum-centric-supercomputing","journal-title":"IBM Research Blog"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2021-04-15-433"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.100.160501"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","unstructured":"Kathrin Hanauer Monika Henzinger and Christian Schulz. 2020. Faster fully dynamic transitive closure in practice. Retrieved from https:\/\/arxiv.org\/abs\/2002.00813. 10.48550\/arXiv.2002.00813","DOI":"10.48550\/arXiv.2002.00813"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-020-2649-2"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58601-6_107"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1997.614960"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629582"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/1227161.1370597"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","unstructured":"Yuxiang Lei Yulei Sui Shuo Ding and Qirun Zhang. 2022. Taming transitive redundancy for context-free language reachability. Proc. ACM Program. Lang. 6 OOPSLA2 (2022). DOI:10.1145\/3563343","DOI":"10.1145\/3563343"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","unstructured":"Yuxiang Lei Yulei Sui Shin Hwei Tan and Qirun Zhang. 2023. Recursive state machine guided graph folding for context-free language reachability. Proc. ACM Program. Lang. 7 PLDI (June 2023). DOI:10.1145\/3591233","DOI":"10.1145\/3591233"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3428218"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3434315"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/TQE.2020.2965803"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/258993.259006"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511976667"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.102.032608"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","unstructured":"Yuxiang Peng Kesha Hietala Runzhou Tao Liyi Li Robert Rand Michael Hicks and Xiaodi Wu. 2023. A Formally Certified End-to-End Implementation of Shor\u2019s Factorization Algorithm. Proc. Natl. Acad. Sci. 120 21 (May 2023) DOI:10.1073\/pnas.2218775120","DOI":"10.1073\/pnas.2218775120"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2018-08-06-79"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.99.012339"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0950-5849(98)00093-7"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192418"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/237721.237727"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","unstructured":"E. M. Stoudenmire and Xavier Waintal. 2023. Grover\u2019s Algorithm Offers No Quantum Advantage. Retrieved from https:\/\/arxiv.org\/abs\/2303.1131710.48550\/arXiv.2303.11317","DOI":"10.48550\/arXiv.2303.11317"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/3428301"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892235"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/2338965.2336784"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2014.2302311"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316310"},{"key":"e_1_3_2_59_2","unstructured":"Thomas Wigren. 2015. The Cauchy-Schwarz inequality: Proofs and applications in various spaces. Retrieved from https:\/\/www.diva-portal.org\/smash\/get\/diva2:861242\/FULLTEXT02.pdf"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/3597503.3639220"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298576"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454061"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/3563297"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462159"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/1328897.1328464"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","unstructured":"Li Zhou Gilles Barthe Pierre-Yves Strub Junyi Liu and Mingsheng Ying. 2023. CoqQ: Foundational verification of quantum programs. Proc. ACM Program. Lang. 7 POPL Article 29 (Jan.2023) 33 pages. DOI:10.1145\/3571222","DOI":"10.1145\/3571222"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.10.041038"}],"container-title":["ACM Transactions on Software Engineering and Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3644389","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3644389","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:50:48Z","timestamp":1750287048000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3644389"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,4]]},"references-count":67,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3644389"],"URL":"https:\/\/doi.org\/10.1145\/3644389","relation":{},"ISSN":["1049-331X","1557-7392"],"issn-type":[{"value":"1049-331X","type":"print"},{"value":"1557-7392","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,4]]},"assertion":[{"value":"2023-07-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-25","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}