= Solution
Use the <Bernstein-Vazirani algorithm>: initialize n <qubits> in $|0^n\rangle$, apply $H^{\otimes n}$, query the supplied <phase oracle> once, apply $H^{\otimes n}$ again, and measure all n computational bits. Immediately after the query the state is
$$
\frac1{\sqrt{2^n}}\sum_x(-1)^{a\cdot x}|x\rangle,
$$
where the dot product in the exponent is taken modulo two. The <Walsh-Hadamard transform> gives amplitude
$$
\begin{aligned}
\langle y|H^{\otimes n}O_fH^{\otimes n}|0^n\rangle
&=\frac1{2^n}\sum_{x\in\{0,1\}^n}(-1)^{(a\oplus y)\cdot x}\\
&=\prod_{j=1}^n\frac{1+(-1)^{a_j\oplus y_j}}2.
\end{aligned}
$$
Every factor is one if $y_j=a_j$ and zero otherwise. Thus the final state is \b[exactly $|a\rangle$], and the measurement outputs a with certainty after \b[one oracle query]. This is the character cancellation behind <Bernstein-Vazirani phase kickback>; because access here is already to the reduced <phase oracle>, no extra target ancilla or conversion from a bit-flip oracle is required.
Back to article page
