# Hadamard gates on multiple qubits

The effect of applying Hadamard gates to multiple qubits is rather subtle and is used in many quantum algorithms.

Consider $n$ input qubits, $|u_1 u_2 u_3 \cdots u_n\rangle$. What will be the output if we apply the Hadamard gate to each of the qubit? Note that a Hadamard gate maps $|0\rangle$ to $|+\rangle=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ and $|1\rangle$ to $|-\rangle=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. So ignoring the scaling factor, the output will be

$(|0\rangle+(-1)^{u_1}|1\rangle)(|0\rangle+(-1)^{u_2}|1\rangle)\cdots(|0\rangle+(-1)^{u_n}|1\rangle)$.

Note that the output contains nonzero contribution for all possible bases

$|x_1 x_2 \cdots x_n\rangle$.

Moreover, only if the $k$th qubit $|x_k\rangle$ is $|1\rangle$, it will pick up the sign of $(-1)^{u_k}$. Therefore, the “overall” sign of $|x_1 x_2 \cdots x_n\rangle$ will be

$(-1)^{(x_1 u_1 + x_2 u_2+\cdots +x_n u_n)}=(-1)^{x \cdot u}$. Thus, we can write the output (after putting back the scaling factor) as

$\frac{1}{2^{n/2}} \sum_{x} -1^{x\cdot u} |x\rangle$.