The Bernstein–Vazirani algorithm, which solves the Bernstein–Vazirani problem, is a quantum algorithm invented by Ethan Bernstein and Umesh Vazirani in 1997. It is a restricted version of the Deutsch–Jozsa algorithm where instead of distinguishing between two different classes of functions, it tries to learn a string encoded in a function. The Bernstein–Vazirani algorithm was designed to prove an oracle separation between complexity classes BQP and BPP.

Given an oracle that implements a function ${\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}$ in which ${\displaystyle f(x)}$ is promised to be the dot product between ${\displaystyle x}$ and a secret string ${\displaystyle s\in \{0,1\}^{n}}$ modulo 2, ${\displaystyle f(x)=x\cdot s=x_{1}s_{1}\oplus x_{2}s_{2}\oplus \cdots \oplus x_{n}s_{n}}$, find ${\displaystyle s}$.

Classically, the most efficient method to find the secret string is by evaluating the function ${\displaystyle n}$ times with the input values ${\displaystyle x=2^{i}}$ for all ${\displaystyle i\in \{0,1,\dots ,n-1\}}$:

In contrast to the classical solution which needs at least ${\displaystyle n}$ queries of the function to find ${\displaystyle s}$, only one query is needed using quantum computing. The quantum algorithm is as follows:

Apply a Hadamard transform to the ${\displaystyle n}$ qubit state ${\displaystyle |0\rangle ^{\otimes n}}$ to get

Next, apply the oracle ${\displaystyle U_{f}}$ which transforms ${\displaystyle |x\rangle \to (-1)^{f(x)}|x\rangle }$. This can be simulated through the standard oracle that transforms ${\displaystyle |b\rangle |x\rangle \to |b\oplus f(x)\rangle |x\rangle }$ by applying this oracle to ${\displaystyle {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}|x\rangle }$. (${\displaystyle \oplus }$ denotes addition mod two.) This transforms the superposition into

Another Hadamard transform is applied to each qubit which makes it so that for qubits where ${\displaystyle s_{i}=1}$, its state is converted from ${\displaystyle |-\rangle }$ to ${\displaystyle |1\rangle }$ and for qubits where ${\displaystyle s_{i}=0}$, its state is converted from ${\displaystyle |+\rangle }$ to ${\displaystyle |0\rangle }$. To obtain ${\displaystyle s}$, a measurement in the standard basis (${\displaystyle \{|0\rangle ,|1\rangle \}}$) is performed on the qubits.

Graphically, the algorithm may be represented by the following diagram, where ${\displaystyle H^{\otimes n}}$ denotes the Hadamard transform on ${\displaystyle n}$ qubits: