Past exam of the computer science course of the University of Oxford / 2020 / Quantum information / 3

Throughout this question let $|A_0⟩={\sum }_{f(x)=0}|x⟩$, $|A_1⟩={\sum }_{f(x)=1}|x⟩$, and $|J⟩={\sum }_{x=0}^{N-1}|x⟩=\sqrt{N}|e_0⟩$. These subset sums are unnormalized: $⟨A_j|A_j⟩=S_j$ and $⟨A_0|A_1⟩=0$. The promise implies that $N>0$ is divisible by four. No power-of-two assumption is needed for the abstract $N$-dimensional calculation.

Substitute the promised cardinalities:The marked and unmarked subsets also exhaust the computational basis, so $S_0+S_1=N$; this will ensure that the uniform initial state has unit norm.

By orthonormality of the computational basis,There is one nonzero term, the term with $y=x$. In particular, the uniform coefficient is unchanged when passing from the ket to its bra because it is real.

Summing part (i) over the $S_0$ unmarked indices gives $⟨e_0|A_0⟩=S_0/\sqrt{N}$. The Grover diffusion operator therefore acts asThis is an identity for an unnormalized subset sum; it does not require replacing its norm by one.

For the marked subset, $⟨e_0|A_1⟩=S_1/\sqrt{N}$ by the same summation of the individual inner products. ConsequentlyThe cardinality is $S_1$ here. Its sign will reverse when this expression is used for the oracle's negative marked component.

The phase oracle multiplies an unmarked basis vector by $+1$ and a marked one by $-1$. Thus the state after the oracle isIts squared norm is $(S_0+S_1)/N=1$. All computational outcomes would still have probability $1/N$ if measured at this point: the oracle has changed the relative phase, not the magnitudes of the amplitudes. The following reflection converts that phase information into a changed probability distribution through quantum interference.

Apply parts (b)(ii) and (b)(iii), keeping the oracle's minus sign:The middle equality uses part (a), and the last uses $|J⟩=|A_0⟩+|A_1⟩$. The final squared norm is $4S_1/N=1$, providing a normalization check.

The sign convention matters: here $W=2|e_0⟩⟨e_0|-I$ fixes $|e_0⟩$ and negates its orthogonal complement. Its action on amplitudes is inversion about the mean. The negative of this reflection would change the final vector by an overall global phase, but mixing those conventions midway would give incorrect intermediate signs.^[ref]

The algorithm returns a uniformly random marked input with certainty. The Born rule applied to the final state gives, for each individual basis label $y$,Summing over the $S_1=N/4$ marked inputs gives $\mathrm{Pr}(f(Y)=1)=1$. The outcome is a marked input label, not merely the bit indicating whether some marked input exists. There is one use of the supplied phase oracle, together with the specified preparation, reflection and measurement.

The exact success relies on the marked fraction $r=S_1/N=1/4$. More generally, the mean amplitude immediately after the oracle is $(1-2r)/\sqrt{N}$. Inversion about the mean sends an unmarked amplitude to $(1-4r)/\sqrt{N}$ and a marked amplitude to $(3-4r)/\sqrt{N}$. Thus a single iteration has marked success probability $r(3-4r{)}^2$. At $r=1/4$ the unmarked amplitudes vanish and the marked amplitudes become $2/\sqrt{N}$, giving the one-step exact Grover search with a quarter of the inputs marked. No claim of one-query certainty for an arbitrary marked fraction is needed.