Hadamard-Transformation: Enthüllung der Leistungsfähigkeit der Hadamard-Transformation in der Computer Vision

Von Fouad Sabry

Was ist die Hadamard-Transformation?

Die Hadamard-Transformation ist ein Beispiel für eine verallgemeinerte Klasse von Fourier-Transformationen. Es führt eine orthogonale, symmetrische, involutive, lineare Operation an 2m reellen Zahlen durch.

Wie Sie profitieren

(I) Einblicke und Validierungen über Folgende Themen werden behandelt:

Kapitel 1: Hadamard-Transformation

Kapitel 2: Diskrete Fourier-Transformation

Kapitel 3: Schnelle Walsh?Hadamard-Transformation

Kapitel 4: Quanten-Fourier-Transformation

Kapitel 5: Braket-Notation

Kapitel 6: Pauli-Matrizen

Kapitel 7: Quantenlogikgatter

Kapitel 8: Kontrolliertes NICHT-Gatter

Kapitel 9: Verallgemeinerungen von Pauli-Matrizen

Kapitel 10: Sphärische Basis

(II) Beantwortung der öffentlichen Top-Fragen zu Hadamard-Transformation.

(III) Beispiele aus der Praxis für die Verwendung von Hadamard-Transformation in vielen Bereichen.

Für wen dieses Buch gedacht ist

Profis, Studenten und Doktoranden, Enthusiasten, Hobbyisten und diejenigen, die über das Grundwissen oder die Informationen für jede Art von Hadamard-Transformation hinausgehen möchten.

 

 

• Sprache: Deutsch
• Herausgeber: Eine Milliarde Sachkundig [German]
• Erscheinungsdatum: 28. Apr. 2024

Buchvorschau

Kapitel 1: Hadamard-Verwandlung

Die Hadamard-Transformation (auch als Walsh-Hadamard-Transformation, Hadamard-Transformation, Rademacher-Walsh-Transformation und Walsh-Transformation, Walsh-Transformation oder Walsh-Fourier-Transformation bezeichnet) ist eine Art von Fourier-Transformation, die zu einer breiteren Kategorie gehört.

Es löst eine orthogonale Gleichung, symmetrische, involutive, lineare Operation auf 2m reellen Zahlen (oder komplexen, sehr komplizierten Zahlen, obwohl Hadamard-Matrizen völlig nicht-imaginär sind).

Man kann sich die Hadamard-Transformation so vorstellen, dass sie aus diskreten Fourier-Transformationen der Größe 2 konstruiert ist. (DFTs) und ist in der Tat äquivalent zu einer mehrdimensionalen DFT der Größe 2 × 2 × ⋯ × 2 × 2.

Es nimmt einen beliebigen Eingabevektor und zerlegt ihn in eine Überlagerung von Walsh-Funktionen.

Benannt ist die Transformation nach dem französischen Mathematiker Jacques Hadamard (französisch: [adamaʁ]), dem Mathematiker deutscher und amerikanischer Abstammung Hans Rademacher und Joseph L. Weisstein Jr. aus den Vereinigten Staaten.

Walsh.

Die Hadamard-Transformation Hm ist eine 2m- × 2m-Matrix, die Hadamard-Matrix (skaliert mit einem Normalisierungsfaktor), die 2m reelle Zahlen xn in 2m reelle Zahlen Xk umwandelt.

Es gibt zwei verschiedene Ansätze, um die Hadamard-Transformation zu definieren, alternativ durch Schreiben von n und k in binärer Form (Basis 2).

Rekursiv definieren wir die 1 × 1 Hadamard-Transformation H0 durch die Identität H0 = 1 und definieren dann Hm für m > 0 durch:

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

wobei die 1/√2 eine Normalisierung ist, die manchmal weggelassen wird.

Für m > 1 können wir Hm  auch wie folgt definieren:

{\displaystyle H_{m}=H_{1}\otimes H_{m-1}}

wobei \otimes das Kronecker-Produkt steht.

Abgesehen von diesem Standardisierungsparameter sind Hadamard-Matrizen also alle Einsen und Nullen.

