Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 61 / 1 / b

Prepare an additional qubit in $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$ by applying $X$ and then the Hadamard gate to $|0⟩$. Apply $H^{\otimes n}$ to the data register. The Boolean quantum oracle then produces quantum phase kickback:A final Walsh-Hadamard transform gives an amplitude for $z$ equal toTo see this identity, the sum factors over the bits; any position at which $a$ and $z$ differ contributes $1-1=0$. This is Bernstein-Vazirani phase kickback, and its output isThere is exactly one oracle query, $O(n)$ fixed quantum gates, and no probabilistic intermediate step. The ancilla qubit can be left in $|A⟩=|-⟩$ or reset to $|0⟩$ using its known inverse preparation. The construction includes the case $a=0$.

The linear decoding must be done coherently, so its output is available inside the next Boolean quantum oracle call. Use registers $Z,X$ of $n$ qubits and a shared phase ancilla qubit in $|-⟩$. Define the Bernstein-Vazirani decoding controlled by a quantum registerThe ancilla qubit is implicit. For every computational index $x$, the Walsh-Hadamard transform calculation givesIn particular $W_g^2=I$ on these states. Initialize $Z$ to $|0⟩$ and $X$ to $H^{\otimes n}|0⟩$. The three query stages areThe middle equality uses the matching index $z=a_x$, not a classical guess of that string. The second $W_g$ performs uncomputation, removing the hidden-string register without losing its phase on $X$. Apply $H^{\otimes n}$ to $X$ to obtainThis requires precisely two queries to $U_g$ and one to $U_f$, and only $O(n)$ additional fixed quantum gates. No measurement of $a_x$ is made: such a measurement would spoil the required coherence. Preparing all registers and the phase ancilla qubit uses only the initially available zero states.