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.

Wed Mar 20 16:29:17 PST 1996