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).

Leave a Reply

Your email address will not be published. Required fields are marked *