Bernstein–Vazirani algorithm

thumb

The Bernstein–Vazirani algorithm, which solves the Bernstein–Vazirani problem, is a quantum algorithm invented by Ethan Bernstein and Umesh Vazirani in 1997.

{{cite journal

| author = Ethan Bernstein and Umesh Vazirani

| title = Quantum Complexity Theory

| journal = SIAM Journal on Computing

| volume = 26

| issue = 5

| pages = 1411–1473

| year = 1997

| doi = 10.1137/S0097539796300921

}}

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_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^{i}$ for all $i \in \{0, 1, \dots, n-1\}$ :

{{cite journal

| author = S D Fallek, C D Herold, B J McMahon, K M Maller, K R Brown, and J M Amini

| title = Transport implementation of the Bernstein–Vazirani algorithm with ion qubits

| journal = New Journal of Physics

| volume = 18

| year = 2016

| doi = 10.1088/1367-2630/aab341

| doi-access = free

| arxiv = 1710.01378

}}

: $\begin{align}
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{align}$

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.

{{cite journal

| author = Alok Shukla and Prakash Vedula

| title = A generalization of Bernstein--Vazirani algorithm with multiple secret keys and a probabilistic oracle

| journal = Quantum Information Processing

| volume = 22:244

| issue = 6

| pages = 1-18

| year = 2023

| doi = 10.1007/s11128-023-03978-3

| arxiv = 2301.10014

}}

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.{{cite web

| url = https://courses.cs.washington.edu/courses/cse599d/06wi/lecturenotes7.pdf

| archive-url = https://web.archive.org/web/20241201172704/https://courses.cs.washington.edu/courses/cse599d/06wi/lecturenotes7.pdf

| archive-date = 2024-12-01

| title = CSE 599d - Quantum Computing The Recursive and Nonrecursive Bernstein-Vazirani Algorithm

| last = Bacon

| first = Dave

| date = 2006

| access-date = 2025-01-17}}

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.