To see how problem structure affects this search algorithm, we evaluate , the probability to find a solution for problems with different structures, ranging from underconstrained to overconstrained. Low values for this probability indicate relatively harder problems. The expected number of repetitions of the search required to find a solution is then given by . The results are shown in Figs. 4 and 5 for different ways of introducing phases for nogood sets. We see the general easy-hard-easy pattern in both cases. Another common feature of phase transitions is an increased variance around the transition region. The quantum search has this property as well, as shown in Fig. 6.

**Figure 4:** Expected number of trials T to find a solution vs. for random problems with prespecified solution with binary constraints, using random phases for nogoods. The solid curve is for N=10, with 100 samples per point. The gray curve is for N=20 with 10 samples per point (but additional samples were used around the peak). The error bars indicate the standard error in the estimate of T.

**Figure 5:** Expected number of trials T to find a solution vs. for random problems with prespecified solution with binary constraints, using inverted phases for nogoods. The solid curve is for N=10, with 1000 samples per point. The gray curve is for N=20 with 100 samples per point (but additional samples were used around the peak). The error bars indicate the standard error in the estimate of T.

**Figure 6:** Standard deviation in the number of trials to find a solution for N=20 as a function of . The black curve is for random phases assigned to nogoods, and the gray one for inverting phases.

Wed Mar 20 16:29:17 PST 1996