= Solution
Use the <Hadamard basis> states $|\pm\rangle=(|0\rangle\pm|1\rangle)/\sqrt2$. The <Hadamard gate> satisfies $H|0\rangle=|+\rangle$, $H|1\rangle=|-\rangle$, and $H^2=I$. After the first three <Hadamard gates>, the full <quantum state> is
$$
|\psi_1\rangle=|+\rangle|+\rangle|-\rangle
=\frac12\bigl(|00\rangle+|01\rangle+|10\rangle+|11\rangle\bigr)|-\rangle.
$$
The <Pauli X gate> obeys $X|-\rangle=-|-\rangle$. Consequently the <Boolean quantum oracle> produces <phase kickback>:
$$
U_a|x\rangle|-\rangle=(-1)^{a\cdot x}|x\rangle|-\rangle.
$$
Factoring out the <ancilla qubit>, the four states immediately after the <function oracle> are
$$
\begin{aligned}
|\psi_{2,00}\rangle&=\tfrac12(|00\rangle+|01\rangle+|10\rangle+|11\rangle)|-\rangle=|++\rangle|-\rangle,\\
|\psi_{2,01}\rangle&=\tfrac12(|00\rangle-|01\rangle+|10\rangle-|11\rangle)|-\rangle=|+-\rangle|-\rangle,\\
|\psi_{2,10}\rangle&=\tfrac12(|00\rangle+|01\rangle-|10\rangle-|11\rangle)|-\rangle=|-+\rangle|-\rangle,\\
|\psi_{2,11}\rangle&=\tfrac12(|00\rangle-|01\rangle-|10\rangle+|11\rangle)|-\rangle=|--\rangle|-\rangle.
\end{aligned}
$$
The final <Hadamard gates> send $|+\rangle$ to $|0\rangle$ and $|-\rangle$ to $|1\rangle$. In particular, the printed <quantum circuit> includes a final <Hadamard gate> on the <ancilla qubit> too. Its full outputs, ordered as $x_1,x_2,y$, are
$$
\boxed{
\begin{array}{c|c}
a&|\psi_{\mathrm{out}}\rangle\\\hline
00&|001\rangle\\
01&|011\rangle\\
10&|101\rangle\\
11&|111\rangle
\end{array}}
$$
Thus \b[one oracle call identifies $a$ with certainty]: a <computational-basis measurement> of the first two <qubits> returns $a_1a_2$. The <ancilla qubit> returns to $|1\rangle$ and carries no additional information about $a$. The <Bernstein-Vazirani algorithm> turns the pattern of relative <quantum phases> into a definite <computational-basis state>.
Back to article page
