To implement *U* specified by Eq. (14) we use two simpler matrices, *W*
and defined as follows. For assignments *r* and *s*,

is the Walsh transform and is a diagonal matrix whose elements depend only on the number of 1-bits in each assignment, namely,

where *h*=| *r* |, ranging from 0 to *n*. The overall phase, , is not essential for the algorithm. It merely serves to
make the final amplitude in the solution be one rather than . Whether or not this overall phase is used, the probability to
find a solution is one.

The matrix *W* is unitary and can be implemented
efficiently [7, 27]. For *n*=1, *W* is just the matrix
of Eq. (3). The phases in the matrix are powers of *i* and
so can be computed rapidly using similar procedures to those described
above for the matrix *R*. In this case we use a procedure that counts
the number of 1-bits in each assignment rather than the number of
conflicts.

Finally we show that *U* can be implemented by the product .
To see this, let . Then

where

with the sum over all assignments *t* with *h* 1-bits. Each 1-bit of
*t* contributes 0, 1 or 2 to
when the corresponding positions of *r* and *s* are both 0, have
exactly a single 1-bit, or are both 1, respectively. Thus
equals where *z*
is the number of 1-bits in *t* that are in exactly one of *r* and
*s*. There are positions from which such bits of *t* can be selected, and by
Eq. (4) this is just *d*(*r*,*s*). Thus the number of assignments
*t* with *h* 1-bits and *z* of these bits in exactly one of *r* and
*s* is given by where *d* =
*d*(*r*,*s*). Thus where

so that with . Substituting the value of from Eq. (21) then gives

which equals as defined in Eq. (14). Thus ,
allowing *U* to be efficiently implemented. As a final note, except
for a different choice of the phases, this is the same
implementation as used for the mixing matrix defined in an
unstructured quantum search algorithm [27].

Feb. 1999