On the Quantum Complexity of Closest Pair and Related Problems

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

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-08
Main Authors: Aaronson, Scott, Nai-Hui Chia, Han-Hsuan, Lin, Wang, Chunhao, Zhang, Ruizhe
Format: Article
Language:English
Subjects:
Algorithms
Complexity
Computational geometry
Data structures
Lower bounds
Supports
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422