While search algorithm performances are often compared based on the
number of search *steps* required, i.e., the number of sequentially
examined assignments, it is also important to compare the number of
more elementary computational operations required. At the most fundamental
level, these operations are logic operators on one or two bits at a time
(e.g., the logical not or exclusive-or operations). As described above,
the matrix operations and forming the initial state can be done with
a series of *O*(*n*) bit operations [7].

The time required to count the number of conflicts in an assignment
depends on data structures used to represent the problem. A single
evaluation will be comparable for both the quantum and classical
algorithms. For a SAT problem with *m* clauses, examining each clause
to see if it conflicts with a given assignment uses *O*(*m*) tests. Each
of these tests will, in turn, require comparing at least part of the
clause to the assignment. Because the clauses in *k*-SAT are of fixed
size, this gives an overall cost of *O*(*m*) to evaluate the number of
conflicts.

For local classical search, the number of conflicts in neighboring
assignments will also be evaluated to determine which assignment
should be examined at the next step of the search. Since neighbors
differ by the value of only one variable, in fact it is only necessary
to examine clauses that involve that variable to determine the
difference in the number of conflicts between an assignment and one of
its neighbors. This evaluation will thus require only *O*(*m*/*n*) tests.
Examining each, or a least a good portion, of the *n* neighbors
results in a total of *O*(*m*) tests to find the next assignment.
Selecting an initial assignment requires a value for each variable,
a cost of *O*(*n*).

Thus we can expect both algorithms to involve costs of *O*(*n*+*m*) to
evaluate a single search step. That is, the cost for a *single*
search step is about the same for the quantum algorithm and classical
searches when neighbors are examined. However, the quantum algorithm
is able to examine the characteristics of all assignments in
superposition while a classical search examines just one state,
allowing the quantum algorithm to complete in just one step while the
best classical methods for *k*-SAT require *O*(*n*) steps. For the
highly constrained *k*-SAT problems with *k*;*SPMgt*;1, discussed below, so the dominant cost will be in the evaluation of the number of
conflicts.

This discussion indicates how a comparison of search steps gives a reasonable comparison in terms of elementary operations as well. However, a full comparison will also depend on details of actual implementations, such as any additional operations required for controlling errors that cannot themselves be performed in parallel with the higher level steps of the algorithm. These remain significant issues in the development of quantum computation [39, 52, 28, 44], but at this point seem unlikely to be fundamental difficulties [5, 48, 38]. In particular, because the algorithm requires only a single step, decoherence is likely to be less of a difficulty for it than search algorithms that require multiple repeated steps to move significant amplitude to solutions [27, 30].

Finally, search algorithms can be compared based on elapsed execution time. Current hardware implementations [1, 6, 13, 14, 15, 25, 50] are quite limited in size, so such a comparison will need to await the construction of quantum machines with a sufficient number of bits to perform interesting searches.

Feb. 1999