Quantum speedups: structure, design, and application

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 show how a problem’s symmetries relate to whether it can admit a polynomial or superpolynomial quantum speedup. In particular, we show that the computation of any partial function of a hypergraph’s adjacency matrix can only admit a polynomial speedup. On the other hand, we construct a partial function of a graph’s adjacency list that admits an exponential speedup. Second, we study the classical paradigm used to solve the problem. We design a natural quantum query analog of the divide and conquer paradigm and apply it to obtain near-optimal quantum query complexities for four important string problems. In particular, we obtain the first quantum speedups for parametrized versions of Longest Increasing Subsequence and Longest Common Subsequence. Third, we study the generalization of a problem known to admit a quantum speedup. We design a near-optimal quantum algorithm that solves the generalized search problem where the goal is to output the most heavily marked item out of a set of partially marked items. Coincidentally, this problem is equivalent to the multi-armed bandit problem, which lies at the heart of reinforcement learning and has many applications.