The algorithm presented above is effective for 1-SAT by exploiting the
simple structure of such problems. As described in §3, many
highly constrained *k*-SAT problems have a similar structure. This
observation allows the 1-SAT algorithm to be applied to more general
problems, although with a reduction in performance. Specifically,
applying Eq. (13) requires knowing the number of conflicts the
assignments would have in the corresponding maximally constrained
1-SAT problem whose solution is equal to one of the solutions of the
original *k*-SAT problem. As described in §3.1, for the
most part this can be computed efficiently using the neighborhood
relations for the problem. This suggests simply changing the 1-SAT
algorithm to use .

To see how this approximation changes the performance, consider an
assignment *s* with *y* bad values with respect to a specific solution
*r* and let

The vector used with the *k*-SAT problem is related
to the vector from the corresponding 1-SAT problem by
. Except for this change, the
remaining transformations of the algorithm are the same as in the
1-SAT case. Thus

where is the result of the corresponding 1-SAT problem,
i.e., all amplitude in the solution, and is a diagonal
matrix, with elements given by . It is convenient to define
the average value of over all assignments with *y* bad values:

where the sum is restricted to just the assignments with
*y* bad values.

The change in the amplitude in the solution state is determined by
when *r* is the solution. This change
can be expressed using Eq. (17) by recalling that *h*=0 for the
solution and replacing the phases by the error in the phases,
:

Since all the have unit magnitude, . If the problem has only one solution, the probability the algorithm will find it is . If there are multiple solutions, this is a lower bound on the probability.

The following sections use these observations to extend the range of problems to which the 1-SAT algorithm can be effectively applied.

Feb. 1999