TheHadamard transform (also known as theWalsh–Hadamard transform,Hadamard–Rademacher–Walsh transform,Walsh transform, orWalsh–Fourier transform) is an example of a generalized class ofFourier transforms. It performs anorthogonal,symmetric,involutive,linear operation on2^mreal numbers (orcomplex, orhypercomplex numbers, although the Hadamard matrices themselves are purely real).

The Hadamard transform can be regarded as being built out of size-2discrete Fourier transforms (DFTs), and is in fact equivalent to a multidimensional DFT of size2 × 2 × ⋯ × 2 × 2.^[2] It decomposes an arbitrary input vector into a superposition ofWalsh functions.

The transform is named for theFrenchmathematicianJacques Hadamard (French:[adamaʁ]), the German-American mathematicianHans Rademacher, and the American mathematicianJoseph L. Walsh.

The Hadamard transformH_m is a 2^m × 2^m matrix, theHadamard matrix (scaled by a normalization factor), that transforms 2^m real numbersx_n into 2^m real numbersX_k. The Hadamard transform can be defined in two ways:recursively, or by using thebinary (base-2) representation of the indicesn andk.

Recursively, we define the 1 × 1 Hadamard transformH₀ by theidentityH₀ = 1, and then defineH_m form > 0 by:where the 1/√2 is a normalization that is sometimes omitted.

Form > 1, we can also defineH_m by:$${\displaystyle H_m=H_1\otimes H_{m-1}}$$where${\displaystyle \otimes }$ represents theKronecker 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

