Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games

Abstract

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 construct a quantum algorithm which, given such access to a search tree of depth at most $n$, estimates the size of the tree $T$ within a factor of $1\pm \delta$ in $\tilde{O}(\sqrt{nT})$ steps. More generally, the same algorithm can be used to estimate size of directed acyclic graphs (DAGs) in a similar model. We then show two applications of this result: a) We show how to transform a classical backtracking search algorithm which examines $T$ nodes of a search tree into an $\tilde{O}(\sqrt{T}{n}^{3/2})$ time quantum algorithm, improving over an earlier quantum backtracking algorithm of Montanaro (arXiv:1509.02374). b) We give a quantum algorithm for evaluating AND-OR formulas in a model where the formula can be discovered by local exploration (modeling position trees in 2-player games). We show that, in this setting, formulas of size $T$ and depth $T^{o(1)}$ can be evaluated in quantum time $O(T^{1/2+o(1)})$. Thus, the quantum speedup is essentially the same as in the case when the formula is known in advance.

Parameters for Algorithm 1 and the proof of Lemma 16 corrected. We thank Mark Goh for pointing out that Lemma 16 in the previous version was incorrect

References in corpus (1)

• Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games

Cited by in corpus (14)

• Quantum computing for finance
• Challenges and Opportunities in Quantum Optimization
• Applying quantum algorithms to constraint satisfaction problems
• Quantum speedup of the Travelling Salesman Problem for bounded-degree graphs
• Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
• A "thoughtful" Local Friendliness no-go theorem: a prospective experiment with new assumptions to suit
• Quantum-accelerated constraint programming
• Diabatic Quantum Annealing for the Frustrated Ring Model
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
• Improved quantum backtracking algorithms using effective resistance estimates
• Hybrid divide-and-conquer approach for tree search algorithms
• Practical implementation of a quantum backtracking algorithm
• Quantum Search with Prior Knowledge
• Relating counting complexity to non-uniform probability measures