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


Note that the output contains nonzero contribution for all possible bases

|x_1 x_2 \cdots x_n\rangle.

Moreover, only if the kth 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.

Leave a Reply

Your email address will not be published. Required fields are marked *