Transformée de Hadamard — Wikipédia

Cet article ne cite pas suffisamment ses sources (janvier 2014).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

La transformée de Hadamard^[1] (aussi connue sous le nom de « transformée de Walsh-Hadamard ») est nommée d'après le mathématicien français Jacques Hadamard et effectue une opération linéaire et involutive avec une matrice orthogonale et symétrique sur 2^m nombres réels (ou complexes, bien que les matrices utilisées possèdent des coefficients réels). Ces matrices sont des matrices de Hadamard.

La transformée de Hadamard peut être vue comme étant une transformée de Fourier discrète multidimensionnelle d'une taille de 2×2×...×2×2. Elle décompose un vecteur arbitraire en entrée en une superposition de fonctions de Walsh^[2].

La transformée de Hadamard H_m utilise une matrice 2^m×2^m (une matrice de Hadamard) multipliée par un facteur de normalisation, et transforme 2^m nombres réels x_n en 2^m nombres réels X_k. La transformée peut être définie de deux manières : récursivement ou en utilisant une représentation binaire des indices n et k.

Récursivement, on définit une première transformation 1×1 via une matrice H₀ qui est la matrice identité avec une seule ligne, une seule colonne, donc seul élément (1). On définit ensuite H_m pour m > 0 grâce à la relation suivante :

${\displaystyle H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}}$

ou bien en utilisant le produit tensoriel pour ${\displaystyle m>1}$ : ${\displaystyle H_{m}=H_{1}\otimes H_{m-1}}$ avec ${\displaystyle H_{1}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}$

1/√2 est un facteur de normalisation qui est parfois omis. Ainsi, à l'exception de la normalisation, les coefficients de la matrice sont égaux à 1 ou -1.

De manière équivalente, on peut définir l'élément (k,n) d'une matrice de Hadamard grâce à ${\displaystyle k=k_{m-1}2^{m-1}+k_{m-2}2^{m-2}+\cdots +k_{1}2+k_{0}}$ et ${\displaystyle n=n_{m-1}2^{m-1}+n_{m-2}2^{m-2}+\cdots +n_{1}2+n_{0}}$, où k_j et n_j sont le bit j (0 ou 1) de respectivement k et n. Dans ce cas, on obtient

${\displaystyle \left(H_{m}\right)_{k,n}={\frac {1}{2^{m/2}}}(-1)^{\sum _{j}k_{j}n_{j}}}$.

Il s'agit d'une transformée de Fourier discrète 2×2×...×2×2 normalisée de manière à être unitaire, si l'on considère les entrées et les sorties comme des tableaux multidimensionnels indexés par n_j et k_j.

Les premières matrices de Hadamard sont données par :

${\displaystyle ~H_{0}=1}$

${\displaystyle H_{1}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}{\begin{array}{rr}1&1\\1&-1\end{array}}\end{pmatrix}}}$

${\displaystyle H_{2}={\frac {1}{2}}{\begin{pmatrix}{\begin{array}{rrrr}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{array}}\end{pmatrix}}}$

${\displaystyle H_{3}={\frac {1}{2^{3/2}}}{\begin{pmatrix}{\begin{array}{rrrrrrrr}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}}\end{pmatrix}}}$

Les lignes d'une matrice de Hadamard forment des fonctions de Walsh.

Dans le traitement de l'informatique quantique, la transformation de Hadamard est appelée « porte de Hadamard » lorsqu'elle agit sur un seul qubit. Elle permet de transformer les états ${\displaystyle |0\rangle }$ et ${\displaystyle |1\rangle }$ du qubit en deux états superposés avec un poids égal : ${\displaystyle |0\rangle }$ et ${\displaystyle |1\rangle }$. Dans la base ${\displaystyle |0\rangle }$, ${\displaystyle |1\rangle }$ cela correspond à la matrice de transformation :

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

Dans toute autre base, en utilisant la notation de Dirac, si l'on note ${\displaystyle H}$ l'operateur de Hadamard agissant sur un état ${\displaystyle |\psi _{0}\rangle }$ pour donner un état ${\displaystyle |\psi _{1}\rangle }$ tel que ${\displaystyle |\psi _{1}\rangle =|H|\psi _{0}\rangle }$

${\displaystyle H={\frac {|0\rangle +|1\rangle }{\sqrt {2}}}\langle 0|+{\frac {|0\rangle -|1\rangle }{\sqrt {2}}}\langle 1|}$

Un grand nombre d'algorithmes quantiques utilisent la transformation de Hadamard comme première étape, car la supériorité du calcul quantique provient de l'exploration d'un domaine de possibilités par des états superposés. La transformation de Hadamard transforme n qubits initialisés avec ${\displaystyle |0\rangle }$ en une superposition de tous les 2ⁿ états orthogonaux.

À titre d'exemple, l'algorithme de Shor fait appel à une telle transformation.

La transformation est utilisée en cryptographie, on parle alors de pseudo-transformation de Hadamard. Elle est aussi utilisée pour générer des nombres aléatoires à partir d'une distribution gaussienne. On l'utilise aussi dans la compression de données comme dans l'algorithme H.264 et pour des opérations de traitement du signal.

La transformation de Hadamard est également utilisée pour étudier l'évolution de systèmes au cours du temps par des méthodes expérimentales telles que la cristallographie aux rayons X^[3].

• Portail des mathématiques
• Portail de l'informatique théorique