The scaling of the probability to find a solution is shown in Fig. 12 using the phase inversion method. More limited experiments with the random phase method showed the same behavior as seen with the unstructured class of problems: somewhat worse performance but similar scaling behavior. The results here are less clear-cut than those of Fig. 8. For c/n=2 the results are consistent with either polynomial or exponential scaling. For problems with more constraints, exponential scaling is a somewhat better fit.
Figure 12: Scaling of the probability to find a solution, using the phase inversion method, as a function of the number of variables for random 3SAT problems. The curves correspond to different clause to variable ratios: 2 (dashed), 4 (solid), 6 (gray) and 8 (gray, dashed). This is shown on log and log-log scales (left and right plots, respectively).
Figure 13: Probability in goods (i.e., consistent sets) as a function of level in the lattice for 3SAT problems with no constraints. This shows the behavior for n equal to 9 (gray dashed), 10 (black dashed), 11 (gray) and 12 (black). For each problem, the final probability at level n is the probability a solution is obtained with the quantum algorithm.
In addition to the general scaling trend, there is also a
noticeable difference in behavior between cases with an even and odd
number of variables. This is due to the behavior of the amplitude at
each step in the lattice. Instead of a monotonic decrease in the
concentration of amplitude into goods, there is an oscillatory behavior
in which amplitude alternates between dispersing and being focused into
goods at different levels. An extreme example of this behavior is shown
in Fig. 13 for 3SAT problems with
no constraints, i.e., c=0. Specifically, at level
i this shows 
where the sum is over all sets
s at level
i in the lattice that are consistent,
which, for these problems with no constraints, are all assignments to
i variables. This is the probability
that a good would be found if the algorithm were terminated at level
i and gives an indication of how well
the algorithm concentrates amplitude among consistent states. In this
case, the expanded search space of the quantum algorithm results in
slightly worse performance than random selection from among complete
assignments (all of which are solutions in this case). Each search
starts with all amplitude in goods at level 3. Then the total
probability in goods alternately decreases and increases as the map
proceeds up to the solution level. Cases with an even number of
variables (the black curves in the figure) end on a step that decreases
the probability in goods, resulting in relatively lower performance
compared to the odd variable cases (gray curves). Although this might
suggest an improvement for the even n
cases by starting in level 2 rather than level 3, in fact this turns out
not to be the case: starting in level 2 gives essentially the same
behavior for the upper levels as starting the search from level 3 of the
lattice due to one oscillation at intermediate levels that takes 2 steps
to complete. Increasing the value of c/n , i.e., examining SAT problems with constraints,
reduces the extent of the oscillations, particularly in higher levels of
the lattice, and eventually results in monotonic decrease in probability
as the search moves up the lattice. Nevertheless, for problems with a
few constraints the existence of these oscillations gives rise to the
observed difference in behavior between cases with an even and odd
number of variables. These oscillations are also seen for
underconstrained cases of unstructured problems in
Figs. 7 and 8.
While Fig. 13 shows that the oscillatory behavior decreases for larger problems, it also suggests there may be more appropriate choices of the phases. Specifically, it may be possible to obtain a greater concentration of amplitude into solutions by allowing more dispersion into nogoods at intermediate levels of the lattice or using an initial condition with some amplitude in nogoods. If so, this would represent a new policy for selecting the phases that takes into account the problem-independent structure of the necessary nogoods. This would be somewhat analogous to focusing light with a lens: paths in many directions are modified by the lens to cause a convergence to a single point.
Figure 14: 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 as a function of the number of variables for random 3SAT problems with clause to variable ratio equal to 4. The solid and dashed curves correspond to using the phase inversion and random phase methods, respectively. The black curves compare to random selection among complete sets, while the gray compare to selection only from among complete assignments. The curves are close to linear on this log scale indicating exponential improvement over the direct selection from among complete sets.
More definite results are obtained for the improvement over random selection. Specifically, Fig. 14 shows an exponential improvement for both the phase inversion and random phase methods, corresponding to the behavior for unstructured problems in Fig. 9. Similar improvement is seen for other values of c/n as well: as in Fig. 9 the more highly constrained problems give larger improvements. A more stringent comparison is with random selection from among complete assignments (i.e., each variable given a single value) rather than from among all complete sets of variable-value pairs. This is also shown in Fig. 14, appearing to grow exponentially as well. This is particularly significant because the quantum algorithm uses a larger search space containing the necessary nogoods. Another view of this comparison is given in Fig. 15, showing the probabilities to find a solution with the quantum search and random selection from among complete assignments. We conclude from these results that the additional structure of necessary nogoods and constraints of different sizes is qualitatively similar to that for unstructured random problems but a detailed comparison of the scaling behaviors requires examining larger problem sizes.
Figure 15: Comparison of scaling of probability to find a solution with the quantum algorithm using the phase inversion method (solid curve) and by random selection from among complete assignments (gray curve) for c/n=4.