Alternativ kann die Hadamard-Matrix durch ihr (k, n)-tes Element definiert werden, wie im Folgenden gezeigt

{\displaystyle {\begin{aligned}k&=\sum _{i=0}^{m-1}{k_{i}2^{i}}=k_{m-1}2^{m-1}+k_{m-2}2^{m-2}+\dots +k_{1}2+k_{0}\\n&=\sum _{i=0}^{m-1}{n_{i}2^{i}}=n_{m-1}2^{m-1}+n_{m-2}2^{m-2}+\dots +n_{1}2+n_{0}\end{aligned}}}

wobei kj und nj die Bitelemente (0 oder 1) von k bzw. n sind.

Achtung, das heißt, für den Punkt oben links definieren wir: k=n=0 .

Hier haben wir jedoch:

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

Dies ist genau die multidimensionale {\textstyle 2\times 2\times \cdots \times 2\times 2} DFT, die einem einzigen Standard entspricht, wenn die Ein- und Ausgänge als mehrdimensionale Arrays betrachtet werden, die durch nj bzw. kj indiziert sind.

Hier sind einige spezifische Beispiele für die Hadamard-Matrix.

{\displaystyle {\begin{aligned}H_{0}&=+{\begin{pmatrix}1\end{pmatrix}}\\[5pt]H_{1}&={\frac {1}{\sqrt {2}}}\left({\begin{array}{rr}1&1\\1&-1\end{array}}\right)\\[5pt]H_{2}&={\frac {1}{2}}\left({\begin{array}{rrrr}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{array}}\right)\\[5pt]H_{3}&={\frac {1}{2^{3/2}}}\left({\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}}\right)\\[5pt](H_{n})_{i,j}&={\frac {1}{2^{n/2}}}(-1)^{i\cdot j}\end{aligned}}}

wobei i\cdot j das bitweise Punktprodukt der binären Darstellungen der Zahlen i und j ist.

Wenn z. B. , {\textstyle n\;\geq \;2} dann

{\displaystyle (H_{n})_{3,2}\;=\;(-1)^{3\cdot 2}\;=\;(-1)^{(1,1)\cdot (1,0)}\;=\;(-1)^{1+0}\;=\;(-1)^{1}\;=\;-1}

Bestätigen des Vorhergehenden (Ignorieren der Gesamtkonstante).

Beachten Sie, dass die erste Zeile, das erste Spaltenelement der Matrix mit bezeichnet wird {\textstyle (H_{n})_{0,0}} .

H1 ist genau die Größe 2 DFT.

Die additive Gruppe aus zwei Elementen, Z/, kann man sich so vorstellen, dass sie eine Fourier-Transformation durchläuft (2).

Hadamard-Matrizen haben Walsh-Funktionen in ihren Zeilen.

Sei H = Hm,n] eine Matrix H, die der vorhergehenden Definition entspricht.

{\displaystyle H[m,n]={\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}

Die Walsh-Transformation erzeugt eine Matrix, die nur die Einträge 1 und 1 enthält. Aufgrund der Beschaffenheit von 1 und 1, die beide keine komplexen Zahlen sind, ist eine komplexe Zahlenberechnung unnötig.

Irrationale Multiplikation ist für die DFT erforderlich, aber nicht für die Hadamard-Transformation. In der Tat sind Vorzeichenwechsel ausreichend, daher ist eine rationale Multiplikation unnötig.

Alle Einträge in der ersten Zeile (und Spalte) der Walsh-Transformationsmatrix sind 1.

{\displaystyle H[m,n]=\left({\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}}\right)}

Diskrete Fourier-Transformation:

{\displaystyle e^{-j2\pi mn/N}}

Wenn m gleich Nullen ist (der Durchschnitt der ersten Zeile), ergibt die diskrete Fourier-Transformation (DFT) ebenfalls 1. Trotz der Unterschiede zur ersten Reihe offenbart die zweite Reihe ein wichtiges Merkmal der Matrix: Das Signal in der anfänglichen Rohmatrix ist niederfrequent, was sich aber im Laufe der Reihen ändert.

