next up previous
Next: 4.5.4 Required Search Time Up: 4.5 Implementation Previous: 4.5.2 Adjusting Phases

4.5.3 The Mixing Matrix

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


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


where h=| r |, ranging from 0 to n. The overall phase, tex2html_wrap_inline2388 , is not essential for the algorithm. It merely serves to make the final amplitude in the solution be one rather than tex2html_wrap_inline2390 . 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 tex2html_wrap_inline2374 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 tex2html_wrap_inline2406 . To see this, let tex2html_wrap_inline2408 . Then




with the sum over all assignments t with h 1-bits. Each 1-bit of t contributes 0, 1 or 2 to tex2html_wrap_inline2416 when the corresponding positions of r and s are both 0, have exactly a single 1-bit, or are both 1, respectively. Thus tex2html_wrap_inline2422 equals tex2html_wrap_inline2424 where z is the number of 1-bits in t that are in exactly one of r and s. There are tex2html_wrap_inline2434 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 tex2html_wrap_inline2450 where d = d(r,s). Thus tex2html_wrap_inline2454 where


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


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

next up previous
Next: 4.5.4 Required Search Time Up: 4.5 Implementation Previous: 4.5.2 Adjusting Phases

Tad Hogg
Feb. 1999