Hadamard transform explained

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 real numbers (or complex, or hypercomplex 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 . It decomposes an arbitrary input vector into a superposition of Walsh functions.

The transform is named for the French mathematician Jacques Hadamard (in French adamaʁ/), the German-American mathematician Hans Rademacher, and the American mathematician Joseph L. Walsh.

Definition

The Hadamard transform Hm is a 2m × 2m matrix, the Hadamard matrix (scaled by a normalization factor), that transforms 2m real numbers xn into 2m real numbers Xk. 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 H0 by the identity H0 = 1, and then define Hm for m > 0 by:H_m = \frac \begin H_ & H_ \\ H_ & -H_ \endwhere the 1/ is a normalization that is sometimes omitted.

For m > 1, we can also define Hm by:H_m = H_ \otimes H_where

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 (kn)-th entry by writing\begin k &= \sum^_ = k_ 2^ + k_ 2^ + \dots + k_1 2 + k_0 \\ n &= \sum^_ = n_ 2^ + n_ 2^ + \dots + n_1 2 + n_0\end

where the kj and nj 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)_ = \frac (-1)^

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 nj and kj, respectively.

Some examples of the Hadamard matrices follow. \begin H_0 & = +\begin1\end\\[5pt] H_1 & = \frac \left(\begin 1 & 1\\ 1 & -1 \end\right)\\[5pt] H_2 & = \frac \left(\begin 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1 \end\right)\\[5pt] H_3 & = \frac \left(\begin 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\right)\\[5pt] (H_n)_ & = \frac (-1)^\endwhere

ij

is the bitwise dot product of the binary representations of the numbers i and j. For example, if n \;\geq\; 2, then (H_n)_ \;=\; (-1)^ \;=\; (-1)^ \;=\; (-1)^ \;=\; (-1)^1 \;=\; -1agreeing with the above (ignoring the overall constant). Note that the first row, first column element of the matrix is denoted by (H_n)_ .

H1 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.

Advantages of the Walsh–Hadamard transform

Real

According to the above definition of matrix H, here we let H = H[''m'',''n'']H[m,n]=\begin 1 & 1 \\ 1 & -1 \end

In the Walsh transform, only 1 and −1 will appear in the matrix. The numbers 1 and −1 are real numbers so there is no need to perform a complex number calculation.

No multiplication is required

The DFT needs irrational multiplication, while the Hadamard transform does not. Even rational multiplication is not needed, since sign flips is all it takes.

Some properties are similar to those of the DFT

In the Walsh transform matrix, all entries in the first row (and column) are equal to 1.H[m,n] = \left(\begin 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\right)

Discrete Fourier transform:e^

In discrete Fourier transform, when m equal to zeros (mean first row), the result of DFT also is 1.At the second row, although it is different from the first row we can observe a characteristic of the matrix that the signal in the first raw matrix is low frequency and it will increase the frequency at second row, increase more frequency until the last row.

If we calculate zero crossing:

First row = 0 zero crossing Second row = 1 zero crossing Third row = 2 zero crossings ⋮ Eight row = 7 zero crossings

Relation to Fourier transform

The Hadamard transform is in fact equivalent to a multidimensional DFT of size .[1]

(\Z/2\Z)n

.[2] [3] Using the Fourier transform on finite (abelian) groups, the Fourier transform of a function

f\colon(\Z/2\Z)n\to\Complex

is the function

\widehatf

defined by\widehat(\chi) = \sum_ f(a) \bar(a)where

\chi

is a character of

(\Z/2\Z)n

. Each character has the form

\chir(a)=(-1)a

for some

r\in(\Z/2\Z)n

, where the multiplication is the boolean dot product on bit strings, so we can identify the input to

\widehat{f}

with

r\in(\Z/2\Z)n

(Pontryagin duality) and define

\widehatf\colon(\Z/2\Z)n\to\Complex

by\widehat(r) = \sum_ f(a) (-1)^

This is the Hadamard transform of

f

, considering the input to

f

and

\widehat{f}

as boolean strings.

In terms of the above formulation where the Hadamard transform multiplies a vector of

2n

complex numbers

v

on the left by the Hadamard matrix

Hn

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

.

Compare this to the usual discrete Fourier transform which when applied to a vector

v

of

2n

complex numbers instead uses characters of the cyclic group

\Z/2n\Z

.

Computational complexity

In the classical domain, the Hadamard transform can be computed in

nlogn

operations (

n=2m

), 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

H1

is the quantum logic gate known as the Hadamard gate, and the application of a Hadamard gate to each qubit of an register in parallel is equivalent to the Hadamard transform

Hadamard gate

In quantum computing, the Hadamard gate is a one-qubit rotation, mapping the qubit-basis states

