= Fast Hadamard transform
= FWHT
{c}
{synonym}
= Fast Walsh-Hadamard transform
{synonym}
= FWT
{c}
{synonym}
The fast Hadamard transform computes multiplication by a tensor power of the two-by-two <Hadamard matrix> using repeated pairwise sums and differences. For $N=2^n$ input amplitudes, one stage replaces each selected pair $(a,b)$ by $(a+b,a-b)$, with factors of $1/\sqrt2$ when using the unitary convention.
There are $n=\log_2N$ stages, each requiring order $N$ arithmetic operations, giving order $N\log N$ classical work instead of a generic dense matrix multiplication. A <quantum circuit> implements the corresponding unitary $H^{\otimes n}$ with one <Hadamard gate> on each of $n$ <qubits>. This compact circuit description does not imply that all $N$ resulting amplitudes can be read out in one measurement; the output statistics still follow the <Born rule>.
Back to article page