Here is some personal notes on Bernstein-Vazirani algorithm. Assume that we have a black box that does nothing but compute $latex u \cdot x$, where $latex x$ is an input binary vector and $latex u$ is another binary vector that we don’t know its value. Note that all operation is bit-wise and so the output $latex b=u \cdot x$ is binary also.
The question is how many inquiries are needed for us to figure out the value of $latex u$. Classically, we will essentially need a minimum of $latex n$ inquiries if the length of $latex u$ and $latex x$ is $latex 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 $latex U_f$ from now on). Besides the $latex n$-bit input $latex x$, we will have one additional input $latex b$ which is just a working bit. The output bits of the quantum circuits will include the original $latex n$-bit input $latex x$ and an output bit $latex 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 $latex u$ and pass it through a group of Hadamard gates $latex H^{\otimes n}$, we will have
$latex \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 $latex 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 $latex |00\cdots0\rangle$ and pass it through a group of Hadamard gates $latex H^{\otimes n}$, we will have
$latex |y\rangle=\frac{1}{2^{n/2}}\sum_x |x\rangle$.
Great! Pretty close to our target already. Now, let pass $latex |y\rangle$ through the black box $latex U_f$ along $latex b=|-\rangle=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Therefore the input state is
$latex |y\rangle|-\rangle=\frac{1}{2^{n/2}}\sum_x |x\rangle|-\rangle$.
Now, note that when $latex f(x)=0$, we have the output for the component $latex |x\rangle|-\rangle$ as
$latex |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 $latex |x\rangle|-\rangle$ when $latex f(x)=1$ is
$latex |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
$latex \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 $latex u$. The overall algorithm is shown in the following block diagram (from Prof. Vazirani’s slide).
