Bernstein–Vazirani algorithm

Short description: Quantum 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:\{0,1{\}}^n\to \{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,...,n-1\}$:

$\begin{array}{rl}f(1000\cdots 0_n)& =s_1\\ f(0100\cdots 0_n)& =s_2\\ f(0010\cdots 0_n)& =s_3\\ & ⋮\\ f(0000\cdots 1_n)& =s_n\\ \end{array}$

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{⟩}^{\otimes n}$ to get

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

Next, apply the oracle $U_f$ which transforms $|x⟩\to (-1{)}^{f(x)}|x⟩$. This can be simulated through the standard oracle that transforms $|b⟩|x⟩\to |b\oplus f(x)⟩|x⟩$ by applying this oracle to $\frac{|0⟩-|1⟩}{\sqrt{2}}|x⟩$. ($\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⟩.$

Another Hadamard transform is applied to each qubit which makes it so that for qubits where $s_i=1$, its state is converted from $|-⟩$ to $|1⟩$ and for qubits where $s_i=0$, its state is converted from $|+⟩$ to $|0⟩$. To obtain $s$, a measurement in the standard basis ($\{|0⟩,|1⟩\}$) 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{⟩}^n\stackrel{H^{\otimes n}}{\to }\frac{1}{\sqrt{2^n}}\sum _{x\in \{0,1{\}}^n}|x⟩\stackrel{U_f}{\to }\frac{1}{\sqrt{2^n}}\sum _{x\in \{0,1{\}}^n}(-1{)}^{f(x)}|x⟩\stackrel{H^{\otimes n}}{\to }\frac{1}{2^n}\sum _{x,y\in \{0,1{\}}^n}(-1{)}^{f(x)+x\cdot y}|y⟩=|s⟩$

The reason that the last state is $|s⟩$ 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=\overrightarrow{0},0\text{ otherwise}.$

Since $s\oplus y=\overrightarrow{0}$ is only true when $s=y$, this means that the only non-zero amplitude is on $|s⟩$. 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.

See also

• Hidden Linear Function problem