Problem 1: Discrete Fourier Transform (40 points)
(a) The N-th roots of unity are defined as solutions to the equation: (ωN )N = 1. There are exactly N distinct N-th roots of unity.
Let ω be a primitive root of unity, for example ωN = e2πi/N . Show the following:
N−1
N,
if N divides m
ωNmk =
k=0
0,
otherwise
(b) For integer N ≥ 2 let
f(0)
f(1)
f ≡
f(N
...
1) .
−
be a vector function f : [N] → C. The Discrete Fourier Transform of f is another
complex vector function F : [N] → C given by
F (0)
F (1)
F ≡
F(N...
1) .
−
of the same dimension N, with
F (k) =
√1
ωNknf(n)
N
n
Thus the Fourier transform is a linear operator represented by the N × N matrix
AN = (akn) with akn = √1N ωNkn.
(i) Write explicitly the Fourier matrix of order 4 using ω4 = e2πi/4 = i.
1
(ii) Find the Fourier Transform of the vector
2
1
−2
1
using the Fourier matrix from (i).
(iii) Using Part (a), verify that the inverse matrix is
A−N1 = √1 (ωN−kn)
N
In other words, a vector f can be recovered from its Fourier Transform F by the
Fourier Inversion Formula:
f(n) =
√1
ωN−nkF (k)
N
k
Problem 2: QFT on three qubits (20 points)
In this problem, you will work with the 3-qubit QFT A8 and its inverse A†8.
(a) What is ω8? Simplify as much as possible.
For the next two problems, you may use any resources you would like for the calculations.
(b) Calculate A8 |2 .
(c) Given
7˜ =
1
1
−
1
−
1
−
1
−
1
−
1
−
1
1
1
1
1
T
2√
i
2√
i
i
2√
+
i
2√
i
+
i
4
4
4
4
4
4
4
2
4
2
2
2
• ˜
Calculate A8 7
˜
(d) Fill in the circuit below such that the resulting state will be 7
[Hint: look at the class exercise for a very similar problem]
| 0
| 1
| 2
2
Problem 3: QFT Qiskit circuit example (40 points) Fill out problem 3 on the attached Jupyter notebook.
3
