Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 58 / 4

The best classical strategy avoids previously failed inputs: inspect a uniformly random permutation. Assume $1\le m\le N$ and let $K$ be the first marked position. For $K=k$, the first $k-1$ guesses must all fail and the next must succeed. ThusThe empty product covers $k=1$. The binomial form follows by choosing the $m$ marked positions uniformly: put one at $k$ and the remaining $m-1$ after it. This is the first marked item in a random permutation distribution.

The requested range is part of its support, but omits the last possible value $k=N-m+1$. All $N-m$ bad inputs can be encountered first, after which success is certain. The same formula includes that nonzero terminal probability; summing through this last value gives one. If $m=0$, the search never succeeds. If sampling were instead with replacement, its inferior repeated-guess strategy would have the geometric law $(1-m/N{)}^{k-1}m/N$ with no such finite endpoint.

With one marked input, after $r$ distinct failed guesses it is uniformly distributed among the $N-r$ untested inputs. Therefore the conditional chance of success on the next guess is $1/(N-r)$. One further failure raises it byor by a multiplicative factor $(N-r)/(N-r-1)$. There is a different unconditional statement: the marked position is uniform, so $\mathbb{P}(K=k)=1/N$ and $\mathbb{P}(K\le k)=k/N$. Thus each additional distinct guess increases cumulative success by $1/N$, even though the conditional next-guess probability increases after each failure. These distinguish the two possible meanings of a probability boost.

At this stage $A$ is an arbitrary unitary operator; do not yet assume it prepares the displayed uniform state from zero. Put $|a⟩=A|0⟩$, $p=e^{i\varphi }$ and $t=e^{i\theta }$. The phase on the zero basis state can be written using a rank-one orthogonal projection as $S_0^{\varphi }=I+(p-1)|0⟩⟨0|$, henceThe marked-state phase sends $|{\psi }_1⟩$ to $t|{\psi }_1⟩$ and leaves $|{\psi }_0⟩$ unchanged. ThereforeandThis is the complete general action. Unless $|a⟩$ lies in their span, that two-dimensional space need not be invariant. The PDF uses $S_f^{\theta }$ in $Q$; the TeX conversion's replacement by $S_0^{\theta }$ is a transcription error and would describe a different operation.

Now $|a⟩=|\psi ⟩$. Suppose $0<m<N$, and normalize the orthogonal good and bad components:Their disjoint computational supports make $(|g⟩,|b⟩)$ an orthonormal basis. For $s=\sin \chi ,c=\cos \chi$, the two-dimensional matrix for phase amplitude amplification isTo obtain its first column, the marked phase first multiplies $|g⟩$ by $t$, then $I+(p-1)|\psi ⟩⟨\psi |$ adds its projection onto $|\psi ⟩$; the second column is obtained similarly without $t$. This also proves unitarity: the rank-one phase has eigenvalues $p,1$ on this plane, and the marked phase has eigenvalues $t,1$, all of unit modulus. Their negative product is unitary for any real phases.

Using the unnormalized pair $(|{\psi }_1⟩,|{\psi }_0⟩)$ instead would produce a differently scaled matrix, which is not in general unitary in the ordinary Euclidean metric. At $m=0$ or $m=N$ one component vanishes and the relevant search space is one-dimensional.

For $p=t=-1$, the preceding matrix becomesMultiplying it by $(\sin \chi ,\cos \chi {)}^T$ gives $(\sin 3\chi ,\cos 3\chi {)}^T$. The sine and cosine addition identities then prove by induction thatFor $0<\chi \le \pi /4$, the first angle reaching the interval $[\pi /4,3\pi /4]$ gives success at least one half. Its smallest integer iteration count isThe ceiling advances the angle by less than $2\chi$, so the chosen angle remains in that success interval. This is the first half-success time in Grover search. If near-certain rather than half success is desired, choose the nearest integer to $\pi /(4\chi )-1/2$; its success is at least ${\cos }^2\chi$ and the count is asymptotic to $(\pi /4)\sqrt{N/m}$. Both exhibit the quadratic query improvement of amplitude amplification. Success oscillates, so further iterations past the first maximum are not automatically beneficial. The count presumes positive known $m$ (or known $\chi$); if no marked item exists, no number of iterations can produce one.