Tag: Bernstein–Vazirani algorithm

Bernstein–Vazirani Algorithm

The Bernstein–Vazirani algorithm is one of the earliest and clearest examples of a quantum algorithm that significantly outperforms any classical counterpart for a well-defined problem. It can be viewed as an application of the Deutsch-Jozsa algorithm. The algorithm was first introduced by Ethan Bernstein and Umesh Vazirani in their 1993 paper and later discussed again in their 1997 paper. The algorithm treats the following problem:

Fig 1. Umesh Vazirani (photo from this talk). I could not find any photo of Ethan Bernstein online; if you come across one, please email me.

Definition (Bernstein–Vazirani problem): Let f be a function from n-bit strings to a single bit, f:\{0,1\}^n \to \{0,1\}, such that there exists a secret bit string s \in \{0,1\}^n with the property that, for every input x \in \{0,1\}^n, f(x) = x \cdot s, where the dot product is defined by x \cdot s = x_1 s_1 \oplus x_2 s_2 \oplus \cdots \oplus x_n s_n, with x = x_1 x_2 \cdots x_n and s = s_1 s_2 \cdots s_n. The task is to determine the secret string s using as few queries to f as possible.

Exercise. 1. For the 3-bit string s = 011, compute x \cdot s for all x \in \{0,1\}^3. As an example, take x = 001. Then x \cdot s = (0 \times 0) \oplus (0 \times 1) \oplus (1 \times 1) = 1 The function defined by f(x) := x \cdot s is an example of a function satisfying the Bernstein–Vazirani property.

2. Show that the majority function
\mathrm{maj}(x) = \begin{cases} 1, \text{ if majority of bits in } x \text{ are 1} \\ 0, \text{ otherwise} \end{cases}
is a counterexample: it does not satisfy the Bernstein–Vazirani property.

Hint: Any function f(x) = x \cdot s is linear over \mathbf{F}_2, i.e. it obeys

f(x \oplus y) = f(x) \oplus f(y) \quad \text{for all } x, y.

To disprove that \mathrm{maj} has the Bernstein–Vazirani form, find explicit x, y for which

\mathrm{maj}(x \oplus y) \neq \mathrm{maj}(x) \oplus \mathrm{maj}(y).

For instance, take x = 110 and y = 011. Then x \oplus y = 101, while

\mathrm{maj}(110) = 1, \quad \mathrm{maj}(011) = 1, \quad \mathrm{maj}(101) = 1,

so \mathrm{maj}(110) \oplus \mathrm{maj}(011) = 0 \neq 1 = \mathrm{maj}(101), showing the required contradiction. ∎

Classically, we can solve the problem by considering a complete basis of bit strings:

10\cdots 0, \quad 010\cdots 0, \quad \dots, \quad 0\cdots 01.

Fig 2. Quantum circuit for the Bernstein-Vazirani algorithm.

If we query the function f(x) := x \cdot s on these strings, we obtain

10\cdots 0 \cdot s = s_1,

010\cdots 0 \cdot s = s_2,

\vdots

0\cdots 01 \cdot s = s_n.

From this, it is clear that the secret string s can be determined with n queries. Because the n bits of s are independent, there is no way to do better classically. Remarkably, a quantum computer allows us to solve the same problem with far fewer queries.

From the expression
H^{\otimes n} |x\rangle = \frac{1}{\sqrt{2^n}} \sum_{z \in \{0,1\}^n} (-1)^{x \cdot z} |z\rangle,
we observe that an inner product appears in the phase factor (-1)^{x \cdot z}. If we can prepare the corresponding state, applying Hadamard gates directly yields s. This state naturally appears just before the final Hadamard transforms in the Deutsch–Jozsa algorithm(see this post), so the same circuit can be used to solve the Bernstein–Vazirani problem with only a single query.

To implement this, we prepare an n-qubit input register in the state |0\rangle^{\otimes n} and a single auxiliary qubit in the state |1\rangle. Applying Hadamard gates to all n+1 qubits yields

|\psi\rangle = \frac{1}{\sqrt{2^n}} \sum_{x \in {0,1}^n} |x\rangle \otimes \frac{1}{\sqrt{2}} \bigl(|0\rangle - |1\rangle\bigr)

We then apply the quantum oracle U_f encoding f:

U_f \, |x\rangle |y\rangle = |x\rangle \, |y \oplus f(x)\rangle

After acting on |\psi\rangle, the combined state becomes

\frac{1}{\sqrt{2^n}} \sum_{x \in {0,1}^n} (-1)^{f(x)} |x\rangle \otimes \frac{1}{\sqrt{2}} \bigl(|0\rangle - |1\rangle\bigr)

This has been carefully discussed in Deutsch–Jozsa algorithm(see this post).

On the input register, this action is equivalently described by the operator Q_f:

Q_f \frac{1}{\sqrt{2^n}} \sum_{x \in {0,1}^n} |x\rangle = \frac{1}{\sqrt{2^n}} \sum_{x \in {0,1}^n} (-1)^{f(x)} |x\rangle

Recall that f(x) := x \cdot s, then apply quantum oracle Q_f to get

\frac{1}{\sqrt{2^n}} \sum_{x \in {0,1}^n} (-1)^{x \cdot s} |x\rangle

Then applying Hadamard gates H^{\otimes n} will give |s\rangle. By measuring the final state, we can read out s.

The quantum circuit of the Bernstein-Vazirani algorithm is completely the same as that for Deutsch-Jozsa. A simpler version is given in Figure 2 based on Q_f.