For the operation 
, note that each value in Eq. (13) has unit
magnitude so R is a unitary diagonal matrix. Furthermore each
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
, 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 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:
. 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 
when we make the correspondence
between the 2-bit vectors 
and the integers
, 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 
. 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 
. In this form, the sums separate to give finally
The net result of applying F using the superposition for the
additional register is to change the phase of each assignment s by
, 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.