[Solved] Quantum Homework 8

1. After k iterations of G in Grovers algorithm, we obtained

where is such that sin() = a. Show that when k = b/(4)c, upon measuring this state the probability of observing a state in |Ai is 1 a.

2. We solved the recurrence in Grovers algorithm by diagonalizing a matrix,

!

ⁱ = b + ia (so sin() = a), is the conjugate of , and b = 1 a with

where = e a [0,1].

Verify that the matrices multiply as claimed in the above equation.

3. Recall that the Fibonacci sequence (f_i)_iN is defined

f0 = 0, f1 = 1, fn+1 = fn + fn1.

• Show that

.

• Use the same technique that we used to find a closed form of the recurrence in Grovers algorithm to find a closed form for the Fibonacci sequence.

Hint: f_n = (1/ 5)(ⁿⁿ) where = (1/2)(1+ 5) is the golden ratio and = (1/2)(1 5) is its conjugate.