= Solution
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 $|{-}\rangle$. Define the <Bernstein-Vazirani decoding controlled by a quantum register>
$$
W_g=(H_Z^{\otimes n}\otimes I_X)\,U_g\,(H_Z^{\otimes n}\otimes I_X).
$$
The <ancilla qubit> is implicit. For every computational index $x$, the <Walsh-Hadamard transform> calculation gives
$$
W_g|z\rangle_Z|x\rangle_X|{-}\rangle
=|z\oplus a_x\rangle_Z|x\rangle_X|{-}\rangle.
$$
In particular $W_g^2=I$ on these states. Initialize $Z$ to $|0\rangle$ and $X$ to $H^{\otimes n}|0\rangle$. The three query stages are
$$
\frac1{\sqrt{2^n}}\sum_x|0\rangle|x\rangle|{-}\rangle
\stackrel{W_g}{\longmapsto}
\frac1{\sqrt{2^n}}\sum_x|a_x\rangle|x\rangle|{-}\rangle
\stackrel{U_f}{\longmapsto}
\frac1{\sqrt{2^n}}\sum_x(-1)^{a\cdot x}|a_x\rangle|x\rangle|{-}\rangle
\stackrel{W_g}{\longmapsto}
|0\rangle\frac1{\sqrt{2^n}}\sum_x(-1)^{a\cdot x}|x\rangle|{-}\rangle.
$$
The 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 obtain
$$
\boxed{|0\rangle_Z|a\rangle_X|{-}\rangle}.
$$
This 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.
Back to article page
