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.^[1] 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.^[2] The Bernstein–Vazirani algorithm was designed to prove an oracle separation between complexity classes BQP and BPP.^[1]

Given an oracle that implements a function ${\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}${\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}} in which ${\displaystyle f(x)}${\displaystyle f(x)} is promised to be the dot product between ${\displaystyle x}${\displaystyle x} and a secret string ${\displaystyle s\in \{0,1\}^{n}}${\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}}${\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}${\displaystyle s}.

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

${\displaystyle {\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}}}${\displaystyle {\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 ${\displaystyle n}${\displaystyle n} queries of the function to find ${\displaystyle s}${\displaystyle s}, only one query is needed using quantum computing. The quantum algorithm is as follows: ^[2]

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

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

Next, apply the oracle ${\displaystyle U_{f}}${\displaystyle U_{f}} which transforms ${\displaystyle |x\rangle \to (-1)^{f(x)}|x\rangle }${\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 }${\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 {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}|x\rangle }. (${\displaystyle \oplus }${\displaystyle \oplus } denotes addition mod two.) This transforms the superposition into

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle .}${\displaystyle {\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 ${\displaystyle s_{i}=1}${\displaystyle s_{i}=1}, its state is converted from ${\displaystyle |-\rangle }${\displaystyle |-\rangle } to ${\displaystyle |1\rangle }${\displaystyle |1\rangle } and for qubits where ${\displaystyle s_{i}=0}${\displaystyle s_{i}=0}, its state is converted from ${\displaystyle |+\rangle }${\displaystyle |+\rangle } to ${\displaystyle |0\rangle }${\displaystyle |0\rangle }. To obtain ${\displaystyle s}${\displaystyle s}, a measurement in the standard basis (${\displaystyle \{|0\rangle ,|1\rangle \}}${\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}}${\displaystyle H^{\otimes n}} denotes the Hadamard transform on ${\displaystyle n}${\displaystyle n} qubits:

${\displaystyle |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 }${\displaystyle |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 ${\displaystyle |s\rangle }${\displaystyle |s\rangle } is because, for a particular ${\displaystyle y}${\displaystyle y},

${\displaystyle {\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}}.}${\displaystyle {\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 ${\displaystyle s\oplus y={\vec {0}}}${\displaystyle s\oplus y={\vec {0}}} is only true when ${\displaystyle s=y}${\displaystyle s=y}, this means that the only non-zero amplitude is on ${\displaystyle |s\rangle }${\displaystyle |s\rangle }. So, measuring the output of the circuit in the computational basis yields the secret string ${\displaystyle s}${\displaystyle s}.

A generalization of Bernstein–Vazirani problem has been proposed that involves finding one or more secret keys using a probabilistic oracle. ^[3] 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.

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 ${\displaystyle O(1)}${\displaystyle O(1)} queries to the problem's oracle, but for which any Probabilistic Turing machine (PTM) algorithm must make ${\displaystyle \Omega (n)}${\displaystyle \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.^{[1] [4]} The resulting decision problem is solvable by a QTM with ${\displaystyle O(n)}${\displaystyle O(n)} queries to the problem's oracle, while a PTM must make ${\displaystyle \Omega (n^{\log n})}${\displaystyle \Omega (n^{\log n})} queries to solve the same problem. Therefore, Bernstein-Vazirani provides a super-polynomial separation between BPP and BQP.

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.

• Hidden Linear Function problem
• Simon's problem

• Quantum algorithms
• Quantum complexity theory
• Computational complexity theory

• CS1 maint: multiple names: authors list
• CS1: long volume value
• Articles with short description
• Short description matches Wikidata