1. Dynamic Transitive Closure-based Static Analysis through the Lens of Quantum Search.
- Author
-
Ren, Jiawei, Sui, Yulei, Cheng, Xiao, Feng, Yuan, and Zhao, Jianjun
- Subjects
TIME complexity ,QUANTUM computers ,ALGORITHMS - 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 article 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}{\it 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. [ABSTRACT FROM AUTHOR]- Published
- 2024
- Full Text
- View/download PDF