.png){kind=icon}
.png){kind=icon}
Return
Quantum Algorithms for Hopcroft's problem
.png){kind=icon}
OA
AI
V
A
J
DOI：10.1145/3787461.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this work, we study quantum algorithms for Hopcroft’s problem which is a fundamental problem in computational geometry. Given n points and n lines in the plane, the task is to determine whether there is a point-line incidence. The classical complexity of this problem is well-studied, with the best known algorithm running in \(O(n^{4/3})\) time, with matching lower bounds in some restricted settings. Our results are two different quantum algorithms with time complexity \(\widetilde{O}(n^{5/6})\). The first algorithm is based on partition trees and the quantum backtracking algorithm. The second algorithm uses a quantum walk together with a history-independent dynamic data structure for storing line arrangement which supports efficient point location queries. In the setting where the number of points and lines differ, the quantum walk-based algorithm is asymptotically faster. The quantum speedups for the aforementioned data structures may be useful for other geometric problems.
Keywords:
Quantum algorithms
quantum walks
computational geometry
Journal
A
IF:
6.8
Papers:
539
Citations:
508
Organization
No organization information available
Cited Papers