In the Bernstein-Vazirani algorithm, what is the use of the second Hadamard gate? What happens if I remove it? Would the algorithm works fine? I read something about it closing the interference.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
After application of the oracle but before the application of the second Hadamard gates, the register is in the state:
$$\frac{1}{\sqrt{2^{n}}}\sum_{x=0}^{2^n-1} (-1)^{f(x)} |x\rangle.$$
Although the phase $(-1)^{f(x)}$ is correct, the the probability (the squared amplitude) is uniformly distributed over each basis state. Thus without the second Hadamard gates you would not learning anything about $f(x)$, and your algorithm would not work.
The second Hadamard gates do indeed "close the interference".
answered Mar 27, 2022 at 14:23
-
$\begingroup$ what does close the interference mean? $\endgroup$– n22Commented Mar 28, 2022 at 17:15
-
$\begingroup$ I copied that from your question; I'd not heard the term before but it seems like a nice way to say that the second Hadamard gates allow for constructive and destructive interference of the phases. $\endgroup$ Commented Mar 28, 2022 at 18:29