Trasformata di Hadamard: Svelare il potere della trasformazione Hadamard nella visione artificiale

Di Fouad Sabry

Che cos'è la trasformata di Hadamard

La trasformata di Hadamard è un esempio di una classe generalizzata di trasformate di Fourier. Esegue un'operazione ortogonale, simmetrica, involutiva e lineare su 2 milioni di numeri reali.

Come trarrai vantaggio

(I) Approfondimenti e convalide sulla seguenti argomenti:

Capitolo 1: Trasformata di Hadamard

Capitolo 2: Trasformata discreta di Fourier

Capitolo 3: Trasformata veloce di Walsh?Hadamard

Capitolo 4: Trasformata quantistica di Fourier

Capitolo 5: Notazione Bra-ket

Capitolo 6: Matrici di Pauli

Capitolo 7: Porta logica quantistica

Capitolo 8: Porta NOT controllata

Capitolo 9: Generalizzazioni delle matrici di Pauli

Capitolo 10: Base sferica

(II) Rispondere alle principali domande del pubblico su trasformata di Hadamard.

(III) Esempi reali dell'utilizzo della trasformata di Hadamard in molti campi.

A chi è rivolto questo libro

Professionisti, studenti universitari e laureati, appassionati, hobbisti e coloro che desiderano andare oltre le conoscenze o le informazioni di base per qualsiasi tipo di Hadamard Transform.

 

 

• Lingua: Italiano
• Editore: Un Miliardo Di Ben Informato [Italian]
• Data di uscita: 28 apr 2024

Anteprima del libro

Capitolo 1: Trasformata di Hadamard

La trasformata di Hadamard (nota anche come trasformata di Walsh-Hadamard), trasformata di Hadamard, trasformata di Rademacher-Walsh e trasformata di Walsh, trasformata di Walsh o trasformata di Walsh-Fourier) è un tipo di trasformata di Fourier che appartiene a una categoria più ampia.

Risolve un'equazione ortogonale, simmetrica, involutiva, lineare su 2m numeri reali (o numeri complessi, , molto complicati, anche se le matrici di Hadamard sono interamente non immaginarie).

È possibile pensare alla trasformata di Hadamard come costruita da trasformate discrete di Fourier di dimensione 2. (DFT), ed è di fatto equivalente ad una DFT multidimensionale di dimensione 2 × 2 × ⋯ × 2 × 2.

Prende qualsiasi vettore di input e lo scompone in una sovrapposizione di funzioni di Walsh.

La trasformata prende il nome dal matematico francese Jacques Hadamard (francese: [adamaʁ]), dal matematico di origine tedesca e americana Hans Rademacher, Joseph L. Weisstein Jr. degli Stati Uniti.

Walsh.

La trasformata di Hadamard Hm è una matrice di 2m × 2m, la matrice di Hadamard (scalata da un fattore di normalizzazione), che trasforma 2m di numeri reali xn in 2m numeri reali Xk.

Esistono due diversi approcci per definire la trasformata di Hadamard, alternativamente, scrivendo n e k in forma binaria (base 2).

Ricorsivamente, definiamo la trasformata di Hadamard 1 × 1 H0 con l'identità H0 = 1, quindi definiamo Hm per m > 0 da:

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

dove 1/√2 è una normalizzazione che a volte viene omessa.

Per m > 1, possiamo anche definire Hm con:

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

dove \otimes rappresenta il prodotto Kronecker.

Quindi, oltre a questo parametro di standardizzazione, le matrici di Hadamard sono tutte uno e zero.

In alternativa, la matrice di Hadamard può essere definita dal suo (k, n)-esimo elemento, come mostrato di seguito

{\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}}}

dove kj e nj sono gli elementi di bit (0 o 1) di k e n, rispettivamente.

Attenzione, cioè per l'elemento in alto a sinistra, definiamo: k=n=0 .

Qui, però, abbiamo:

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

Questa è esattamente la DFT multidimensionale {\textstyle 2\times 2\times \cdots \times 2\times 2} , conforme ad un unico standard, se gli ingressi e le uscite sono considerati come array multidimensionali indicizzati rispettivamente da nj e kj.

Di seguito sono riportati alcuni esempi specifici di matrici di Hadamard.

{\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}}}

dove i\cdot j è il prodotto scalare bit per bit delle rappresentazioni binarie dei numeri i e j.

Ad esempio, se {\textstyle n\;\geq \;2} , allora

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

confermando il precedente (ignorando la costante complessiva).

Tenere presente che la prima riga, il primo elemento della colonna della matrice è indicato da {\textstyle (H_{n})_{0,0}} .

H1 è precisamente la dimensione 2 DFT.

Il gruppo additivo di due elementi, Z/, può essere pensato come soggetto a una trasformazione di Fourier (2).

Le matrici di Hadamard hanno funzioni di Walsh nelle loro righe.

Sia H = Hm,n] una matrice H che soddisfi la definizione precedente.

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

La trasformata di Walsh produce una matrice con solo le voci 1 e 1. A causa della natura di 1 e 1, nessuno dei quali è un numero complesso, non è necessario un calcolo del numero complesso.

La moltiplicazione irrazionale è necessaria per la DFT ma non per la trasformata di Hadamard. In effetti, i cambiamenti di segno sono sufficienti, quindi la moltiplicazione razionale non è necessaria.

Tutte le voci nella prima riga (e colonna) della matrice di trasformata di Walsh sono 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)}

Trasformata discreta di Fourier:

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

Quando m è uguale a zeri (la media della prima riga), anche la trasformata discreta di Fourier (DFT) produce 1. Nonostante le sue differenze rispetto alla prima riga, la seconda riga rivela un'importante caratteristica della matrice: il segnale nella matrice grezza iniziale è a bassa frequenza, ma questo cambia man mano che le righe avanzano.

