Angular Error associated with Quantum Search Algorithm

Question

Chapter 6.3 of "Quantum Computation and Quantum Information 10th Anniversary Edition" textbook by Nielsen and Chuang talks about using the Quantum Counting Algorithm to find the number of solutions to the Quantum Search Algorithm before actually implementing it.

For a search space of size $2N$ with $M$ number of solutions, the number of Grover iterations $R$ required to obtain the state of solutions is upper bounded by (Eqn 6.17):

$$R \leq \lceil\frac{\pi}{4}\sqrt{2N/M}\space\rceil $$

At the last paragraph of this chapter, they stated that the angular error after the $R$ number of Grover iterations is at most $\pi/4(1+|\Delta\theta|/\theta)$. I think that this means:

$$|\Delta\theta| R \leq |\Delta\theta|\lceil\frac{\pi}{4}\sqrt{2N/M}\space\rceil = \pi/4(1+|\Delta\theta|/\theta) $$

We know that $\sin^2(\theta/2)=\frac{M}{2N}$, so I tried to use substitution in the attempt to get the stated angular error. This is what I got:

$$|\Delta\theta| R \leq |\Delta\theta| \space \lceil \frac{\pi}{4}\frac{1}{\sin(\theta/2)} \rceil $$

Can someone explain to me how to get the stated angular error?

Answer 1

The angle of each rotation $\theta$ obeys $0\leq \theta \leq \frac{\pi}{2}$ so that $0\leq \frac{\theta}{2} \leq \frac{\pi}{4}$. The Grover Iterations as we know, rotates our initial state vector $|\psi\big>=\cos(\theta/2) |\alpha\big> + \sin(\theta/2)|\beta\big>$ by the angle $\theta$ a few times, such that eventually $|\psi \big>$ will be rotated to within an angle $\frac{\theta}{2}\leq \frac{\pi}{4}$ of $|\beta\big>$ which is our desired state.

By using the Quantum Counting Algorithm to get an estimate of $\theta\approx\theta+\Delta\theta$ and thus $M\approx M+\Delta M$ which is the number of solutions, we introduced the error of $\Delta\theta/2$ to our initial state $|\psi \big>$. Since we know $\frac{\theta}{2}\leq \frac{\pi}{4}$, the maximum error tied to our initial state $|\psi\big>$ will be given as:

$$\text{Maximum Initial Error} = \frac{\pi}{4} \times \frac{|\Delta\theta/2|}{\theta/2} = \frac{\pi}{4} \frac{|\Delta\theta|}{\theta}$$

Grover Iterations will then rotate $|\psi\big>$ close to $|\beta\big>$, with the maximum angular separation being $\frac{\pi}{4}$ no matter what is the value of the initial angle of $\frac{\theta+\Delta\theta}{2}$. So the total angular deviation (accounting for the offset of $\Delta\theta/2$ in the initial state $|\psi\big>$) from $|\beta\big>$ in this case is:

$$\text{Total Angular Deviation} =\frac{\pi}{4}+\text{Maximum Initial Error}$$

This is why we'll get $\frac{\pi}{4}\big(1+\frac{|\Delta\theta|}{\theta}\big)$ as compared to just $\frac{\pi}{4}$. Please do input additional comments if any.

Answer 2

In the last equation in the question above the left hand, and right hand - the $\Delta \theta$ terms cancel, and the denominator $\sin^{2}(\theta)$ term whose root is as you mentioned inverted (as it's in the denominator) to give the bound as the first equation in the question. See related question for the floor operation,