Some texts implement the quantum function evaluator as a “controlled-
˜
U
f
”
gate (Figure 8.19), where
˜
U
f
acts only on the lower register, and is defined
by
˜
U
f
|yi = |y ⊕f(x)i:
|xi
•
|xi
|yi
˜
U
f
|y ⊕ f(x)i
FIGURE 8.19: The quantum function evaluator as a controlled
˜
U
f
gate.
How is the action of this implementation different from the f-controlled
NOT gate of Figure 7.15? Check by using standard basis states as well as
superpositions as inputs.
8.2. Show that the phase kickback trick works because the input state in the
bottom register is an eigenstate of the
˜
U
f
operator for the Deutsch algo-
rithm.
8.3. Deutsch’s original version of his algorithm used |0i as the input to the
bottom register instead of |0i − |1i. Show that in this case you obtain
the correct answer with probability 3/4. Also show that the algorithm has
probability 1/2 of succeeding.
8.4. Prove the shift-invariance property of the Fourier transform, i.e., show that
ˆ
F|x + ki = e
iθ
ˆ
F|xi (8.88)
for some θ. Find θ in terms of k.
8.5. For the operator R
d
of Equation 8.45, give a construction for the controlled
R
d
gate using CNOT and single-qubit gates.
8.6. Find the eigenvalues and eigenvectors of the matrix R
d
. What can you say
about the commutators (i) [R
d
, X] (ii) [R
d
, Y ] (iii) [R
d
, Z] (iv) [R
d
, R
0
d
] ?
8.7. Work out a circuit that calculates the inverse quantum Fourier transform.
8.8. Consider a periodic function f(x + r) = f(x) for 0 ≤ x < N where N is
174 Introduction to Quantum Physics and Information Processing
an integer multiple of r. Suppose you are given a unitary operator U
y
that
performs the transformation U
y
|f(x)i = |f (x + y)i. Show that the state
|
˜
f(k)i =
1
√
N
N−1
X
x=0
e
−2πikx/N
|f(x)i (8.89)
is an eigenvector of U
y
. Calculate the corresponding eigenvalue.
8.9. Compute the output of the controlled-QFT gate
shown in the figure if the input is H
⊗3
|xi.
•
ˆ
F
8.10. On examining the period finding algorithm, we can find a relationship with
the phase-estimation algorithm. On applying the oracle, we get
1
√
N
X
|xi|0i
U
f
−−→
1
√
N
X
|f(x)i.
Express |f (x)i in terms of its Fourier transform, |
˜
f(k)i. Invert this expres-
sion and show that |
˜
f(k)i are of the same form as Equation 8.89 of Problem
8.8. Now show that the period finding algorithm is the phase estimation for
the operator U
y
defined there.
8.11. Apply the quantum phase estimation algorithm to the following cases and
obtain the results:
(a) U = X, |ui = |−i, t = 2,
(b) U = R
d
, |ui = |1i, t = d + 1.
Leave a Reply