Bernstein-Vazirani algorithm

The Bernstein-Vazirani algorithm identifies the coefficient string of a linear Boolean function with one Boolean quantum oracle call. It contrasts with the $n$ calls required by the classical query complexity of linear Boolean function identification. Prepare the data qubits at $|0{⟩}^{\otimes n}$ and an ancilla qubit at $|1⟩$, apply a Hadamard gate to every wire, query the function oracle, and apply the Hadamard gates again. The full output is $|a⟩|1⟩$.

The mechanism is Bernstein-Vazirani phase kickback. The Pauli X gate has eigenvector $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$ with eigenvalue $-1$. Thus the target flips become relative quantum phases on the data, givingThe final Hadamard transform maps this product to $|a⟩$, so computational-basis measurement recovers every coefficient with certainty. The ancilla preparation for the Bernstein-Vazirani algorithm ensures the required minus sign, and the Hadamard-conjugated linear oracle gives an exact quantum circuit interpretation. One query is optimal for $n\ge 1$, since without a query the output cannot depend on the unknown string.

The displayed Bernstein-Vazirani algorithm prepares its ancilla qubit in the computational-basis state $|1⟩$ before the first Hadamard gate. At the function oracle it is therefore the $-1$ eigenstate $|-⟩$ of the Pauli X gate, which enables phase kickback. Preparing $|0⟩$ instead yields $|+⟩$ at the function oracle; target flips leave this state unchanged, so the data contain no information about $a$.

The Hadamard-conjugated linear oracle makes the more general statement transparent. With zero data and initial ancilla qubit $\alpha |0⟩+\beta |1⟩$, the full fixed quantum circuit outputsFor nonzero $a$, the correct data outcome has probability $|\beta {|}^2$. To obtain exact identification for all $a$, this preparation must have $\alpha =0$, so it is $|1⟩$ up to global phase. This is a condition on the prescribed preparation circuit: any alternative quantum state preparation that supplies $|-⟩$ at the function oracle is equivalent.

Let $U_a|x⟩|b⟩=|x⟩|b\oplus (a\cdot x)⟩$ 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 identityHere $\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.