Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2004.08949

Quantum algorithms for computational geometry problems

Andris Ambainis, Nikita Larka

Published Apr 19, 2020• 1 citation
arXivHTMLPDF

Abstract

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 \in 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.

DOI
10.48550/arxiv.2004.08949

Related papers

Quantum Algorithms for Computational Geometry Problems

Andris Ambainis, Nikita Larka

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.

Leibniz international proceedings in informatics•Jan 1, 2020•6 citations

Quantum Speedup for Some Geometric 3SUM-Hard Problems and Beyond

Keil, J. Mark, Fraser McLeod, Debajyoti Mondal

The classical 3SUM conjecture states that the class of 3SUM-hard problems does not admit a truly subquadratic $O(n^{2-δ})$-time algorithm, where $δ>0$, in classical computing. The geometric 3SUM-hard problems have widely been studied in computational geometry and recently, these problems have been examined under the quantum computing model. For example, Ambainis and Larka [TQC'20] designed a quantum algorithm that can solve many geometric 3SUM-hard problems in $O(n^{1+o(1)})$-time, whereas Buhrman [ITCS'22] investigated lower bounds under quantum 3SUM conjecture that claims there does not exist any sublinear $O(n^{1-δ})$-time quantum algorithm for the 3SUM problem. The main idea of Ambainis and Larka is to formulate a 3SUM-hard problem as a search problem, where one needs to find a point with a certain property over a set of regions determined by a line arrangement in the plane. The quantum speed-up then comes from the application of the well-known quantum search technique called Grover search over all regions. This paper further generalizes the technique of Ambainis and Larka for some 3SUM-hard problems when a solution may not necessarily correspond to a single point or the search regions do not immediately correspond to the subdivision determined by a line arrangement. Given a set of $n$ points and a positive number $q$, we design $O(n^{1+o(1)})$-time quantum algorithms to determine whether there exists a triangle among these points with an area at most $q$ or a unit disk that contains at least $q$ points. We also give an $O(n^{1+o(1)})$-time quantum algorithm to determine whether a given set of intervals can be translated so that it becomes contained in another set of given intervals and discuss further generalizations.

arXiv:2404.04535•Apr 6, 2024•0 citations

Limits of Quantum Speed-Ups for Computational Geometry and Other Problems: Fine-Grained Complexity via Quantum Walks

Harry Buhrman, Bruno Loff, Subhasree Patro +1 more

Many computational problems are subject to a quantum speed-up: one might find that a problem having an O(n^3)-time or O(n^2)-time classic algorithm can be solved by a known O(n^1.5)-time or O(n)-time quantum algorithm. The question naturally arises: how much quantum speed-up is possible? The area of fine-grained complexity allows us to prove optimal lower-bounds on the complexity of various computational problems, based on the conjectured hardness of certain natural, well-studied problems. This theory has recently been extended to the quantum setting, in two independent papers by Buhrman, Patro, and Speelman (arXiv:1911.05686), and by Aaronson, Chia, Lin, Wang, and Zhang (arXiv:1911.01973). In this paper, we further extend the theory of fine-grained complexity to the quantum setting. A fundamental conjecture in the classical setting states that the 3SUM problem cannot be solved by (classical) algorithms in time O(n^{2-a}), for any a>0. We formulate an analogous conjecture, the Quantum-3SUM-Conjecture, which states that there exist no sublinear O(n^{1-b})-time quantum algorithms for the 3SUM problem. Based on the Quantum-3SUM-Conjecture, we show new lower-bounds on the time complexity of quantum algorithms for several computational problems. Most of our lower-bounds are optimal, in that they match known upper-bounds, and hence they imply tight limits on the quantum speedup that is possible for these problems.

arXiv:2106.02005•Leibniz international proceedings in informatics•Jun 3, 2021•9 citations

Quantum Algorithms for Hopcroft's problem

Vladimirs Andrejevs, Aleksandrs Belovs, Jevgēnijs Vihrovs

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. Finally, we examine the connections between Hopcroft’s problem and other computational problems via fine-grained complexity. For example, we show a conditional \(\Omega (n^{3/4})\) time lower bound on Hopcroft’s problem in 5 dimensions based on the quantum analogue of a classical hardness conjecture, which is stronger than the (optimal) \(\Theta (n^{2/3})\) query complexity bounds.

arXiv:2405.01160•ACM Transactions on Quantum Computing•Jan 5, 2026•1 citation

A panoply of quantum algorithms

Bartholomew Furrow

