next up previous
Next: 4.5.3 The Mixing Matrix Up: 4.5 Implementation Previous: 4.5.1 Forming the Initial

4.5.2 Adjusting Phases

For the operation tex2html_wrap_inline2290 , note that each value in Eq. (13) has unit magnitude so R is a unitary diagonal matrix. Furthermore each tex2html_wrap_inline2294 only requires using the efficient classical procedure f(s) that counts the number of conflicts in an assignment s. We require a reversible version of this procedure, which can be made with an additional program register. When the phases to be introduced are just tex2html_wrap_inline2300 , this additional register needs to take on only two values, 0 or 1, corresponding to whether the phase should be 1 or -1, respectively. Thus it can be represented with a single additional quantum bit, beyond those required to represent the assignment. Such phases have been used in previous algorithms [29, 27] and can be implemented through a single evaluation of f(s) by setting the extra variable to be a superposition of its two values [7].

In the algorithm presented here, Eq. (13) requires phases that are powers of i, which can take on four different values: 1, i, -1 and -i. The technique used with tex2html_wrap_inline2300 phases can be generalized to work with these four values, again with a single evaluation of f(s). The additional register must consist of two quantum bits, so it can take on the values 0, 1, 2 or 3. For an assignment s and register x, we use the reversible operation


where c=f(s) is the number of conflicts in assignment s. It then remains to show how this operation can be used to perform the required phase adjustments. Just as we operate with a superposition of all possible assignments, to implement the phase adjustment, we set register x to be a particular superposition of its four values: tex2html_wrap_inline2328 . One way to construct this superposition is to start with both bits of x set to 1, operate on the most significant bit with Eq. (3) and then operate on the other bit with


to get


This is just the superposition tex2html_wrap_inline2334 when we make the correspondence between the 2-bit vectors tex2html_wrap_inline2336 and the integers tex2html_wrap_inline2338 , respectively.

We start with the equal superposition of amplitudes for the assignments and this superposition for x:


As illustrated with Eq. (2), the operation F acts on each term in this superposition separately, to produce


where c is the number of conflicts in assignment s. Let tex2html_wrap_inline2348 . Then, for a given assignment s, as x ranges from 0 to 3, y also takes on these values, but not necessarily in the same order. Thus this resulting superposition can also be written as


because tex2html_wrap_inline2356 . In this form, the sums separate to give finally


The net result of applying F using the superposition tex2html_wrap_inline2334 for the additional register is to change the phase of each assignment s by tex2html_wrap_inline2364 , as required by Eq. (13). Importantly, the final result reproduces the original factored form in which the superposition of assignments is not correlated with the superposition of the register. This factored form means the register plays no role in the subsequent mixing operation applied by the matrix U to the superposition of assignments. Thus this procedure produces the required phase changes using only one evaluation of f(s), showing how the phases of a superposition of assignments can be adjusted without requiring any prior explicit knowledge of the solution.

next up previous
Next: 4.5.3 The Mixing Matrix Up: 4.5 Implementation Previous: 4.5.1 Forming the Initial

Tad Hogg
Feb. 1999