Worldlex Wiki 
La transformée de Hadamard (également connue sous le nom de transformée de Walsh-Hadamard , transformée de Hadamard-Rademacher-Walsh , transformée de Walsh ou transformée de Walsh-Fourier ) est un exemple de transformée de Fourier généralisée . Elle effectue une opération orthogonale , symétrique , involutive et linéaire sur un n-uplet de nombres .
La transformée de Hadamard peut être considérée comme étant construite à partir de transformées de Fourier discrètes (TFD) de taille 2 , et est en fait équivalente à une TFD multidimensionnelle de taille [ adamaʁ ] ), du mathématicien germano-américain Hans Rademacher et du mathématicien américain Joseph L. Walsh .
Définition
La transformée de Hadamard H m est une matrice 2 m × 2 m , la matrice de Hadamard (mise à l'échelle par un facteur de normalisation), qui transforme 2 m nombres réels x n en 2 m nombres réels X k . La transformée de Hadamard peut être définie de deux manières : récursivement , ou en utilisant la représentation binaire ( base -2) des indices n et k .
Par récurrence, nous définissons la transformée de Hadamard 1 × 1 H 0 par l' identité H 0 = 1, puis nous définissons H m pour m > 0 par :
Pour m > 1, on peut également définir H m par :
De manière équivalente, on peut définir la matrice de Hadamard par son élément ( k , n ) en écrivant
où k<sub> j </sub> et n<sub> j</sub> sont les éléments binaires (0 ou 1) de k et n , respectivement. Notez que pour l'élément situé dans le coin supérieur gauche, nous définissons :
C'est précisément cela le multidimensionnel
Voici quelques exemples de matrices de Hadamard.
H 1 correspond précisément à la DFT de taille 2. Elle peut également être considérée comme la transformée de Fourier sur le groupe additif à deux éléments de Z /(2).
Les lignes des matrices de Hadamard sont les fonctions de Walsh .
Relation avec la transformée de Fourier
La transformée de Hadamard est équivalente à une DFT multidimensionnelle de taille [ En utilisant la transformée de Fourier sur les groupes finis (abéliens) , la transformée Fourier d'une fonction
[ En utilisant la Il s'agit de la transformée de Hadamard de
En termes de la formulation ci-dessus où la transformée de Hadamard multiplie un vecteur de
La transformée de Fourier discrète usuelle , appliquée à un vecteur
Complexité computationnelle
Dans le domaine classique, la transformée de Hadamard peut être calculée en
Dans le domaine quantique, la transformée de Hadamard peut être calculée en
Applications de l'informatique quantique
La transformée de Hadamard est largement utilisée en informatique quantique . La transformée de Hadamard 2 × 2 en parallèle est équivalent à la transformation de Hadamard.
.Porte d'Hadamard
etopérations de la porte d'Hadamard
L'application de la porte de Hadamard à un qubit 0 ou 1 produit un état quantique qui, s'il est observé, sera un 0 ou un 1 avec une probabilité égale (comme illustré dans les deux premières opérations). Ceci est identique au lancer d'une pièce équilibrée dans le modèle probabiliste standard du calcul . Cependant, si la porte de Hadamard est appliquée deux fois de suite (comme c'est le cas dans les deux dernières opérations), l'état final est toujours identique à l'état initial.
Transformation de Hadamard dans les algorithmes quantiques
Le calcul de la transformée de Hadamard quantique se résume à l'application d'une porte de Hadamard à chaque qubit individuellement, en raison de la structure de produit tensoriel de cette transformée. Ce résultat simple implique que la transformée de Hadamard quantique nécessite
Pour un
L'état de superposition quantique uniforme résultant est alors :
La mesure de cet état quantique uniforme donne lieu à un état aléatoire entre
De nombreux algorithmes quantiques utilisent la transformation de Hadamard comme étape initiale, car, comme expliqué précédemment, elle transforme n qubits initialisés avec
Préparation d'états de superposition quantique uniformes dans le cas général, lorsque
Réseaux neuronaux convolutifs
La transformée de Hadamard trouve des applications en apprentissage automatique quantique , notamment dans les réseaux de neurones hybrides quantiques-classiques. La convolution dyadique entre deux vecteurs équivaut à la multiplication terme à terme de leurs représentations par transformée de Hadamard ; ainsi, les couches convolutionnelles peuvent être réalisées efficacement en appliquant la transformée de Hadamard, en multipliant les vecteurs, puis en inversant cette transformée. Alors que le calcul classique de la transformée de Hadamard nécessite O( n log n ) opérations avec l’algorithme rapide de Hadamard, l’implémentation quantique permet de calculer la transformée en O(1) en appliquant simultanément des portes de Hadamard à tous les qubits.
Application en biologie évolutive
La transformation de Hadamard permet d'estimer les arbres phylogénétiques à partir de données moléculaires. Appliquée à un vecteur (ou une matrice) de fréquences de motifs de sites, obtenu par alignement multiple de séquences d'ADN, cette transformation génère un vecteur contenant des informations sur la topologie de l'arbre. L'inversibilité de la transformation de Hadamard phylogénétique permet également de calculer les vraisemblances des sites à partir d'un vecteur de topologie, ce qui rend possible son utilisation pour l'estimation du maximum de vraisemblance des arbres phylogénétiques.
Cette dernière application est moins utile que la transformation du vecteur de motifs de sites en vecteur d'arbre, car il existe d'autres méthodes de calcul des vraisemblances de sites bien plus efficaces. Cependant, l'inversibilité de la transformation phylogénétique de Hadamard constitue un outil élégant pour la phylogénétique mathématique.
Le mécanisme de la transformation phylogénétique de Hadamard implique le calcul d'un vecteur
La nature inversible de cette équation permet de calculer un vecteur (ou une matrice) de configuration de site attendu comme suit :
On peut utiliser le modèle de substitution à deux états de Cavender-Farris- Neyman (CFN) pour l'ADN en codant les nucléotides sous forme de caractères binaires (les purines A et G sont codées par R et les pyrimidines C et T par Y). Ceci permet de coder l'alignement de séquences multiples sous forme de vecteur de motifs de sites.
L'exemple présenté dans ce tableau utilise le schéma simplifié à trois équations et concerne un arbre à quatre taxons pouvant s'écrire ((A,B),(C,D)) ; au format Newick . Les motifs de sites sont écrits dans l'ordre ABCD. Cet arbre particulier possède deux longues branches terminales (0,2 substitutions par transversion par site), deux courtes branches terminales (0,025 substitutions par transversion par site) et une courte branche interne (0,025 substitutions par transversion par site) ; il s'écrirait donc ((A:0,025,B:0,2):0,025,(C:0,025,D:0,2)) ; au format Newick. Cet arbre présentera une attraction des longues branches si les données sont analysées selon le critère de parcimonie maximale (en supposant que la séquence analysée soit suffisamment longue pour que les fréquences des motifs de sites observés soient proches des fréquences attendues indiquées dans le tableau).
Notez que le motif de site avec 0 correspond aux sites qui n'ont pas changé (après encodage des nucléotides en purines ou pyrimidines). Les indices marqués d'un astérisque (3, 5 et 6) sont « informatifs pour la parcimonie », et les indices restants représentent des motifs de site où un taxon diffère des trois autres (ils sont donc équivalents aux longueurs des branches terminales dans un arbre phylogénétique standard de vraisemblance maximale).
Si l'on souhaite utiliser des données nucléotidiques sans les recoder en R et Y (et finalement en 0 et 1), il est possible d'encoder les motifs de sites sous forme de matrice. Dans un arbre à quatre taxons, on compte 256 motifs de sites (quatre nucléotides à la puissance 4). Cependant, les symétries du modèle de Kimura à trois paramètres (ou K81) permettent de réduire ces 256 motifs à 64, rendant ainsi possible l'encodage des données nucléotidiques d'un arbre à quatre taxons sous forme d'une matrice 8 × 8 de manière similaire au vecteur à 8 éléments utilisé précédemment pour les motifs de sites de transversion (RY). Ceci est réalisé en recodant les données à l'aide du groupe de Klein à quatre dimensions .
Comme pour les données RY, les motifs de sites sont indexés par rapport à la base du premier taxon choisi arbitrairement, les bases des taxons suivants étant codées par rapport à cette première base. Ainsi, le premier taxon reçoit la paire de bits (0,0). À partir de ces paires de bits, on peut générer deux vecteurs similaires aux vecteurs RY, puis remplir la matrice avec ces vecteurs. Ceci peut être illustré par l'exemple de Hendy et al. (1994), , basé sur un alignement multiple de séquences de quatre pseudogènes d'hémoglobine de primates :
Le nombre beaucoup plus élevé de motifs de sites dans la colonne 0 reflète le fait que cette colonne correspond aux différences de transition , qui s'accumulent plus rapidement que les différences de transversion dans pratiquement toutes les comparaisons de régions génomiques (et s'accumulent encore plus rapidement dans les pseudogènes de l'hémoglobine utilisés pour cet exemple ). Si l'on considère le motif de site AAGG, le motif binaire serait 0000 pour le second élément de la paire de bits du groupe de Klein et 0011 pour le premier. Dans ce cas, le motif binaire est basé sur le premier élément, qui correspond à l'indice 3 (donc la ligne 3 de la colonne 0 ; indiqué par un astérisque dans le tableau). Les motifs de sites GGAA, CCTT et TTCC seraient encodés exactement de la même manière. Le motif de site AACT serait encodé avec le motif binaire 0011 basé sur le second élément et 0001 basé sur le premier ; cela donne l'indice 1 pour le premier élément et l'indice 3 pour le second. L'index basé sur la deuxième paire de bits du groupe de Klein est multiplié par 8 pour obtenir l'index de colonne (dans ce cas, il s'agirait de la colonne 24). La cellule qui inclurait le nombre de motifs de site AACT est indiquée par deux astérisques ; cependant, l'absence de nombre dans l'exemple indique que l'alignement de séquence ne contient aucun motif de site AACT (de même, les motifs de site CCAG, GGTC et TTGA, qui seraient encodés de la même manière, sont absents).
Autres applications
La transformée de Hadamard est également utilisée en chiffrement de données , ainsi que dans de nombreux algorithmes de traitement du signal et de compression de données , tels que JPEG XR et MPEG-4 AVC . En compression vidéo , elle est généralement employée sous la forme de la somme des différences transformées absolues . Elle constitue également un élément crucial d'un nombre important d'algorithmes en informatique quantique. La transformée de Hadamard est aussi utilisée dans des techniques expérimentales telles que la RMN , la spectrométrie de masse et la cristallographie . Enfin, elle est employée dans certaines versions du hachage sensible à la localité , afin d'obtenir des rotations de matrices pseudo-aléatoires.