# Deutsch-Jozsa algorithm as a generalization of Bernstein-Vazirani

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?

• Welcome on the site! It is "Deutsch-Jozsa". – peterh - Reinstate Monica May 5 '19 at 8:18
• @peterh thanks, I see you have keen eyes :) – Labo May 5 '19 at 10:32

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