The discussion of §3.2 shows how a maximum likelihood
estimate for 
can be computed for each assignment.
This value can then be used to extend the algorithm to arbitrary
k-SAT problems. To the extent that the errors introduced by this
approximation are small, the quantum algorithm will have a substantial
probability to find a solution in a single step.
When averaged over the problem ensemble, the error given by Eq. (27) becomes
where 
is the probability an assignment with y bad values is
(incorrectly) determined to have a different number of bad values. In
terms of the conditional probabilities of §3.2,
where 
when the maximum likelihood estimate for a
state with c conflicts is y (i.e., 
, and 0
otherwise.
For simplicity, these maximum likelihood estimates are determined
solely from the number of conflicts in each state. The
values could be made a bit more accurate by including neighborhood
information, as was used for maximally constrained random problems in
§6.
Because highly constrained random SAT problems are relatively easy,
they have not been well-studied with classical algorithms. Hence, to
provide comparison with the quantum search results presented below,
these problems were also solved with the classical GSAT
procedure [47], limiting each trial to use no more than
2n steps before a new random initial state was selected. For both
random and balanced ensembles, the median number of search steps
required to find a solution grows linearly over the range of sizes
considered here when 
. In particular, while the balanced
ensemble has larger search costs, it still grows linearly when there
is such a large number of clauses.