|0\rangle

and

|1\rangle

to two superposition states with equal weight of the computational basis states

|0\rangle

and

|1\rangle

. Usually the phases are chosen so thatH=\frac
1\rangle
\langle0|+\frac
1\rangle
\langle1|

in Dirac notation. This corresponds to the transformation matrixH_1=\frac\begin 1 & 1 \\ 1 & -1 \endin the

|0\rangle,|1\rangle

basis, also known as the computational basis. The states \frac and \frac are known as

\left|\boldsymbol{+}\right\rangle

and

\left|\boldsymbol{-}\right\rangle

respectively, and together constitute the polar basis in quantum computing.

Hadamard gate operations

\begin H(|0\rangle) &= \frac|0\rangle + \frac|1\rangle =: |+\rangle\\ H(|1\rangle) &= \frac|0\rangle - \frac|1\rangle =: |-\rangle\\ H(|+\rangle) &= H\left(\frac|0\rangle + \frac|1\rangle \right) = \frac\Big(|0\rangle + |1\rangle\Big) + \frac\Big(|0\rangle - |1\rangle\Big) = |0\rangle\\ H(|-\rangle) &= H\left(\frac|0\rangle - \frac|1\rangle \right) = \frac\Big(|0\rangle + |1\rangle\Big) - \frac\Big(|0\rangle - |1\rangle\Big) = |1\rangle\end

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

log2N

operations, compared to the classical case of

Nlog2N

operations.

For an

n

-qubit system, Hadamard gates acting on each of the

n

qubits (each initialized to the

|0\rangle

) can be used to prepare uniform quantum superposition states when

N

is of the form

N=2n

.In this case case with

n

qubits, the combined Hadamard gate

Hn

is expressed as the tensor product of

n

Hadamard gates:

Hn=\underbrace{HH\ldotsH}n

The resulting uniform quantum superposition state is then:

Hn|0\rangle=

1
\sqrt{2n
} \sum_^ |j\rangleThis generalizes the preparation of uniform quantum states using Hadamard gates for any

N=2n

.[4]

Measurement of this uniform quantum state results in a random state between

|0\rangle

and

Many quantum algorithms use the Hadamard transform as an initial step, since as explained earlier, it maps n qubits initialized with

|0\rangle

to a superposition of all 2n orthogonal states in the

|0\rangle,|1\rangle

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

(\Z/2\Z)n

and the second on

\Z/2n\Z

.

Preparation of uniform quantum superposition states in the general case, when

N

2n

is non-trivial and requires more work. An efficient and deterministic approach for preparing the superposition state |\Psi\rangle = \frac \sum_^ |j\rangle with a gate complexity and circuit depth of only

O(log2N)

for all

N

was recently presented.[5] This approach requires only

n=\lceillog2N\rceil

qubits. Importantly, neither ancilla qubits nor any quantum gates with multiple controls are needed in this approach for creating the uniform superposition state

|\Psi\rangle

.

Molecular phylogenetics (evolutionary biology) applications

The Hadamard transform can be used to estimate phylogenetic trees from molecular data.[6] [7] [8] Phylogenetics is the subfield of evolutionary biology focused on understanding the relationships among organisms. A Hadamard transform applied to a vector (or matrix) of site pattern frequencies obtained from a DNA multiple sequence alignment can be used to generate another vector that carries information about the tree topology. The invertible nature of the phylogenetic Hadamard transform also allows the calculation of site likelihoods from a tree topology vector, allowing one to use the Hadamard transform for maximum likelihood estimation of phylogenetic trees. However, the latter application is less useful than the transformation from the site pattern vector to the tree vector because there are other ways to calculate site likelihoods[9] that are much more efficient. However, the invertible nature of the phylogenetic Hadamard transform does provide an elegant tool for mathematic phylogenetics.[10] [11]

The mechanics of the phylogenetic Hadamard transform involve the calculation of a vector

\gamma(T)

that provides information about the topology and branch lengths for tree

T

using the site pattern vector or matrix

s(T)

.

\gamma(T) = H^(\ln(Hs(T)))where

H

is the Hadamard matrix of the appropriate size. This equation can be rewritten as a series of three equations to simplify its interpretation:

\begin r &= H s(T) \\ \rho &= \ln r \\ \gamma(T) &= H^\rho\end

The invertible nature of this equation allows one to calculate an expected site pattern vector (or matrix) as follows:

s(T)=H^(\exp(H\gamma(T)))

We can use the Cavender–Farris–Neyman (CFN) two-state substitution model for DNA by encoding the nucleotides as binary characters (the purines A and G are encoded as R and the pyrimidines C and T are encoded as Y). This makes it possible to encode the multiple sequence alignment as the site pattern vector

