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.