Theoretically, search algorithms are often evaluated for the worst
possible case. However, in practice, search problems are often found
to be considerably easier than suggested by these worst case
analyses [32]. This observation leads to examining the
typical behavior of search algorithms with respect to a specified
ensemble of problems, i.e., a class of problems and a probability for
each to occur. For instance, the ensemble of random k-SAT is
specified by the number of variables n, the size of the clauses k
and the number of distinct
clauses m.
The quantum algorithm presented in this paper is effective for highly constrained soluble k-SAT problems. When there are many constraints, soluble problems are very rare among randomly generated instances. Thus to study the algorithm's behavior we generate random problems with a prespecified solution. That is, a random assignment is selected to be a solution and used to restrict the selection of clauses for the problem. In the remainder of this section we describe two methods for generating such problems, and how they can be related to corresponding 1-SAT problems.