 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⟩$ by $-1$ and fixes the other computational-basis states. Since $HXH=Z$,The Controlled-Z gate is symmetric in its two wires. Combining this symmetry with $H^2=I$ givesThis is an 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⟩⟨b|$: conjugating $C_{1\to 2}=P_0\otimes I+P_1\otimes X$ by $H\otimes H$ gives

For the three-wire quantum circuit, put $W=H^{\otimes 3}$. 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 isThese are the simplified quantum circuits in the figure: for $a=00$ there are no gates; for $a=01$ there is $C_{y\to 2}$; for $a=10$ there is $C_{y\to 1}$; and for $a=11$ there are both. The ancilla qubit becomes their common control. On every computational-basis state, the entire simplified circuit acts asStarting the data qubits at $|00⟩$, the prescribed computational basis preparation of the ancilla qubit must therefore be $|1⟩$: it activates the required flips and gives $|a⟩|1⟩$. Starting it at $|0⟩$ instead gives $|00⟩|0⟩$ for every $a$, so no information is obtained.

More generally, an initial ancilla qubit state $\alpha |0⟩+\beta |1⟩$ in this same fixed quantum circuit givesFor 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 $|-⟩$, up to global phase. Other quantum state preparation procedures that deliver this same state are equivalent; $|1⟩$ is the prescribed input before the first Hadamard gate.

For arbitrary $n$, linearity of the linear Boolean function suppliesThis 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{⟩}^{\otimes n}|1⟩$ to $|a⟩|1⟩$. Equivalently, phase kickback gives a product statewhich the final Hadamard transform decodes to $|a⟩$. Thus one quantum oracle call suffices for every $n\ge 1$, 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.