Hadamard transform

The product of a Boolean function and a Hadamard matrix is its Walsh spectrum:
(1, 0, 1, 0, 0, 1, 1, 0) × H(8) = (4, 2, 0, −2, 0, 2, 0, 2)

Fast Walsh–Hadamard transform, a faster way to calculate the Walsh spectrum of (1, 0, 1, 0, 0, 1, 1, 0).

The original function can be expressed by means of its Walsh spectrum as an arithmetical polynomial.

The Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms. It performs an orthogonal, symmetric, involutive, linear operation on a tuple of Template:Math numbers.

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 Template:Math. It decomposes an arbitrary input vector into a superposition of Walsh functions.

The transform is named for the French mathematician Jacques Hadamard (Template:IPA), the German-American mathematician Hans Rademacher, and the American mathematician Joseph L. Walsh.

Definition

The Hadamard transform H_m is a 2^m × 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. The Hadamard transform can be defined in two ways: recursively, or by using the binary (base-2) representation of the indices n and k.

Recursively, we define the 1 × 1 Hadamard transform H₀ by the identity H₀ = 1, and then define H_m for m > 0 by: $$H_m=\frac{1}{2^{m/2}}\left(\begin{array}{cc}{H}_{m-1}& H_{m-1}\\ H_{m-1}& -H_{m-1}\end{array}\right)$$ where the division by 2^m/2 is a normalization that is sometimes omitted.

For m > 1, we can also define H_m by: $$H_m=H_1\otimes H_{m-1}$$ where $\otimes$ represents the Kronecker product. 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 $$\begin{array}{cc}k& =\sum _{i=0}^{m-1}{k}_i{2}^i=k_{m-1}{2}^{m-1}+k_{m-2}{2}^{m-2}+\dots +k_{1}2+k_0\\ n& =\sum _{i=0}^{m-1}{n}_i{2}^i=n_{m-1}{2}^{m-1}+n_{m-2}{2}^{m-2}+\dots +n_{1}2+n_0\end{array}$$

where the k_j and n_j are the bit elements (0 or 1) of k and n, respectively. Note that for the element in the top left corner, we define: $k=n=0$. In this case, we have: $$(H_m{)}_{k,n}=\frac{1}{2^{m/2}}(-1{)}^{\sum _j{k}_j{n}_j}$$

This is exactly the multidimensional $2\times 2\times \cdots \times 2\times 2$ DFT, normalized to be unitary, if the inputs and outputs are regarded as multidimensional arrays indexed by the n_j and k_j, respectively.

Some examples of the Hadamard matrices follow. $$\begin{array}{cc}{H}_0& =+\left(\begin{array}{c}1\end{array}\right)\\ H_1& =\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)\\ H_2& =\frac{1}{2}\left(\begin{array}{cccc}1& 1& 1& 1\\ 1& -1& 1& -1\\ 1& 1& -1& -1\\ 1& -1& -1& 1\end{array}\right)\\ H_3& =\frac{1}{2^{3/2}}\left(\begin{array}{cccccccc}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{array}\right)\\ (H_n{)}_{i,j}& =\frac{1}{2^{n/2}}(-1{)}^{i\cdot j}\end{array}$$ where $i\cdot j$ is the bitwise dot product of the binary representations of the numbers i and j. For example, if $n\ge 2$, then $$(H_n{)}_{3,2}=(-1{)}^{3\cdot 2}=(-1{)}^{(1,1)\cdot (1,0)}=(-1{)}^{1+0}=(-1{)}^1=-1$$, agreeing with the above (ignoring the overall constant). Note that the first row, first column element of the matrix is denoted by $(H_n{)}_{0,0}$.

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

The rows of the Hadamard matrices are the Walsh functions.

Relation to Fourier transform

The Hadamard transform is equivalent to a multidimensional DFT of size Template:Math.

Formally, the Hadamard transform is a Fourier transform on the Boolean group $(\mathbb{Z}/2\mathbb{Z}{)}^n$. Using the Fourier transform on finite (abelian) groups, the Fourier transform of a function $f:(\mathbb{Z}/2\mathbb{Z}{)}^n\to ℂ$ is the function $\hat{f}$ defined by $$\hat{f}(\chi )=\sum _{a\in (\mathbb{Z}/2\mathbb{Z}{)}^n}f(a)\overline{\chi }(a)$$ where $\chi$ is a character of $(\mathbb{Z}/2\mathbb{Z}{)}^n$. Each character has the form ${\chi }_r(a)=(-1{)}^{a\cdot r}$ for some $r\in (\mathbb{Z}/2\mathbb{Z}{)}^n$, where the multiplication is the boolean dot product on bit strings, so we can identify the input to $\hat{f}$ with $r\in (\mathbb{Z}/2\mathbb{Z}{)}^n$ (Pontryagin duality) and define $\hat{f}:(\mathbb{Z}/2\mathbb{Z}{)}^n\to ℂ$ by $$\hat{f}(r)=\sum _{a\in (\mathbb{Z}/2\mathbb{Z}{)}^n}f(a)(-1{)}^{r\cdot a}$$

