Bernstein-Vazirani Algorithm


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.

Hnxn=12ny{0,1}n(1)xyyH^{\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 0n|0\rangle^n

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

Hn0n=12ny{0,1}n(1)xyyH^{\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:

Hn12nx{0,1}nx \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)=sxf(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.

Ufx=12y{0,1}(1)xyyU_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:

Uf12nx{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.

Hn12nx{0,1}n(1)f(x)[12ny{0,1}n(1)xyy]\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

  • 12nxy(1)f(x)+xyy\frac{1}{2^n} \sum_x \sum_y (-1)^{f(x) + x \cdot y} |y \rangle
  • 12nxy(1)xs+xyy\frac{1}{2^n} \sum_x \sum_y (-1)^{ x \cdot s + x \cdot y} |y \rangle
  • 12nxy(1)x(sy)y\frac{1}{2^n} \sum_x \sum_y (-1)^{x \cdot (s \oplus y)} |y \rangle

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

  • As=12nx(1)x0 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


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

0n |0\rangle^n

Hn12nx{0,1}nx \xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1 \}^n} |x \rangle

Uf12nx{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

Hn12ny{0,1}n(1)f(x)+xyy\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.