Aaronson, Scott ;
Chia, NaiHui ;
Lin, HanHsuan ;
Wang, Chunhao ;
Zhang, Ruizhe
On the Quantum Complexity of Closest Pair and Related Problems
Abstract
The closest pair problem is a fundamental problem of computational geometry: given a set of n points in a ddimensional 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 historyindependent 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 finegrained complexity and introduce the Quantum Strong Exponential Time Hypothesis (QSETH), which is based on the assumption that Grover’s algorithm is optimal for CNFSAT 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.
BibTeX  Entry
@InProceedings{aaronson_et_al:LIPIcs:2020:12568,
author = {Scott Aaronson and NaiHui Chia and HanHsuan Lin and Chunhao Wang and Ruizhe Zhang},
title = {{On the Quantum Complexity of Closest Pair and Related Problems}},
booktitle = {35th Computational Complexity Conference (CCC 2020)},
pages = {16:116:43},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771566},
ISSN = {18688969},
year = {2020},
volume = {169},
editor = {Shubhangi Saraf},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12568},
URN = {urn:nbn:de:0030drops125681},
doi = {10.4230/LIPIcs.CCC.2020.16},
annote = {Keywords: Closest pair, Quantum computing, Quantum fine grained reduction, Quantum strong exponential time hypothesis, Fine grained complexity}
}
17.07.2020
Keywords: 

Closest pair, Quantum computing, Quantum fine grained reduction, Quantum strong exponential time hypothesis, Fine grained complexity 
Seminar: 

35th Computational Complexity Conference (CCC 2020)

Issue date: 

2020 
Date of publication: 

17.07.2020 