This paper's aim is to explore improvements to, and applications of, a fundamental quantum algorithm invented by Grover\cite{grover}. Grover's algorithm is a basic tool that can be applied to a large number of problems in computer science, creating quantum algorithms that are polynomially faster than fastest known and fastest possible classical algorithms that solve the same problems. Our goal in this paper is to make these techniques readily accessible to those without a strong background in quantum physics: we achieve this by providing a set of tools, each of which makes use of Grover's algorithm or similar techniques, which can be used as subroutines in many quantum algorithms.}{The tools we provide are carefully constructed: they are easy to use, and in many cases they are asymptotically faster than the best tools previously available. The tools we build on include algorithms by Boyer, Brassard, Hoyer and Tapp, Buhrman, Cleve, de Witt and Zalka and Durr and Hoyer.}{After creating our tools, we create several new quantum algorithms, each of which is faster than the fastest known deterministic classical algorithm that accomplishes the same aim, and some of which are faster than the fastest possible deterministic classical algorithm. These algorithms solve problems from the fields of graph theory and computational geometry, and some employ dynamic programming techniques. We discuss a breadth-first search that is faster than $\Theta(\text{edges})$ (the classical limit) in a dense graph, maximum-points-on-a-line in $O(N^{3/2}\lg N)$ (faster than the fastest classical algorithm known), as well as several other algorithms that are similarly illustrative of solutions in some class of problem. Through these new algorithms we illustrate the use of our tools, working to encourage their use and the study of quantum algorithms in general.

Quantum Information and Computation•Sep 1, 2008•6 citations

A panoply of quantum algorithms

Bartholomew Furrow

This thesis’ aim is to explore improvements to, and applications of, a fundamental quantum algorithm invented by Grover. Grover’s algorithm is a basic tool that can be applied to a large number of problems in computer science, creating quantum algorithms that are polynomially faster than fastest known and fastest possible classical algorithms that solve the same problems. Our goal in this thesis is to make these techniques readily accessible to those without a strong background in quantum physics: we achieve this by providing a set of tools, each of which makes use of Grover’s algorithm or similar techniques, that can be used as subroutines in many quantum algorithms. The tools we provide are carefully constructed: they are easy to use, and they are asymptotically faster than the best tools previously available. The tools that we supersede include algorithms by Boyer, Brassard, Hoyer and Tapp, Buhrman, Cleve, de Witt and Zalka and Durr and Hoyer. After creating our tools, we create several new quantum algorithms, each of which is faster than the fastest known classical algorithm that accomplishes the same aim, and some of which are faster than the fastest possible classical algorithm. These algorithms come from graph theory, computational geometry and dynamic programming. We discuss a breadth-first search that is faster than (edges) (the classical limit) in a dense graph, maximum-points-on-a-line in (N3/2 lgN) (faster than the fastest classical algorithm known), as well as several other algorithms that are similarly illustrative of solutions in some class of problem. Through these new algorithms we illustrate the use of our tools, working to encourage their use and the study of quantum algorithms in general.

