[SOLVED] Quantum Homework 12

1. Let t ∈ N.
   • Prove that

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

k=0

• Prove that x = e^2πi(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 = 2−n/2 X e2πi[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 = 2−n/2 X e−2πi[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^2πi/n. [Hint: this is an 8 × 8 ]

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

{0,1}ⁿ).