A quantum computer, operating on superpositions of all assignments for
*any* 1-SAT problem, can find a solution in a single search
step [31]. As a basis for solving highly constrained problems
with larger clause sizes, we focus on maximally constrained 1-SAT
which, from Eq. (5), has *m*=*n* clauses and allows a simple
specification. Specifically, we first motivate and define the
algorithm for this case and illustrate it with small examples. Then we
show that it is guaranteed to find a solution if one exists, and
finally describe how the algorithm can be efficiently implemented on a
quantum computer. The remainder of the paper then shows how this
algorithm can form the basis for effectively solving highly
constrained *k*-SAT for *k*>1.

- 4.1 Motivation
- 4.2 The Algorithm for Maximally Constrained 1-SAT
- 4.3 Examples
- 4.4 Performance of the Algorithm
- 4.5 Implementation

Feb. 1999