T2: 4. Quantum Algorithms

Question 1

Briefly state the problem of Simon’s algorithm

Answer 1

Period finding: given an n bit function f(x), find the period a such that f(x)=f(x⊕a)

Question 2

How does the U_f for Simon’s algorithm act on |x⟩|m⟩

Answer 2

U_f|x⟩|m⊕f(x)⟩

Question 3

State the general formula for uniform n-bit basis states

Answer 3

1/(2^n/2) SUM_(0,2^n -1) |x⟩

Question 4

State the action of a Hadamard on general n-bit basis states

Answer 4

H^(⊗n)|x⟩
= PROD_(0,n-1) 1/sqrt(2) [|0⟩_i+(-1)^x_i|1⟩i]
= 1/2^(n/2) SUM(0,2^n -1) (-1)^x.y|y⟩

Question 5

What does x.y denote in the Hadamard on general n-bits?

Answer 5

x.y = bitwise product
x_0 y_0 + x_1 y_1 + … + x_n y_n mod2

Question 6

Briefly describe the procedure for Simon’s algorithm

Answer 6

• Start with a system of n inputs and n ouputs all prepared in the |0⟩ state.
• Act with H^(⊗n) on the input qubits
• Act with U_f on the entangled state
• Measure the output bits, projecting the input to a superposition of 1/sqrt(2)[|x_0⟩ + |x_0 +a⟩]
• Act with H^(⊗n) on the input qubits
• Measure the input qubits; since a.b = 0 we can find a set of n-1 linear eqs to solve for a

Question 7

State the quantum Fourier Transform (QFT)

Answer 7

U_FT |x⟩ = 1/sqrt(2) SUM_(0,2^n -1) exp(2πixy/2^n) |y⟩

Question 8

Given an arbitrary state |ψ⟩=SUM_x ψ_x |x⟩ how does the QFT act

Answer 8

|ψ˜⟩ = U_FT |ψ⟩

|ψ˜⟩ = SUM_y ψ˜_y |y⟩

Question 9

What do ψ˜_y represent in QFT

Answer 9

The discrete fourier transform of the vector ψ_x with each exp a Fourier coefficient.

Question 10

What is the general form the controlled phase gate in QFT?

Answer 10

Identity with e^iπ/2^k in bottom right

Question 11

How can we construct a SWAP gate from the elementary set?

Answer 11

Three CNOTs alternating control/targets

Question 12

Briefly state the problem of Shor’s algorithm

Answer 12

Given a composite number N, we want to find some prime number p such that p divides N.

Question 13

How do we set up the problem for Shor’s algorithm

Answer 13

Construct the function f(a) = y^a mod N where r is the smallest value of a > 0 which satisfies f(r)=1; the period of f.
Suppose r is even: (y^r - 1) = 0 modN and find diff of two squares. Provided its not a multiple of N, y^r/2 -1 and N share a common factor and we can use Euclid’s algo to find it.

Question 14

Briefly describe the procedure for Shor’s algorithm

Answer 14

• Start with a system of n inputs and n ouputs all prepared in the |0⟩ state.
• Act with H^(⊗n) on the input qubits
• Act with U_f on the entangled state