CS 166课程代写、Java，Python程序设计代写

日期：2022-02-28 10:21

CS 166: Quantum Computation Instructor: Sandy Irani

Homework 7

Due: February 25, 2022

1. 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

22. 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

.

3. 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?

4. 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.

5. 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?