TL;DR
This paper characterizes the quantum time complexity of the classic Closest Pair (CP) problem and its relatives (Bichromatic Closest Pair and Orthogonal Vectors). For constant dimensions, the authors design an optimal $\widetilde{O}(n^{2/3})$ quantum walk algorithm supported by a custom history-independent data structure. For higher dimensions ($\mathrm{polylog}(n)$), they introduce the Quantum Strong Exponential Time Hypothesis (QSETH) and develop a theory of quantum fine-grained reductions to prove that the simple Grover-based $\widetilde{O}(n)$ search is essentially optimal.
What Problem Does This Paper Address?
In computational geometry, the Closest Pair problem (CP) asks: given $n$ points in $\mathbb{R}^d$, find the pair separated by the minimum Euclidean distance. Classically, when dimension $d = O(1)$, divide-and-conquer solves this in $O(n \log n)$ time. However, in $\mathrm{polylog}(n)$ dimensions, running times blow up to $\Omega(n^2)$, a barrier proven conditional on the Strong Exponential Time Hypothesis (SETH).
Despite extensive study in classical algorithms, the quantum time complexity of CP was largely unresolved:
- In low dimensions, can quantum algorithms beat $O(n \log n)$, and what is the optimal quantum time bound?
- In higher dimensions, naive Grover search over all $O(n^2)$ pairs gives an $\widetilde{O}(n)$ quantum algorithm. Can we do better, or can we prove that Grover search is conditionally optimal in a quantum analogue of fine-grained complexity?
Methods
The authors tackle both low- and high-dimensional regimes with distinct toolsets:
-
Quantum Walks with History-Independent Data Structures ($d = O(1)$): The algorithm implements a quantum walk search on a Johnson graph. A major barrier in translating quantum query speedups (like Ambainis's element distinctness walk) to time-efficient geometric algorithms is maintaining the data structure in superposition. If the memory representation depends on the history or order of insertions/deletions, interference is destroyed. The authors solve this by introducing a strictly history-independent data structure: space is discretized into hypercubes ($\epsilon$-boxes), tracked by an augmented radix tree, skip lists, and hash tables. This supports $O(\log n)$ updates and $O(1)$ checking for $\epsilon$-close pairs without leaking state history.
-
Quantum Fine-Grained Complexity and QSETH ($d = \mathrm{polylog}(n)$): Standard SETH fails in quantum settings because Grover’s algorithm already solves CNF-SAT in $\widetilde{O}(2^{n/2})$. The authors formulate QSETH: no quantum algorithm solves $k$-SAT in $O(2^{(1/2 - \epsilon)n})$ time for large clause width $k$. They then formalize quantum fine-grained reductions, overcoming classical bottlenecks by:
-
Simulating input oracles "on-the-fly" in superposition rather than explicitly writing out exponentially large vector sets.
- Using quantum minimum-finding over non-adaptive oracle calls to compress multiple classical reduction branches quadratically.
Datasets
Not discussed in the paper (this is a theoretical computer science paper; no empirical datasets or benchmarks were used).
Key Insights and Ideas
- History independence is mandatory for quantum walks: Standard dynamic spatial indices (like kd-trees or fair-split trees) depend on insertion sequence. Using superpositions over valid memory cell layouts combined with canonical tree and list representations allows coherent quantum interference during updates and walk steps.
- Bridging query lower bounds to time complexity: Element Distinctness naturally embeds into 1D Closest Pair (distance zero corresponds to a collision), instantly giving an $\Omega(n^{2/3})$ quantum query lower bound. The paper's walk algorithm matches this bound up to polylogarithmic factors.
- Why naive classical reductions break in quantum fine-grained complexity: Classical reductions often construct $N = 2^{n/2}$ vectors in $O(N)$ time, which is trivially fine-grained classically ($O(2^{n/2}) \ll 2^n$), but exceeds the quantum target runtime under QSETH ($O(2^{n/2})$). Quantum reductions must query constructed instances implicitly via superposed gates.
- Bichromatic Closest Pair (BCP) separation: In constant dimensions, BCP remains strictly harder than CP: the authors show an $\Omega(n^{2/3})$ query lower bound, an $\widetilde{O}(n^{1 - 1/(2d) + \delta})$ exact quantum algorithm, and an optimal $\widetilde{O}(n^{2/3})$ algorithm for $(1+\xi)$-approximation.
Key Results
| Problem | Dimension ($d$) | Quantum Lower Bound | Quantum Upper Bound |
|---|---|---|---|
| CP | $O(1)$ | $\Omega(n^{2/3})$ (unconditional) | $\widetilde{O}(n^{2/3})$ |
| CP | $\mathrm{polylog}(n)$ | $n^{1 - o(1)}$ (under QSETH) | $\widetilde{O}(n)$ |
| OV (Orthogonal Vectors) | $O(1)$ | $\Omega(n^{1/2})$ | $\widetilde{O}(n^{1/2})$ |
| OV | $\mathrm{polylog}(n)$ | $n^{1 - o(1)}$ (under QSETH) | $\widetilde{O}(n)$ |
| BCP | $O(1)$ | $\Omega(n^{2/3})$ | $\widetilde{O}(n^{1 - \frac{1}{2d} + \delta})$ (exact)<br>$\widetilde{O}(\xi^{-d} n^{2/3})$ ($(1+\xi)$-approx) |
| BCP | $2^{O(\log^* n)}$ | $n^{1 - o(1)}$ (under QSETH) | $\widetilde{O}(n)$ |
Limitations and Future Work
- Exact BCP Gap in Constant Dimensions: While approximate BCP matches the $\widetilde{O}(n^{2/3})$ bound, exact BCP sits between $\Omega(n^{2/3})$ and $\widetilde{O}(n^{1 - 1/(2d) + \delta})$. Closing this gap requires either a history-independent data structure capable of efficient nearest-neighbor searches across two colors or stronger lower bounds.
- QSETH Foundation: As an axiomatic complexity hypothesis, QSETH assumes Grover search is essentially optimal for large-width SAT. Further investigation into potential non-Grover quantum shortcuts for structured SAT formulas remains open.
- Broadening Quantum Fine-Grained Reductions: Extending the quantum fine-grained framework to other classic problems (such as 3SUM, Edit Distance, and All-Pairs Shortest Paths) is a natural and active direction.
Summary updated