Past exam of the introduction to quantum information course of the University of Oxford / 2015 / 1 / b / Solution

Write $\oplus$ for bitwise exclusive or. Both quantum registers begin in $|0^n⟩$. After the first Hadamard transform their joint quantum state isThe quantum oracle $U_f$ maps each component $|x⟩|0^n⟩$ to $|x⟩|f(x)⟩$. By linearity, the required quantum state is thereforeThe different first-register computational-basis states are orthogonal, so there are $2^n$ orthogonal joint components of squared probability amplitude $2^{-n}$, even though some second-register values coincide. Thus the displayed quantum state is normalized.