Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 47 / 2 / Solution

The Walsh-Hadamard transform is the tensor product of one Hadamard gate on each qubit. Indeed,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 measurement in quantum mechanics.

For the supplied linear-phase input, the amplitude on output $y$ isEach factor is obtained by summing over the independent bit $x_j$. This directly proves the relevant orthogonality of the binary Fourier phases, and yields the output state $|a⟩$ 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 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{⟩}^{\otimes n}$ and its answer ancilla qubit in $|-⟩$, which can be prepared as $H|1⟩$. 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 producesA computational-basis measurement of the data wires gives all bits of $a$ with certainty. This is Bernstein-Vazirani phase kickback: 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.