1
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ what does close the interference mean? $\endgroup$
    – n22
    Mar 28 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$
    – Mark S
    Mar 28 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.