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 for each of the
assignments *s*, and the final state vector is

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

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

and *d* ranging from 0 to *n*.

Feb. 1999