Bernstein-Vazirani Algorithm

Part of Womanium Quantum + AI 2024 program

Definition

Bernstein-Vazirani algorithm is another algorithm that proves the quantum advantage and not designed to be practically effective for a specific task.

Problem

Let's define $f$ as a function such that

\begin{matrix} f : {0, 1}^{n} \to {0, 1} \\ f (x) = x \cdot s \end{matrix}

Where $x \cdot s$ is the inner product of $x$ and $s$ , such that

x \cdot s = (x_{0} . s_{0} + x_{1} . s_{1} + \dots + x_{n - 1} . s_{n - 1}) (\mod 2)

The goal is to query $f$ to find the secret string $s$ .

Classically, we would need $n$ queries of $f$ , where $n$ is the length of the string $s$ . Each query will be a string of zeros except for one bit at position $i$ , this will let us know the value of $s_{i}$ , doing this $n$ times will give us all of the bits of $s$ .

Bernstein-Vazirani Algorithm

The algorithm is very similar to Deutsch-Jozsa Algorithm, except for the oracle used.

We start applying the algorithm from the initial state ${| 0 ⟩}^{\otimes n} | 0 ⟩$

\begin{aligned} {| 0 ⟩}^{\otimes n} | 0 ⟩ & \overset{I \otimes X}{\to} {| 0 ⟩}^{\otimes n} | 1 ⟩ \\ \overset{H^{\otimes n} H}{\to} \frac{1}{\sqrt{N}} \sum_{x \in {0, 1}^{n}} | x ⟩ \otimes | - ⟩ \\ \overset{U_{f}}{\to} \frac{1}{\sqrt{N}} \sum_{x \in {0, 1}^{n}} U_{f} | x ⟩ \otimes | - ⟩ \\ = \frac{1}{\sqrt{N}} \sum_{x \in {0, 1}^{n}} (- 1)^{f (x)} | x ⟩ \otimes | - ⟩ \\ = \frac{1}{\sqrt{N}} \sum_{x \in {0, 1}^{n}} (- 1)^{x \cdot s} | x ⟩ \otimes | - ⟩ \end{aligned}

Now we discard of the ancilla qubit and continue to apply the Hadamard gates.

\begin{aligned} ∴ \frac{1}{\sqrt{N}} \sum_{x \in {0, 1}^{n}} (- 1)^{x \cdot s} | x ⟩ \otimes | - ⟩ \to \frac{1}{\sqrt{N}} \sum_{x \in {0, 1}^{n}} (- 1)^{x \cdot s} | x ⟩ \\ \overset{H^{\otimes n}}{\to} \frac{1}{\sqrt{N}} \sum_{x \in {0, 1}^{n}} \frac{1}{\sqrt{N}} \sum_{z \in {0, 1}^{n}} (- 1)^{x \cdot z + x \cdot s} | z ⟩ \\ = \frac{1}{N} \sum_{x \in {0, 1}^{n}} \sum_{z \in {0, 1}^{n}} (- 1)^{x \cdot z + x \cdot s} | z ⟩ \end{aligned}

Now, let's look at the state where $z = s$ , if we were able to get this then it will be the final answer.

\begin{aligned} ∴ \frac{1}{N} \sum_{x \in {0, 1}^{n}} \sum_{z \in {0, 1}^{n}} (- 1)^{x \cdot z + x \cdot s} | z ⟩ \\ \overset{z = s}{↪} \frac{1}{N} \sum_{x \in {0, 1}^{n}} (- 1)^{x \cdot s + x \cdot s} \\ = \frac{1}{N} \sum_{x \in {0, 1}^{n}} (- 1)^{2 (x \cdot s)} \end{aligned}

But we know that:

(- 1)^{2 (i)} = 1, i \in Z

\begin{aligned} ∴ \frac{1}{N} \sum_{x \in {0, 1}^{n}} (- 1)^{2 (x \cdot s)} \\ = \frac{1}{N} \sum_{x \in {0, 1}^{n}} 1 \\ = \frac{1}{N} N = \frac{N}{N} = 1 \end{aligned}

Therefore, we know that after applying the algorithm we will measure the string $s$ with a probability of 100%.

Conclusion

Bernstein-Vazirani algorithm is another algorithm that proves the special advantage that quantum computers posses.

Its problem define a function that uses a secret string to apply an inner product with the input then give a 1 bit result. The algorithm shows how we can find the value of the secret string in one query of the function, where after the algorithm we will measure the value of the secret string.

Practicality

The problem for Bernstein-Vazirani algorithm was specially tailored to show the quantum advantage and it doesn't have an effective practical use.

< Prev | Next: Simon's Algorithm >