An important question in the behavior of this search method is how its average performance scales with problem size. To examine this question, we consider the scaling with fixed . This is shown in Figs. 7 and 8 for algorithms using random and inverted phases for nogoods, respectively. To help identify the likely scaling, we show the same results on both a log plot (where straight lines correspond to exponential scaling) and a log-log plot (where straight lines correspond to power-law or polynomial scaling).

It is difficult to make definite conclusions from these results for two reasons. First, the variation in behavior of different problems gives a statistical uncertainty to the estimates of the average values, particularly for the larger sizes where fewer samples are available. The standard errors in the estimates of the averages are indicated by the error bars in the figures (though in most cases, the errors are smaller than the size of the plotted points). Second, the scaling behavior could change as larger cases are considered. With these caveats in mind, the figures suggest that remains nearly constant for underconstrained problems, even though the fraction of complete sets that are solutions is decreasing exponentially. This behavior is also seen in the overlap of the curves for small in Figs. 4 and 5. For problems with more constraints, appears to decrease polynomially with the size of the problem, i.e., the curves are closer to linear in the log-log plots than in the log plots. This in confirmed quantitatively by making a least squares fit to the values and seeing that the residuals of the fit to a power-law are smaller than those for an exponential fit. An interesting observation in comparing the two phase choices is that the scaling is qualitatively similar, even though the phase inversion method performs better. This suggests the detailed values of the phase choices are not critical to the scaling behavior, and in particular high precision evaluation of the phases is not required. Finally we should note that this illustration of the average scaling leaves open the behavior for the worst case instances.

**Figure 7:** Scaling of the probability to find a solution using the random phase method, for of 1 (solid), 2 (dashed), 3 (gray) and 4 (dashed gray). This is shown on log and log-log scales (left and right plots, respectively).

**Figure 8:** Scaling of the probability to find a solution using the phase inversion method, for of 1 (solid), 2 (dashed), 3 (gray) and 4 (dashed gray). This is shown on log and log-log scales (left and right plots, respectively).

For the underconstrained cases in Figs. 7 and 8 there is a small additional difference between cases with an even and odd number of variables. This is due to oscillations in the amplitude in goods at each level of the lattice, and is discussed more fully in the context of SAT problems below.

Another scaling comparison is to see how much this algorithm enhances the probability to find a solution beyond the simple quantum algorithm of evaluating all the complete sets and then making a measurement. As shown in Fig. 9, this quantum algorithm appears to give an exponential improvement in the concentration of amplitude into solutions. A more explicit view of this difference in behavior is shown in Fig. 10 for . In this figure, the dashed curve shows the behavior of for the phase inversion method, and is identical to the curve of Fig. 8.

**Figure 9:** Scaling of the ratio of the probability to find a solution using the quantum algorithm to the probability to find a solution by random selection at the solution level, using the phase inversion method, for of 1 (solid), 2 (dashed), 3 (gray) and 4 (dashed gray). The curves are close to linear on this log scale indicating exponential improvement over the direct selection from among complete sets, with a higher enhancement for problems with more constraints.

**Figure 10:** Comparison of scaling of probability to find a solution with the quantum algorithm using the phase inversion method (dashed curve) and by random selection at the solution level (solid curve) for equals 2.

Wed Mar 20 16:29:17 PST 1996