[Solved] Quantum Homework 12

1. Let t N.
   • Prove that

t1 x^t 1 = (x 1)^Xx^k.

k=0

• Prove that x = e^2i(m/t) is a solution to x^t 1 for m Z.
• 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}ⁿ.

2. (i) Explicitly calculate QFT _n |0ⁿ

(ii) Explicitly calculate QFT _n |1ⁿi.

3. Show that

QFT _n |xi = 2n/2 X e2i[x][y]/2ⁿ |yi,

y{0,1}ⁿ

where [x] represents the number with binary representation x {0,1}ⁿ (and so [x][y] is the product of x and y, regarded as binary numbers).

Problems continue on the next page.

1

QUANTUM ALGORITHMS, HW 11 ADDITIONAL PROBLEMS 2

4. Use the previous problem to prove that

QFT _n |xi = 2n/2 X e2i[x][y]/2ⁿ |yi

y{0,1}ⁿ

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

2ⁿ1

ⁿ

5. (i) Write the matrix for QFT ₃ in the standard computational basis (i.e. |xi for x {0,1}ⁿ). Use the notation _n = e^2i/n. [Hint: this is an 8 8 ]

(ii) Write the matrix for in the standard computational basis (i.e. |xi for x

{0,1}ⁿ).