Se usiamo il calcolo del passaggio per lo zero:

Prima riga = 0 passaggio per lo zero

Seconda fila = 1 passaggio per lo zero

Terza fila = 2 passaggi per lo zero

⋮

Otto righe = 7 passaggi per lo zero

La trasformata di Hadamard è infatti equivalente ad una DFT multidimensionale di dimensione 2 × 2 × ⋯ × 2 × 2.

Un altro approccio consiste nel considerare la trasformata di Hadamard come una trasformata di Fourier sul gruppo booleano {\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}} .

Applicando la trasformata di Fourier a gruppi finiti (abeliani), la trasformata di Fourier di una funzione {\displaystyle f\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} } è la funzione {\widehat {f}} definita da

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

dove \chi è un carattere di (\Z/2\Z)^n .

Ogni carattere ha la forma {\displaystyle \chi _{r}(a)=(-1)^{a\cdot r}} per alcuni {\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}} , dove una stringa di bit viene moltiplicata per se stessa usando il prodotto scalare booleano, in modo da poter identificare l'input di {\widehat {f}} con {\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}} (dualità di Pontryagin) e definire {\displaystyle {\widehat {f}}\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} } per

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

Questa è la trasformata di Hadamard di f , considerando l'input di f e {\widehat {f}} come stringhe booleane.

Nei termini della formulazione precedente in cui la trasformata di Hadamard moltiplica un vettore di 2^{n} numeri complessi v a sinistra per la matrice di Hadamard H_{n} , l'equivalenza è vista prendendo f in input la stringa di bit corrispondente all'indice di un elemento di v , e avendo f in output il corrispondente elemento di v .

Confrontate questo con la solita trasformata discreta di Fourier che, quando applicata a un vettore v di 2^{n} numeri complessi, utilizza invece i caratteri del gruppo ciclico {\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} } .

Mentre il campo classico, la trasformata di Hadamard può essere calcolata in n\log n operazioni ( n=2^{m} ), usando un metodo di trasformata di Hadamard veloce.

In meccanica quantistica, la trasformata di Hadamard può essere calcolata nel O(1) tempo, poiché è una porta logica quantistica parallelizzabile.

L'informatica quantistica si basa fortemente sulla trasformata di Hadamard.

Le trasformate di Hadamard 2 × 2 H_{1} sono la porta logica quantistica nota come porta di Hadamard e l'applicazione di una porta di Hadamard a ciascun qubit di un registro di n-qubit in parallelo è equivalente alla trasformata di Hadamard H_{n} .

Calcolando a livello quantistico, la porta di Hadamard esegue una rotazione di un singolo qubit, mappando gli stati di base del qubit |0\rangle e |1\rangle a due stati di sovrapposizione con uguale peso degli stati di base computazionali |0\rangle e |1\rangle .

Le fasi sono in genere selezionate per garantire

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

nella notazione di Dirac. Questa è la matrice che fa la trasformazione, tra l'altro.

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

nella |0\rangle ,|1\rangle base, equivalente alla base computazionale.

Gli stati {\textstyle {\frac {\left|0\right\rangle +\left|1\right\rangle }{\sqrt {2}}}} e {\textstyle {\frac {\left|0\right\rangle -\left|1\right\rangle }{\sqrt {2}}}} sono noti come {\displaystyle \left|{\boldsymbol {+}}\right\rangle } e {\displaystyle \left|{\boldsymbol {-}}\right\rangle } rispettivamente, Insieme, forniscono la base polare dell'informatica quantistica.

{\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}}}

Quando viene applicata a un qubit 0 o 1, la porta di Hadamard crea uno stato quantistico che ha la stessa probabilità di essere 0 o 1. (come si è visto nelle prime due operazioni). Nel paradigma probabilistico tradizionale della computazione, questo equivale a lanciare una moneta giusta. Lo stato finale è sempre lo stesso dello stato iniziale se la porta di Hadamard viene applicata due volte di seguito (come viene effettivamente fatto nelle ultime due procedure).

A causa della natura del prodotto tensoriale della trasformata di Hadamard, calcolare la trasformata di Hadamard quantistica è facile come applicare una porta di Hadamard a ciascun qubit separatamente. In base a questa semplice conclusione, a differenza delle n operazioni log n necessarie nella situazione classica, la trasformata di Hadamard quantistica richiede solo operazioni log n.

La trasformata di Hadamard è la pietra angolare di molti algoritmi quantistici, poiché mappa m qubit inizializzati con |0\rangle a una sovrapposizione di tutti gli stati ortogonali di 2m nella |0\rangle ,|1\rangle base con uguale peso.

Ad esempio, l'algoritmo di Deutsch-Jozsa si basa su queste informazioni, l'algoritmo di Simon, l'algoritmo di Bernstein-Vazirani, inoltre, l'algoritmo di Grover.

Per cominciare, l'approccio di Shor impiega una trasformata di Hadamard, per non parlare della QFT (trasformata quantistica di Fourier), e sono, rispettivamente, trasformazioni di Fourier su gruppi finiti e serie di Fourier; la prima su {\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}} e la seconda su {\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} } .

Gli alberi filogenetici possono essere dedotti dai dati molecolari utilizzando la trasformata di Hadamard.

La meccanica della trasformata filogenetica di Hadamard prevede il calcolo di un vettore {\displaystyle \gamma (T)} che fornisce informazioni sulla topologia e sulle lunghezze dei rami per l'albero T utilizzando il vettore o la matrice del modello del sito {\displaystyle s(T)} .

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

dove H è la matrice di Hadamard della dimensione appropriata.

La complessità di questo problema può essere ridotta scrivendolo come una serie di tre equazioni:

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

Poiché questa