= Solution
Prepare an additional <qubit> in $|{-}\rangle=(|0\rangle-|1\rangle)/\sqrt2$ by applying $X$ and then the <Hadamard gate> to $|0\rangle$. Apply $H^{\otimes n}$ to the data register. The <Boolean quantum oracle> then produces <quantum phase kickback>:
$$
\frac1{\sqrt{2^n}}\sum_x|x\rangle|{-}\rangle
\stackrel{U_f}{\longmapsto}
\frac1{\sqrt{2^n}}\sum_x(-1)^{a\cdot x}|x\rangle|{-}\rangle.
$$
A final <Walsh-Hadamard transform> gives an amplitude for $z$ equal to
$$
\frac1{2^n}\sum_x(-1)^{(a\oplus z)\cdot x}=\delta_{z,a}.
$$
To 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 is
$$
\boxed{|a\rangle|{-}\rangle}.
$$
There is exactly one oracle query, $O(n)$ fixed <quantum gates>, and no probabilistic intermediate step. The <ancilla qubit> can be left in $|A\rangle=|{-}\rangle$ or reset to $|0\rangle$ using its known inverse preparation. The construction includes the case $a=0$.
Back to article page
