We show a simple generalization of the quantum walk algorithm for search in backtracking trees by Montanaro (ToC 2018) to the case where vertices can have different times of computation. If a vertex \(v\) in the tree of depth \(D\) is computed in \(t_v\) steps from its parent, then we show that detection of a marked vertex requires \(\text O(\sqrt {TD})\) queries to the steps of the computing procedures, where \(T = \sum_v t^2_v\). This framework provides an easy and convenient way to re-obtain a number of other quantum frameworks like variable time search, quantum divide & conquer and bomb query algorithms. The underlying algorithm is simple, explicitly constructed, and has low poly-logarithmic factors in the complexity.
We show a simple generalization of the quantum walk algorithm for search in backtracking trees by Montanaro (ToC 2018) to the case where vertices can have different times of computation. If a vertex (v) in the tree of depth (D) is computed in (t_v) steps from its parent, then we show that detection of a marked vertex requires (\text O(\sqrt {TD})) queries to the steps of the computing procedures, where (T = \sum_v t^2_v). This framework provides an easy and convenient way to re-obtain a number of other quantum frameworks like variable time search, quantum divide & conquer and bomb query algorithms. The underlying algorithm is simple, explicitly constructed, and has low poly-logarithmic factors in the complexity.
$ $ We describe a general method to obtain quantum speedups of classical algorithms which are based on the technique of backtracking, a standard approach for solving constraint satisfaction problems (CSPs). Backtracking algorithms explore a tree whose vertices are partial solutions to a CSP in an attempt to find a complete solution. Assume there is a classical backtracking algorithm which finds a solution to a CSP on n variables, or outputs that none exists, and whose corresponding tree contains T vertices, each vertex corresponding to a test of a partial solution. Then we show that there is a bounded-error quantum algorithm which completes the same task using O(Tn3/2logn) tests. In particular, this quantum algorithm can be used to speed up the DPLL algorithm, which is the basis of many of the most efficient SAT solvers used in practice. The quantum algorithm is based on the use of a quantum walk algorithm of Belovs to search in the backtracking tree.
We investigate quantum backtracking algorithms of the type introduced by Montanaro (Montanaro, arXiv:1509.02374). These algorithms explore trees of unknown structure and in certain settings exponentially outperform their classical counterparts. Some of the previous work focused on obtaining a quantum advantage for trees in which a unique marked vertex is promised to exist. We remove this restriction by recharacterizing the problem in terms of the effective resistance of the search space. In this paper, we present a generalization of one of Montanaro's algorithms to trees containing k marked vertices, where k is not necessarily known a priori. Our approach involves using amplitude estimation to determine a near-optimal weighting of a diffusion operator, which can then be applied to prepare a superposition state with support only on marked vertices and ancestors thereof. By repeatedly sampling this state and updating the input vertex, a marked vertex is reached in a logarithmic number of steps. The algorithm thereby achieves the conjectured bound of $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{\mathcal{O}}(\sqrt{T{R}_{\mathrm{max}}})$ for finding a single marked vertex and $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{\mathcal{O}}(k\sqrt{T{R}_{\mathrm{max}}})$ for finding all k marked vertices, where T is an upper bound on the tree size and Rmax is the maximum effective resistance encountered by the algorithm. This constitutes a speedup over Montanaro's original procedure in both the case of finding one and the case of finding multiple marked vertices in an arbitrary tree.
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.
We describe a general method to obtain quantum speedups of classical algorithms which are based on the technique of backtracking, a standard approach for solving constraint satisfaction problems (CSPs). Backtracking algorithms explore a tree whose vertices are partial solutions to a CSP in an attempt to find a complete solution. Assume there is a classical backtracking algorithm which finds a solution to a CSP on n variables, or outputs that none exists, and whose corresponding tree contains T vertices, each vertex corresponding to a test of a partial solution. Then we show that there is a bounded-error quantum algorithm which completes the same task using O(sqrt(T) n^(3/2) log n) tests. In particular, this quantum algorithm can be used to speed up the DPLL algorithm, which is the basis of many of the most efficient SAT solvers used in practice. The quantum algorithm is based on the use of a quantum walk algorithm of Belovs to search in the backtracking tree. We also discuss how, for certain distributions on the inputs, the algorithm can lead to an exponential reduction in expected runtime.
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.
There has been a very large body of research on searching a marked vertex on a graph based on quantum walks, and Grover's algorithm can be regarded as a quantum walk-based search algorithm on a special graph. However, the existing quantum walk-based search algorithms suffer severely from the souffl\'e problem, which mainly means that the success probability of finding a marked vertex could shrink dramatically, even to zero, when the number of search steps is greater than the right one, thus heavily reducing the robustness and practicability of the algorithm. Surprisingly, while the souffl\'e problem of Grover's algorithm has attracted enough attention, how to address this problem for general quantum walk-based search algorithms is missing in the literature. Here we initiate the study of overcoming the souffl\'e problem for quantum walk-based search algorithms by presenting a quantum walk-based search framework that achieves robustness without sacrificing the quantum speedup. In this framework, for any adjustable parameter $\ensuremath{\epsilon}$, the quantum algorithm can find a marked vertex on an N-vertex complete bipartite graph with probability at least $1\ensuremath{-}\ensuremath{\epsilon}$, whenever the number of search steps h satisfies $h\ensuremath{\ge}ln(\frac{2}{\sqrt{\ensuremath{\epsilon}}})\sqrt{N}+1$. Note that the algorithm need not know the exact number of marked vertices. Consequently, we obtain quantum search algorithms with stronger robustness and practicability.