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

.