Why the Hadamard Transform?
The Hadamard transform is one of the most fundamental operations in quantum computing. It creates superpositions from definite states, bridges the computational and Hadamard bases, and is at the heart of nearly every quantum algorithm — from Deutsch-Jozsa to Grover's search to Shor's factoring.
This interactive guide builds the n-qubit Hadamard transform from the ground up. Along the way, we will discover how tensor products combine single-qubit operations, how the bilinear form over GF(2) determines every matrix entry, and how the transform acts on uniform superpositions over subspaces and cosets.
The Single-Qubit Hadamard Gate
A single qubit lives in a 2-dimensional space spanned by the computational basis states \(|0\rangle\) and \(|1\rangle\). The Hadamard gate \(H\) is defined by the matrix:
\[ H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \]Its action on the basis states is:
\[ H|0\rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}} = |{+}\rangle, \qquad H|1\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}} = |{-}\rangle \]Notice the pattern: the coefficient of \(|y\rangle\) in \(H|x\rangle\) is \(\frac{1}{\sqrt{2}}(-1)^{x \cdot y}\), where \(x \cdot y\) is just the product of two bits. When \(x=0\), all signs are positive. When \(x=1\), the sign of \(|1\rangle\) flips.
\[ H|x\rangle = \frac{1}{\sqrt{2}} \sum_{y \in \{0,1\}} (-1)^{xy}\,|y\rangle \]Scaling Up: Tensor Products
To apply Hadamard to multiple qubits, we use the tensor product (Kronecker product). If \(H\) acts on one qubit, then \(H^{\otimes n} = \underbrace{H \otimes H \otimes \cdots \otimes H}_{n}\) acts on \(n\) qubits independently.
The key property of the tensor product for operators is:
\[ (A \otimes B)\,(|\psi\rangle \otimes |\phi\rangle) = (A|\psi\rangle) \otimes (B|\phi\rangle) \]As a matrix, \(A \otimes B\) is built by replacing each entry \(a_{ij}\) of \(A\) with the block \(a_{ij} \cdot B\). For \(H \otimes H\):
Hover over a block in \(H^{\otimes 2}\) to see which entry of \(H\) it corresponds to. Each 2×2 block is a copy of \(H\) scaled by the corresponding entry of \(H\).
The GF(2) Bilinear Form
\(\text{GF}(2)\) is the finite field with two elements: \(\{0, 1\}\), where addition is XOR (so \(1 + 1 = 0\)) and multiplication is AND.
An \(n\)-bit string \(x = x_1 x_2 \cdots x_n\) is a vector in \(\text{GF}(2)^n\). The bilinear form (dot product) over \(\text{GF}(2)\) is:
\[ x \cdot y = x_1 y_1 \oplus x_2 y_2 \oplus \cdots \oplus x_n y_n \]This is computed as: multiply corresponding bits (AND), then XOR all the products. The result is always 0 or 1.
The n-Qubit Hadamard Formula
Combining the tensor product structure with the single-qubit formula, we can derive the action of \(H^{\otimes n}\) on any computational basis state.
Each matrix entry is therefore \(\bigl(H^{\otimes n}\bigr)_{y,x} = \frac{1}{\sqrt{2^n}}(-1)^{x \cdot y}\). The entire matrix is determined by the GF(2) dot product!
Explore the Hadamard Matrix
Hover over any cell to see the GF(2) computation. Rows = output \(|y\rangle\), columns = input \(|x\rangle\). Cyan = +1, Red = −1 (before the \(1/\sqrt{2^n}\) factor).
Transform a Basis State
Toggle the input bits to see how \(H^{\otimes n}|x\rangle\) changes. Cyan bars = positive amplitude, red bars = negative.
Creating Uniform Superpositions
The most famous application: when the input is \(|0\rangle^{\otimes n}\), all dot products \(0\cdots0 \cdot y = 0\), so every sign is \(+1\):
\[ H^{\otimes n}|0\cdots0\rangle = \frac{1}{\sqrt{2^n}} \sum_{y \in \{0,1\}^n} |y\rangle \]This is the uniform superposition over all \(2^n\) computational basis states — the standard starting state for most quantum algorithms.
Self-Inverse Property
The Hadamard gate is its own inverse: \(H^2 = I\). This extends to the \(n\)-qubit case: \((H^{\otimes n})^2 = I^{\otimes n} = I\). Applying the Hadamard twice returns to the original state. This is because \(H\) is both unitary (\(HH^\dagger = I\)) and Hermitian (\(H = H^\dagger\)), so \(H^{-1} = H^\dagger = H\).
H⊗n
H⊗n
No matter what input you choose, applying the Hadamard twice always returns to the original state. The middle chart shows the superposition created by the first application.
Subspaces, Cosets & the Hadamard
The deepest structure of the Hadamard transform emerges when we consider its action on uniform superpositions over subspaces of \(\text{GF}(2)^n\).
Subspaces of GF(2)n
A subspace \(S \subseteq \text{GF}(2)^n\) is a subset that is closed under XOR: if \(s, t \in S\), then \(s \oplus t \in S\). It always contains \(0\cdots0\). A subspace of dimension \(k\) is spanned by \(k\) linearly independent vectors and has \(|S| = 2^k\) elements.
Orthogonal Complement
The orthogonal complement of \(S\) is: \[ S^\perp = \{y \in \text{GF}(2)^n \;:\; x \cdot y = 0 \;\;\text{for all } x \in S\} \] If \(\dim(S) = k\), then \(\dim(S^\perp) = n - k\), so \(|S| \cdot |S^\perp| = 2^n\).
The Subspace Theorem
Let \(|S\rangle = \frac{1}{\sqrt{|S|}}\sum_{s \in S}|s\rangle\) be the uniform superposition over \(S\). Then:
\[ \boxed{\; H^{\otimes n}\,|S\rangle = |S^\perp\rangle \;} \]The Hadamard maps the uniform superposition over a subspace to the uniform superposition over its orthogonal complement!
Cosets and Phase Shifts
A coset \(a \oplus S = \{a \oplus s \;:\; s \in S\}\) is a "shifted" copy of the subspace. When we apply the Hadamard to a uniform superposition over a coset:
\[ \boxed{\; H^{\otimes n} \frac{1}{\sqrt{|S|}}\sum_{s \in S}|a \oplus s\rangle = \frac{1}{\sqrt{|S^\perp|}} \sum_{t \in S^\perp} (-1)^{a \cdot t}\,|t\rangle \;} \]The output still has support on \(S^\perp\), but each amplitude picks up a phase \((-1)^{a \cdot t}\) that depends on the shift vector \(a\). This is the mathematical foundation of Simon's algorithm, Bernstein-Vazirani, and related quantum algorithms.
Observe: the output is supported exactly on \(S^\perp\). The shift \(a\) only affects the signs (phases) of the amplitudes, not which basis states appear.