next up previous
Next: 4.5 Implementation Up: 4 Solving 1-SAT Previous: 4.3 Examples

4.4 Performance of the Algorithm 

Consider a maximally constrained soluble 1-SAT problem with n variables. As described in §3, in such a problem each clause involves a separate variable and there is exactly one solution. To show that the algorithm works for all n, we evaluate Eq. (12).

For each assignment s, tex2html_wrap_inline2228 from Eq. (13). Then for each assignment r, tex2html_wrap_inline2232 . Each s in this sum can be characterized by

Let h be the number of conflicts in the assignment r, i.e., the number of the n variables to which r assigns an incorrect value. In terms of these quantities, s has x+y conflicts and is at Hamming distance d(r,s) = (h-x)+y from r. The number of such assignments is tex2html_wrap_inline2264 , so the sum can be written as


Substituting the values from Eq. (13) and (14), gives


This gives tex2html_wrap_inline2266 where tex2html_wrap_inline2268 if x=y and 0 otherwise by use of the identity


Thus, tex2html_wrap_inline2272 has all its amplitude in the state with no conflicts, i.e., the unique solution. A measurement made on this final state is guaranteed to produce a solution.

Tad Hogg
Feb. 1999