= Bernstein-Vazirani algorithm
{c}
= BV algorithm
{c}
{synonym}
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\rangle^{\otimes n}$ and an <ancilla qubit> at $|1\rangle$, apply a <Hadamard gate> to every wire, query the <function oracle>, and apply the <Hadamard gates> again. The full output is $|a\rangle|1\rangle$.
The mechanism is <Bernstein-Vazirani phase kickback>. The <Pauli X gate> has <eigenvector> $|-\rangle=(|0\rangle-|1\rangle)/\sqrt2$ with <eigenvalue> $-1$. Thus the target flips become relative <quantum phases> on the data, giving
$$
2^{-n/2}\sum_x(-1)^{a\cdot x}|x\rangle
=\bigotimes_{j=1}^{n}\frac{|0\rangle+(-1)^{a_j}|1\rangle}{\sqrt2}.
$$
The final <Hadamard transform> maps this product to $|a\rangle$, 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\ge1$, since without a query the output cannot depend on the unknown string.
Back to article page
