Bernstein Vazirani Algorithm

Published by strangeworks (01/22/2021)

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)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 ff; f:{0,1}n→{0,1}f:\{0,1\}^n \to \{0,1\} and f(x)=s⋅x (mod 2)f(x) = s \cdot x \ (\rm{mod}\ 2) we are tasked to find ss; s∈{0,1}ns \in \{0,1\}^n.

Algorithm

A classical algorithm to find s can do no better than nn​ queries, where nn​ 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⟩\lvert 0 \rangle​ state. Begin by applying Hadamard gates to the data qubits (q0,…,q7)(q_0, \ldots, q_7)​ in the ∣0⟩\lvert 0 \rangle​ state to put them in a superposition and provide  quantum parallelism. Apply an X gate to q8q_8​, the target qubit, to put q8q_8​ in the ∣1⟩\lvert 1 \rangle​ state, followed by H to enable phase kickback. 

Next we'll query our 'black-box' function ff​. What this step essentially does is query all the possible combinations of q1,…,q7q_1,\ldots,q_7​ in one step, with q8q_8​ allowing the entanglement of the data qubits with the target qubits and constructively interfering the state ss​ that is desired while destructively interfering all the other incorrect ss​ states.

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

Thanks to the interference the result is exactly ss​.

References

Example taken from here and here.