# Quantum algorithms for computational geometry problems

arXiv: https://arxiv.org/abs/2004.08949 · HTML: https://mlsanity.com/paper/2004.08949/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Apr 2020.

## Built on by (most cited first, 1 of 1)

- [Comprehensive characterization of three-qubit Grover search algorithm on IBM's 127-qubit superconducting quantum computers](https://mlsanity.com/paper/2406.16018/) (2024)

## Abstract (arXiv)

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 Omega(n2-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(nc) time quantumly, for c<2? We answer this question affirmatively, by constructing a quantum algorithm that solves POINT-ON-3-LINES in time O(n1 + o(1)). The algorithm combines recursive use of amplitude amplification with geometrical ideas. We show that the same ideas give O(n1 + o(1)) time algorithm for many 3SUM-HARD geometrical problems.