Next: Phase Transition Up: Average Behavior of Previous: Scaling

## Random 3SAT

These experiments leave open the question of how additional problem structure might affect the scaling behaviors. While the universality of the phase transition behavior in other search methods suggests that the average behavior of this algorithm will also be the same for a wide range of problems, it is useful to check this empirically. To this end the algorithm was applied to the satisfiability (SAT) problem. This constraint satisfaction problem consists of a propositional formula with n variables and the requirement to find an assignment (true or false) to each variable that makes the formula true. Thus there are b=2 assignments for each variable and N=2n possible variable-value pairs. We consider the well-studied NP-complete 3SAT problem where the formula is a conjunction of c clauses, each of which is a disjunction of 3 (possibly negated) variables.

The SAT problem is readily represented by nogoods in the lattice of sets [53]. As described in Sec. 2.2, there will be n necessary nogoods, each of size 2. In addition, each distinct clause in the proposition gives a single nogood of size 3. This case is thus of additional interest in having specified nogoods of two sizes. For evaluating the quantum algorithm, we start at level 3 in the lattice. Thus the smallest case for which the phase choices will influence the result is for n=5.

We generate random problems with a given number of clauses by selecting that number of different nogoods of size 3 from among those sets not already excluded by the necessary nogoods. For random 3SAT, the hard problems are concentrated near the transition [40] at c=4.2n. Finally, from among these randomly generated problems, we use only those that do in fact have a solution. Using randomly selected soluble problems results in somewhat harder problems than using a prespecified solution. Like other studies that need to examine many goods and nogoods in the lattice [45], these results are restricted to much smaller problems than in most studies of random SAT. Consequently, the transition region is rather spread out. Furthermore, the additional structure of the necessary nogoods and the larger size of the constraints, compared with the previous class of problems, makes it more likely that larger problems will be required to see the asymptotic scaling behavior. However, at least some asymptotic behaviors have been observed [10] to persist quite accurately even for problems as small as n=3, so some indication of the scaling behavior is not out of the question for the small problems considered here.

Next: Phase Transition Up: Average Behavior of Previous: Scaling