Quantum algorithms for computational geometry problems
share
We study quantum algorithms for problems in computational geometry, such as POINT-ON-3-LINES problem. In this problem, we are given a set of lines and we are asked to find a point that lies on at least 3 of these lines. POINT-ON-3-LINES and many other computational geometry problems are known to be 3SUM-HARD. That is, solving them classically requires time Ω(n^2-o(1)), unless there is faster algorithm for the well known 3SUM problem (in which we are given a set S of n integers and have to determine if there are a, b, c ∈ S such that a + b + c = 0). Quantumly, 3SUM can be solved in time O(n log n) using Grover's quantum search algorithm. This leads to a question: can we solve POINT-ON-3-LINES and other 3SUM-HARD problems in O(n^c) time quantumly, for c<2? We answer this question affirmatively, by constructing a quantum algorithm that solves POINT-ON-3-LINES in time O(n^1 + o(1)). The algorithm combines recursive use of amplitude amplification with geometrical ideas. We show that the same ideas give O(n^1 + o(1)) time algorithm for many 3SUM-HARD geometrical problems.
READ FULL TEXT