Next: 7.2 Balanced Clauses Up: 7 Solving Highly Constrained Previous: 7 Solving Highly Constrained

## 7.1 Random k-SAT

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).

Next: 7.2 Balanced Clauses Up: 7 Solving Highly Constrained Previous: 7 Solving Highly Constrained