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

At this level, only set 1,2 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, because the average value of is zero. Inverting the phase of the nogood, i.e., using , gives . 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.

Wed Mar 20 16:29:17 PST 1996