5.2.4 Bernstein-Vazirani algorithm

Above, we discussed how to use the Hadamard transform to solve an interesting problem. Given a function $f\colon\{0,1\}^{n}\to\{0,1\}$ and the promise that $f$ is either constant or balanced, the Deutsch-Jozsa algorithm was able to determine which of these two options was the case.

In this section we will discuss another interesting problem that one can solve by a slight variant of the same procedure. As before, we will start with a promise about the unknown function $f$ that we are dealing with. This time, instead of assuming that it is constant or balanced, we will assume that it is of the following special form:

where $a_{1},\dots,a_{n}\in\{0,1\}$ is some fixed bitstring that defines the function.

If $n=1$ then there are only two such functions:

• •
  ​

  $f(x_{1})=0$, corresponding to $a_{1}=0$, and

• •
  ​

  $f(x_{1})=x_{1}$, corresponding to $a_{1}=1$.

If $n=2$ then there are already four such functions:

• •
  ​

  $f(x_{1},x_{2})=0$, corresponding to $[a_{1},a_{2}]=[0,0]$,

• •
  ​

  $f(x_{1},x_{2})=x_{2}$, corresponding to $[a_{1},a_{2}]=[0,1]$,

• •
  ​

  $f(x_{1},x_{2})=x_{1}$, corresponding to $[a_{1},a_{2}]=[1,0]$, and

• •
  ​

  $f(x_{1},x_{2})=x_{1}\oplus x_{2}$, corresponding to $[a_{1},a_{2}]=[1,1]$.

Note that each of these functions computes the sum modulo two of some subset of the variables $x_{i}$. Which subset? Whenever $a_{i}=1$, the corresponding variable $x_{i}$ is included in the subset.

In general, there are $2^{n}$ choices of the bitstring $a_{1},\dotsc,a_{n}$ and hence $2^{n}$ functions $f$ of the special form (5.14). In fact, we may think of Eq. 5.14 as a way of hiding the bitstring

in the function $f$. How many evaluations of the function do we need to uncover it? Since

we conclude that $n$ evaluations of the function $f$ are certainly enough. For any classical algorithm, this is also optimal: each time you evaluate the function you only learn a single bit. Since the unknown bits $a_{1},\dots,a_{n}$ are completely arbitrary and there are $n$ of them, you need to evaluate the function at least $n$ times to learn them all.

We will now see that we can do much better using a quantum algorithm. To start, let us compute how the sign oracle for the function in Eq. 5.14 acts on the basis states:

In the second step we used that $(-1)^{a}$ only depends on $a$ modulo two (i.e., on whether $a$ is even or odd), so it does not matter whether we use addition modulo 2 (‘$\oplus$’) or the ordinary addition. How can this sign oracle be implemented? We do not really care, since our algorithm will treat the oracle as a black box. But since it is a nice exercise, you can try to figure this out in the following problem.

We now present the Bernstein-Vazirani algorithm, which uncovers the hidden bitstring $[a_{1},\dots,a_{n}]$ using a single evaluation of the sign oracle for $f$:

1. 1.
   ​

   Start with $\left|0\dots 0\right\rangle$.

2. 2.
   ​

   Apply the Hadamard transform $H\otimes\dotsb\otimes H$.

3. 3.
   ​

   Apply the sign oracle $O_{f}$ corresponding to the function $f$.

4. 4.
   ​

   Apply the Hadamard transform $H\otimes\dotsb\otimes H$ again.

5. 5.
   ​

   Measure all qubits. The measurement outcome is precisely the bitstring $[a_{1},\dots,a_{n}]$.

The algorithm is identical to the Deutsch-Jozsa algorithm in Section 5.2.3 except for the last step, which is even simpler.