Quantum computing offers the potential to solve problems more efficiently than classical methods, yet understanding its capabilities requires new conceptual frameworks. This dissertation explores quantum algorithms with a focus on maintaining connections to classical intuition, clarifying both their strengths and limitations. In Part I, we explore the capabilities of a class of quantum algorithms known as quantum walks. These quantum walks, the quantum analogs of classical random walks, serve as powerful yet accessible tools for solving a variety of computational problems. Our key contribution is the development of a novel way to construct quantum walks, resulting in multidimensional quantum walks. By applying these walks to the $k$-distinctness problem, we achieve a time-efficient algorithm matching the best-known query upper bound up to polylogarithmic factors. Additionally, applying them to the welded tree problem results in exponential speedups, marking the first instance of a discrete quantum walk to do so. Furthermore, we extend the well-known link between quantum walks and electrical networks to the multidimensional quantum walks. In Part II, we turn to the limitations of quantum algorithms by examining techniques for establishing quantum query lower bounds, representing the minimum computational cost required for any quantum algorithm to solve a given computational problem, regardless of the quantum algorithm used. To this goal, we introduce the multiplicative ladder adversary method, a simplified version of the multiplicative adversary method which unifies the compressed oracle technique within the broader adversary framework while extending its applicability, offering a more intuitive approach to establishing quantum lower bounds.
Quantum computing offers the potential to solve problems more efficiently than classical methods, yet understanding its capabilities requires new conceptual frameworks. This dissertation explores quantum algorithms with a focus on maintaining connections to classical intuition, clarifying both their strengths and limitations. In Part I, we explore the capabilities of a class of quantum algorithms known as quantum walks. These quantum walks, the quantum analogs of classical random walks, serve as powerful yet accessible tools for solving a variety of computational problems. Our key contribution is the development of a novel way to construct quantum walks, resulting in multidimensional quantum walks. By applying these walks to the k-distinctness problem, we achieve a time-efficient algorithm matching the best-known query upper bound up to polylogarithmic factors. Additionally, applying them to the welded tree problem results in exponential speedups, marking the first instance of a discrete quantum walk to do so. Furthermore, we extend the well-known link between quantum walks and electrical networks to the multidimensional quantum walks. In Part II, we turn to the limitations of quantum algorithms by examining techniques for establishing quantum query lower bounds, representing the minimum computational cost required for any quantum algorithm to solve a given computational problem, regardless of the quantum algorithm used. To this goal, we introduce the multiplicative ladder adversary method, a simplified version of the multiplicative adversary method which unifies the compressed oracle technique within the broader adversary framework while extending its applicability, offering a more intuitive approach to establishing quantum lower bounds.
Multidimensional Quantum Walks, with Application to k-Distinctness
While the quantum query complexity of k-distinctness is known to be O(n3/4−1/4(2k−1)) for any constant k≥4, the best previous upper bound on the time complexity was O(n1−1/k). We give a new upper bound of O(n3/4−1/4(2k−1)) on the time complexity, matching the query complexity up to polylogarithmic factors. In order to achieve this upper bound, we give a new technique for designing quantum walk search algorithms, which is an extension of the electric network framework. We also show how to solve the welded trees problem in O(n) queries and O(n2) time using this new technique, showing that the new quantum walk framework can achieve exponential speedups. Comment: Journal version for TheoretiCS
While the quantum query complexity of k-distinctness is known to be O(n3/4 − 1/4(2k−1)) for any constant k≥ 4 [Belovs, FOCS 2012], the best previous upper bound on the time complexity was O(n1−1/k). We give a new upper bound of O(n3/4 − 1/4(2k−1)) on the time complexity, matching the query complexity up to polylogarithmic factors. In order to achieve this upper bound, we give a new technique for designing quantum walk search algorithms, which is an extension of the electric network framework. We also show how to solve the welded trees problem in O(n) queries and O(n2) time using this new technique, showing that the new quantum walk framework can achieve exponential speedups.
Due to the difficulty of constructing new quantum algorithms, frameworks that facilitate this construction are of great importance in quantum computing. These frameworks reduce the problem of coming up with a quantum algorithm to that of constructing some combinatorial object that is often much simpler to reason about. The implementation and analysis of an algorithm for the specified problem follow from the properties of this object. A number of such frameworks have been extremely successful in leading to the development of numerous quantum algorithms for a variety of problems. In this thesis, we build on two of these frameworks, the quantum walk search framework, and the span program framework, extending their algorithmic potential. \n \nThe quantum walk search framework gives a generic quantum analogue to a specific type of classical algorithm based on random walks. If one can construct a classical algorithm of this form, a corresponding quantum algorithm with better complexity immediately follows. In this framework, a generic algorithm is constructed from several subroutines for which implementations must be given for each application. One of these subroutines, a checking subroutine, is run many times throughout the algorithm. This subroutine may be implemented by any quantum algorithm that satisfies the required functionality, including another quantum walk algorithm. By making a slight modification to the quantum walk framework, we can show how to nest a quantum walk algorithm in the checking subroutine of another quantum walk algorithm in a way that gives better complexity than the naive nesting. This modification allows us to reproduce a number of upper bounds previously obtained in another framework, the learning graph framework, including upper bounds for triangle finding, and more generally, subgraph finding for constant-sized subgraphs. Porting these upper bounds over to the setting of quantum walks is desirable because the algorithms achieved in the quantum walk search framework are much more explicit than those of the learning graph framework, making them easier to work with, modify, and build on, as needed. Our efficient nested checking idea has already been used to come up with new quantum algorithms for finding sub-hypergraphs. \n \nAnother subroutine that is called repeatedly by the generic quantum walk search algorithm is the update subroutine. It was not clear how to use a quantum walk algorithm to perform this step, but by making another slight modification to the quantum walk search framework, we are able to show how to nest a quantum walk in the update step of another quantum walk in an efficient way. Our technique for doing this is a special case of a technique that allows the update to be implemented with garbage --- i.e., some unwanted data in an auxiliary register, entangled with the desired state. This technique may have other applications. \n \nUsing the nested update technique, we are able to improve the best known upper bounds on the time complexity of k-distinctness. Previously the best known upper bound on the time complexity was nk/(k+1), due to Ambainis. Belovs had recently improved the query complexity of k-distinctness to o(n3/4) for all k, but since this upper bound was obtained in a framework called span programs, which only gives upper bounds on quantum query complexity, there was no known time efficient implementation of his k-distinctness algorithm. We use ideas from his construction and our nested update technique to get a quantum time upper bound for 3-distinctness of n5/7, matching his quantum query upper bound. We can generalize our algorithm get a time upper bound of n(k−1)/k for any k>3, slightly improving on the best previous upper bound. \n \nAnother framework, the span program framework, is known to be equivalent to quantum query complexity, in the sense that for any Boolean decision problem, there exists a span program construction that yields a tight upper bound on its quantum query complexity. We explore several variations of this framework. First, we slightly modify the definition of a span program so that we can show that for \\emph{any} (not necessarily Boolean) decision problem, there is a span program construction that yields a tight upper bound on its quantum query complexity. Previously this was only known up to logarithmic factors. We also explore several approximate versions of span programs, and show them to be equivalent. Finally, we explore the structure of span program witnesses, and use this structure to present an algorithm for evaluating span programs that is straightforward and intuitive. We also show how to evaluate approximate span programs, opening the possibility for the construction of new upper bounds using approximate span programs.
In the welded tree problem, an algorithm is tasked with navigating a graph formed from two binary trees joined at the leaves through a ``weld'' of connecting edges. A quantum walk can navigate from root to root exponentially faster than any classical algorithm. However, known efficient quantum algorithms cannot find a path between the roots, as recording the path destroys constructive interference and thus the speedup. We prove that this is inherent: any quantum algorithm needs exponentially many queries to find a path between the roots of an independently matched welded tree graph. This provides an example of a problem that a quantum computer can solve exponentially faster than any classical algorithm by exploring exponentially many paths in superposition, but where it is provably intractable to find any such path. The proof uses compressed permutation oracles to record the progress of a quantum algorithm as it queries the graph. We show that the compressed database remains path-free up to a small error. By controlling such errors and bounding the progress of the algorithm with each compressed oracle query, we show that Ω(2n/12) queries are required to find a path in a height-n tree with constant success probability.
In the thesis, we use a recently developed tight characterisation of quantum query complexity, the adversary bound, to develop new quantum algorithms and lower bounds. Our results are as follows: * We develop a new technique for the construction of quantum algorithms: learning graphs. * We use learning graphs to improve quantum query complexity of the triangle detection and the k-distinctness problems. * We prove tight lower bounds for the k-sum and the triangle sum problems. * We construct quantum algorithms for some subgraph-finding problems that are optimal in terms of query, time and space complexities. * We develop a generalisation of quantum walks that connects electrical properties of a graph and its quantum hitting time. We use it to construct a time-efficient quantum algorithm for 3-distinctness.
In the first part of the thesis we construct a new, simple framework which amplifies to a constant the success probability of any abstract search algorithm. The total query complexity is given by the quantum hitting time of the resulting operator, which we show that it is of the same order as the quantum hitting time of the original algorithm. As a major application of our framework, we show that for any reversible walk P and a single marked state, the quantum walk corresponding to P can find the solution using a number of queries that is quadratically smaller than the classical hitting time of P. Our algorithm is more general and simpler to implement than the solution known previously in the literature (Krovi, Magniez, Ozols, and Roland, 2015), which was developed specifically for quantum walks; we also prove that, for the particular case of quantum walks, we can embed their algorithm into our framework, thus simulating it exactly. Finally, we show that we can implement amplitude amplification using our tool. In the second part of the thesis we give a new lower bound in the query model which proves that Grover's algorithm for unordered searching is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same an exact bound. We then turn our attention to non-adaptive algorithms for the same problem of searching an unordered set. In this model, we obtain a lower bound and we give an algorithm which matches the lower bound, thus showing that the lower bound is exactly optimal.