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

The question is how many inquiries are needed for us to figure out the value of . Classically, we will essentially need a minimum of inquiries if the length of and is . 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 from now on). Besides the -bit input , we will have one additional input which is just a working bit. The output bits of the quantum circuits will include the original -bit input and an output bit as shown in the figure below (from Prof. Vazirani’s slide).

From our previous post on Hadamard gates, if we know and pass it through a group of Hadamard gates , we will have

.

Since Hadamard gates are reversible, we can get back 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 and pass it through a group of Hadamard gates , we will have

.

Great! Pretty close to our target already. Now, let pass through the black box along . Therefore the input state is

.

Now, note that when , we have the output for the component as

and the output for the component when is

.

In summary, we have the output state equal to

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