# 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 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.

## Problem statement

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

## Algorithm

Classically, the most efficient method to find the secret string is by evaluating the function $n$ times with the input values $x=2^{i}$ for all $i\in \{0,1,\dots ,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 .$
Next, apply the oracle $U_{f}$ which transforms $|x\rangle \to (-1)^{f(x)}|x\rangle$. This can be simulated through the standard oracle that transforms $|b\rangle |x\rangle \to |b\oplus f(x)\rangle |x\rangle$ by applying this oracle to ${\frac {|0\rangle -|1\rangle }{\sqrt {2}}}|x\rangle$. ($\oplus$ denotes addition mod two.) 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 in the standard basis ($\{|0\rangle ,|1\rangle \}$) is performed on the qubits.
Graphically, the algorithm may be represented by the following diagram, where $H^{\otimes n}$ denotes the Hadamard transform on $n$ qubits:
    $|0\rangle ^{n}\xrightarrow {H^{\otimes n}} {\frac {1}{\sqrt {2^{n}}}}\sum _{x\in \{0,1\}^{n}}|x\rangle \xrightarrow {U_{f}} {\frac {1}{\sqrt {2^{n}}}}\sum _{x\in \{0,1\}^{n}}(-1)^{f(x)}|x\rangle \xrightarrow {H^{\otimes n}} {\frac {1}{2^{n}}}\sum _{x,y\in \{0,1\}^{n}}(-1)^{f(x)+x\cdot y}|y\rangle =|s\rangle$
The reason that the last state is $|s\rangle$ is because, for a particular $y$,
    ${\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{f(x)+x\cdot y}={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{x\cdot s+x\cdot y}={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{x\cdot (s\oplus y)}=1{\text{ if }}s\oplus y={\vec {0}},\,0{\text{ otherwise}}.$
Since $s\oplus y={\vec {0}}$ is only true when $s=y$, this means that the only non-zero amplitude is on $|s\rangle$. So, measuring the output of the circuit in the computational basis yields the secret string $s$.
A generalization of Bernstein–Vazirani problem has been proposed that involves finding one or more secret keys using a probabilistic oracle.
This is an interesting problem for which a quantum algorithm can provide efficient solutions with certainty or with a high degree of confidence, while classical algorithms completely fail to solve the problem in the general case.

## Classical vs. quantum complexity

The Bernstein-Vazirani problem is usually stated in its non-decision version. In this form, it is an example of a problem solvable by a Quantum Turing machine (QTM) with $O(1)$ queries to the problem's oracle, but for which any Probabilistic Turing machine (PTM) algorithm must make $\Omega (n)$ queries.
To provide a separation between BQP and BPP, the problem must be reshaped into a decision problem (as these complexity classes refer to decision problems). This is accomplished with a recursive construction and the inclusion of a second, random oracle. The resulting decision problem is solvable by a QTM with $O(n)$ queries to the problem's oracle, while a PTM must make $\Omega (n^{\log n})$ queries to solve the same problem. Therefore, Bernstein-Vazirani provides a super-polynomial separation between BPP and BQP.

## Bernstein-Vazirani algorithm Qiskit implementation

The quantum circuit shown here is from a simple example of how the Bernstein-Vazirani algorithm can be implemented in Python using Qiskit, an open-source quantum computing software development framework by IBM.