Transformée de Hadamard

La transformée d´Hadamard est un exemple d'une classe généralisée d'une transformée de Fourier. Elle est appelée selon le mathématicien français Jacques Hadamard...

Catégories :

Informatique quantique - Mécanique quantique - Physique quantique

Source image : fr.wikipedia.org
Cette image est un résultat de recherche de Google Image. Elle est peut-être réduite par rapport à l'originale et/ou protégée par des droits d'auteur.

Page(s) en rapport avec ce sujet :

Nous venons de voir que la transformation d'Hadamard s'obtient en ef- fectuant le produit de la matrice d'Hadamard par le vecteur des données f.... (source : blackwell-synergy)

La transformée d´Hadamard (aussi connue sous le nom de «transformée de Walsh-Hadamard») est un exemple d'une classe généralisée d'une transformée de Fourier. Elle est appelée selon 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, quoique les matrices utilisées possèdent des cœfficients réels). Ces matrices sont des matrices de Hadamard.

La transformée de Hadamard peut être vue comme étant issue d'une transformée de Fourier discrète et s'avère être en fait l'équivalent d'une transformée de Fourier discrète multidimensionnelle d'une taille de $2\times2\times\cdots\times2\times2$ . Elle décompose un vecteur arbitraire en entrée en une superposition de fonctions de Walsh.

Définition formelle

La transformée de Hadamard $H m$ utilise une matrice $2ˆm \times 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\times1$ via une matrice $H 0$ qui est la matrice identité avec un seul élément (1). On définit ensuite $H m$ pour $m > 0$ grâce à la relation suivante :

$H_m = \frac{1}{\sqrt2} \begin{pmatrix} H_{m-1} & H_{m-1} \\ H_{m-1} & -H_{m-1} \end{pmatrix},$

où $1/\sqrt2$ est un facteur de normalisation qui est quelquefois omis. Ainsi, à l'exception de la normalisation, les cœfficients 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 à $k=k_{m-1} 2ˆ{m-1} + k_{m-2} 2ˆ{m-2} + \cdots + k_1 2 + k_0$ et $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 $n$ et $k$ . Dans ce cas, on obtient

$\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\times2\times\cdots\times2\times2$ normalisée de façon à être unitaire, si on considère les entrées et les sorties comme des tableaux multidimensionnels indexés par $n j$ et $k j$ .

Quelques matrices de Hadamard :

$∼H_0 = 1$

$H_1 = \frac{1}{\sqrt2} \begin{pmatrix}\begin{array}{rr} 1 & 1 \\ 1 & -1 \end{array}\end{pmatrix}$

$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}$

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

Applications

Dans le traitement de l'informatique quantique, la transformation de Hadamard, plus fréquemment nommée «porte de Hadamard» dans ce contexte, est une rotation d'un qubit. Elle sert à transformer les états $|0 \rangle$ et $|1 \rangle$ du qubit en deux états juxtaposés avec un poids identique : $|0 \rangle$ et $|1 \rangle$ . Généralement, les phases sont choisies de telle manière que :

$\frac{|0\rangle+|1\rangle}{\sqrt{2}}\langle0|+\frac{|0\rangle-|1\rangle}{\sqrt{2}}\langle1|$

dans la notation de Dirac. Cela correspond à la matrice de transformation :

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

dans la base $|0 \rangle , |1 \rangle$ .

La plupart d'algorithmes quantiques utilisent la transformation de Hadamard comme première étape, puisque elle transforme n qubits initialisés avec |0› en une superposition de l'ensemble des 2ⁿ états orthogonaux exprimés dans la base $|0 \rangle , |1 \rangle$ avec une pondération identique.

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

Autres applications

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.

Recherche sur Amazone (livres) :

Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Transform%C3%A9e_de_Hadamard.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 13/04/2009.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.