Quantum Fine-Grained Complexity

(The speaker is also a professor at University of Amsterdam & QuSoft. This is a joint seminar with the iTHEMS Quantum Computation Study Group.)

One of the major challenges in computer science is to establish lower bounds on the resources, typically time, that are needed to solve computational problems, especially those encountered in practice. A promising approach to this challenge is the study of fine-grained complexity, which employs special reductions to prove time lower bounds for many diverse problems based on the conjectured hardness of key problems.
For instance, the problem of computing the edit distance between two strings, which is of practical interest for determining the genetic distance between species based on their DNA, has an algorithm that takes O(n^2) time. Through a fine-grained reduction, it can be demonstrated that a faster algorithm for edit distance would imply a faster algorithm for the Boolean Satisfiability (SAT) problem. Since faster algorithms for SAT are generally considered unlikely to exist, this implies that faster algorithms for the edit distance problem are also unlikely to exist. Other problems used for such reductions include the 3SUM problem and the All Pairs Shortest Path (APSP) problem.
The quantum regime presents similar challenges; almost all known lower bounds for quantum algorithms are defined in terms of query complexity, which offers limited insight for problems where the best-known algorithms take super-linear time. Employing fine-grained reductions in the quantum setting, therefore, represents a natural progression. However, directly translating classical fine-grained reductions to the quantum regime poses various challenges.
In this talk, I will present recent results in which we overcome these challenges and prove quantum time lower bounds for certain problems in BQP, conditioned on the conjectured quantum hardness of, for example, SAT (and its variants), the 3SUM problem, and the APSP problem. This presentation is based on joint works with Andris Ambainis, Bruno Loff, Florian Speelman, and Subhasree Patro.