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

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.

• – glS
Commented Jul 15 at 7:59

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.