Bernstein-Vazirani Algorithm

Introduction

Say you have a number. If this number can be multiplied by a number, the quantum computer could 'guess' that number in one try. Counterintuitive right? This is the magic of the Bernstein-Vazirani algorithm. To classical computer scientists, these algorithms completely change algorithm writing. Let's explore a bit more.

Review of notation

∣0⟩|0\rangle and ∣1⟩|1\rangle qubit states correlates to vectors [10]and[01]\begin{bmatrix}1\\0\end{bmatrix} \text{and} \begin{bmatrix}0\\1\end{bmatrix} respectively. When we apply the Hadamard transformation, we apply a matrix multiplication that sends everything into superposition.

We apply a Hadamard transformation. This is a function a complex matrix transformation.

H⊗n∣xn⟩=12n∑y∈{0,1}n(−1)x⋅y∣y⟩H^{\otimes n} \left| x^n \right\rangle = \frac{1}{\sqrt{2^n}} \sum_{y \in \{0,1\}^n} (-1)^{x \cdot y} \left| y \right\rangle

Step 1 - Hadamard Gate

We have a quantum register of nn qubits that all have an initial state of ∣0⟩|0\rangle. Hence, we can represent this as ∣0⟩n|0\rangle^n

Let's apply the Hadamard gate on them using the skeleton formula above.

H⊗n∣0n⟩=12n∑y∈{0,1}n(−1)x⋅y∣y⟩H^{\otimes n} | 0^n \rangle = \frac{1}{\sqrt{2^n}} \sum_{y \in \{0,1\}^n} (-1)^{x \cdot y} |y\rangle

The idea here is to start them at a defined state and throw them into a superposition so that we can take advantage of the superposition of qubits later. This step is written concisely as:

→H⊗n12n∑x∈{0,1}n∣x⟩ \xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1 \}^n} |x \rangle

Step 2 - Unitary

UfU_f is an oracle that transforms ∣x⟩→(−1)f(x)∣x⟩|x\rangle \rightarrow (-1)^{f(x)} |x\rangle where f(x)=s⋅xf(x) = s \cdot x This particular function is special, but you should think of it as a black box that tests the hidden number ss against all the superimposed states of the qubits at once.

Uf∣x⟩=12∑y∈{0,1}(−1)x⋅y∣y⟩U_f \left| x \right\rangle = \frac{1}{\sqrt{2}} \sum_{y \in \{0,1\}} (-1)^{x \cdot y} \left| y \right\rangle

This can be more concisely written as:

→Uf12n∑x∈{0,1}n(−1)f(x)∣x⟩\xrightarrow{U_f} \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1 \}^n} (-1)^{f(x)} |x \rangle

Step 3 - Hadamard Gate

We apply the Hadamard one last time.

→H⊗n12n∑x∈{0,1}n(−1)f(x)[12n∑y∈{0,1}n(−1)x⋅y∣y⟩]\xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}} \sum_{x \in \{0, 1 \}^{n}} (-1)^{f(x)} [ \frac{1}{\sqrt{2^n}} \sum_{y \in \{0,1 \}^n} (-1)^{x \cdot y} |y \rangle ]

This actually now simplifies to just ∣s⟩| s \rangle

  • 12n∑x∑y(−1)f(x)+x⋅y∣y⟩\frac{1}{2^n} \sum_x \sum_y (-1)^{f(x) + x \cdot y} |y \rangle
  • 12n∑x∑y(−1)x⋅s+x⋅y∣y⟩\frac{1}{2^n} \sum_x \sum_y (-1)^{ x \cdot s + x \cdot y} |y \rangle
  • 12n∑x∑y(−1)x⋅(s⊕y)∣y⟩\frac{1}{2^n} \sum_x \sum_y (-1)^{x \cdot (s \oplus y)} |y \rangle

Say y=sy = s. Then s⊕y=0s \oplus y = 0

  • As=12n∑x(−1)x⋅0 A_s = \frac{1}{2^n} \sum_x (-1)^{x \cdot 0}
  • As=12n2nA_s = \frac{1}{2^n} 2^n
  • As=1A_s = 1

Probability of 1 that we measure ∣s⟩|s\rangle.

Circuit equivalent

Find the jupyter notebook here

Summary

Just three steps. Where f(x)=s⋅xf(x) = s \cdot x

∣0⟩n |0\rangle^n

→H⊗n12n∑x∈{0,1}n∣x⟩ \xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1 \}^n} |x \rangle

→Uf12n∑x∈{0,1}n(−1)f(x)∣x⟩\xrightarrow{U_f} \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1 \}^n} (-1)^{f(x)} |x \rangle

→H⊗n12n∑y∈{0,1}n(−1)f(x)+x⋅y∣y⟩\xrightarrow{H^{\otimes n}} \frac{1}{2^n} \sum_{y \in \{0,1 \}^n} (-1)^{f(x) + x \cdot y} |y \rangle

=∣s⟩= |s \rangle

The superposition of being able to multiply any number in at the same time gives us all the information we need to guess the number.

This was part of a mentorship program. Thank you Thilo Scharnhorst for reviewing.