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:1911.01973

On the Quantum Complexity of Closest Pair and Related Problems

Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, Ruizhe Zhang

Published Nov 5, 2019• 2 citations
arXivHTMLPDF

Abstract

The closest pair problem is a fundamental problem of computational geometry: given a set of $n$ points in a $d$-dimensional space, find a pair with the smallest distance. A classical algorithm taught in introductory courses solves this problem in $O(n\log n)$ time in constant dimensions (i.e., when $d=O(1)$). This paper asks and answers the question of the problem's quantum time complexity. Specifically, we give an $\tilde{O}(n^{2/3})$ algorithm in constant dimensions, which is optimal up to a polylogarithmic factor by the lower bound on the quantum query complexity of element distinctness. The key to our algorithm is an efficient history-independent data structure that supports quantum interference. In $\mathrm{polylog}(n)$ dimensions, no known quantum algorithms perform better than brute force search, with a quadratic speedup provided by Grover's algorithm. To give evidence that the quadratic speedup is nearly optimal, we initiate the study of quantum fine-grained complexity and introduce the Quantum Strong Exponential Time Hypothesis (QSETH), which is based on the assumption that Grover's algorithm is optimal for CNF-SAT when the clause width is large. We show that the naïve Grover approach to closest pair in higher dimensions is optimal up to an $n^{o(1)}$ factor unless QSETH is false. We also study the bichromatic closest pair problem and the orthogonal vectors problem, with broadly similar results.

DOI
10.48550/arxiv.1911.01973

Related papers

On the Quantum Complexity of Closest Pair and Related Problems

Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin +2 more

The closest pair problem is a fundamental problem of computational geometry: given a set of n points in a d-dimensional space, find a pair with the smallest distance. A classical algorithm taught in introductory courses solves this problem in O(n log n) time in constant dimensions (i.e., when d = O(1)). This paper asks and answers the question of the problem’s quantum time complexity. Specifically, we give an Õ(n^(2/3)) algorithm in constant dimensions, which is optimal up to a polylogarithmic factor by the lower bound on the quantum query complexity of element distinctness. The key to our algorithm is an efficient history-independent data structure that supports quantum interference. In polylog(n) dimensions, no known quantum algorithms perform better than brute force search, with a quadratic speedup provided by Grover’s algorithm. To give evidence that the quadratic speedup is nearly optimal, we initiate the study of quantum fine-grained complexity and introduce the Quantum Strong Exponential Time Hypothesis (QSETH), which is based on the assumption that Grover’s algorithm is optimal for CNF-SAT when the clause width is large. We show that the naïve Grover approach to closest pair in higher dimensions is optimal up to an n^o(1) factor unless QSETH is false. We also study the bichromatic closest pair problem and the orthogonal vectors problem, with broadly similar results.

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

Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization

Daniel Gibney, Ce Jin, Tomasz Kociumaka +1 more

Classically, the edit distance of two length-$n$ strings can be computed in $O(n^2)$ time, whereas an $O(n^{2-ε})$-time procedure would falsify the Orthogonal Vectors Hypothesis. If the edit distance does not exceed $k$, the running time can be improved to $O(n+k^2)$, which is near-optimal (conditioned on OVH) as a function of $n$ and $k$. Our first main contribution is a quantum $\tilde{O}(\sqrt{nk}+k^2)$-time algorithm that uses $\tilde{O}(\sqrt{nk})$ queries, where $\tilde{O}(\cdot)$ hides polylogarithmic factors. This query complexity is unconditionally optimal, and any significant improvement in the time complexity would resolve a long-standing open question of whether edit distance admits an $O(n^{2-ε})$-time quantum algorithm. Our divide-and-conquer quantum algorithm reduces the edit distance problem to a case where the strings have small Lempel-Ziv factorizations. Then, it combines a quantum LZ compression algorithm with a classical edit-distance subroutine for compressed strings. The LZ factorization problem can be classically solved in $O(n)$ time, which is unconditionally optimal in the quantum setting. We can, however, hope for a quantum speedup if we parameterize the complexity in terms of the factorization size $z$. Already a generic oracle identification algorithm yields the optimal query complexity of $\tilde{O}(\sqrt{nz})$ at the price of exponential running time. Our second main contribution is a quantum algorithm that achieves the optimal time complexity of $\tilde{O}(\sqrt{nz})$. The key tool is a novel LZ-like factorization of size $O(z\log^2n)$ whose subsequent factors can be efficiently computed through a combination of classical and quantum techniques. We can then obtain the string's run-length encoded Burrows-Wheeler Transform (BWT), construct the $r$-index, and solve many fundamental string processing problems in time $\tilde{O}(\sqrt{nz})$.

arXiv:2311.01793•Nov 3, 2023•0 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

Grover’s Algorithm applied to the Molecular Distance Geometry Problem

Carlile Lavor, Leo Liberti, Nelson Maculan

Grover's algorithm is a quantum algorithm for searching in unstructured databases. Due to the proper- ties of quantum mechanics, it provides a quadratic speedup over its classical counterparts. We present a new applica- tion of the algorithm to the Molecular Distance Geome- try Problem. This problem is related to the determination of the tridimensional structure of a molecule based on the knowledge of some of the distances between pairs of atoms. This problem is NP-hard unless all possible inter-atomic distances are known. Index Terms—Quantum Computation, Grover's algo- rithm, Molecular Distance Geometry Problem.

