Many quantum algorithms critically rely on quantum walk search, or the use of quantum walks to speed up search problems on graphs. However, the main results on quantum walk search are scattered over different, incomparable frameworks, such as the hitting time framework, the MNRS framework, and the electric network framework. As a consequence, a number of pieces are currently missing. For example, recent work by Ambainis et al. (STOC'20) shows how quantum walks starting from the stationary distribution can always find elements quadratically faster. In contrast, the electric network framework allows quantum walks to start from an arbitrary initial state, but it only detects marked elements. We present a new quantum walk search framework that unifies and strengthens these frameworks, leading to a number of new results. For example, the new framework effectively finds marked elements in the electric network setting. The new framework also allows to interpolate between the hitting time framework, minimizing the number of walk steps, and the MNRS framework, minimizing the number of times elements are checked for being marked. This allows for a more natural tradeoff between resources. In addition to quantum walks and phase estimation, our new algorithm makes use of quantum fast-forwarding, similar to the recent results by Ambainis et al. This perspective also enables us to derive more general complexity bounds on the quantum walk algorithms, e.g., based on Monte Carlo type bounds of the corresponding classical walk. As a final result, we show how in certain cases we can avoid the use of phase estimation and quantum fast-forwarding, answering an open question of Ambainis et al.
Many quantum algorithms critically rely on quantum walk search, or the use of quantum walks to speed up search problems on graphs. However, the main results on quantum walk search are scattered over different, incomparable frameworks, such as the hitting time framework, the MNRS framework, and the electric network framework. As a consequence, a number of pieces are currently missing. For example, recent work by Ambainis et al. (STOC'20) shows how quantum walks starting from the stationary distribution can always find elements quadratically faster. In contrast, the electric network framework allows quantum walks to start from an arbitrary initial state, but it only detects marked elements. We present a new quantum walk search framework that unifies and strengthens these frameworks, leading to a number of new results. For example, the new framework effectively finds marked elements in the electric network setting. The new framework also allows to interpolate between the hitting time framework, minimizing the number of walk steps, and the MNRS framework, minimizing the number of times elements are checked for being marked. This allows for a more natural tradeoff between resources. In addition to quantum walks and phase estimation, our new algorithm makes use of quantum fast-forwarding, similar to the recent results by Ambainis et al. This perspective also enables us to derive more general complexity bounds on the quantum walk algorithms, e.g., based on Monte Carlo type bounds of the corresponding classical walk. As a final result, we show how in certain cases we can avoid the use of phase estimation and quantum fast-forwarding, answering an open question of Ambainis et al.
We propose a new framework for turning quantum search algorithms that decide into quantum algorithms for finding a solution. Consider we are given an abstract quantum search algorithm A that can determine whether a target g exists or not. We give a general construction of another operator U that both determines and finds the target, whenever one exists. Our amplification method at most doubles the cost over using A, has little overhead, and works by controlling the evolution of A. This is the first known general framework to the open question of turning abstract quantum search algorithms into quantum algorithms for finding a solution. We next apply the framework to random walks. We develop a new classical algorithm and a new quantum algorithm for finding a unique marked element. Our new random walk finds a unique marked element using H update operations and 1/eps checking operations. Here H is the hitting time, and eps is the probability that the stationary distribution of the walk is in the marked state. Our classical walk is derived via quantum arguments. Our new quantum algorithm finds a unique marked element using H^(1/2) update operations and 1/eps^(1/2) checking operations, up to logarithmic factors. This is the first known quantum algorithm being simultaneously quadratically faster in both parameters. We also show that the framework can simulate Grover's quantum search algorithm, amplitude amplification, Szegedy's quantum walks, and quantum interpolated walks.
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.
We consider the problem of finding a marked vertex in a graph from an arbitrary starting distribution, using a quantum walk based algorithm. We work in the framework introduced by Belovs which showed how to detect the existence of a marked vertex in O(RW) quantum walk steps, where R is the effective resistance and W is the total weight of the graph. Our algorithm outputs a marked vertex in the same runtime up to a logarithmic factor in the number of marked vertices. When starting in the stationary distribution, this recovers the recent results of Ambainis et al. We also describe a new algorithm to estimate the effective resistance R.
Abstract Quantum walks are powerful tools for building quantum search algorithms. However, these success probabilities are far below 1. Amplitude amplification is usually used to amplify success probability, but the soufflé problem follows. Only stop at the right step can we achieve a maximum success probability. Otherwise, as the number of steps increases, the success probability may decrease, which will cause troubles in the practical application of the algorithm when the optimal number of steps is unknown. In this work, we define generalized interpolated quantum walks instead of amplitude amplification, which can not only improve the success probability but also avoid the soufflé problem. We choose a special case of generalized interpolated quantum walks and construct a series of new search algorithms based on phase estimation and quantum fast-forwarding, respectively. Especially, by combining our interpolated quantum walks with quantum fast-forwarding, we both reduce the time complexity of the search algorithm from Θ ( ( ε − 1 ) H T ) to Θ ( log ( ε − 1 ) HT ) and reduce the number of ancilla qubits required from Θ ( log ( ε − 1 ) + log H T ) to Θ ( log log ( ε − 1 ) + log H T ) , where ɛ denotes the precision and H T denotes the classical hitting time. In addition, we show that our generalized interpolated quantum walks can improve the construction of quantum stationary states corresponding to reversible Markov chains. Finally, we give an application to construct a slowly evolving Markov chain sequence by applying generalized interpolated quantum walks, which is the necessary premise in adiabatic stationary state preparation.
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.
n this paper, we consider the problem of searching a marked vertex in a graph based on quantum walks. A very large body of research exists on this issue, from both theoretical and experimental studies, yet the existing quantum walk-based search algorithms require knowing exactly how many marked vertices there are before starting the search process. In addition, even if the precise knowledge of the number of marked vertices is known, the success probability of these algorithms could shrink dramatically when the number of search steps is greater than the right one. For avoiding these defects, in this paper we present a new quantum walk-based search algorithm which need not know any prior information about the marked vertices, but still keeps a quadratic speedup over classical ones and ensures that the error is bounded by a tunable parameter ϵ. More specifically, for an N-vertex complete bipartite graph with marked vertices but without knowing the number of marked vertices, if the number of search steps h satisfies h≥ln(ϵ2)N, then the algorithm will output a marked vertex with probability at least $ 1-\epsilon$ for any given ϵ∈(0,1]. This feature leads to quantum search algorithms with stronger robustness and a wider scope of application.