s(T)

that can be converted to a tree vector

\gamma(T)

, as shown in the following example:
Example showing the Hadamard transform for a specific tree (values for worked example adapted from Waddell et al. 1997[12])
IndexBinary patternAlignment patterns

\gamma(T)

\rho=H-1\gamma(T)

r=\exp(\rho)

s(T)=H-1\rho

00000RRRR and YYYY−0.475010.6479
10001RRRY and YYYR0.2−0.50.60650.1283
20010RRYR and YYRY0.025−0.150.86070.02
3*0011RRYY and YYRR0.025−0.450.63760.0226
40100RYRR and YRYY0.2−0.450.63760.1283
5*0101RYRY and YRYR0−0.850.42740.0258
6*0110RYYR and YRRY0−0.50.60650.0070
70111RYYY and YRRR0.025−0.90.40660.02

The example shown in this table uses the simplified three equation scheme and it is for a four taxon tree that can be written as ((A,B),(C,D)); in newick format. The site patterns are written in the order ABCD. This particular tree has two long terminal branches (0.2 transversion substitutions per site), two short terminal branches (0.025 transversion substitutions per site), and a short internal branch (0.025 transversion substitutions per site); thus, it would be written as ((A:0.025,B:0.2):0.025,(C:0.025,D:0.2)); in newick format. This tree will exhibit long branch attraction if the data are analyzed using the maximum parsimony criterion (assuming the sequence analyzed is long enough for the observed site pattern frequencies to be close to the expected frequencies shown in the

s(T)=H-1\rho

column). The long branch attraction reflects the fact that the expected number of site patterns with index 6 -- which support the tree ((A,C),(B,D)); -- exceed the expected number of site patterns that support the true tree (index 4). Obviously, the invertible nature of the phylogenetic Hadamard transform means that the tree vector means that the tree vector

\gamma(T)

corresponds to the correct tree. Parsimony analysis after the transformation is therefore statistically consistent,[13] as would be a standard maximum likelihood analysis using the correct model (in this case the CFN model).

Note that the site pattern with 0 corresponds to the sites that have not changed (after encoding the nucleotides as purines or pyrimidines). The indices with asterisks (3, 5, and 6) are "parsimony-informative", and. the remaining indices represent site patterns where a single taxon differs from the other three taxa (so they are the equivalent of terminal branch lengths in a standard maximum likelihood phylogenetic tree).

If one wishes to use nucleotide data without recoding as R and Y (and ultimately as 0 and 1) it is possible to encode the site patterns as a matrix. If we consider a four-taxon tree there are a total of 256 site patterns (four nucleotides to the 4th power). However, symmetries of the Kimura three-parameter (or K81) model allow us to reduce the 256 possible site patterns for DNA to 64 patterns, making it possible to encode the nucleotide data for a four-taxon tree as an 8 × 8 matrix[14] in a manner similar to the vector of 8 elements used above for transversion (RY) site patterns. This is accomplished by recoding the data using the Klein four-group:

Klein four-group coding for phylogenetic Hadamard transform
Nucleotide 1Nucleotide 2Nucleotide 3Nucleotide 4
A (0,0)G (1,0)C (0,1)T (1,1)
C (0,0)T (1,0)A (0,1)G (1,1)
G (0,0)A (1,0)T (0,1)C (1,1)
T (0,0)C (1,0)G (0,1)A (1,1)

As with RY data, site patterns are indexed relative to the base in the arbitrarily chosen first taxon with the bases in the subsequent taxa encoded relative to that first base. Thus, the first taxon receives the bit pair (0,0). Using those bit pairs one can produce two vectors similar to the RY vectors and then populate the matrix using those vectors. This can be illustrated using the example from Hendy et al. (1994), which is based on a multiple sequence alignment of four primate hemoglobin pseudogenes:

Example of encoded sequence alignment (from Hendy et al. 1994)(values are counts out of 9879 sites)
08162432404856
08988910122490
1419
24513
354*143
49420
51
622
73561175

The much larger number of site patterns in column 0 reflects the fact that column 0 corresponds to transition differences, which accumulate more rapidly than transversion differences in virtually all comparisons of genomic regions (and definitely accumulate more rapidly in the hemoglobin pseudogenes used for this worked example[15]). If we consider the site pattern AAGG it would to binary pattern 0000 for the second element of the Klein group bit pair and 0011 for the first element. in this case binary pattern based on the first element first element corresponds to index 3 (so row 3 in column 0; indicated with a single asterisk in the table). The site patterns GGAA, CCTT, and TTCC would be encoded in the exact same way. The site pattern AACT would be encoded with binary pattern 0011 based on the second element and 0001 based on the first element; this yields index 1 for the first element and index 3 for the second. The index based on the second Klein group bit pair is multiplied by 8 to yield the column index (in this case it would be column 24) The cell that would include the count of AACT site patterns is indicated with two asterisks; however, the absence of a number in the example indicates that the sequence alignment include no AACT site patterns (likewise, CCAG, GGTC, and TTGA site patterns, which would be encoded in the same way, are absent).

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

