A general view of the combinatorial search problem is that it
consists of *N*
items and a requirement to find a
solution, i.e., a set of items that satisfies specified conditions or
constraints. These conditions in turn can be described as a collection
of *nogoods*, i.e., sets of items whose
combination is inconsistent with the given conditions. In this context
we define a *good* to be a set of items that is
consistent with all the constraints of the problem. We also say a set is
*complete* if it has
*L* items, while smaller sets are
*partial* or *incomplete*. Thus a
solution is a complete good set. In addition, a *partial
solution* is an incomplete good set.

A key property that makes this set representation conceptually useful is that if a set is nogood, so are all of its supersets. These sets, grouped by size and with each set linked to its immediate supersets and subsets, form a lattice structure. This structure for N=4 is shown in Fig. 1. We say that the

sets of size *i* are at level
*i* in the lattice. As described below,
the various paths through the lattice from levels near the bottom up to
solutions, at level *L*, can be used to
create quantum interference as the basis for a search algorithm.

**Figure 1:** Structure of the set lattice for a problem with four items. The subsets of {1,2,3,4} are grouped into levels by size and lines drawn between each set and its immediate supersets and subsets. The bottom of the lattice, level 0, represents the single set of size zero, the four points at level 1 represent the four singleton subsets, etc.

As an example, consider a problem with N=4 and L=2, and suppose the constraints eliminate items 1 and 3. Then we have the sets {}, {2}, and {4} as partial goods, while {1} and {3} are partial nogoods. Among the 6 complete sets, only {2,4} is good as the others are supersets of {1} or {3} and hence nogood.

For the search problems studied here, the nogoods directly specified by the problem constraints will be small sets of items, e.g., of size two or three. On the other hand, the number of items and the size of the solutions will grow with the problem size. This gives a number of small nogoods, i.e., near the bottom of the lattice. Examples of such problems include binary constraint satisfaction, graph coloring and propositional satisfiability mentioned above.

For CSPs, the items are just the possible variable-value pairs in
the problem. Thus a CSP with *n*
variables and *b* values for each has
N=nb items. A solution consists of an
assignment to each variable that satisfies whatever constraints are
given in the problem. Thus a solution consists of a set of
L=n items. In terms of the general framework for
combinatorial search these constraint satisfaction problems will also
contain a number of problem-independent *necessary*
nogoods, namely those corresponding to giving the same variable two
different values. There are such necessary nogoods. For a nontrivial search we
must have , so we restrict our attention to the case where
. This requirement is important in allowing the
construction of the quantum search method described below.

Another example is given by a simple CSP consisting of n=2 variables ( and ) each of which can take on one of b=2 values (1 or 2) and the single constraint that the two variables take on distinct values, i.e., . Hence there are N=nb=4 variable-value pairs which we denote as items 1,2,3,4 respectively. The corresponding lattice is given in Fig. 1. What are the nogoods for this problem? First there are those due to the explicit constraint that the two variables have distinct values: and or {1,3} and {2,4}. In addition, there are necessary nogoods implied by the requirement that a variable takes on a unique value so that any set giving multiple assignments to the same variable is necessarily nogood, namely and or {1,2} and {3,4}. Referring to Fig. 1, we see that these four nogoods force all sets of size 3 and 4 to be nogood too. However, sets of size zero and one are goods as are the remaining two sets of size two: {2,3} and {1,4} corresponding to and which are the solutions to this problem.

Search methods use various strategies for examining the sets in
this lattice. For instance, methods such as simulated annealing [32], heuristic repair [39] and GSAT [46] move among complete sets, attempting to
find a solution by a series of small changes to the sets. Generally
these search techniques continue indefinitely if the problem has no
solution and thus they can never show that a problem is insoluble. Such
methods are called *incomplete*. In these methods,
the search is repeated, from different initial conditions or making
different random choices, until either a solution is found or some
specified limit on the number of trials is reached. In the latter case,
one cannot distinguish a problem with no solution at all from just a
series of unlucky choices for a soluble problem. Other search techniques
attempt to build solutions starting from smaller sets, often by a
process of extending a consistent set until either a solution is found
or no further consistent extensions are possible. In the latter case the
search backtracks to a previous decision point and tries another
possible extension until no further choices remain. By recording the
pending choices at each decision point, these backtrack methods can
determine a problem is insoluble, i.e., they are
*complete* or *systematic* search
methods.

This description highlights two distinct aspects of the search procedure: a general method for moving among sets, independent of any particular problem, and a testing procedure that checks sets for consistency with the particular problem's requirements. Often, heuristics are used to make the search decisions depend on the problem structure hoping to identify changes most likely to lead to a solution and avoid unproductive regions of the search space. However, conceptually these aspects can be separated, as in the case of the quantum search algorithm presented below.

Wed Mar 20 16:29:17 PST 1996