Quantum Computation and Decision Trees

Details Quantum Computation and Decision Trees Quantum Computation and Decision Trees

1997-06-27

arxiv.org/abs/quant-ph/9706062v2

Physics

Quantum Physics

Revised version to appear in Phys Rev A; technical error corrected, methods and conclusions remain the same; 28 pages, 11 figu

Scientific paper

10.1103/PhysRevA.58.915

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 levels 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.

Affiliated with

Also associated with

No associations

Rating

Quantum Computation and Decision Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Computation and Decision Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Computation and Decision Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-332251