# Bernstein Vazirani Algorithm

Bernstein-Vazirani (BV) is a great example for illustrating the power of constructive and destructive interference in quantum algorithms.

We have access to a black box function that takes as input a binary string, and reutrns a binary bit. We're told that $f(x)$ is a simply multiplication of the given string with some unknown string. Can we find the unknown string?

Mathematically, given an oracle function $f$; $f:{0,1}_{n}→{0,1}$ and $f(x)=s⋅x(mod2)$ we are tasked to find $s$; $s∈{0,1}_{n}$.

## Algorithm

A classical algorithm to find s can do no better than $n$ queries, where $n$ is the number of bits in s. However, BV's algorithm can solve the problem using quantum effects with one query.

All qubits begin in a $∣0⟩$ state. Begin by applying Hadamard gates to the data qubits $(q_{0},…,q_{7})$ in the $∣0⟩$ state to put them in a superposition and provide quantum parallelism. Apply an X gate to $q_{8}$, the target qubit, to put $q_{8}$ in the $∣1⟩$ state, followed by H to enable phase kickback.

Next we'll query our 'black-box' function $f$. What this step essentially does is query all the possible combinations of $q_{1},…,q_{7}$ in one step, with $q_{8}$ allowing the entanglement of the data qubits with the target qubits and constructively interfering the state $s$ that is desired while destructively interfering all the other incorrect $s$ states.

Finally, we'll apply Hadamard gates to the data qubits to return from the ${∣+⟩,∣−⟩}$ basis to the ${∣0⟩,∣1⟩}$ basis and measure the result.

Thanks to the interference the result is exactly $s$.