= Solution
{c}
Write $\oplus$ for bitwise <exclusive or>. Both <quantum registers> begin in $|0^n\rangle$. After the first <Hadamard transform> their joint <quantum state> is
$$
2^{-n/2}\sum_{x\in\{0,1\}^n}|x\rangle|0^n\rangle.
$$
The <quantum oracle> $U_f$ maps each component $|x\rangle|0^n\rangle$ to $|x\rangle|f(x)\rangle$. By <linearity>, the required <quantum state> is therefore
$$
\boxed{|\Psi\rangle=2^{-n/2}\sum_{x\in\{0,1\}^n}|x\rangle|f(x)\rangle.}
$$
The 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.
Back to article page
