Trasformata di Hadamard

La trasformata di Hadamard (anche conosciuta come la trasformata di Walsh–Hadamard, trasformata di Hadamard–Rademacher–Walsh, trasformata di Walsh, o trasformata di Walsh–Fourier) è un esempio di classe generalizzata di trasformate di Fourier. Effettua una trasformazione lineare ortogonale, simmetrica, involutiva su 2m numeri reali (o complessi, o ipercomplessi, anche le matrici di Hadamard di per sé sono reali).

Si può considerare la trasformata di Hadamard come costruita da trasformate discrete di Fourier (DFT) di dimensione 2, ed è di fatto equivalente a una DFT multidimensionale di dimensione 2 × 2 × ⋯ × 2 × 2.^[2] Scompone un vettore di input arbitrario in una sovrapposizione di funzioni di Walsh.

La trasformata prende il nome dal matematico francese Jacques Hadamard, il matematico tedesco-americano Hans Rademacher, e il matematico statunitense Joseph L. Walsh.

Definizione modifica

La trasformata di Hadamard H_m è una matrice 2^m × 2^m, la matrice di Hadamard (riscalata con un fattore di normalizzazione), che trasforma 2^m numeri reali x_n in 2^m numeri reali X_k. La trasformata di Hadamard può essere definita in due modi: ricorsivamente, o usando la rappresentazione binaria (base 2) degli indici n e k.

Ricorsivamente, si può definire la trasformata di Hadamard 1 × 1 l'identità: H₀ = 1, e poi definire H_m per m > 0 come:

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 è un fattore di normalizzazione a volte omesso.

Per m > 1, si può definire H_m come:

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

dove $\otimes$ rappresenta il prodotto di Kronecker. Pertanto, a parte il fattore di normalizzazione, le matrici di Hadamard sono fatte interamente di 1 e −1.

Equivalentemente, è possibile definire la matrice di Hadamard con l'entrata (k, n)-esima scrivendo

{\begin{aligned}k&=\sum _{i=0}^{m-1}{k_{i}2^{i}}=k_{m-1}2^{m-1}+k_{m-2}2^{m-2}+\cdots +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}+\cdots +n_{1}2+n_{0}\end{aligned}}

Applicazioni in computazione quantistica modifica

In informatica quantistica la trasformazione di Hadamard, spesso chiamata porta di Hadamard in questo contesto (cfr. porta quantistica), è una rotazione di un qubit, che mappa gli stati di base $|0\rangle$ e $|1\rangle$ a una sovrapposizione dei due stati con peso uguale. Solitamente le fasi sono scelte in modo tale che

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

nella notazione bra-ket. Questo corrisponde alla matrice di trasformazione

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

nella base $|0\rangle ,|1\rangle$ , detta anche 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 conosciuti anche rispettivamente come $\left|{\boldsymbol {+}}\right\rangle$ e $\left|{\boldsymbol {-}}\right\rangle$ , e insieme costituiscono la base polare.

Molti algoritmi quantistici usano la trasformata di Hadamard come passo iniziale, siccome mappa m qubit inizializzati con $|0\rangle$ a una sovrapposizione di tutti i 2^m stati ortogonali nella base $|0\rangle ,|1\rangle$ con peso uguale.

Operazioni della porta di Hadamard modifica

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

Un'applicazione della porta di Hadamard a un qubit 0 o 1 qubit produrrà uno stato quantistico che, se osservato, sarà 0 o 1 con uguale probabilità. Questo è esattamente come tirare una moneta equa nel modello standard probabilistico della computazione. Tuttavia, se la porta di Hadamard viene applicata due volte in sequenza (come nelle ultime due operazioni sopra), allora lo stato finale sarà sempre lo stato di partenza.