next up previous
Next: 5 Applying the Algorithm Up: 4.5 Implementation Previous: 4.5.3 The Mixing Matrix

4.5.4 Required Search Time

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, tex2html_wrap_inline2498 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.


next up previous
Next: 5 Applying the Algorithm Up: 4.5 Implementation Previous: 4.5.3 The Mixing Matrix

Tad Hogg
Feb. 1999