= Solution
The <Walsh-Hadamard transform> is the <tensor product> of one <Hadamard gate> on each <qubit>. Indeed,
$$
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)^{\sum_jx_jy_j}|y\rangle.
$$
The network therefore consists of $n$ parallel <Hadamard gates>, with no interaction between wires. Applied to an all-zero <quantum register>, it produces the <uniform quantum superposition> of all $2^n$ input strings. This lets a <Boolean quantum oracle> act coherently on all those inputs; a subsequent operation can turn their relative phases into useful interference. It does not permit reading all oracle values from a single <quantum measurement>.
\Image[/past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2003/iii/paper-47-hadamard-networks.png]
{title=Parallel Hadamard gates and the one-query Bernstein-Vazirani network}
For the supplied linear-phase input, the amplitude on output $y$ is
$$
2^{-n}\sum_{x\in\{0,1\}^n}(-1)^{a\cdot x+x\cdot y}
=\prod_{j=1}^n\frac{1+(-1)^{a_j\oplus y_j}}2
=\begin{cases}1,&y=a,\\0,&y\ne a.\end{cases}
$$
Each factor is obtained by summing over the independent bit $x_j$. This directly proves the relevant <orthogonality> of the binary Fourier phases, and yields \b[the output state $|a\rangle$ exactly].
For exact classical identification, query the <Boolean function> at the $n$ standard unit vectors: $f(e_j)=a_j$. Hence $n$ oracle calls suffice. They are also necessary in the worst case, even with adaptive queries: every answer supplies one binary linear equation in the unknown string. With fewer than $n$ queries, their coefficient <matrix> has <matrix rank> at most the number of queries, so its <null space> contains a nonzero string $h$. The strings $a$ and $a\oplus h$ give identical answers along that adaptive transcript and cannot both be identified correctly. Equivalently, a depth-$t$ binary decision tree has at most $2^t$ leaves and must distinguish $2^n$ possibilities. Thus \b[the exact classical query count is $n$]. This concerns exact recovery, rather than allowing an arbitrary error probability.
The quantum network in the lower panel starts its data <quantum register> in $|0\rangle^{\otimes n}$ and its answer <ancilla qubit> in $|-\rangle$, which can be prepared as $H|1\rangle$. Apply <Hadamard gates> to the data wires, make one <Boolean quantum oracle> call, then apply <Hadamard gates> again to all data wires. <Quantum phase kickback> produces
$$
|0^n\rangle|-\rangle
\longmapsto 2^{-n/2}\sum_x|x\rangle|-\rangle
\longmapsto 2^{-n/2}\sum_x(-1)^{a\cdot x}|x\rangle|-\rangle
\longmapsto |a\rangle|-\rangle.
$$
A <computational-basis measurement> of the data wires gives all bits of $a$ with certainty. This is <Bernstein-Vazirani phase kickback>: \b[one quantum query], $2n$ data <Hadamard gates>, and one answer-state preparation suffice. The answer <ancilla qubit> stays separate from the data at the output.
Back to article page
