Quantum Query Algorithms: Design, Optimality, Complexity

Abstract

In this thesis we investigate quantum query algorithms from three perspectives: design paradigms, optimality, and complexity.

First, we study how the divide and conquer paradigm---widely used in classical algorithm design---can be adapted to quantum algorithms. We leverage the quantum adversary method to develop a generic framework for designing quantum query algorithms using divide and conquer. We demonstrate the utility of our framework by proposing near-optimal quantum query algorithms for a variety of string processing problems, such as decision versions of the string rotation, string suffix, longest increasing subsequence, and longest common subsequence problems.

Next, we study translation-invariant quantum algorithms for the ordered search problem. On a classical computer, this problem is solved optimally by the binary search algorithm using ⌈log2(n)⌉ queries. Quantum computers offer only a constant-factor speedup: the quantum query complexity of solving this problem (with no error) is known to lie between approximately 0.221 log2(n) and 0.433 log2(n). We make progress towards closing this gap in two ways. First, we improve the above upper bound to approximately 0.390 log2(n). Second, we prove that the class of translation-invariant algorithms, to which most algorithms proposed for this problem belong, is in fact optimal for ordered search. A consequence of our result is that no workspace is needed by optimal algorithms for this problem.

Finally, we consider the long-standing open question of whether the rational degree is polynomially related to the degree of a total Boolean function, a question that characterizes the power of exact, postselected quantum algorithms. We prove asymptotically tight bounds on the rational degree in terms of the degree for special classes of functions such as symmetric and unate functions. Additionally, we show that almost all Boolean functions on n variables have rational degree at least n/2 - O(√n). We also establish AND and OR composition lemmas for the rational degree and exhibit new polynomial separations between the rational degree and other well-studied complexity measures, such as sensitivity and spectral sensitivity.