It is known that both algorithms use the same gates: $H^{\oplus n}U_fH^{\oplus n}$.

After the circuit, the qubits are in the state $\sum_y \left( \sum_x (-1)^{f(x)+xy} \right) |y\rangle $.

In DJ's algorithm, one measures the amplitude of $|0\rangle^{\oplus n}$. It can only be $0$ or $\pm 1$, and the function is balanced iff it is 0 (for any balanced or constant function).

In Bernstein-Vazirani, one measures every qubit in its $Z$ basis and deduces the bits of the dot-product function.

It seems that one can apply Bernstein-Vazirani to any balanced or constant function (not just a dot-product function) to get a bit vector, and state that the function is constant iff the vector is zero.

What seems strange to me is that all the vector returned by BV for a DJ input is not necessarily all zero or all one, so I don't understand the criterion.

How are the measurements of each qubit and of the state $|0\rangle^{\oplus n}$ related?

  • 1
    $\begingroup$ Welcome on the site! It is "Deutsch-Jozsa". $\endgroup$
    – peterh
    May 5, 2019 at 8:18
  • $\begingroup$ @peterh thanks, I see you have keen eyes :) $\endgroup$
    – Labo
    May 5, 2019 at 10:32

1 Answer 1


Finally, I found the answer myself there.

The only interesting thing is the amplitude of $|0\rangle^{\oplus n}$. If the function is constant, it is $\pm 1$ and if the function is balanced, it is $0$.

Hence, in the first case we are sure to measure all qubits in the $|0\rangle$ state and in the second case, we cannot measure all of them in this state (else we would have the state $|0\rangle^{\oplus n}$ that has amplitude $0$).

  • $\begingroup$ Hi, Labo. Welcome to Quantum Computing SE! Could you please summarize the answer in that link over here? In case the link gets obsolete we'll no longer be able to view it. $\endgroup$ May 5, 2019 at 12:24
  • $\begingroup$ @SanchayanDutta Thanks ^^ Do you see anything that is not covered by my answer? $\endgroup$
    – Labo
    May 5, 2019 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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