Quantum computation and decision trees

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.

• Physical Review A
  View
• arXiv (Cornell University)
  View PDF
• DataCite API
  View