Congresso Brasileiro de Redes Neurais (CBRN)•Aug 29, 2016•4 citations

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

arXiv:2004.08949•Apr 19, 2020•1 citation

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
The closest pair problem is a fundamental problem of computational geometry: given a set of nnn points in a ddd-dimensional space, find a pair with the smallest distance. A classical algorithm taught in introductory courses solves this problem in O(nlog⁡n)O(n\log n)O(nlogn) time in constant dimensions (i.e., when d=O(1)d=O(1)d=O(1)). This paper asks and answers the question of the problem's quantum time complexity. Specifically, we give an O~(n2/3)\tilde{O}(n^{2/3})O~(n2/3) algorithm in constant dimensions, which is optimal up to a polylogarithmic factor by the lower bound on the quantum query complexity of element distinctness. The key to our algorithm is an efficient history-independent data structure that supports quantum interference. In polylog(n)\mathrm{polylog}(n)polylog(n) dimensions, no known quantum algorithms perform better than brute force search, with a quadratic speedup provided by Grover's algorithm. To give evidence that the quadratic speedup is nearly optimal, we initiate the study of quantum fine-grained complexity and introduce the Quantum Strong Exponential Time Hypothesis (QSETH), which is based on the assumption that Grover's algorithm is optimal for CNF-SAT when the clause width is large. We show that the naïve Grover approach to closest pair in higher dimensions is optimal up to an no(1)n^{o(1)}no(1) factor unless QSETH is false. We also study the bichromatic closest pair problem and the orthogonal vectors problem, with broadly similar results.
The closest pair problem is a fundamental problem of computational geometry: given a set of n points in a d-dimensional space, find a pair with the smallest distance. A classical algorithm taught in introductory courses solves this problem in O(n log n) time in constant dimensions (i.e., when d = O(1)). This paper asks and answers the question of the problem’s quantum time complexity. Specifically, we give an Õ(n^(2/3)) algorithm in constant dimensions, which is optimal up to a polylogarithmic factor by the lower bound on the quantum query complexity of element distinctness. The key to our algorithm is an efficient history-independent data structure that supports quantum interference. In polylog(n) dimensions, no known quantum algorithms perform better than brute force search, with a quadratic speedup provided by Grover’s algorithm. To give evidence that the quadratic speedup is nearly optimal, we initiate the study of quantum fine-grained complexity and introduce the Quantum Strong Exponential Time Hypothesis (QSETH), which is based on the assumption that Grover’s algorithm is optimal for CNF-SAT when the clause width is large. We show that the naïve Grover approach to closest pair in higher dimensions is optimal up to an n^o(1) factor unless QSETH is false. We also study the bichromatic closest pair problem and the orthogonal vectors problem, with broadly similar results.
Classically, the edit distance of two length-nnn strings can be computed in O(n2)O(n^2)O(n2) time, whereas an O(n2−ε)O(n^{2-ε})O(n2−ε)-time procedure would falsify the Orthogonal Vectors Hypothesis. If the edit distance does not exceed kkk, the running time can be improved to O(n+k2)O(n+k^2)O(n+k2), which is near-optimal (conditioned on OVH) as a function of nnn and kkk. Our first main contribution is a quantum O~(nk+k2)\tilde{O}(\sqrt{nk}+k^2)O~(nk​+k2)-time algorithm that uses O~(nk)\tilde{O}(\sqrt{nk})O~(nk​) queries, where O~(⋅)\tilde{O}(\cdot)O~(⋅) hides polylogarithmic factors. This query complexity is unconditionally optimal, and any significant improvement in the time complexity would resolve a long-standing open question of whether edit distance admits an O(n2−ε)O(n^{2-ε})O(n2−ε)-time quantum algorithm. Our divide-and-conquer quantum algorithm reduces the edit distance problem to a case where the strings have small Lempel-Ziv factorizations. Then, it combines a quantum LZ compression algorithm with a classical edit-distance subroutine for compressed strings. The LZ factorization problem can be classically solved in O(n)O(n)O(n) time, which is unconditionally optimal in the quantum setting. We can, however, hope for a quantum speedup if we parameterize the complexity in terms of the factorization size zzz. Already a generic oracle identification algorithm yields the optimal query complexity of O~(nz)\tilde{O}(\sqrt{nz})O~(nz​) at the price of exponential running time. Our second main contribution is a quantum algorithm that achieves the optimal time complexity of O~(nz)\tilde{O}(\sqrt{nz})O~(nz​). The key tool is a novel LZ-like factorization of size O(zlog⁡2n)O(z\log^2n)O(zlog2n) whose subsequent factors can be efficiently computed through a combination of classical and quantum techniques. We can then obtain the string's run-length encoded Burrows-Wheeler Transform (BWT), construct the rrr-index, and solve many fundamental string processing problems in time O~(nz)\tilde{O}(\sqrt{nz})O~(nz​).
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.
Grover's algorithm is a quantum algorithm for searching in unstructured databases. Due to the proper- ties of quantum mechanics, it provides a quadratic speedup over its classical counterparts. We present a new applica- tion of the algorithm to the Molecular Distance Geome- try Problem. This problem is related to the determination of the tridimensional structure of a molecule based on the knowledge of some of the distances between pairs of atoms. This problem is NP-hard unless all possible inter-atomic distances are known. Index Terms—Quantum Computation, Grover's algo- rithm, Molecular Distance Geometry Problem.
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.
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.