External links

Notes and References

  1. H.O. . Kunz . On the Equivalence Between One-Dimensional Discrete Walsh–Hadamard and Multidimensional Discrete Fourier Transforms . IEEE Transactions on Computers . 28 . 3 . 267–8 . 1979 . 10.1109/TC.1979.1675334 . 206621901 .
  2. https://www.staff.uni-mainz.de/pommeren/Kryptologie/Bitblock/A_Nonlin/Fourier.pdf Fourier Analysis of Boolean Maps– A Tutorial –, pp. 12–13
  3. https://www.cse.iitk.ac.in/users/rmittal/prev_course/s19/reports/5_algo.pdf Lecture 5: Basic quantum algorithms, Rajat Mittal, pp. 4–5
  4. Book: Quantum Computation and Quantum Information. Nielsen. Michael A.. Chuang. Isaac. 2010. Cambridge University Press. 978-1-10700-217-3. Cambridge. 43641333. Michael Nielsen. Isaac Chuang.
  5. Alok Shukla and Prakash Vedula . An efficient quantum algorithm for preparation of uniform quantum superposition states . Quantum Information Processing . 23:38 . 1 . 2024 . 38 . 10.1007/s11128-024-04258-4 . 2306.11747 . 2024QuIP...23...38S .
  6. Hendy. Michael D.. Penny. David. December 1989. A Framework for the Quantitative Study of Evolutionary Trees. Systematic Zoology. 38. 4. 297. 10.2307/2992396. 2992396.
  7. Hendy. Michael D.. Penny. David. January 1993. Spectral analysis of phylogenetic data. Journal of Classification. en. 10. 1. 5–24. 10.1007/BF02638451. 122466038. 0176-4268.
  8. Székely, L. A., Erdős, P. L., Steel, M. A., & Penny, D. (1993). A Fourier inversion formula for evolutionary trees. Applied mathematics letters, 6(2), 13–16.
  9. Felsenstein. Joseph. November 1981. Evolutionary trees from DNA sequences: A maximum likelihood approach. Journal of Molecular Evolution. en. 17. 6. 368–376. 10.1007/BF01734359. 7288891. 1981JMolE..17..368F . 8024924. 0022-2844.
  10. Chor. Benny. Benny Chor . Hendy. Michael D.. Holland. Barbara R.. Penny. David. 2000-10-01. Multiple Maxima of Likelihood in Phylogenetic Trees: An Analytic Approach. Molecular Biology and Evolution. en. 17. 10. 1529–1541. 10.1093/oxfordjournals.molbev.a026252. 11018159. 1537-1719. free.
  11. Matsen. Frederick A.. Steel. Mike. 2007-10-01. Ané. Cécile. Cécile Ané . Sullivan. Jack. Phylogenetic Mixtures on a Single Tree Can Mimic a Tree of Another Topology. Systematic Biology. en. 56. 5. 767–775. 10.1080/10635150701627304. 17886146. 1076-836X. free. 0704.2260.
  12. Waddell. Peter J. Steel. M.A. December 1997. General Time-Reversible Distances with Unequal Rates across Sites: Mixing Γ and Inverse Gaussian Distributions with Invariant Sites. Molecular Phylogenetics and Evolution. en. 8. 3. 398–414 . 10.1006/mpev.1997.0452. 9417897.
  13. Steel. M. A.. Hendy. M. D.. Penny. D.. 1993-12-01. Parsimony Can Be Consistent!. Systematic Biology. en. 42. 4. 581–587. 10.1093/sysbio/42.4.581. 1063-5157.
  14. Hendy. M. D.. Penny. D.. Steel. M. A.. 1994-04-12. A discrete Fourier analysis for evolutionary trees.. Proceedings of the National Academy of Sciences. en. 91. 8. 3339–3343. 10.1073/pnas.91.8.3339. 0027-8424. 43572. 8159749. 1994PNAS...91.3339H . free.
  15. Miyamoto. M. M.. Koop. B. F.. Slightom. J. L.. Goodman. M.. Tennant. M. R.. 1988-10-01. Molecular systematics of higher primates: genealogical relations and classification.. Proceedings of the National Academy of Sciences. en. 85. 20. 7627–7631. 10.1073/pnas.85.20.7627. 0027-8424. 282245. 3174657. 1988PNAS...85.7627M . free.