Wenn wir die Nulldurchgangsberechnung verwenden:

Erste Zeile = 0 Nulldurchgang

Zweite Reihe = 1 Nulldurchgang

Dritte Reihe = 2 Nulldurchgänge

⋮

Acht Reihen = 7 Nulldurchgänge

Die Hadamard-Transformation ist in der Tat äquivalent zu einer mehrdimensionalen DFT der Größe 2 × 2 × ⋯ × 2 × 2.

Ein anderer Ansatz besteht darin, die Hadamard-Transformation als Fourier-Transformation auf der Booleschen Gruppe zu betrachten {\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}} .

Wendet man die Fourier-Transformation auf endliche Gruppen (abelsche Transformation) an, so ist die Fourier-Transformation einer Funktion {\displaystyle f\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} } die Funktion, die {\widehat {f}} durch

{\displaystyle {\widehat {f}}(\chi )=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a){\bar {\chi }}(a)}

wobei \chi ein Zeichen von (\Z/2\Z)^n ist.

Jedes Zeichen hat die Form {\displaystyle \chi _{r}(a)=(-1)^{a\cdot r}} für einige {\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}} , wobei eine Bitzeichenfolge mit sich selbst multipliziert wird, indem das boolesche Punktprodukt verwendet wird, so dass wir die Eingabe mit {\widehat {f}} identifizieren {\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}} können (Pontrjagin-Dualität) und {\displaystyle {\widehat {f}}\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} } definieren durch

{\displaystyle {\widehat {f}}(r)=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a)(-1)^{r\cdot a}}

Dies ist die Hadamard-Transformation von f unter Berücksichtigung der Eingabe in f und {\widehat {f}} als boolesche Zeichenfolgen.

In Bezug auf die obige Formulierung, bei der die Hadamard-Transformation einen Vektor 2^{n} komplexer Zahlen v auf der linken Seite mit der Hadamard-Matrix H_{n} multipliziert, wird die Äquivalenz dadurch gesehen, dass f als Eingabe die Bitzeichenfolge genommen wird, die dem Index eines Elements von v entspricht, und f das entsprechende Element von ausgegeben v wird.

Vergleichen Sie dies mit der üblichen diskreten Fourier-Transformation, die, wenn sie auf einen Vektor komplexer Zahlen angewendet wird, v 2^{n} stattdessen Zeichen der zyklischen Gruppe verwendet {\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} } .

Während das klassische Feld die Hadamard-Transformation in n\log n Operationen () berechnet werden kann, n=2^{m} indem eine schnelle Hadamard-Transformationsmethode verwendet wird.

In der Quantenmechanik kann die Hadamard-Transformation in der Zeit berechnet werden O(1) , da es sich um ein parallelisierbares Quantenlogikgatter handelt.

Quantencomputer stützen sich stark auf die Hadamard-Transformation.

Die 2 × 2 Hadamard-Transformation H_{1} ist das Quantenlogikgatter, das als Hadamard-Gatter bekannt ist, und die Anwendung eines Hadamard-Gatters auf jedes Qubit eines n-Qubit-Registers parallel ist äquivalent zur Hadamard-Transformation H_{n} .

Bei der Berechnung auf Quantenebene führt das Hadamard-Gatter eine Rotation eines einzelnen Qubits durch, wobei die Qubit-Basiszustände |0\rangle und |1\rangle zwei Überlagerungszustände mit gleichem Gewicht der Rechenbasiszustände |0\rangle und  abgebildet |1\rangle werden.

Die Phasen werden in der Regel so ausgewählt, dass sichergestellt ist, dass

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

in der Notation von Dirac. Das ist übrigens die Matrix, die die Transformation durchführt.

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

in der |0\rangle ,|1\rangle Basis, äquivalent zur rechnerischen Grundlage.

