next up previous
Next: Average Behavior of Up: Quantum Search Methods Previous: Summary

An Example of Quantum Search

To illustrate the algorithm's operation and behavior, consider the small case of tex2html_wrap2694 with the map starting from level tex2html_wrap2933 and going up to level tex2html_wrap2327 . Suppose that tex2html_wrap_inline2380 3 tex2html_wrap_inline2382 and its supersets are the only nogoods. We begin with all amplitude in the empty set, i.e., with the state tex2html_wrap2935 . The map from level 0 to 1 gives equal amplitude to all singleton sets, producing tex2html_wrap2936 . We then introduce a phase for the nogood set, giving tex2html_wrap2937 . Finally we use Eq. 16 to map this to the sets at level 2, giving the final state


At this level, only set tex2html_wrap_inline2380 1,2 tex2html_wrap_inline2382 is good, i.e., a solution. Note that the algorithm does not make any use of testing the states at the solution level for consistency.

The probability to obtain a solution when the final measurement is made is determined by the amplitude of the solution set, so in this case Eq. 22 becomes


From this we can see the effect of different methods for selecting the phase for nogoods. If the phase is selected randomly, tex2html_wrap2938 because the average value of tex2html_wrap2939 is zero. Inverting the phase of the nogood, i.e., using tex2html_wrap2940 , gives tex2html_wrap2941 . These probabilities compare with the 1/3 chance of selecting a solution by random choice. In this case, the optimal choice of phase is the same as that obtained by simple inversion. However this is not true in general: picking phases optimally will require knowledge about the solutions and hence is not a feasible mapping. Note also that even the optimal choice of phase doesn't guarantee a solution is found.

Tad Hogg
Wed Mar 20 16:29:17 PST 1996