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.