This is the Hadamard transform of $f$, considering the input to $f$ and $\hat{f}$ as boolean strings.

In terms of the above formulation where the Hadamard transform multiplies a vector of $2^n$ complex numbers $v$ on the left by the Hadamard matrix $H_n$ the equivalence is seen by taking $f$ to take as input the bit string corresponding to the index of an element of $v$, and having $f$ output the corresponding element of $v$.

The usual discrete Fourier transform, applied to a vector $v$ of $2^n$ complex numbers, instead uses characters of the cyclic group $\mathbb{Z}/2^n\mathbb{Z}$. Consequently the DFT requires substantially more complicated arithmetic than the Hadamard transform. Unlike the DFT, the Hadamard transform is purely real, and in fact requires no multiplication, only sign flips.

Computational complexity

In the classical domain, the Hadamard transform can be computed in $n\log n$ operations ($n=2^m$), using the fast Hadamard transform algorithm.

In the quantum domain, the Hadamard transform can be computed in $O(1)$ time, as it is a quantum logic gate that can be parallelized.

Quantum computing applications

The Hadamard transform is used extensively in quantum computing. The 2 × 2 Hadamard transform $H_1$ is the quantum logic gate known as the Hadamard gate, and the application of a Hadamard gate to each qubit of an Template:Nowrap register in parallel is equivalent to the Hadamard transform Template:Nowrap

Hadamard gate

Template:Further In quantum computing, the Hadamard 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⟩$ and $|1⟩$. Usually the phases are chosen so that $$H=\frac{|0⟩+|1⟩}{\sqrt{2}}⟨0|+\frac{|0⟩-|1⟩}{\sqrt{2}}⟨1|$$

in Dirac notation. This corresponds to the transformation matrix $$H_1=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$$ in the $|0⟩,|1⟩$ basis, also known as the computational basis. The states $\frac{|0⟩+|1⟩}{\sqrt{2}}$ and $\frac{|0⟩-|1⟩}{\sqrt{2}}$ are known as $|\mathit{+}⟩$ and $|\mathit{-}⟩$ respectively, and together constitute the polar basis in quantum computing.

Hadamard gate operations

$$\begin{array}{cc}H(|0⟩)& =\frac{1}{\sqrt{2}}|0⟩+\frac{1}{\sqrt{2}}|1⟩=:|+⟩\\ H(|1⟩)& =\frac{1}{\sqrt{2}}|0⟩-\frac{1}{\sqrt{2}}|1⟩=:|-⟩\\ H(|+⟩)& =H(\frac{1}{\sqrt{2}}|0⟩+\frac{1}{\sqrt{2}}|1⟩)=\frac{1}{2}(|0⟩+|1⟩)+\frac{1}{2}(|0⟩-|1⟩)=|0⟩\\ H(|-⟩)& =H(\frac{1}{\sqrt{2}}|0⟩-\frac{1}{\sqrt{2}}|1⟩)=\frac{1}{2}(|0⟩+|1⟩)-\frac{1}{2}(|0⟩-|1⟩)=|1⟩\end{array}$$

One application of the Hadamard gate to either a 0 or 1 qubit will produce a quantum state that, if observed, will be a 0 or 1 with equal probability (as seen in the first two operations). This is exactly like flipping a fair coin in the standard probabilistic model of computation. However, if the Hadamard gate is applied twice in succession (as is effectively being done in the last two operations), then the final state is always the same as the initial state.

Hadamard transform in quantum algorithms

Computing the quantum Hadamard transform is simply the application of a Hadamard gate to each qubit individually because of the tensor product structure of the Hadamard transform. This simple result means the quantum Hadamard transform requires ${\log }_{2}N$ operations, compared to the classical case of $N{\log }_{2}N$ operations.

For an $n$-qubit system, Hadamard gates acting on each of the $n$ qubits (each initialized to the $|0⟩$) can be used to prepare uniform quantum superposition states when $N$ is of the form $N=2^n$. In this case with $n$ qubits, the combined Hadamard gate $H_n$ is expressed as the tensor product of $n$ Hadamard gates: $H_n=\underset{n\text{ times}}{\underbrace{H\otimes H\otimes \dots \otimes H}}$

The resulting uniform quantum superposition state is then: $H_n|0{⟩}^{\otimes n}=\frac{1}{\sqrt{2^n}}\sum _{j=0}^{2^n-1}|j⟩$ This generalizes the preparation of uniform quantum states using Hadamard gates for any $N=2^n$.

Measurement of this uniform quantum state results in a random state between $|0⟩$ and Template:Nowrap

Many quantum algorithms use the Hadamard transform as an initial step, since as explained earlier, it maps n qubits initialized with $|0⟩$ to a superposition of all 2ⁿ orthogonal states in the $|0⟩,|1⟩$ basis with equal weight. For example, this is used in the Deutsch–Jozsa algorithm, Simon's algorithm, the Bernstein–Vazirani algorithm, and in Grover's algorithm. Note that Shor's algorithm uses both an initial Hadamard transform, as well as the quantum Fourier transform, which are both types of Fourier transforms on finite groups; the first on $(\mathbb{Z}/2\mathbb{Z}{)}^n$ and the second on $\mathbb{Z}/2^n\mathbb{Z}$.

