Quantum fine-grained complexity and the quantum advantage

One way towards dealing with this situation is the study of fine-grained complexity where we use special reductions to prove time lower bounds for many diverse problems based on the conjectured hardness of some key problems. For example, computing the edit distance between two strings, a problem that has a practical interest when determining the genetic distance between species based on their DNA, has an algorithm that takes O(n^2) time. Using a fine-grained reduction it can be shown that faster algorithms for edit distance also imply a faster algorithm for the Boolean Satisfiability (SAT) problem (that is believed to not exist). This is evidence that the current edit distance algorithms are optimal. Another problem, besides SAT, that is used as a basis for these reductions is the 3SUM problem.

The situation in the quantum regime is no better; almost all known lower bounds for quantum algorithms are defined in terms of query complexity, which doesn’t help much for problems for which the best-known algorithms take super-linear time. Therefore, employing fine-grained reductions in the quantum setting seems a natural way forward. However, translating the classical fine-grained reductions directly into the quantum regime is not always possible for various reasons. In this talk, I will present some recent results in which we circumvent these challenges and prove quantum time lower bounds for some problems in BQP conditioned on the conjectured quantum hardness of for example SAT (and its variants) the 3SUM problem, and the All Pairs Shortest Path (APSP) problem.

One consequence of our work is that many computational problems have at most a quadratic quantum speedup and often even less. In practise, this speedup is countered by the slowdown quantum computers incur due to error-correction and fault tolerant computation, which means that for these tasks quantum advantage only kicks in for very large inputs. This in turn means that they require many logical qubits which will not be available in the foreseeable future.

This is based on joint work with Koen Leijnse, Bruno Loff, Subhasree Patro ,and Florian Speelman.