= Hadamard-conjugated linear oracle
{c}
{title2=$H^{\otimes(n+1)}U_aH^{\otimes(n+1)}$}
Let $U_a|x\rangle|b\rangle=|x\rangle|b\oplus(a\cdot x)\rangle$ be the <Boolean quantum oracle> for a <linear Boolean function>, and put $W=H^{\otimes(n+1)}$. The <CNOT gates> $C_{j\to y}^{a_j}$ implement $U_a$, where the data wires control the <ancilla qubit>. <CNOT control reversal in the Hadamard basis> and $W^2=I$ imply the exact <unitary operator> identity
$$
WU_aW=\prod_{j=1}^{n}C_{y\to j}^{a_j},
\qquad
WU_aW|x\rangle|b\rangle=|x\oplus ba\rangle|b\rangle.
$$
Here $\oplus$ on strings is <bitwise exclusive or>. To conjugate a product, insert $W^2=I$ between its factors; each factor reverses its control and target, and the unused <Hadamard gates> cancel. The <global phase> is exactly $1$. In particular, the identity holds on arbitrary <quantum superpositions>, not only on the initialized inputs of the <Bernstein-Vazirani algorithm>.
Back to article page
