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