= Solution
{c}
Apply one <Hadamard gate> to each of the $n$ <qubits>, with all gates acting in parallel. This <quantum circuit> implements the <tensor product> $H^{\otimes n}$; it needs $n$ single-qubit gates and one layer. For one <qubit>,
$$
H|x_j\rangle=\frac1{\sqrt2}\sum_{y_j=0}^1(-1)^{x_jy_j}|y_j\rangle.
$$
Taking the <tensor product> of these expressions multiplies the <probability amplitudes> and adds their exponents, giving
$$
\boxed{H^{\otimes n}|x\rangle=2^{-n/2}\sum_{y\in\{0,1\}^n}(-1)^{x\cdot y}|y\rangle.}
$$
Here the <dot product> is evaluated using <modular arithmetic> modulo two.
\Image[/past-exam-of-the-introduction-to-quantum-information-course-of-the-university-of-oxford/2015-hadamard-network.png]
{title=The <Hadamard transform> applies one <Hadamard gate> to each <qubit> in a parallel layer}
In particular, an initially zero <quantum register> becomes the <uniform quantum superposition>
$$
\boxed{H^{\otimes n}|0^n\rangle=2^{-n/2}\sum_x|x\rangle.}
$$
This is useful at the start of a <quantum algorithm> because a subsequent <quantum oracle> acts on all these components coherently. Later <quantum interference> can reveal a global property of the function. Measuring immediately would merely produce a uniformly random <binary string>; the useful resource is the preserved <quantum coherence>, rather than the ability to read every function value in one run.
Back to article page
