Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 53 / 4

For independent attempts, measuring after each application of $A$ produces a success with probability $p$. Recognize the answer with the verifier and restart on failure. The number $T$ of attempts has a geometric distribution, with $\mathrm{Pr}(T=k)=(1-p{)}^{k-1}p$. Summing the tail probabilities givesThis counts applications of $A$; it presumes $p>0$ and a fresh preparation for each attempt. If $p=0$, neither repetition nor the amplification construction can create a good component from this input.

Let ${\Pi }_g$ project onto the good-output subspace and let $|g⟩=|{\Psi }_g⟩$, $|b⟩=|{\Psi }_b⟩$. They are orthonormal because their supporting computational basis strings are disjoint. The verification unitary operator is $V=I-2{\Pi }_g$, so $V|g⟩=-|g⟩$ and $V|b⟩=|b⟩$.

Also $V_0=I-2|0⟩⟨0|$. Since $A|0⟩=|\Psi ⟩$, conjugating gives $A{V}_0{A}^{†}=I-2|\Psi ⟩⟨\Psi |$. ThusBoth reflections preserve the span of $|g⟩$ and $|b⟩$: $V$ is diagonal there, and the other reflection only adds a multiple of $|\Psi ⟩$, already in that span. Direct substitution of $|\Psi ⟩=\sqrt{p}|g⟩+\sqrt{1-p}|b⟩$ yieldsThe minus sign in the first image follows from applying $V$ before the state reflection. In the ordered basis $(|b⟩,|g⟩)$ the matrix isThis exhibits the invariant plane without assumptions about the action of $A$ on the other input basis vectors.

Choose $0<\theta <\pi /2$ with $\sin \theta =\sqrt{p}$. Then $1-2p=\cos 2\theta$ and $2\sqrt{p(1-p)}=\sin 2\theta$. The matrix found in part 2 is a rotation by $2\theta$ in the ordered good-bad plane, with the bad coordinate listed first. The initial coordinate vector is $(\cos \theta ,\sin \theta {)}^T$.

After $r$ rotations its angle from the bad axis is $(2r+1)\theta$. Equivalently, multiplication of the displayed matrix and the addition formulas for sine and cosine prove the assertion by induction from $r=0$. HenceThe Born rule therefore gives good-output probability ${\sin }^2((2r+1)\theta )$. This is the geometric mechanism of amplitude amplification: each coherent iteration rotates the already existing good amplitude toward the good axis.

For known $p$, use nearest-integer stopping for amplitude amplification. SetWriting $x=\pi /(4\theta )$, the difference between $r+1/2$ and $x$ has absolute value at most $1/2$. Thus $|(2r+1)\theta -\pi /2|\le \theta$. The Born rule and part 3 giveCount the initial $A$ once and the $A^{†}$ and $A$ occurring inside each of the $r$ amplification iterates. The number of applications of either preparation unitary is thereforeThe counts separately are $r+1$ applications of $A$ and $r$ applications of $A^{†}$, in addition to $r$ applications each of $V$ and $V_0$. This is a quadratic improvement over the $1/p$ mean number of unamplified trials. At an exact rounding tie either nearest iterate meets the probability bound. Knowledge of $p$ is used in selecting the stopping time; repeatedly applying $Q$ without a suitable stopping rule can rotate the state past the good axis and reduce success again. The fact that answers lie in NP supplies verification, but by itself gives no claim that $1/\sqrt{p}$ is polynomial in input length.