文章基本信息

标题：On the Quantum Complexity of Closest Pair and Related Problems
本地全文：下载
作者：Scott Aaronson ; Nai-Hui Chia ; Han-Hsuan Lin 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：169
页码：16:1-16:43
DOI：10.4230/LIPIcs.CCC.2020.16
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 OÌf(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 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Ã¯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.
关键词：Closest pair; Quantum computing; Quantum fine grained reduction; Quantum strong exponential time hypothesis; Fine grained complexity