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, from Eq. (13). Then for each assignment r, . Each s in this sum can be characterized by

• x: the number of conflicts s shares with r
• y: the number of conflicts of s that are not conflicts of r

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 , so the sum can be written as

 

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

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

 

Thus, 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.