For random k-SAT with prespecified solution, Stirling's asymptotic
expansion in Eq. (8) shows that 
for y=O(n) when m
grows as 
, which is much less that the maximum 
. In this case, the asymptotic behavior of the bound B is
determined by the values near the maximum of the binomial coefficient,
i.e., near y=n/2. Thus if 
, we have 
. From Eq. (29), 
at least when B< 1.
This is the case for 
where
where 
. For instance,
is 1.01 and 17.3 for k=2 and 3, respectively. Thus, the
algorithm presented here is simple enough to allow an analytic bound
on its behavior for highly constrained problems, thus demonstrating
its asymptotic effectiveness in these cases. Other, more complex,
structured quantum algorithms have only been evaluated
empirically [29, 30], which is limited to small problems.
The algorithm's behavior with fewer constraints, i.e., 
,
is not easily evaluted analytically since the bound provided by B
is no longer useful. Instead, the behavior can be examined
empirically using a classical simulation [34], which is
however limited to problems with a relatively small number of
variables. These empirical studies may eventually be extendable to
larger problems using approximate evaluation techniques [9].
An example is given in Fig. 3. This shows good performance for highly constrained problems, as expected from the behavior of the lower bound. Performance is also good with few constraints; not because the algorithm is capturing the problem structure particularly well but rather because there are many solutions to weakly constrained problems. As with other classical and quantum search methods that use problem structure, the hardest cases are for problems with an intermediate number of constraints [32].
Figure 3: Probability to find a solution for random 3-SAT for n=10 (solid) and 20 (dashed) vs. m/n, on a log-log scale. Each point is an average over at least 100 problem instances, and includes error bars for the standard deviation in this estimate of the averge. The error bars are smaller than the size of the plotted points. The gray lines show the corresponding lower bounds 
.
From Fig. 4 we see that the nonzero asymptotic limit for the
probability of a solution appears to continue for somewhat fewer
constraints than expected from the value of . Below this
value, the probability for finding a solution appears to decrease as a
power of n, indicated by linear scaling on the log-log plot of
Fig. 4 for 
. Similar empirical evaluations of the
scaling with an intermediate number of constraints where the hard
problems are concentrated, e.g., m = 4 n for 3-SAT, shows linear
scaling on a log-plot, indicating exponential decrease in the
probability to find a solution. Moreover, the resulting search costs
in these cases are larger than those of other structured quantum
search algorithms [29, 30]. Thus the structure of these
harder cases differs enough from the simple 1-SAT problems that this
algorithm is not effective for them.
Figure 4: Probability to find a solution for random soluble 3-SAT vs. n with, from top to bottom, 
, 
and 
, respectively, on a log-log plot. For each value of n, at least 100 problem instances were used. Error bars showing the expected error in the estimate are included but are smaller than the size of the plotted points.
In summary, the algorithm solves highly constrained problems with
in O(1) steps for , and possibly for
somewhat smaller values of 
as well. As the number of clauses
is further reduced, the required number of steps appears to grow
polynomially when 
and exponentially when m = O(n).