Abstract
Many computational problems are subject to a quantum speedup: one might find that a problem having an O(n³)time or O(n²)time classic algorithm can be solved by a known O(n^{1.5})time or O(n)time quantum algorithm. The question naturally arises: how much quantum speedup is possible?
The area of finegrained complexity allows us to prove optimal lowerbounds on the complexity of various computational problems, based on the conjectured hardness of certain natural, wellstudied problems. This theory has recently been extended to the quantum setting, in two independent papers by Buhrman, Patro and Speelman [Buhrman et al., 2021], and by Aaronson, Chia, Lin, Wang, and Zhang [Aaronson et al., 2020].
In this paper, we further extend the theory of finegrained complexity to the quantum setting. A fundamental conjecture in the classical setting states that the 3SUM problem cannot be solved by (classical) algorithms in time O(n^{2ε}), for any ε > 0. We formulate an analogous conjecture, the Quantum3SUMConjecture, which states that there exist no sublinear O(n^{1ε})time quantum algorithms for the 3SUM problem.
Based on the Quantum3SUMConjecture, we show new lowerbounds on the time complexity of quantum algorithms for several computational problems. Most of our lowerbounds are optimal, in that they match known upperbounds, and hence they imply tight limits on the quantum speedup that is possible for these problems.
These results are proven by adapting to the quantum setting known classical finegrained reductions from the 3SUM problem. This adaptation is not trivial, however, since the original classical reductions require preprocessing the input in various ways, e.g. by sorting it according to some order, and this preprocessing (provably) cannot be done in sublinear quantum time.
We overcome this bottleneck by combining a quantum walk with a classical dynamic datastructure having a certain "historyindependence" property. This type of construction has been used in the past to prove upper bounds, and here we use it for the first time as part of a reduction. This general proof strategy allows us to prove tight lower bounds on several computationalgeometry problems, on Convolution3SUM and on the 0EdgeWeightTriangle problem, conditional on the Quantum3SUMConjecture.
We believe this proof strategy will be useful in proving tight (conditional) lowerbounds, and limits on quantum speedups, for many other problems.
BibTeX  Entry
@InProceedings{buhrman_et_al:LIPIcs.ITCS.2022.31,
author = {Buhrman, Harry and Loff, Bruno and Patro, Subhasree and Speelman, Florian},
title = {{Limits of Quantum SpeedUps for Computational Geometry and Other Problems: FineGrained Complexity via Quantum Walks}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {31:131:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15627},
URN = {urn:nbn:de:0030drops156273},
doi = {10.4230/LIPIcs.ITCS.2022.31},
annote = {Keywords: complexity theory, finegrained complexity, 3SUM, computational geometry problems, data structures, quantum walk}
}
Keywords: 

complexity theory, finegrained complexity, 3SUM, computational geometry problems, data structures, quantum walk 
Collection: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022) 
Issue Date: 

2022 
Date of publication: 

25.01.2022 