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 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\^n\rightarrow \$ in which $f(x)$ is promised to be the dot product between $x$ and a secret string $s \in \^n$ modulo 2, $f(x) = x \cdot s = x_1s_1 \oplus x_2s_2 \oplus \cdots \oplus x_ns_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^$ for all $i \in \$:

: $\begin f(1000\cdots0_n) & = s_1 \\ f(0100\cdots0_n) & = s_2 \\ f(0010\cdots0_n) & = s_3 \\ & \,\,\,\vdots \\ f(0000\cdots1_n) & = s_n \\ \end$

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^$ to get

:$\frac\sum_^ , x\rangle.$

Next, apply the oracle $U_f$ which transforms $, x\rangle \to (-1)^, 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, x\rangle$. ($\oplus$ denotes addition mod two.) This transforms the superposition into

:$\frac\sum_^ (-1)^ , 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 ($\$) is performed on the qubits.

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

: $, 0\rangle^n \xrightarrow \frac \sum_ , x\rangle \xrightarrow \frac\sum_(-1)^, x\rangle \xrightarrow \frac \sum_(-1)^, y\rangle = , s\rangle$

The reason that the last state is $, s\rangle$ is because, for a particular $y$,
: $\frac\sum_(-1)^ = \frac\sum_(-1)^ = \frac\sum_(-1)^ = 1 \text s \oplus y = \vec,\, 0 \text.$
Since $s \oplus y = \vec$ 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$.

See also

* Hidden Linear Function problem

References

{{DEFAULTSORT:Bernstein-Vazirani algorithm
Quantum algorithms

Quantum complexity theory

Computational complexity theory