next up previous
Next: 4.3 Examples Up: 4 Solving 1-SAT Previous: 4.1 Motivation

4.2 The Algorithm for Maximally Constrained 1-SAT 

Briefly, the algorithm starts with an equal superposition of all the assignments, adjusts the phases of the amplitudes based on the number of conflicts in the assignments, and then mixes the amplitudes from different assignments. This algorithm requires only a single testing of the assignments, corresponding to a single classical search step.

Specifically, the initial state is tex2html_wrap_inline1954 for each of the tex2html_wrap_inline1628 assignments s, and the final state vector is

  equation280

where the matrices R and U are defined as follows. The matrix R is diagonal with tex2html_wrap_inline2110 depending on the number of conflicts c in the assignment s, ranging from 0 to n:

  equation284

The mixing matrix elements tex2html_wrap_inline2118 depend only on the Hamming distance between the assignments r and s, with

  equation289

and d ranging from 0 to n.



Tad Hogg
Feb. 1999