Hadamard gate is used in the Deutch - Jozsha algorithm to prepare a superposition representing all possible bit combinations. It uses the quantum parallelism concept to compute all values of f(x) from the superposition in polynomial time, instead of growing exponentially with the number of bases. We can breakdown the algorithm into the following major steps.
We initially prepare two quantum registers. The first is an n-qubit
register initialized to |0>, and the second is a one-qubit register
initialized to |1>.
Then we apply a Hadamard gate to each qubit. At this stage, our input register is an equal superposition of all the states in the computational basis.
Then the quantum oracle is applied such that it does not decohere the inputs.
At this point, the second single qubit register may be ignored.
Then we apply a Hadamard gate to each qubit in the first register.
In this approach, we are constructing a constant and balanced oracle. When the oracle is constant, it has no effect on the input qubits, and the quantum states before and after querying the oracle are the same. The following quantum circuit diagram depicts the algorithm.