Preparation of uniform quantum superposition states in the general case, when $N$ ≠ $2^n$ is non-trivial and requires more work. An efficient and deterministic approach for preparing the superposition state $$|\mathrm{\Psi }⟩=\frac{1}{\sqrt{N}}\sum _{j=0}^{N-1}|j⟩$$ with a gate complexity and circuit depth of only $O({\log }_{2}N)$ for all $N$ was recently presented. This approach requires only $n=\lceil {\log }_{2}N\rceil$ qubits. Importantly, neither ancilla qubits nor any quantum gates with multiple controls are needed in this approach for creating the uniform superposition state $|\mathrm{\Psi }⟩$.

Convolutional neural networks

The Hadamard transform has found applications in quantum machine learning, particularly in hybrid quantum-classical neural networks. Dyadic convolution between two vectors is equivalent to element-wise multiplication of their Hadamard transform representations; thus convolutional layers can be performed efficiently by taking the Hadamard transform, multiplying, and then inverting the Hadamard transform. While classical computation of the Hadamard transform requires O(n log n) operations using the fast Hadamard transform algorithm, the quantum implementation can compute the transform in O(1) time by applying Hadamard gates to all qubits simultaneously.

Application in evolutionary biology

The Hadamard transform can be used to estimate phylogenetic trees from molecular data. In principle, the Hadamard transform can be applied to many different models of sequence evolution, but the case of greatest interest uses data from nucleic acids (NAs).

Formally, consider the four possible strand nucleobases as elements of the Klein 4-group Template:Mvar acting on itself. One C₂ axis corresponds to transitions and the other to transversions. NA sequences of length Template:Mvar are elements of Template:Math, and a given index into these length-Template:Mvar sequences is called a site. A phylogenetic tree Template:Mvar is a tree, rooted at some Template:Mvar, in which each point has been identified with a NA sequence.

In biological applications, one would like to specify mutation rates for each edge of Template:Mvar and then compute the resulting probability of observing Template:Mvar. Ideally, this process should be easily invertible, such that an optimization algorithm can find a (tree, mutation rate) pair producing the observed DNA sequences with maximum likelihood. In fact, this can be done with the Hadamard transform, as follows.

Let Template:Mvar be the power set of Template:Math, and consider the following Template:Math-indexed vector Template:Mvar. Each site Template:Mvar determines a Template:Math, the set of points with a transition relative to Template:Mvar at site Template:Mvar. Likewise transversions determine another Template:Math for each site. Then Template:Math is the proportion (out of Template:Math) of sites determining Template:Math.

The linear operator Template:Math with Template:Mathth coefficient Template:Math is a Hadamard matrix; in fact, it defines a Hadamard transform when Template:Mvar is enumerated in a certain order. Let

Template:Math

where the Template:Math indicates that the logarithm acts on each component of the vector. Then Template:Math is almost the mutation rates Template:Mvar necessary to produce the observed probability distribution Template:Mvar, as follows.

For the full Kimura model, with all 4 nucleic acids distinguished, there are three free parameters for each edge. Converting these values to the corresponding entry in Template:Math requires conjugation of another logarithm with a Template:Math matrix.

If the sequences are instead RY-coded, then the relationship is much simpler. In that case, Template:Mvar and Template:Math are indexed by Template:Mvar (rather than Template:Math), as can Template:Mvar be: for even-sized Template:Math, let Template:Math; for odd-sized Template:Math, let Template:Math; and let Template:Math be the mutation rate on the edge disconnecting Template:Math from the rest of Template:Mvar. (Template:Mvar is not quite a measured quantity, as it includes the probability of reverted mutations. It is related to the observed probability of character change via

Template:Math

where Template:Mvar is the observed probability.) Then Template:Math.

This technique can also be generalized to the case in which different sites mutate at different rates.

In all cases, the time complexity of determining the tree is dominated by the Hadamard transform, which takes Template:Math-many steps. However, algorithms can reconstruct the tree by piecing together smaller trees constructed from a subset of Template:Mvar.

Other applications

The Hadamard transform is also used in data encryption, as well as many signal processing and data compression algorithms, such as JPEG XR and MPEG-4 AVC. In video compression applications, it is usually used in the form of the sum of absolute transformed differences. It is also a crucial part of significant number of algorithms in quantum computing. The Hadamard transform is also applied in experimental techniques such as NMR, mass spectrometry and crystallography. It is additionally used in some versions of locality-sensitive hashing, to obtain pseudo-random matrix rotations.

See also

• Fast Walsh–Hadamard transform
• Pseudo-Hadamard transform
• Haar transform
• Generalized distributive law

External links

• Template:Cite web
• Template:Cite journal
• Pan, Jeng-shyang Data Encryption Method Using Discrete Fractional Hadamard Transformation (May 28, 2009)
• Lachowicz, Dr. Pawel. Walsh–Hadamard Transform and Tests for Randomness of Financial Return-Series (April 7, 2015)
• Template:Cite web
• Template:Cite journal