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.^[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]

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 \dots \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}$ :^[2]

\begin{aligned} f (1000 \dots 0_{n}) & = s_{1} \\ f (0100 \dots 0_{n}) & = s_{2} \\ f (0010 \dots 0_{n}) & = s_{3} \\ ⋮ \\ f (0000 \dots 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: ^[2]

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} \overset{H^{\otimes n}}{\to} \frac{1}{\sqrt{2^{n}}} \sum_{x \in {0, 1}^{n}} | x ⟩ \overset{U_{f}}{\to} \frac{1}{\sqrt{2^{n}}} \sum_{x \in {0, 1}^{n}} (- 1)^{f (x)} | x ⟩ \overset{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 if s \oplus y = \vec{0}, 0 otherwise .

Since $s \oplus y = \vec{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. ^[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.

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 $Ω (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 $O (n)$ queries to the problem's oracle, while a PTM must make $Ω (n^{\log n})$ queries to solve the same problem. Therefore, Bernstein-Vazirani provides a super-polynomial separation between BPP and BQP.