Bernstein-Vazirani Algorithm

Here is some personal notes on Bernstein-Vazirani algorithm. Assume that we have a black box that does nothing but compute $u \cdot x$, where $x$ is an input binary vector and $u$ is another binary vector that we don’t know its value. Note that all operation is bit-wise and so the output $b=u \cdot x$ is binary also.

The question is how many inquiries are needed for us to figure out the value of $u$. Classically, we will essentially need a minimum of $n$ inquiries if the length of $u$ and $x$ is $n$. However, only one inquiry is necessary if we are considering quantum circuit instead!

Since all quantum circuits are reversible, we need to modify our black box a little bit (let us denote it as $U_f$ from now on). Besides the $n$-bit input $x$, we will have one additional input $b$ which is just a working bit. The output bits of the quantum circuits will include the original $n$-bit input $x$ and an output bit $b\oplus f(x)$ as shown in the figure below (from Prof. Vazirani’s slide). From our previous post on Hadamard gates, if we know $u$ and pass it through a group of Hadamard gates $H^{\otimes n}$, we will have $\frac{1}{2^{n/2}}\sum_x -1^{u\cdot x}|x\rangle=\frac{1}{2^{n/2}}\sum_x -1^{f(x)}|x\rangle$.

Since Hadamard gates are reversible, we can get back $u$ from the above also. Therefore, we will change our objective to trying to construct the above state.

Now, if we have a group of zero states $|00\cdots0\rangle$ and pass it through a group of Hadamard gates $H^{\otimes n}$, we will have $|y\rangle=\frac{1}{2^{n/2}}\sum_x |x\rangle$.

Great! Pretty close to our target already. Now, let pass $|y\rangle$ through the black box $U_f$ along $b=|-\rangle=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Therefore the input state is $|y\rangle|-\rangle=\frac{1}{2^{n/2}}\sum_x |x\rangle|-\rangle$.

Now, note that when $f(x)=0$, we have the  output for the component $|x\rangle|-\rangle$ as $|x\rangle|-\oplus 0\rangle=\frac{1}{\sqrt{2}}(|x\rangle|0\rangle-|x\rangle|1\rangle)=|x\rangle|-\rangle$

and the output for the component $|x\rangle|-\rangle$ when $f(x)=1$ is $|x\rangle|-\oplus 1\rangle=\frac{1}{\sqrt{2}}(|x\rangle|1\rangle-|x\rangle|0\rangle)=-|x\rangle|-\rangle$.

In summary, we have the output state equal to $\frac{1}{2^{n/2}}\sum_x -1^{f(x)}|x\rangle|-\rangle$

as desired. Now we can pass this state through a group of Hadamard gates again and we will get back $u$. The overall algorithm is shown in the following block diagram (from Prof. Vazirani’s slide). 