Die Zustände {\textstyle {\frac {\left|0\right\rangle +\left|1\right\rangle }{\sqrt {2}}}} und {\textstyle {\frac {\left|0\right\rangle -\left|1\right\rangle }{\sqrt {2}}}} werden als {\displaystyle \left|{\boldsymbol {+}}\right\rangle } {\displaystyle \left|{\boldsymbol {-}}\right\rangle } bzw. bezeichnet, zusammen bilden sie die polare Grundlage des Quantencomputings.

{\displaystyle {\begin{aligned}H(|0\rangle )&={\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle =:|+\rangle \\H(|1\rangle )&={\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle =:|-\rangle \\H(|+\rangle )&=H\left({\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{2}}{\Big (}|0\rangle +|1\rangle {\Big )}+{\frac {1}{2}}{\Big (}|0\rangle -|1\rangle {\Big )}=|0\rangle \\H(|-\rangle )&=H\left({\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{2}}{\Big (}|0\rangle +|1\rangle {\Big )}-{\frac {1}{2}}{\Big (}|0\rangle -|1\rangle {\Big )}=|1\rangle \end{aligned}}}

Wenn das Hadamard-Gatter auf ein 0- oder 1-Qubit angewendet wird, erzeugt es einen Quantenzustand, der mit gleicher Wahrscheinlichkeit entweder 0 oder 1 ist. (wie in den ersten beiden Operationen zu sehen). Im traditionellen probabilistischen Paradigma der Berechnung ist dies gleichbedeutend mit dem Werfen einer fairen Münze. Der Endzustand ist immer derselbe wie der Ausgangszustand, wenn das Hadamard-Tor zweimal hintereinander angewendet wird (wie es bei den letzten beiden Prozeduren effektiv der Fall ist).

Aufgrund der Tensorproduktnatur der Hadamard-Transformation ist die Berechnung der Quanten-Hadamard-Transformation so einfach wie das Anwenden eines Hadamard-Gatters auf jedes Qubit separat. Nach dieser einfachen Schlussfolgerung benötigt die Quanten-Hadamard-Transformation im Gegensatz zu den n log n Operationen, die in der klassischen Situation benötigt werden, nur log n Operationen.

Die Hadamard-Transformation ist der Eckpfeiler vieler Quantenalgorithmen, da sie m Qubits, die mit initialisiert wurden |0\rangle , auf eine Überlagerung aller 2m orthogonalen Zustände in der |0\rangle ,|1\rangle Basis mit gleichem Gewicht abbildet.

Zum Beispiel stützt sich der Deutsch-Jozsa-Algorithmus auf diese Information, Simons Algorithmus, Algorithimum Bernstein-Vazirani, außerdem Grovers Algorithmus.

Zunächst einmal verwendet Shors Ansatz eine Hadamard-Transformation, ganz zu schweigen von QFT (Quanten-Fourier-Transformation), und es handelt sich jeweils um Fourier-Transformationen auf endlichen Gruppen und Fourier-Reihen; die erste auf {\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}} und die zweite auf {\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} } .

Phylogenetische Bäume können mit Hilfe der Hadamard-Transformation aus molekularen Daten abgeleitet werden.

Die Mechanik der phylogenetischen Hadamard-Transformation beinhaltet die Berechnung eines Vektors {\displaystyle \gamma (T)} , der Informationen über die Topologie und die Verzweigungslängen für den Baum T unter Verwendung des Ortsmustervektors oder der Matrix {\displaystyle s(T)} liefert.

{\displaystyle \gamma (T)=H^{-1}(\ln(Hs(T)))}

wobei H die Hadamard-Matrix die entsprechende Größe hat.

Die Komplexität dieses Problems kann reduziert werden, indem man es als eine Reihe von drei Gleichungen schreibt:

{\displaystyle {\begin{aligned}r&=Hs(T)\\\rho &=\ln r\\\gamma (T)&=H^{-1}\rho \end{aligned}}}

Da diese Gleichung invertierbar ist, können wir sie verwenden, um den Vektor oder die Matrix zu finden, die die typische Konfiguration eines bestimmten Standorts darstellt:

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

Indem wir die Nukleotide als binäre Zeichen speichern, können wir das Cavender-Farris-Neyman (CFN)