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

For $r$ brackets the control-zero branch still does nothing, and the control-one branch applies $G^r$ to the target. Immediately before the final two Hadamard gates, the quantum state isFor the constant function with $k=0$, the phase oracle is $U_f=-I$, so $G=(-X)(-I)=X$. Since $|+⟩$ is an eigenstate of the Pauli X gate with eigenvalue $+1$, $G^r|+⟩=|+⟩$ for every integer $r$. The final two Hadamard gates therefore giveIn particular, the first qubit always ends in $|0⟩$.

For the constant function with $k=2$, $U_f=I$ and $G=-X$, so $G^r|+⟩=(-1{)}^r|+⟩$. Thus the target remains in $|+⟩$, and the top qubit before its final Hadamard gate is $(|0⟩+(-1{)}^r|1⟩)/\sqrt{2}$. The sign is a relative quantum phase between the control branches. The Hadamard gate converts it into the integer parity of $r$:The first qubit is therefore $|0⟩$ for even $r$ and $|1⟩$ for odd $r$, including all requested $r>1$.