Improved quantum backtracking algorithms using effective resistance estimates
Michael Jarret, Kianna Wan · Physical Review A · 2018
We investigate quantum backtracking algorithms of the type introduced by Montanaro (Montanaro, arXiv:1509.02374). These algorithms explore trees of unknown structure and in certain settings exponentially outperform their classical counterparts. Some of the previous work focused on obtaining a quantum advantage for trees in which a unique marked vertex is promised to exist. We remove this restriction by recharacterizing the problem in terms of the effective resistance of the search space. In this paper, we present a generalization of one of Montanaro's algorithms to trees containing $k$ marked vertices, where $k$ is not necessarily known a priori. Our approach involves using amplitude estimation to determine a near-optimal weighting of a diffusion operator, which can then be applied to prepare a superposition state with support only on marked vertices and ancestors thereof. By repeatedly sampling this state and updating the input vertex, a marked vertex is reached in a logarithmic number of steps. The algorithm thereby achieves the conjectured bound of $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{\mathcal{O}}(\sqrt{T{R}_{\mathrm{max}}})$ for finding a single marked vertex and $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{\mathcal{O}}(k\sqrt{T{R}_{\mathrm{max}}})$ for finding all $k$ marked vertices, where $T$ is an upper bound on the tree size and ${R}_{\mathrm{max}}$ is the maximum effective resistance encountered by the algorithm. This constitutes a speedup over Montanaro's original procedure in both the case of finding one and the case of finding multiple marked vertices in an arbitrary tree.