The effect of applying Hadamard gates to multiple qubits is rather subtle and is used in many quantum algorithms.
Consider input qubits, . What will be the output if we apply the Hadamard gate to each of the qubit? Note that a Hadamard gate maps to and to . So ignoring the scaling factor, the output will be
Note that the output contains nonzero contribution for all possible bases
Moreover, only if the th qubit is , it will pick up the sign of . Therefore, the “overall” sign of will be
. Thus, we can write the output (after putting back the scaling factor) as