The fast Hadamard transform computes multiplication by a tensor power of the two-by-two Hadamard matrix using repeated pairwise sums and differences. For input amplitudes, one stage replaces each selected pair by , with factors of when using the unitary convention.
There are stages, each requiring order arithmetic operations, giving order classical work instead of a generic dense matrix multiplication. A quantum circuit implements the corresponding unitary with one Hadamard gate on each of qubits. This compact circuit description does not imply that all resulting amplitudes can be read out in one measurement; the output statistics still follow the Born rule.

Articles by others on the same topic (0)

There are currently no matching articles.