QUANTUM ALGORITHMS
1. Let t ∈ N.
(i) Prove that
t−1 xt − 1 = (x − 1)Xxk.
k=0
(ii) Prove that x = e2πi(m/t) is a solution to xt − 1 for m ∈ Z.
(iii) Let m ∈ Z with 0 ≤ m < t. Use the previous parts to prove that
if m = 0, 0 otherwise.
k=0
Recall that the n-qubit Quantum Fourier Transform (QFT n) is characterized by its action on basis vector |xi,
where [0.···] represents the number with binary decimal representation 0.··· and likewise [x] represents the number with binary representation x ∈ {0,1}n.
2. (i) Explicitly calculate QFT n |0ni.
(ii) Explicitly calculate QFT n |1ni.
3. Show that
QFT n |xi = 2−n/2 X e2πi[x][y]/2n |yi,
y∈{0,1}n
where [x] represents the number with binary representation x ∈ {0,1}n (and so [x][y] is the product of x and y, regarded as binary numbers).
Problems continue on the next page.
4. Use the previous problem to prove that
QFT †n |xi = 2−n/2 X e−2πi[x][y]/2n |yi
y∈{0,1}n
for basis vector |xi ∈ {0,1} defines the inverse of QFT n.
Hint 1: Show that QFT n ◦ QFT †n |xi = QFT †n ◦ QFT n |xi = |xi.
Hint 2: You may find this identity useful
2n−1
n
X 2πi k`/2
e = 0
k=0
if
` 6= 0.
5. (i) Write the matrix for QFT 3 in the standard computational basis (i.e. |xi for x ∈ {0,1}n). Use the notation ωn = e2πi/n. [Hint: this is an 8 × 8 matrix.]
(ii) Write the matrix for in the standard computational basis (i.e. |xi for x ∈
{0,1}n).
