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.

Feb. 1999