Quantum algorithm for tree size estimation

Qu&Co comments on this publication:

In this paper, Ambainis et al. study quantum algorithms on search trees of unknown structure, in a model where the tree can be discovered by local exploration. They construct a quantum algorithm which, given a search tree of depth at most n, estimates the size of the tree T with an upper-bound of sqrt(nT) steps. They apply their results to improve the time-complexity of a classical backtracking algorithm and to develop a quantum algorithm for evaluating AND-OR formulas in 2-player game type models.