Past exam of the quantum information course of the University of Cambridge / 2013 / Paper 1 / 2

Set $N=2^n$, $a=N^{-1/2}=\sin t$ and $c=\cos t$, with $N>1$. The ordered vectors $|w⟩,|s⟩$ are normalized but nonorthogonal, since $⟨w|s⟩=a$. Their coordinate Gram matrix is thereforeAn operator matrix in this basis is obtained from the coefficients in the images of its basis vectors, not by treating those vectors as orthogonal measurement outcomes. Directly applying the two reflection operators givesTheir columns are consequentlyThese are physical unitary operators even though the coordinate matrices are not unitary in the ordinary Euclidean coordinate norm: they preserve $S$, so $U^{†}SU=S$.

The Grover iteration in a nonorthogonal basis isIt has determinant one and trace $2-4a^2=2\cos 2t$, hence eigenvalues $e^{\pm 2it}$. For example, the invertible matrix of eigenvectorssatisfiesThis diagonalization is exact for $N>1$; no large-$n$ approximation is needed.

To extract an actual probability using the Born rule, introduce the orthonormal unmarked superposition $|b⟩=(|s⟩-a|w⟩)/c$. In the ordered basis $|w⟩,|b⟩$, the same iteration is the rotationAfter $r$ iterations,Equivalently the original coordinates are $[\sin (2rt)/c,\cos ((2r+1)t)/c{]}^T$. The overlap with $|w⟩$ is the first coordinate plus $a$ times the second, recovering the same amplitude. Squaring just the first coordinate would be incorrect in a nonorthogonal basis.

For large $n$, $t\simeq N^{-1/2}$, and dropping the initial angle $t$ gives the requested approximation $P_r\simeq {\sin }^2(2rt)$. The first near-unit success occurs at the integer closest to $\pi /(4t)-1/2$:One can choose $r_{\mathrm{opt}}=\lfloor \pi /(4t)\rfloor$, with either neighbor equivalent in a tie. Further iterations overshoot and reduce success rather than monotonically improving it. The special $N=1$ problem needs no search and the two-vector coordinate construction becomes singular.

For an unstructured search, a reversible Boolean quantum oracle implements a phase change on the marked entry, while the diffusion reflection about a uniform state is known. Repeating the pair of reflections amplifies the marked amplitude and measurement yields a candidate that can be checked by another oracle query. The bounded-error query count is $O(\sqrt{N})$ for one marked item, compared with classical $\Theta (N)$ queries. It is a quadratic oracle-query speedup: state preparation, the cost of implementing the oracle and access to a classical database still matter. The method does not reveal an unknown marked value without the promised query access.^[ref]