next up previous
Next: 4.1 Motivation Up: Solving Highly Constrained Search Previous: 3.2.2 Balanced Clauses

4 Solving 1-SAT 

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.

Tad Hogg
Feb. 1999