= Solution
Apply one <Hadamard gate> independently to each <qubit>. These gates act in parallel, so the <quantum circuit> implements $H^{\otimes n}$ with $n$ gates and depth one.
\Image[/past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2004/iii/paper-53-hadamard-network.png]
{title=Parallel Hadamard gates implementing the binary Fourier transform}
For a <computational basis> state, factorization gives
$$
H^{\otimes n}|x_1\cdots x_n\rangle=\bigotimes_{j=1}^n\frac{|0\rangle+(-1)^{x_j}|1\rangle}{\sqrt2}=2^{-n/2}\sum_{y\in\{0,1\}^n}(-1)^{x\cdot y}|y\rangle.
$$
The exponent is the dot product over the <finite field> $\mathbb F_2$, because multiplying the separate signs adds their exponents modulo two. This is the <Walsh-Hadamard transform>, equivalently the <quantum Fourier transform> on the finite Abelian group $(\mathbb Z_2)^n$.
In particular, the all-zero input becomes the uniform coherent <superposition> $2^{-n/2}\sum_y|y\rangle$. It is a useful initial operation because an oracle can then act on all amplitudes in one call, and subsequent interference can reveal a global property. Measurement alone does not read all function values: the later interference step is what turns the preparation into an algorithmic advantage.
Back to article page
