QUANTUM ALGORITHMS
1. 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.
2. 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.
3. Recall that the Fibonacci sequence (fi)i∈N is defined
f0 = 0, f1 = 1, fn+1 = fn + fn−1.
(i) Show that
.
(ii) 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.
1
