Past exam of the laser science and quantum information processing course of the University of Oxford / 2006 / 5 / 2 / Solution

Define the Hadamard basis states $|\pm ⟩=(|0⟩\pm |1⟩)/\sqrt{2}$. The initial two Hadamard gates prepare $|+⟩|+⟩$. For one bracket, the two control branches giveUsing the Pauli X gate $X=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$, unitary conjugation by the Hadamard gate gives $H{U}_{0}H=-X$, so $G=-X{U}_f$. Keeping every sign, the target states along the control-one branch, in the exact gate order, areThe last column also includes the final target Hadamard gate, which lies outside the bracket. Writing $|{\chi }_f⟩=HG|+⟩$, applying the final top Hadamard gate gives the exact normalized two-qubit quantum stateThus the complete outputs, in top-then-bottom computational basis order, areFor the first qubit, the Pauli matrix ${\sigma }_z=Z$ has expectation value $P(0)-P(1)$ by the Born rule. The two $k=1$ cases each have $P(0)=P(1)=1/2$, while the $k=0$ and $k=2$ cases are deterministic. Equivalently, this Hadamard test measuresThis explains the approximate quantum counting interpretation: repeated preparations estimate the expectation value, and hence $k$. A single top-qubit computational-basis measurement need not identify $k$.