Dynamic Transitive Closure-Based Static Analysis through the Lens of Quantum Search

Ren, J; Sui, Y; Cheng, X; Feng, Y; Zhao, J

Dynamic Transitive Closure-Based Static Analysis through the Lens of Quantum Search

Ren, J Sui, Y Cheng, X Feng, Y

Zhao, J

Permalink

Publisher:: Association for Computing Machinery (ACM)
Publication Type:: Journal Article
Citation:: ACM Transactions on Software Engineering and Methodology

Closed Access

	Filename	Description	Size
	Quantum_Static_Analysis (1).pdf	Accepted version	893.42 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Ren, J
dc.contributor.author	Sui, Y
dc.contributor.author	Cheng, X
dc.contributor.author	Feng, Y https://orcid.org/0000-0002-3097-3896
dc.contributor.author	Zhao, J
dc.date.accessioned	2024-03-06T01:34:34Z
dc.date.available	2024-03-06T01:34:34Z
dc.identifier.citation	ACM Transactions on Software Engineering and Methodology
dc.identifier.issn	1049-331X
dc.identifier.issn	1557-7392
dc.identifier.uri	http://hdl.handle.net/10453/176175
dc.description.abstract	<jats:p> 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 paper studies the quantum speedups on searching subtasks in DTC-based static analysis algorithms using quantum search (e.g., Grover’s algorithm). We first introduce our oracle implementation in Grover’s 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 ( <jats:inline-formula content-type="math/tex"> <jats:tex-math notation="TeX" version="MathJaX">\(O(N^2\sqrt {N}{polylog}(N)) \)</jats:tex-math> </jats:inline-formula> ), yielding better results than the upper bound ( <jats:italic>O</jats:italic> ( <jats:italic>N</jats:italic> <jats:sup>3</jats:sup> /log <jats:italic>N</jats:italic> )) of existing classical algorithms. Finally, we conducted a classical simulation of Grover’s 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 <jats:sans-serif>Qiskit</jats:sans-serif> 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. </jats:p>
dc.language	en
dc.publisher	Association for Computing Machinery (ACM)
dc.relation	http://purl.org/au-research/grants/arc/DP220102059
dc.relation	http://purl.org/au-research/grants/arc/DP180100691
dc.relation.ispartof	ACM Transactions on Software Engineering and Methodology
dc.relation.isbasedon	10.1145/3644389
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	0803 Computer Software, 0806 Information Systems
dc.subject.classification	Software Engineering
dc.subject.classification	4612 Software engineering
dc.title	Dynamic Transitive Closure-Based Static Analysis through the Lens of Quantum Search
dc.type	Journal Article
utslib.for	0803 Computer Software
utslib.for	0806 Information Systems
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	closed_access	*
dc.date.updated	2024-03-06T01:34:32Z
pubs.publication-status	Published online

Abstract:

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 paper studies the quantum speedups on searching subtasks in DTC-based static analysis algorithms using quantum search (e.g., Grover’s algorithm). We first introduce our oracle implementation in Grover’s 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 (

\(O(N^2\sqrt {N}{polylog}(N)) \)

), yielding better results than the upper bound ( O ( N 3 /log N )) of existing classical algorithms. Finally, we conducted a classical simulation of Grover’s 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 Qiskit 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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/176175