Hadamard transform

From Wikipedia, the free encyclopedia

The Hadamard transform (also known as the Walsh-Hadamard transform, the Walsh transform, or the Walsh-Fourier transform) is an example of a generalized class of Fourier transforms. It is named for the French mathematician Jacques Hadamard, and performs an orthogonal, symmetric, involutary, linear operation on $2 m$ real numbers (or complex numbers, although the Hadamard matrices themselves are purely real).

The Hadamard transform can be regarded as being built out of size-2 discrete Fourier transforms (DFTs), and is in fact equivalent to a multidimensional DFT of size $2\times2\times\cdots\times2\times2$ . It decomposes an arbitrary input vector into a superposition of Walsh functions.

1 Definition
2 Quantum computing applications
3 Other applications
4 See also

[edit] Definition

The Hadamard transform $H m$ is a $2^m \times 2^m$ matrix, the Hadamard matrix (scaled by a normalization factor), that transforms $2 m$ real numbers $x n$ into $2 m$ real numbers $X k$ . We can define the Hadamard transform in two ways: recursively, or by using the binary (base-2) representation of the indices $n$ and $k$ .

Recursively, we define the $1\times1$ Hadamard transform $H 0$ by the identity $H 0 = 1$ , and then define $H m$ for $m > 0$ by:

$H_m = \frac{1}{\sqrt2} \begin{pmatrix} H_{m-1} & H_{m-1} \\ H_{m-1} & -H_{m-1} \end{pmatrix},$

where the $1/\sqrt2$ is a normalization that is sometimes omitted. Thus, other than this normalization factor, the Hadamard matrices are made up entirely of 1 and −1.

Equivalently, we can define the Hadamard matrix by its $(k, n)$ -th entry by writing $k=k_{m-1} 2^{m-1} + k_{m-2} 2^{m-2} + \cdots + k_1 2 + k_0$ and $n=n_{m-1} 2^{m-1} + n_{m-2} 2^{m-2} + \cdots + n_1 2 + n_0$ , where the $k j$ and $n j$ are the binary digits (0 or 1) of $n$ and $k$ , respectively. In this case, we have:

$\left( H_m \right)_{k,n} = \frac{1}{2^{m/2}} (-1)^{\sum_j k_j n_j}$ .

This is exactly the multi-dimensional $2\times2\times\cdots\times2\times2$ DFT, normalized to be unitary, if we regard the inputs and outputs as multidimensional arrays indexed by the $n j$ and $k j$ , respectively.

Some examples of the Hadamard matrices follow.

H 0 = + 1

$H_1 = \frac{1}{\sqrt2} \begin{pmatrix} +1 & +1 \\ +1 & -1 \end{pmatrix}$

(This $H 1$ is precisely the size-2 DFT. It can also be regarded as the Fourier transform on the two-element additive group of Z/(2).)

$H_2 = \frac{1}{2} \begin{pmatrix} +1 & +1 & +1 & +1 \\ +1 & -1 & +1 & -1 \\ +1 & +1 & -1 & -1 \\ +1 & -1 & -1 & +1\end{pmatrix}$

$H_3 = \frac{1}{2^{3/2}} \begin{pmatrix} +1 & +1 & +1 & +1 & +1 & +1 & +1 & +1\\ +1 & -1 & +1 & -1 & +1 & -1 & +1 & -1 \\ +1 & +1 & -1 & -1 & +1 & +1 & -1 & -1 \\ +1 & -1 & -1 & +1 & +1 & -1 & -1 & +1 \\ +1 & +1 & +1 & +1 & -1 & -1 & -1 & -1\\ +1 & -1 & +1 & -1 & -1 & +1 & -1 & +1 \\ +1 & +1 & -1 & -1 & -1 & -1 & +1 & +1 \\ +1 & -1 & -1 & +1 & -1 & +1 & +1 & -1\end{pmatrix}$

The rows of the Hadamard matrices are the Walsh functions.

[edit] Quantum computing applications

In quantum information processing the Hadamard transformation, more often called Hadamard gate in this context (cf. quantum gate), is a one-qubit rotation, mapping the qubit-basis states |0› and |1› to two superposition states with equal weight of the computational basis states $|0 \rangle$ and $|1 \rangle$ . Usually the phases are chosen so that we have

$\frac{|0\rangle+|1\rangle}{\sqrt{2}}\langle0|+\frac{|0\rangle-|1\rangle}{\sqrt{2}}\langle1|$

in Dirac notation. This corresponds to the transformation matrix

$H_1=\frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$

in the $|0 \rangle , |1 \rangle$ basis.

Many quantum algorithms use the Hadamard transform as an initial step, since it maps n qubits initialized with |0› to a superposition of all 2ⁿ orthogonal states in the $|0 \rangle , |1 \rangle$ basis with equal weight.

[edit] Other applications

The Hadamard transform can also be used to generate random numbers with a Gaussian distribution by the central limit theorem. Or you can combine a series of Hadamard transforms with random permutations to transform data into Gaussian noise.

The Hadamard transform is used in many signal processing, and data compression algorithms.