CS 166: Quantum Computation Instructor: Sandy Irani
Homework 7
Due: February 25, 2022
- Suppose x ∈ {0, . . . , N ? 1}, where N is a power of 2. Let x1x2 · · · xn be the binary
representation of the integer x.
(a) Express the state resulting from applying QFTN to the state |x〉.
(b) Now suppose that y ∈ {0, . . . , N?1}. Let y1y2 · · · yn be the binary representation
of the integer y. Express the output of the circuit below as a function of y:
(c) Put your answers together for the first two parts of this problem to express the
output of the following circuit as a function of x.
(d) Now express the output of the following circuit. In order to describe the output
of QFT?1, think about what input to QFT would produce the state that is the
input to QFT?1 in the circuit.
1 - Give the 6-qubit state after each gate in the circuit below is applied. Express the state
using ket notation. All phases (including ?1) should be expressed as ωx, where x is
an integer and ω = e2pii/2
6
. - Consider the Period Finding Algorithm for function f : {0, . . . , N ? 1} → {0, . . . ,M ?
1}, where f(y) = 5x mod M . M = 12 and N = 16.
(a) What is the current state of the algorithm after step 3? The state after step 3 is:
1√
N
N?1∑
y=0
|y〉|f(y)〉.
You need to express this state using the specific values of M , x,and N given
above. Since this may be a bit tedious to do by hand, you are welcome to write
a program to do the calculation for you.
(b) If the second register is measured, then what are the possible outcomes?
3(c) Suppose you measure the second register and the outcome is the largest of all the
possible outcomes. Then what is the state after measurement? - M = 337123, and x = 29680.
(a) Verify that x is a square root of 1 mod M . You can use a calculator, but write
down in your solution the condition you are checking.
(b) Use x to factor M . Show enough work to indicate that you know how to apply
the algorithm to factor M . You can use a gcd calculator if you like. - Consider the result of measuring the first register from your circuit in Lab 7.
(a) What are the possible outcomes from measuring first register and which outcomes
allow you to recover the period of 2s mod 15?
(b) After determining the period of 2s mod 15, then how would you use that infor-
mation to factor 15?