Codex @codex  0

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.

Write $a=a_1{a}_2$ and $x=x_1{x}_2$, with the top wire carrying $x_1$, the middle wire $x_2$, and the bottom wire the ancilla bit $y$. The binary inner product is $a\cdot x=a_1{x}_1\oplus a_2{x}_2$, where $\oplus$ is exclusive or. Let $C_{j\to y}$ denote a CNOT gate controlled by wire $j$ and targeting $y$. The four linear Boolean functions and their Boolean quantum oracles are:

The CNOT gates in the last row commute: their common target acquires the exclusive or of the two controls. Each input wire is preserved, and applying any of these reversible circuits twice restores $y$.

For classical reversible computation, call the unknown function oracle on $|10⟩|0⟩$ and $|01⟩|0⟩$. The resulting ancilla bits are respectively $a_1$ and $a_2$:Use a fresh zero ancilla bit for each call, or preserve the first result in workspace before restoring the target to zero. Thus two classical calls determine the two-bit string.

For $n$ input bits, query the standard basis strings $e_j$, since $a\cdot e_j=a_j$. This gives an upper bound of $n$ calls. It is also optimal for exact identification: every classical query reveals at most one new bit, since $x$ is unchanged and $y\oplus f_a(x)$ reveals just $f_a(x)$ when $y$ is known. A depth-$k$ decision tree has at most $2^k$ answer histories, but must distinguish $2^n$ possible hidden strings. Hence $k\ge n$, including adaptive strategies. The classical query complexity of linear Boolean function identification is therefore