Quantum Speedups: Structure, Design, and Application

Abstract

A quantum speedup occurs when a computational problem can be solved faster on a quantum computer than on a classical computer. This thesis studies the circumstances under which quantum speedups can arise from three perspectives. First, we study the structure of the problem. We characterize how a problem's symmetries decide whether it admits a superpolynomial or polynomial quantum speedup. In particular, we show that the computation of any partial function of a hypergraph's adjacency matrix admits at most a polynomial speedup. Such functions are only weakly symmetric and subsequent work shows that if the symmetry is weakened even further, then a superpolynomial speedup can be possible. To complete the picture for graph problems, we also construct a partial function of a graph's adjacency list that admits an exponential speedup. Second, we study classical paradigms for solving problems. We design a natural quantum query analogue of the divide and conquer paradigm, which we call the ``quantum divide and conquer'' framework. This framework allows us to quantumly speed up the solution of many problems that are classically solved using divide and conquer. The main technical novelty of our framework is that it naturally combines quantum adversary and quantum algorithmic techniques. To showcase its usefulness, we apply it to obtain near-optimal quantum query complexities for four string problems: (i) recognizing regular languages; (ii) decision versions of String Rotation and String Suffix; and natural parameterized versions of (iii) Longest Increasing Subsequence and (iv) Longest Common Subsequence. Third, we study ways of generalizing a problem known to admit a quantum speedup. We generalize the search problem of finding a marked item in a database to the case where the items are not either marked or unmarked, but are ``partially marked''. The goal is to find the item that is the most heavily marked. We construct a quantum algorithm for this problem within the variable-time framework and prove its near-optimality by modifying the standard adversary method to work for oracles encoding probability distributions. Coincidentally, the problem studied is equivalent to the multi-armed bandits problem in reinforcement learning, which has many applications.