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

arXiv: https://arxiv.org/abs/1704.06774 · HTML: https://mlsanity.com/paper/1704.06774/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Apr 2017.

## Built on by (most cited first, 1 of 1)

- [Physics-Informed Neural Networks for an optimal counterdiabatic quantum computation](https://mlsanity.com/paper/2309.04434/) (2023)

## Abstract (arXiv)

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± δ in tildeO(√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 tildeO(√Tn3/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 To(1) can be evaluated in quantum time O(T1/2+o(1)). Thus, the quantum speedup is essentially the same as in the case when the formula is known in advance.