where thek_j andn_j are the bit elements (0 or 1) ofk andn, respectively. Note that for the element in the top left corner, we define:${\displaystyle k=n=0}$. In this case, we have:$${\displaystyle (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 beunitary, if the inputs and outputs are regarded as multidimensional arrays indexed by then_j andk_j, respectively.

Some examples of the Hadamard matrices follow.where${\displaystyle i\cdot j}$ is the bitwisedot product of the binary representations of the numbers i and j. For example, if$n\ge 2$, then$${\displaystyle (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 theFourier transform on the two-elementadditive group ofZ/(2).

The rows of the Hadamard matrices are theWalsh functions.

This sectionis missing information about ordering variants of the Hadamard matrices: sequency (Walsh matrix), Hadamard, and dyadic. Please expand the section to include this information. Further details may exist on thetalk page.(April 2024)

According to the above definition of matrixH, here we letH =H[m,n]

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 acomplex number calculation.

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

In the Walsh transform matrix, each row and each column is aWalsh function, in which the number of sign changes increases consecutively. That is, in the first row and first column, there are zero sign changes (all entries are equal to 1). In the second, there is one sign change; in the third, two sign changes; and so on.Compare this to a discrete Fourier transform$e^{-j2\pi mn/N}$, in which each rowi contains$i-1$zero crossings.

In a discrete Fourier transform, whenm is equal to zero (corresponding to the first row), the result is also 1. For subsequent rows, we can observe a characteristic of the matrix that the signal frequency begins low in the first raw matrix, and increases in following rows, until the last row.

The Hadamard transform is in fact equivalent to a multidimensional DFT of size2 × 2 × ⋯ × 2 × 2.^[2]

Another approach is to view the Hadamard transform as a Fourier transform on theBoolean group${\displaystyle (\mathbb{Z}/2\mathbb{Z}{)}^n}$.^[3][4] Using theFourier transform on finite (abelian) groups, the Fourier transform of a function${\displaystyle f:(\mathbb{Z}/2\mathbb{Z}{)}^n\to \mathbb{C}}$ is the function${\displaystyle \hat{f}}$ defined by$${\displaystyle \hat{f}(\chi )=\sum _{a\in (\mathbb{Z}/2\mathbb{Z}{)}^n}f(a)\overline{\chi }(a)}$$where${\displaystyle \chi }$ is acharacter of${\displaystyle (\mathbb{Z}/2\mathbb{Z}{)}^n}$. Each character has the form${\displaystyle {\chi }_r(a)=(-1{)}^{a\cdot r}}$ for some${\displaystyle 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${\displaystyle \hat{f}}$ with${\displaystyle r\in (\mathbb{Z}/2\mathbb{Z}{)}^n}$ (Pontryagin duality) and define${\displaystyle \hat{f}:(\mathbb{Z}/2\mathbb{Z}{)}^n\to \mathbb{C}}$ by$${\displaystyle \hat{f}(r)=\sum _{a\in (\mathbb{Z}/2\mathbb{Z}{)}^n}f(a)(-1{)}^{r\cdot a}}$$

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

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

Compare this to the usualdiscrete Fourier transform which when applied to a vector${\displaystyle v}$ of${\displaystyle 2^n}$ complex numbers instead uses characters of thecyclic group${\displaystyle \mathbb{Z}/2^n\mathbb{Z}}$.

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

In the quantum domain, the Hadamard transform can be computed in${\displaystyle O(1)}$ time, as it is aquantum logic gate that can beparallelized.

The Hadamard transform is used extensively inquantum computing. The 2 × 2 Hadamard transform${\displaystyle H_1}$ is thequantum logic gate known as the Hadamard gate, and the application of a Hadamard gate to each qubit of an${\displaystyle n}$-qubit register in parallel is equivalent to the Hadamard transform${\displaystyle H_n}$.

In quantum computing, the Hadamard gate is a one-qubitrotation, mapping the qubit-basis states${\displaystyle |0⟩}$ and${\displaystyle |1⟩}$ to two superposition states with equal weight of the computationalbasis states${\displaystyle |0⟩}$ and${\displaystyle |1⟩}$. Usually the phases are chosen so that$${\displaystyle H=\frac{|0⟩+|1⟩}{\sqrt{2}}⟨0|+\frac{|0⟩-|1⟩}{\sqrt{2}}⟨1|}$$

inDirac notation. This corresponds to thetransformation matrixin the${\displaystyle |0⟩,|1⟩}$ basis, also known as thecomputational basis. The states$\frac{|0⟩+|1⟩}{\sqrt{2}}$ and$\frac{|0⟩-|1⟩}{\sqrt{2}}$ are known as${\displaystyle |\mathbf{+}⟩}$ and${\displaystyle |\mathbf{-}⟩}$ respectively, and together constitute thepolar basis inquantum computing.

One application of the Hadamard gate to either a 0 or 1 qubit will produce aquantum 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 standardprobabilistic 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.

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${\displaystyle {\log }_{2}N}$ operations, compared to the classical case of${\displaystyle N{\log }_{2}N}$ operations.

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

The resulting uniform quantum superposition state is then:${\displaystyle 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${\displaystyle N=2^n}$.^[5]

Measurement of this uniform quantum state results in arandom state between${\displaystyle |0⟩}$ and${\displaystyle |N-1⟩}$.

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

Preparation of uniform quantum superposition states in the general case, when${\displaystyle N}$ ≠${\displaystyle 2^n}$ is non-trivial and requires more work. An efficient and deterministic approach for preparing the superposition state$${\displaystyle |\mathrm{\Psi }⟩=\frac{1}{\sqrt{N}}\sum _{j=0}^{N-1}|j⟩}$$with a gate complexity and circuit depth of only${\displaystyle O({\log }_{2}N)}$ for all${\displaystyle N}$ was recently presented.^[6] This approach requires only${\displaystyle 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${\displaystyle |\mathrm{\Psi }⟩}$.

The Hadamard transform can be used to estimatephylogenetic trees from molecular data.^[7][8][9]Phylogenetics is the subfield ofevolutionary biology focused on understanding the relationships among organisms. A Hadamard transform applied to a vector (or matrix) of site pattern frequencies obtained from a DNAmultiple 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 formaximum 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^[10][11] that are much more efficient. However, the invertible nature of the phylogenetic Hadamard transform does provide an elegant tool for mathematic phylogenetics.^[12][13]

The mechanics of the phylogenetic Hadamard transform involve the calculation of a vector${\displaystyle \gamma (T)}$ that provides information about the topology and branch lengths for tree${\displaystyle T}$ using thesite pattern vector or matrix${\displaystyle s(T)}$.

$${\displaystyle \gamma (T)=H^{-1}(\ln (Hs(T)))}$$where${\displaystyle H}$ is the Hadamard matrix of the appropriate size. This equation can be rewritten as a series of three equations to simplify its interpretation:

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

$${\displaystyle s(T)=H^{-1}(\exp (H\gamma (T)))}$$

We can use the Cavender–Farris–Neyman (CFN) two-statesubstitution model for DNA by encoding thenucleotides as binary characters (thepurines A and G are encoded as R and thepyrimidines C and T are encoded as Y). This makes it possible to encode the multiple sequence alignment as the site pattern vector${\displaystyle s(T)}$ that can be converted to a tree vector${\displaystyle \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^[14])

Index	Binary pattern	Alignment patterns	${\displaystyle \gamma (T)}$	${\displaystyle \rho =H^{-1}\gamma (T)}$	${\displaystyle r=\exp (\rho )}$	${\displaystyle s(T)=H^{-1}\rho }$
0	0000	RRRR and YYYY	−0.475	0	1	0.6479
1	0001	RRRY and YYYR	0.2	−0.5	0.6065	0.1283
2	0010	RRYR and YYRY	0.025	−0.15	0.8607	0.02
3*	0011	RRYY and YYRR	0.025	−0.45	0.6376	0.0226
4	0100	RYRR and YRYY	0.2	−0.45	0.6376	0.1283
5*	0101	RYRY and YRYR	0	−0.85	0.4274	0.0258
6*	0110	RYYR and YRRY	0	−0.5	0.6065	0.0070
7	0111	RYYY and YRRR	0.025	−0.9	0.4066	0.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)); innewick format. The site patterns are written in the order ABCD. This particular tree has two long terminal branches (0.2transversion 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 exhibitlong branch attraction if the data are analyzed using themaximum 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${\displaystyle 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${\displaystyle \gamma (T)}$ corresponds to the correct tree. Parsimony analysis after the transformation is thereforestatistically consistent,^[15] 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 theKimura 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^[16] 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 theKlein four-group:

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),^[16] which is based on a multiple sequence alignment of four primate hemoglobin pseudogenes:

The much larger number of site patterns in column 0 reflects the fact that column 0 corresponds totransition differences, which accumulate more rapidly than transversion differences in virtually all comparisons of genomic regions (and definitely accumulate more rapidly in thehemoglobin pseudogenes used for this worked example^[17]). 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 secondKlein 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).

The Hadamard transform is also used indata encryption, as well as manysignal processing anddata compressionalgorithms, such asJPEG XR andMPEG-4 AVC. Invideo compression applications, it is usually used in the form of thesum 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 asNMR,mass spectrometry andcrystallography. It is additionally used in some versions oflocality-sensitive hashing, to obtain pseudo-random matrix rotations.

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

• Ritter, Terry (August 1996)."Walsh–Hadamard Transforms: A Literature Survey".
• Akansu, Ali N.; Poluri, R. (July 2007)."Walsh-Like Nonlinear Phase Orthogonal Codes for Direct Sequence CDMA Communications"(PDF).IEEE Transactions on Signal Processing.55 (7):3800–6.Bibcode:2007ITSP...55.3800A.doi:10.1109/TSP.2007.894229.S2CID 6830633.
• Pan, Jeng-shyangData 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)
• Beddard, Godfrey; Yorke, Briony A. (January 2011)."Pump-probe Spectroscopy using Hadamard Transforms"(PDF). Archived fromthe original(PDF) on 2014-10-18. Retrieved2012-04-28.
• Yorke, Briony A.; Beddard, Godfrey; Owen, Robin L.; Pearson, Arwen R. (September 2014)."Time-resolved crystallography using the Hadamard transform".Nature Methods.11 (11):1131–1134.doi:10.1038/nmeth.3139.PMC 4216935.PMID 25282611.

• Quantum algorithms
• Transforms

• CS1: long volume value
• Articles with short description
• Short description is different from Wikidata
• Use American English from January 2019
• All Wikipedia articles written in American English
• Pages with French IPA
• Articles to be expanded from April 2024