Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
On page 157 of Kaye, Laflamme and Mosca they write that in Grover's algorithm we need to apply Grover's iterate a total of: $$\Big\lfloor \frac{\pi}{4} \sqrt{N}\Big\rfloor$$ (They actually wrote $\Big\lfloor \frac{\pi}{4} \frac{1}{\sqrt{N}}\Big\rfloor$ but I assume the above is what is intended.)
My question is why the floor? Would it not be better to go to the nearest integer - since if e.g. $ \frac{\pi}{4} \sqrt{N}=5.9999$ it would seem a bit silly to do $5$ rather then $6$ iterations.
Applying the Grover iterate a total number of $\lfloor \frac{\pi}{4}\sqrt{N}\rfloor$ times is the best choice if we want to maximize the success probability of Grover's algorithm. This is to some extent explained in Kaye, Laflamme and Mosca (KLM), but let me elaborate on the most important details here.
Let $n$ be a natural number, $N = 2^n$, and suppose that we have a function $f : \{0,1\}^n \to \{0,1\}$. Suppose that we can evaluate this function $f$ by a quantum phase oracle $U_f$ (this is the same operator $U_f$ as described by KLM in equation 8.1.5 on page 155), with the property that for all $i \in \{0,1\}^n$: $$U_f : |i\rangle \mapsto (-1)^{f(i)}|i\rangle$$ Now, we define $G = f^{-1}(\{1\})$ and $B = f^{-1}(\{0\})$. Hence, $G \subseteq \{0,1\}^n$ is the set of all $n$-bit strings that will evaluate to $1$ if we use them as input in $f$. Another way of saying this is $i \in G \Leftrightarrow f(i) = 1$. For the purpose of this question, let's assume that $|G| = 1$, hence there is exactly one $i \in \{0,1\}^n$ such that $f(i) = 1$.
Next, we proceed with defining the good and bad states, as follows (these are defined by KLM in equation 8.1.3 on page 155): $$|\psi_{good}\rangle = \frac{1}{\sqrt{|G|}}\sum_{i \in G}|i\rangle \qquad \text{and} \qquad |\psi_{bad}\rangle = \frac{1}{\sqrt{|B|}}\sum_{i \in B}|i\rangle$$ Moreover, we define: $$|\psi_{uniform}\rangle = \frac{1}{\sqrt{N}}\sum_{i \in \{0,1\}^n}|i\rangle = \sin\theta |\psi_{good}\rangle + \cos\theta |\psi_{bad}\rangle$$ where $\theta = \arcsin(\sqrt{|G|/N}) = \arcsin(1/\sqrt{N})$.
Let's now devise an intuitive visualization of Grover's algorithm. To that end, consider all the quantum states that can be written as $\alpha|\psi_{good}\rangle + \beta|\psi_{bad}\rangle$ with $|\alpha|^2 + |\beta|^2 = 1$, and let's display them in the following picture.
We can use the visualization above to understand what Grover's iterate actually does. Grover's iterate does nothing but rotate any state in the circle above over an angle $2\theta$ counterclockwise. Hence, by applying Grover's iterate multiple times, we can rotate states over angles that are multiples of $2\theta$. How this works can be found in KLM, specifically we see the rotation over an angle of $2\theta$ appear in the last equation on page 160.
Now, suppose that we start with the state $|\psi_{uniform}\rangle$. After applying $k$ iterations of Grover's iterate, we obtain the state $|\psi_k\rangle$. From the picture, using the intuitive interpretation of Grover's iterate, we can easily see that the angle between $|\psi_k\rangle$ and $|\psi_{bad}\rangle$ is $(2k+1)\theta$. Hence, we find: $$|\psi_k\rangle = \sin((2k+1)\theta)|\psi_{good}\rangle + \cos((2k+1)\theta)|\psi_{bad}\rangle$$ As we want to maximize the success probability, we want our state to be as close to $|\psi_{good}\rangle$ as possible. Hence, we want $(2k+1)\theta$ to be as close to $\frac{\pi}{2}$ as possible. Solving this equation, we obtain: $$(2k+1)\theta = \frac{\pi}{2} \Leftrightarrow k = \frac{\pi}{4\theta} - \frac12$$ Recall that $\theta = \arcsin(1/\sqrt{N})$. By making the assumption that $N$ is big, and using the approximation $\arcsin(x) \approx x$ when $|x| \ll 1$, we obtain that our ideal choice for $k$ would be: $$k \approx \frac{\pi}{4}\sqrt{N} - \frac12$$ But we can only apply Grover's iterate an integer number of times, say $k^*$, so we must find the integer $k^*$ that matches $k$ as closely as possible. Hence, we round the quantity on the RHS to obtain (using the notation explained in the box on page 163 of KLM): $$k^* = \left[\frac{\pi}{4}\sqrt{N} - \frac12\right] = \left\lfloor \frac{\pi}{4}\sqrt{N}\right\rfloor$$ as $[x-\frac12] = \lfloor x\rfloor$ for all real $x$. If we trace back where this $\frac12$ comes from, we can see that it originates from the fact that we already start at an elevated angle of $\theta$ in the circle, even before we apply any of the Grover iterates. The floor, hence, is a deep consequence of the fact that the total angle of rotation doesn't have to be all of $\frac{\pi}{2}$, but rather $\frac{\pi}{2} - \theta$.
Using floor is logical as a general recommendation to build a Grover's algorithm circuit, because it means that we need less gates compared with ceiling.
Grover's algorithm is probabilistic; the probability of obtaining correct result grows until we reach about $\pi/4\sqrt{N}$ iterations, and starts decreasing after that number. For large $N$ the probability of obtaining correct result is very close to $1$ if the number of iterations is close to $\pi/4\sqrt{N}$; exact number of iterations does not matter given it is close to $\pi/4\sqrt{N}$.
