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].
