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