2026-07-23T10:34:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12568 2024-03-06T10:50:28Z ddc:004 open_access

On the Quantum Complexity of Closest Pair and Related Problems Aaronson, Scott Chia, Nai-Hui Lin, Han-Hsuan Wang, Chunhao Zhang, Ruizhe Closest pair Quantum computing Quantum fine grained reduction Quantum strong exponential time hypothesis Fine grained complexity 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 Õ(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Scott Aaronson and Nai-Hui Chia and Han-Hsuan Lin and Chunhao Wang and Ruizhe Zhang 2020 Is Part Of LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2020.16 urn:nbn:de:0030-drops-125681 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.16 eng https://creativecommons.org/licenses/by/3.0/legalcode