Back

Quantum algorithm for tree size estimation

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

Published by Andris Ambainis, Martins Kokainis (University of Latvia), 22nd April 2017

arXiv:1704.06774
Quantum search
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.