 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 $|-⟩$. 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.