Trasformata di Hadamard

Il prodotto di una funzione booleana e di una matrice di Walsh è il suo spettro di Walsh:[1]

(1, 0, 1, 0, 0, 1, 1, 0) × H(8) = (4, 2, 0, −2, 0, 2, 0, 2)
La trasformata di Walsh–Hadamard veloce, un modo più rapido di calcolare lo spettro di Walsh di (1, 0, 1, 0, 0, 1, 1, 0).
La funzione originale può essere espressa per mezzo del suo spettro di Walsh come un polinomio aritmetico.

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

La trasformata di Hadamard Hm è una matrice 2m × 2m, la matrice di Hadamard (riscalata con un fattore di normalizzazione), che trasforma 2m numeri reali xn in 2m numeri reali Xk. 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à: H0 = 1, e poi definire Hm per m > 0 come:

H m = 1 2 ( H m − 1 H m − 1 H m − 1 − H m − 1 ) {\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 è un fattore di normalizzazione a volte omesso.

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

H m = H 1 ⊗ H m − 1 {\displaystyle H_{m}=H_{1}\otimes H_{m-1}}

dove ⊗ {\displaystyle \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

k = ∑ i = 0 m − 1 k i 2 i = k m − 1 2 m − 1 + k m − 2 2 m − 2 + ⋯ + k 1 2 + k 0 n = ∑ i = 0 m − 1 n i 2 i = n m − 1 2 m − 1 + n m − 2 2 m − 2 + ⋯ + n 1 2 + n 0 {\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}+\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

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 ⟩ {\displaystyle |0\rangle } e | 1 ⟩ {\displaystyle |1\rangle } a una sovrapposizione dei due stati con peso uguale. Solitamente le fasi sono scelte in modo tale che

H = | 0 ⟩ + | 1 ⟩ 2 ⟨ 0 | + | 0 ⟩ − | 1 ⟩ 2 ⟨ 1 | {\displaystyle 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 = 1 2 ( 1 1 1 − 1 ) {\displaystyle H_{1}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}

nella base | 0 ⟩ , | 1 ⟩ {\displaystyle |0\rangle ,|1\rangle } , detta anche base computazionale. Gli stati | 0 ⟩ + | 1 ⟩ 2 {\textstyle {\frac {\left|0\right\rangle +\left|1\right\rangle }{\sqrt {2}}}} e | 0 ⟩ − | 1 ⟩ 2 {\textstyle {\frac {\left|0\right\rangle -\left|1\right\rangle }{\sqrt {2}}}} sono conosciuti anche rispettivamente come | + ⟩ {\displaystyle \left|{\boldsymbol {+}}\right\rangle } e | − ⟩ {\displaystyle \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 ⟩ {\displaystyle |0\rangle } a una sovrapposizione di tutti i 2m stati ortogonali nella base | 0 ⟩ , | 1 ⟩ {\displaystyle |0\rangle ,|1\rangle } con peso uguale.

Operazioni della porta di Hadamard

H ( | 0 ⟩ ) = 1 2 | 0 ⟩ + 1 2 | 1 ⟩ =: | + ⟩ H ( | 1 ⟩ ) = 1 2 | 0 ⟩ − 1 2 | 1 ⟩ =: | − ⟩ H ( 1 2 | 0 ⟩ + 1 2 | 1 ⟩ ) = 1 2 ( | 0 ⟩ + | 1 ⟩ ) + 1 2 ( | 0 ⟩ − | 1 ⟩ ) = | 0 ⟩ H ( 1 2 | 0 ⟩ − 1 2 | 1 ⟩ ) = 1 2 ( | 0 ⟩ + | 1 ⟩ ) − 1 2 ( | 0 ⟩ − | 1 ⟩ ) = | 1 ⟩ {\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\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.

Note

  1. ^ Compare Figure 1 in W. J. Townsend e M. A. Thornton, Walsh Spectrum Computations Using Cayley Graphs.
  2. ^ H.O. Kunz, On the Equivalence Between One-Dimensional Discrete Walsh-Hadamard and Multidimensional Discrete Fourier Transforms, in IEEE Transactions on Computers, vol. 28, n. 3, 1979, pp. 267–8, DOI:10.1109/TC.1979.1675334.

Voci correlate

Collegamenti esterni

  • (EN) Eric W. Weisstein, Trasformata di Hadamard, su MathWorld, Wolfram Research. Modifica su Wikidata
  • Walsh-Hadamard Transforms: A Literature Survey, su ciphersbyritter.com.
  • A.N. Akansu e R. Poluri, Walsh-Like Nonlinear Phase Orthogonal Codes for Direct Sequence CDMA Communications (PDF), in IEEE Transactions on Signal Processing, vol. 55, n. 7, luglio 2007, pp. 3800–6, DOI:10.1109/TSP.2007.894229.
  • Jeng-shyang Pan, Data Encryption Method Using Discrete Fractional Hadamard Transformation, su freepatentsonline.com, 28 maggio 2009.
  • Dr. Pawel Lachowicz, Walsh–Hadamard Transform and Tests for Randomness of Financial Return-Series, su quantatrisk.com, 7 aprile 2015.
  • Pump-probe Spectroscopy using Hadamard Transforms (PDF), su www1.chem.leeds.ac.uk. URL consultato il 16 febbraio 2021 (archiviato dall'url originale il 18 ottobre 2014).
  • Briony A. Yorke, Godfrey Beddard e Robin L. Owen, Time-resolved crystallography using the Hadamard transform, in Nature Methods, vol. 11, n. 11, settembre 2014, pp. 1131–1134, DOI:10.1038/nmeth.3139, PMID 25282611.
  Portale Informatica
  Portale Matematica
  Portale Quantistica