next up previous
Next: Acknowledgments Up: Solving Highly Constrained Search Previous: 7.2 Balanced Clauses

8 Discussion

The algorithm presented in this paper provides an analytic demonstration that quantum machines can significantly exploit the structure of highly constrained k-SAT problems, thereby extending the range of search problems that definitely have effective quantum algorithms. This contrasts with previous work on structured quantum algorithms that could only be evaluated empirically.

In addition, for maximally constrained 2-SAT problems and many maximally constrained balanced k-SAT problems, the algorithm finds a solution with probability one. Thus in these cases, failure to find a solution definitely indicates the problem is not soluble, i.e., the search method is complete. As described in §3.1, with the slight additional cost of evaluating the number of conflicts in the complement of an assignment as well as the assignment itself for maximally constrained k-SAT, the correct corresponding 1-SAT problem can be determined. This additional information thus gives a complete search algorithm for maximally constrained k-SAT. This contrasts with previously proposed quantum algorithms that find solutions with probability less than one and hence cannot guarantee no solutions exist.

One direction for future work is generalizing this algorithm to other types of combinatorial search. For instance, the algorithm is restricted to CSPs with two values per variable, such as SAT. While other CSPs can be recast as satisfiability problems, this mapping may obscure structure inherent in the original formulation. Thus it would be useful to find algorithms that apply directly to more general CSP formulations. One possible approach would be based on search methods that construct solutions incrementally from smaller parts, i.e., expanding the set of states to include assignments that give values to only some of the variables in the problem. Such a representation can apply readily to CSPs with any number of values for the variables [29, 30]. Another approach would examine replacing Walsh transforms with the approximate Fourier transform [37] as has been proposed to extend an unstructured search method to cases where the size of the search space is not a power of two [7]. Beyond CSPs, it would be interesting to investigate optimization problems.

Search problems with an intermediate number of constraints are the most difficult for classical heuristics as well as structure-based quantum searches [29, 30] based on analogies with these classical methods. For k-SAT, these hard cases occur when the number of clauses grows linearly with the number of variables, which is much smaller than the tex2html_wrap_inline2662 used in §7. The intermediate number of clauses creates considerable variance in the detailed structure of the search space from one problem instance to another. Thus one cannot rely on precise a priori knowledge of the structure in designing the algorithm. Nevertheless, the average or typical structure of these harder search problems has been characterized [12, 32, 33, 36, 43, 54] and may be suitable as a basis for developing appropriate search methods. Instead of aiming for a single-step algorithm, the large variation in structure is likely to require a series of smaller changes to the amplitudes, along with repeated tests of the consistency of all assignments, as with previous proposals [27, 30]. However, since a quantum algorithm can explore all search paths simultaneously, it can avoid some of the variability encountered in classical methods: namely, that due to random selection of initial states or random tie-breaking when evaluating heuristics. Thus a quantum algorithm can focus on variation due only to differences in problem instances rather than also to the particular choices made in exploring a single search path. Ultimately, this observation may allow quantum algorithms to more usefully exploit improved understanding of typical problem structure than is feasible for classical methods.

This discussion raises the general issue of optimally using the information that can be readily extracted from CSP search states, as commonly used in classical heuristics. Such information includes the number of conflicts a state has and how it compares with its neighbors. Additional information is available on partial assignments, as used with incremental searches, but at the cost of involving a greatly expanded search space. The approach described in §5 suggests a useful technique is matching quantum algorithms to the average structure of search problem ensembles.

The most significant open question is the extent to which quantum algorithms can solve problems in polynomial time that require exponential time classically. Factoring provides one example [49], if, as commonly believed, it cannot be done in polynomial time classically. By contrast, highly constrained searches can be solved in polynomial time by both classical heuristics and, as shown in this paper, quantum machines. At the other extreme, searches that ignore problem structure are exponential, requiring tex2html_wrap_inline2770 steps classically, and tex2html_wrap_inline2772 steps on quantum computers [7]. These observations can be summarized as:


This comparison suggests some problems, including factoring, have enough structure to allow quantum machines to operate in polynomial time but not enough for classical machines to do so. Identifying the class of such problems is an important research direction for quantum computation. For example, an interesting open question is whether there is a scaling regime for the number of clauses, m, as a function of n where the probability of finding a solution with a quantum machine decreases only polynomially with n while classical searches require an exponential number of steps, even with the best known heuristics. This question is difficult to treat empirically, pointing to the need for further analytic investigation of quantum algorithms and the structure of search problems.

next up previous
Next: Acknowledgments Up: Solving Highly Constrained Search Previous: 7.2 Balanced Clauses

Tad Hogg
Feb. 1999