Wong's "Introduction to Classical and Quantum Computing" Exercise 7.23

Question

I am currently working my way through "Introduction to Classical and Quantum Computing" by Thomas Wong. I am trying to solve the following problem:

Exercise 7.23. Answer the following questions about Grover’s algorithm: (a) When the n qubits are in their initial state (all $|+\rangle$ states), if you measure the qubits, what is the probability that you get $|w\rangle$? Express your answer in terms of $N = 2^n$.

(b) Say you apply just one step of Grover’s algorithm (one query $U_f$ and one reflection $R$). If you measure the qubits after this one step, what is the probability that you get $|w\rangle$? Express your answer in terms of $N = 2^n$. Hint: In the $rw$-plane, the amplitude of the state in $|w\rangle$ is the sine of the angle between the state and $|r\rangle$.

I have already solved and understand a) (answer: $\frac1N$). However, I am having trouble figuring out b). The answer index says that $\frac9N − \frac{24}{N^2} + \frac{16}{N^3}$ is the probability. To be frank, I really do not know how they arrived to this answer. I do not know how to get the amplitude of $|w\rangle$ (and therefore find the probability), even with the hint. Any help on how to go about solving this would be greatly appreciated.

Answer 1

I don't have access to the book, so I'm not exactly sure on the notation, or the appropriate starting point...

In general, Grover's algorithm is set up to work in a two-dimensional subspace, which I'll denote by $|w\rangle$ and $|w^\perp\rangle$ where $w$ is the target state and $\langle w|w^\perp\rangle=0$. The initial state can be written as $$ |+\rangle^{\otimes n}=\cos\theta|w^\perp\rangle+\sin\theta|w\rangle $$ where $\sin\theta=\frac{1}{\sqrt{N}}$.

Each step of Grover's algorithm changes the angle by $2\theta$ (you probably want to prove that), so after 1 step, you'll have the state $$ \cos3\theta|w^\perp\rangle+\sin3\theta|w\rangle. $$ The probability of finding $w$ is $\sin^2(3\theta)$, which you can use double angle formulae to show is the same as $\sin^2\theta(3-4\sin^2\theta)^2$. If you substitute in the value of $\sin\theta$, you'll get the claimed answer.