= Solution
The required identity is <CNOT control reversal in the Hadamard basis>. To derive it using standard <quantum circuit> identities, let $\mathrm{CZ}$ be the <Controlled-Z gate>, which multiplies $|11\rangle$ by $-1$ and fixes the other <computational-basis states>. Since $HXH=Z$,
$$
C_{1\to2}=(I\otimes H)\,\mathrm{CZ}\,(I\otimes H).
$$
The <Controlled-Z gate> is symmetric in its two wires. Combining this symmetry with $H^2=I$ gives
$$
\begin{aligned}
(H\otimes H)C_{1\to2}(H\otimes H)
&=(H\otimes I)\,\mathrm{CZ}\,(H\otimes I)\\
&=\boxed{C_{2\to1}}.
\end{aligned}
$$
This is an \b[exact operator identity], including its <global phase>, and applies to arbitrary inputs. One can also check it directly from the <orthogonal projectors> $P_b=|b\rangle\langle b|$: conjugating $C_{1\to2}=P_0\otimes I+P_1\otimes X$ by $H\otimes H$ gives
$$
\frac{I+X}{2}\otimes I+\frac{I-X}{2}\otimes Z
=I\otimes P_0+X\otimes P_1=C_{2\to1}.
$$
For the three-wire <quantum circuit>, put $W=H^{\otimes3}$. Conjugation distributes over products because $W^2=I$: $WABW=(WAW)(WBW)$. Each <CNOT gate> in $U_a$ therefore reverses direction, while the <Hadamard gates> on untouched wires cancel. The <Hadamard-conjugated linear oracle> is
$$
\boxed{WU_aW=C_{y\to2}^{\,a_2}C_{y\to1}^{\,a_1}.}
$$
These are the simplified <quantum circuits> in the figure: for $a=00$ there are no gates; for $a=01$ there is $C_{y\to2}$; for $a=10$ there is $C_{y\to1}$; and for $a=11$ there are both. The <ancilla qubit> becomes their common control. On every <computational-basis state>, the entire simplified circuit acts as
$$
|x_1x_2\rangle|b\rangle
\longmapsto
|x_1\oplus ba_1,\ x_2\oplus ba_2\rangle|b\rangle.
$$
Starting the data <qubits> at $|00\rangle$, the prescribed <computational basis> preparation of the <ancilla qubit> must therefore be \b[$|1\rangle$]: it activates the required flips and gives $|a\rangle|1\rangle$. Starting it at $|0\rangle$ instead gives $|00\rangle|0\rangle$ for every $a$, so no information is obtained.
More generally, an initial <ancilla qubit> state $\alpha|0\rangle+\beta|1\rangle$ in this same fixed <quantum circuit> gives
$$
\alpha|00\rangle|0\rangle+\beta|a\rangle|1\rangle.
$$
For nonzero $a$, the desired data output has <probability> $|\beta|^2$, and exact identification for every $a$ requires $\alpha=0$. This condition refers to the displayed <ancilla preparation for the Bernstein-Vazirani algorithm>: the state entering the <function oracle> must be $|-\rangle$, up to <global phase>. Other <quantum state preparation> procedures that deliver this same state are equivalent; $|1\rangle$ is the prescribed input before the first <Hadamard gate>.
For arbitrary $n$, <linearity> of the <linear Boolean function> supplies
$$
U_a=\prod_{j=1}^{n}C_{j\to y}^{\,a_j},
\qquad
H^{\otimes(n+1)}U_aH^{\otimes(n+1)}
=\prod_{j=1}^{n}C_{y\to j}^{\,a_j}.
$$
This decomposition is for analysis: the <Bernstein-Vazirani algorithm> calls the unknown <function oracle> as one supplied operation. The common control starts at $1$, so the simplified <quantum circuit> takes $|0\rangle^{\otimes n}|1\rangle$ to $|a\rangle|1\rangle$. Equivalently, <phase kickback> gives a product state
$$
\frac1{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}(-1)^{a\cdot x}|x\rangle
=\bigotimes_{j=1}^{n}\frac{|0\rangle+(-1)^{a_j}|1\rangle}{\sqrt2},
$$
which the final <Hadamard transform> decodes to $|a\rangle$. Thus \b[one quantum oracle call suffices for every $n\ge1$], compared with $n$ classical calls. This counts <function oracle> uses; the surrounding <Hadamard gates> and final <computational-basis measurement> still act on $n+1$ and $n$ <qubits>, respectively.
Back to article page
