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 - Reinstate Monica May 5 '19 at 8:18
  • $\begingroup$ @peterh thanks, I see you have keen eyes :) $\endgroup$ – Labo May 5 '19 at 10:32

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

| improve this answer | |
  • $\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$ – Sanchayan Dutta May 5 '19 at 12:24
  • $\begingroup$ @SanchayanDutta Thanks ^^ Do you see anything that is not covered by my answer? $\endgroup$ – Labo May 5 '19 at 18:55
  • 1
    $\begingroup$ I didn't get time to read through the question and answer, sorry. If all the necessary details in that page are covered in your answer, that's great. I was just making sure that we won't miss out on anything in case the link breaks. :) $\endgroup$ – Sanchayan Dutta May 5 '19 at 18:58

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.