We study quantum algorithms on search trees of unknown structure, in a model where the tree can be discovered by local exploration. That is, we are given the root of the tree and access to a black box which, given a vertex v, outputs the children of v.
We give a quantum algorithm for stochastic 2-player games. Their game trees are the expectiminimax trees of classical game search: m adversarial layers alternate with m chance layers, every node has deg children, and the leaf values lie in an interval of length N. The algorithm estimates the value of the game to root mean square error ε with O(KDdeg4DεND4Dlog(εdegN)4D),D=2m queries to the leaf values, where K is an absolute constant. If we treat the depth D as a constant as is sometimes done in the literature, the bound is O(degm/2ε−1) against the classical O(degmε−2). So the quadratic speedup in the branching factor known for adversarial trees and the quadratic speedup in the accuracy known for a single expectation both survive when we nest one inside the other.
We use a derandomised multilevel Monte Carlo estimator for chance layers and a coherent binary search for adversarial layers. The composition is done by introducing a conversion between root-mean-square and uniform error guarantees, and a composition to nest it with quantum mean estimation. We state the algorithm for stochastic games, but it is valid for the following conditions: the value of a parent is a Lipschitz function of the values of its children and the value at a chance vertex is linear in its children, however the speedup is preserved only if the deterministic step has a quantum subroutine with sublinear query 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 tv steps from its parent, then we show that detection of a marked vertex requires O(TD) queries to the steps of the computing procedures, where T=∑vtv2. 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.
A quantum algorithm is known that solves an unstructured search problem in a number of iterations of order d, where d is the dimension of the search space, whereas any classical algorithm necessarily scales as O(d). It is shown here that an improved quantum search algorithm can be devised that exploits the structure of a tree search problem by nesting one quantum search within another. The average number of iterations required to find the solution of a typical hard instance of a constraint satisfaction problem is found to scale as $\sqrt{{d}^{\ensuremath{\alpha}}},$ with the constant $\ensuremath{\alpha}<1$ depending on the nesting depth and the type of problem considered. This corresponds to a square-root speedup over a classical nested search algorithm, of which our algorithm is the quantum counterpart. When applying a single nesting level to a problem with constraints of size 2 such as the graph coloring problem, $\ensuremath{\alpha}$ is estimated to be around 0.62.
$ $ 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.
In this work, we investigate quantum tree search via amplitude amplification. Amplitude amplification generalizes Grover's algorithm by replacing the Hadamard initialization with an arbitrary unitary A, with Grover's algorithm recovered as the special case of uniform initialization. We demonstrate the construction of a dynamic search tree of depth m with query complexity (bavg)m where bavg denotes the average branching factor, improving upon the commonly assumed (bmax)m, where bmax is the maximum branching factor. We further challenge the widespread assumption that amplitude amplification is inferior to quantum backtracking. In fact, quantum backtracking is unsuitable for problems that do not naturally admit a backtracking structure; in such cases, amplitude amplification yields improved query complexity. We observe that amplitude amplification constructs the search tree dynamically, rendering its internal structure inaccessible, a constraint that applies equally to quantum backtracking. To address this, we propose sampling-based methods to estimate the tree structure, under the assumption that it approximates a normal distribution with increasing depth. Finally, we introduce a quantum greedy search based on a lookahead heuristic inspired by the classical cognitive architecture Soar, which models human-like problem-solving strategies.
One of the challenges of quantum computers in the near- and mid- term is the limited number of qubits we can use for computations. Finding methods that achieve useful quantum improvements under size limitations is thus a key question in the field. In this vein, it was recently shown that a hybrid classical-quantum method can help provide polynomial speed-ups to classical divide-and-conquer algorithms, even when only given access to a quantum computer much smaller than the problem itself. In this work, we study the hybrid divide-and-conquer method in the context of tree search algorithms, and extend it by including quantum backtracking, which allows better results than previous Grover-based methods. Further, we provide general criteria for polynomial speed-ups in the tree search context, and provide a number of examples where polynomial speed ups, using arbitrarily smaller quantum computers, can be obtained. We provide conditions for speedups for the well known algorithm of DPLL, and we prove threshold-free speed-ups for the PPSZ algorithm (the core of the fastest exact Boolean satisfiability solver) for well-behaved classes of formulas. We also provide a simple example where speed-ups can be obtained in an algorithm-independent fashion, under certain well-studied complexity-theoretical assumptions. Finally, we briefly discuss the fundamental limitations of hybrid methods in providing speed-ups for larger problems.