Description
- After k iterations of G in Grover’s 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.
- We solved the recurrence in Grover’s algorithm by diagonalizing a matrix,
!
iθ = √b + i√a (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.
- Recall that the Fibonacci sequence (fi)i∈N is defined
f0 = 0,                    f1 = 1,                        fn+1 = fn + fn−1.
- Show that
.
- Use the same technique that we used to find a closed form of the recurrence in Grover’s algorithm to find a closed form for the Fibonacci sequence.
√                                                         √                                                                       √
Hint: fn = (1/ 5)(ϕn−ψn) where ϕ = (1/2)(1+ 5) is the golden ratio and ψ = (1/2)(1− 5) is its conjugate.