Quantum Information and Computation•Jan 1, 2010•7 citations
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 333 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 Ω(n2−o(1))Ω(n^{2-o(1)})Ω(n2−o(1)), unless there is faster algorithm for the well known 3SUM problem (in which we are given a set SSS of nnn integers and have to determine if there are a,b,c∈Sa, b, c \in Sa,b,c∈S such that a+b+c=0a + b + c = 0a+b+c=0). Quantumly, 3SUM can be solved in time O(nlog⁡n)O(n \log n)O(nlogn) 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)O(n^c)O(nc) time quantumly, for c<2c<2c<2? We answer this question affirmatively, by constructing a quantum algorithm that solves POINT-ON-3-LINES in time O(n1+o(1))O(n^{1 + o(1)})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))O(n^{1 + o(1)})O(n1+o(1)) time algorithm for many 3SUM-HARD geometrical problems.
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.
The classical 3SUM conjecture states that the class of 3SUM-hard problems does not admit a truly subquadratic O(n2−δ)O(n^{2-δ})O(n2−δ)-time algorithm, where δ>0δ>0δ>0, in classical computing. The geometric 3SUM-hard problems have widely been studied in computational geometry and recently, these problems have been examined under the quantum computing model. For example, Ambainis and Larka [TQC'20] designed a quantum algorithm that can solve many geometric 3SUM-hard problems in O(n1+o(1))O(n^{1+o(1)})O(n1+o(1))-time, whereas Buhrman [ITCS'22] investigated lower bounds under quantum 3SUM conjecture that claims there does not exist any sublinear O(n1−δ)O(n^{1-δ})O(n1−δ)-time quantum algorithm for the 3SUM problem. The main idea of Ambainis and Larka is to formulate a 3SUM-hard problem as a search problem, where one needs to find a point with a certain property over a set of regions determined by a line arrangement in the plane. The quantum speed-up then comes from the application of the well-known quantum search technique called Grover search over all regions. This paper further generalizes the technique of Ambainis and Larka for some 3SUM-hard problems when a solution may not necessarily correspond to a single point or the search regions do not immediately correspond to the subdivision determined by a line arrangement. Given a set of nnn points and a positive number qqq, we design O(n1+o(1))O(n^{1+o(1)})O(n1+o(1))-time quantum algorithms to determine whether there exists a triangle among these points with an area at most qqq or a unit disk that contains at least qqq points. We also give an O(n1+o(1))O(n^{1+o(1)})O(n1+o(1))-time quantum algorithm to determine whether a given set of intervals can be translated so that it becomes contained in another set of given intervals and discuss further generalizations.
Many computational problems are subject to a quantum speed-up: one might find that a problem having an O(n^3)-time or O(n^2)-time classic algorithm can be solved by a known O(n^1.5)-time or O(n)-time quantum algorithm. The question naturally arises: how much quantum speed-up is possible? The area of fine-grained complexity allows us to prove optimal lower-bounds on the complexity of various computational problems, based on the conjectured hardness of certain natural, well-studied problems. This theory has recently been extended to the quantum setting, in two independent papers by Buhrman, Patro, and Speelman (arXiv:1911.05686), and by Aaronson, Chia, Lin, Wang, and Zhang (arXiv:1911.01973). In this paper, we further extend the theory of fine-grained complexity to the quantum setting. A fundamental conjecture in the classical setting states that the 3SUM problem cannot be solved by (classical) algorithms in time O(n^{2-a}), for any a>0. We formulate an analogous conjecture, the Quantum-3SUM-Conjecture, which states that there exist no sublinear O(n^{1-b})-time quantum algorithms for the 3SUM problem. Based on the Quantum-3SUM-Conjecture, we show new lower-bounds on the time complexity of quantum algorithms for several computational problems. Most of our lower-bounds are optimal, in that they match known upper-bounds, and hence they imply tight limits on the quantum speedup that is possible for these problems.
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(n4/3)O(n^{4/3})O(n4/3) time, with matching lower bounds in some restricted settings. Our results are two different quantum algorithms with time complexity O~(n5/6)\widetilde{O}(n^{5/6})O(n5/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. Finally, we examine the connections between Hopcroft’s problem and other computational problems via fine-grained complexity. For example, we show a conditional Ω(n3/4)\Omega (n^{3/4})Ω(n3/4) time lower bound on Hopcroft’s problem in 5 dimensions based on the quantum analogue of a classical hardness conjecture, which is stronger than the (optimal) Θ(n2/3)\Theta (n^{2/3})Θ(n2/3) query complexity bounds.
This paper's aim is to explore improvements to, and applications of, a fundamental quantum algorithm invented by Grover\cite{grover}. Grover's algorithm is a basic tool that can be applied to a large number of problems in computer science, creating quantum algorithms that are polynomially faster than fastest known and fastest possible classical algorithms that solve the same problems. Our goal in this paper is to make these techniques readily accessible to those without a strong background in quantum physics: we achieve this by providing a set of tools, each of which makes use of Grover's algorithm or similar techniques, which can be used as subroutines in many quantum algorithms.}{The tools we provide are carefully constructed: they are easy to use, and in many cases they are asymptotically faster than the best tools previously available. The tools we build on include algorithms by Boyer, Brassard, Hoyer and Tapp, Buhrman, Cleve, de Witt and Zalka and Durr and Hoyer.}{After creating our tools, we create several new quantum algorithms, each of which is faster than the fastest known deterministic classical algorithm that accomplishes the same aim, and some of which are faster than the fastest possible deterministic classical algorithm. These algorithms solve problems from the fields of graph theory and computational geometry, and some employ dynamic programming techniques. We discuss a breadth-first search that is faster than Θ(edges)\Theta(\text{edges})Θ(edges) (the classical limit) in a dense graph, maximum-points-on-a-line in O(N3/2lg⁡N)O(N^{3/2}\lg N)O(N3/2lgN) (faster than the fastest classical algorithm known), as well as several other algorithms that are similarly illustrative of solutions in some class of problem. Through these new algorithms we illustrate the use of our tools, working to encourage their use and the study of quantum algorithms in general.
This thesis’ aim is to explore improvements to, and applications of, a fundamental quantum algorithm invented by Grover. Grover’s algorithm is a basic tool that can be applied to a large number of problems in computer science, creating quantum algorithms that are polynomially faster than fastest known and fastest possible classical algorithms that solve the same problems. Our goal in this thesis is to make these techniques readily accessible to those without a strong background in quantum physics: we achieve this by providing a set of tools, each of which makes use of Grover’s algorithm or similar techniques, that can be used as subroutines in many quantum algorithms. The tools we provide are carefully constructed: they are easy to use, and they are asymptotically faster than the best tools previously available. The tools that we supersede include algorithms by Boyer, Brassard, Hoyer and Tapp, Buhrman, Cleve, de Witt and Zalka and Durr and Hoyer. After creating our tools, we create several new quantum algorithms, each of which is faster than the fastest known classical algorithm that accomplishes the same aim, and some of which are faster than the fastest possible classical algorithm. These algorithms come from graph theory, computational geometry and dynamic programming. We discuss a breadth-first search that is faster than (edges) (the classical limit) in a dense graph, maximum-points-on-a-line in (N3/2 lgN) (faster than the fastest classical algorithm known), as well as several other algorithms that are similarly illustrative of solutions in some class of problem. Through these new algorithms we illustrate the use of our tools, working to encourage their use and the study of quantum algorithms in general.