  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.
