Bernstein–Vazirani algorithm

The Bernstein–Vazirani algorithm, which solves the Bernstein–Vazirani problem is a quantum algorithm invented by Ethan Bernstein and Umesh Vazirani in 1992. It's 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.

Problem statement

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

Algorithm

Classically, the most efficient method to find the secret string is by evaluating the function $n$ times where $x=2^{i}$, $i\in \{0,1,...,n-1\}$

${\begin{aligned}f(1000\cdots 0_{n})&=s_{1}\\f(0100\cdots 0_{n})&=s_{2}\\f(0010\cdots 0_{n})&=s_{3}\\&\,\,\,\vdots \\f(0000\cdots 1_{n})&=s_{n}\\\end{aligned}}$

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

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

${\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}|x\rangle .$

Perform a controlled negation of every state in the superposition generated by the previous Hadamard transformation for which the oracle when applied to this state returns 1. This transforms the superposition into

${\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle .$

Another Hadamard transform is applied to each qubit which makes it so that for qubits where $s_{i}=1$, its state is converted from $|-\rangle$ to $|1\rangle$ and for qubits where $s_{i}=0$, its state is converted from $|+\rangle$ to $|0\rangle$.

To obtain $s$, a measurement on the Standard basis ($\{|0\rangle ,|1\rangle \}$) is performed on the qubits. Graphically algorithm may be represented by the following diagram:

Scheme of the algorithm

Where $H^{\otimes n}$ is the Hadamard transform.

See also

• Hidden Linear Function problem