Quantum computation and decision trees

Abstract

Many interesting computational problems can be reformulated in terms of decision trees. A natural classical algorithm is to then run a random walk on the tree, starting at the root, to see if the tree contains a node $n$ level from the root. We devise a quantum-mechanical algorithm that evolves a state, initially localized at the root, through the tree. We prove that if the classical strategy succeeds in reaching level $n$ in time polynomial in $n,$ then so does the quantum algorithm. Moreover, we find examples of trees for which the classical algorithm requires time exponential in $n,$ but for which the quantum algorithm succeeds in polynomial time. The examples we have so far, however, could also be solved in polynomial time by different classical algorithms.