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"{i}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.
Introduction
The Closest Pair (CP) problem is a cornerstone of computational geometry. Given $n$ points in a $d$-dimensional space, the objective is to identify the two points separated by the minimum Euclidean distance. While classical computer science has long established an $O(n \log n)$ solution for constant dimensions, the problem's quantum complexity has remained less certain. This research addresses whether quantum algorithms can leverage geometric structure to surpass the general quadratic speedup offered by Grover's unstructured search.
Constant Dimensions: Quantum Walks and History-Independence
In low-dimensional spaces ($d=O(1)$), the authors demonstrate an optimal quantum algorithm running in $\tilde{O}(n^{2/3})$ time. This result is significant as it matches the lower bound for the "Element Distinctness" problem, proving its optimality up to polylogarithmic factors.
The primary technical challenge in achieving this speedup via Quantum Walks on a Johnson graph is maintaining History-Independence. In quantum mechanics, if the internal state of a data structure (like a tree or heap) depends on the order in which elements were inserted, the resulting quantum states will fail to interfere correctly. This decoherence destroys the quantum speedup. To overcome this, the authors designed a unique, augmented data structure combining radix trees, hash tables, and skip lists. This structure ensures a unique memory representation for any set of points, regardless of their insertion history, thereby enabling valid quantum interference.
High Dimensions: Quantum Fine-Grained Complexity
As the number of dimensions grows to $d = \text{polylog } n$, the problem encounters a "curse of dimensionality" where geometric advantages vanish. To analyze this regime, the authors introduce the Quantum Strong Exponential Time Hypothesis (QSETH). QSETH assumes that Grover’s algorithm is essentially the best possible approach for solving CNF-SAT problems.
By "quantizing" classical fine-grained reductions, the authors prove that under QSETH, the Closest Pair problem in high dimensions requires $n^{1-o(1)}$ time. This implies that the $O(n)$ time complexity achieved by a naive Grover search over all pairs is nearly optimal. A key innovation in this proof is the "on-the-fly" reduction, a quantum subroutine that simulates the output of a reduction without the need to write down a massive intermediate dataset, which would otherwise exceed the time budget.
Summary of Results
The paper provides a comprehensive map of quantum complexity across several related problems, including the Bichromatic Closest Pair (BCP) and Orthogonal Vectors (OV) problems. The findings highlight a sharp divide: in low dimensions, geometric structure allows for significant speedups, while in high dimensions, the problems become combinatorial and resistant to improvements beyond Grover's search.
Conclusion
This work establishes the first tight bounds for the quantum complexity of the Closest Pair problem. By introducing QSETH and developing history-independent data structures, the authors provide a framework for future research into quantum fine-grained complexity. While the $O(n^{2/3})$ algorithm is theoretically optimal, its reliance on complex data structures suggests that practical implementation on near-term hardware may face significant constant-factor overheads.
Summary updated