Quantum algorithms for Hopcroft's problem
<|reference_start|>Quantum algorithms for Hopcroft's problem: 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.<|reference_end|>
@article{andrejevs2024quantum,
    title={Quantum algorithms for Hopcroft's problem},
    author={Vladimirs Andrejevs, Aleksandrs Belovs, Jevg=enijs Vihrovs},
    journal={arXiv preprint arXiv:2405.01160},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.01160},
    primaryClass={quant-ph cs.CG}
}