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 
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 
steps classically, and 
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.