Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Hadamard transform
Summary
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 2m 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 2 × 2 × ⋯ × 2 × 2. It decomposes an arbitrary input vector into a superposition of Walsh functions.
The transform is named for the French mathematician Jacques Hadamard (adamaʁ), the German-American mathematician Hans Rademacher, and the American mathematician Joseph L. Walsh.
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:
where the 1/ is a normalization that is sometimes omitted.
For m > 1, we can also define Hm by:
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 (k, n)-th entry by writing
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: . In this case, we have:
This is exactly the multidimensional 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.
where is the bitwise dot product of the binary representations of the numbers i and j.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Ontological neighbourhood
Related courses (7)
MATH-646: Reading group in quantum computing
Quantum computing has received wide-spread attention lately due the possibility of a near-term breakthrough of quantum supremacy. This course acts as an introduction to the area of quantum computing.
PHYS-641: Quantum Computing
After introducing the foundations of classical and quantum information theory, and quantum measurement, the course will address the theory and practice of digital quantum computing, covering fundament
CS-308: Introduction to quantum computation
The course introduces the paradigm of quantum computation in an axiomatic way. We introduce the notion of quantum bit, gates, circuits and we treat the most important quantum algorithms. We also touch
Related lectures (35)
Shor Algorithm: Quantum Factorization
Covers the Shor algorithm for quantum factorization and the general formula for arithmetic periods.
Shor's Factoring Algorithm
Covers Shor's factoring algorithm, which efficiently factors large numbers using quantum computers.
Quantum and Nanocomputing
Covers standard transformations, entanglement, superpositions, and measurements in quantum computing.
Related publications (52)
Related people (13)
Related units (2)