Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 190/264: Quantum Computation Homework 5
Note: Graduate students are required to do problems 3-6. Undergraduates are required to do problems 1-5.
A note on terminology: I didn’t use this terminology in class but the Discrete Fourier Transform on an N-dimensional vectors (with ω = e 2πi/N ), is called the Fourier Transform mod N.
A note to the undergraduates: It would be fairly easy to find the answers to problems 1 and 2 on the internet or in one of the texts listed on the course web page. I would like you to do those to problems without consulting outside sources as you will understand the constructions much better that way.
1. Give the diagram for the Fast Fourier Transform for N = 8. In what order do you want to line up the initial values α0, . . . , α7 into your diagram?
2. Write out the circuit for a Quantum Fourier Transform for n = 4 qubits. You can use H gates or gates of the form: Pk = 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 e 2πi/2 k .
You can denote a gate of this type in your circuit diagram as:
3. Let FN be the matrix denoting the Fourier Transform mod N. As defined in class, (FN )j,k = ω jk, where ω = e 2φi/N .
(a) We proved in class that FN is unitary. Therefore FN has a well defined inverse. Describe the matrix denoting the inverse Fourier Transform mod N
(b) Give a quantum circuit to compute the inverse Fourier Transform.
4. Let a|N and b|N. What is the Fourier transform mod N of the uniform superposition of all 0 ≤ x < N such that a|N or b|N? You can assume that a and b are relatively prime. Express your answer as a superposition of |ΦN/ai, |ΦN/bi, and |ΦN/abi.
5. Show how to implement the function |xi → |x + 1 mod 2n i using the Quantum Fourier transform. What is the complexity (big-Oh of the number of gates) of your circuit?
For graduate students: skip problems 1 and 2, and do the following problem:
6. Consider the quantum circuit that computes the Fourier transform mod 2 n . Now assume it is only necessary to compute the Fourier transform to within , where distance is measured in the operator norm. How much more efficient can you make the circuit? (Hint: consider omitting some of the phase shifts for small angles).
You can use the fact that if A abd B are N × N matrices and maxj,k |(A − B)j,k| ≤ /√ N, then the operator norm of A − B is at most .