Transformación de Hadamard: Revelando el poder de la transformación de Hadamard en visión por computadora

Por Fouad Sabry

Qué es la transformada de Hadamard

La transformada de Hadamard es un ejemplo de una clase generalizada de transformadas de Fourier. Realiza una operación ortogonal, simétrica, involutiva y lineal en 2 millones de números reales.

Cómo se beneficiará

(I) Información y validaciones sobre el siguientes temas:

Capítulo 1: Transformada de Hadamard

Capítulo 2: Transformada discreta de Fourier

Capítulo 3: Transformada rápida de Walsh?Hadamard

Capítulo 4: Transformada cuántica de Fourier

Capítulo 5: Notación Bra-ket

Capítulo 6: Matrices de Pauli

Capítulo 7: Puerta lógica cuántica

Capítulo 8: Puerta NOT controlada

Capítulo 9: Generalizaciones de matrices de Pauli

Capítulo 10: Base esférica

(II) Respondiendo las principales preguntas del público sobre transformada de hadamard.

(III) Ejemplos del mundo real para el uso de la transformada de hadamard en muchos campos.

Para quién es este libro

Profesionales, estudiantes de pregrado y posgrado, entusiastas, aficionados y aquellos que quieran ir más allá del conocimiento o la información básica para cualquier tipo de Transformada Hadamard.

 

 

• Idioma: Español
• Editorial: Mil Millones De Conocimientos [Spanish]
• Fecha de lanzamiento: 28 abr 2024

Vista previa del libro

Capítulo 1: Transformación de Hadamard

La transformada de Hadamard (también conocida como transformada de Walsh-Hadamard), transformada de Hadamard, transformada de Rademacher-Walsh y transformada de Walsh, transformada de Walsh o transformada de Walsh-Fourier) es un tipo de transformada de Fourier que pertenece a una categoría más amplia.

Resuelve una ecuación ortogonal, simétrica, involutiva, operación lineal sobre números reales de 2 m (o números complejos, muy complicados, aunque las matrices de Hadamard sean completamente no imaginarias).

Es posible pensar que la transformada de Hadamard está construida a partir de transformadas discretas de Fourier de tamaño 2. (DFT), y es de hecho equivalente a una DFT multidimensional de tamaño 2 × 2 × ⋯ × 2 × 2.

Toma cualquier vector de entrada y lo descompone en una superposición de funciones de Walsh.

La transformada lleva el nombre del matemático francés Jacques Hadamard (en francés: [adamaʁ]), el matemático de ascendencia alemana y estadounidense Hans Rademacher, Joseph L. Weisstein Jr. de los Estados Unidos.

Walsh.

La transformada de Hadamard Hm es una matriz de 2m × 2m, la matriz de Hadamard (escalada por un factor de normalización), que transforma 2m de números reales xn en 2m de números reales Xk.

Hay dos enfoques diferentes para definir la transformada de Hadamard, alternativamente, escribiendo n y k en forma binaria (base-2).

Recursivamente, definimos la transformada de Hadamard 1 × 1 H0 por la identidad H0 = 1, y luego definimos Hm para m > 0 por:

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

donde 1/√2 es una normalización que a veces se omite.

Para m > 1, también podemos definir Hm por:

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

donde \otimes representa el producto Kronecker.

Por lo tanto, además de este parámetro de estandarización, las matrices de Hadamard son todas unos y ceros.

Alternativamente, la matriz de Hadamard se puede definir por su (k, n)-ésimo elemento, como se muestra en la siguiente

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

donde kj y nj son los elementos bit (0 o 1) de k y n, respectivamente.

Tenga cuidado, eso es para el elemento en la parte superior izquierda, definimos: k=n=0 .

Aquí, sin embargo, tenemos:

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

Esta es exactamente la {\textstyle 2\times 2\times \cdots \times 2\times 2} DFT multidimensional, conformada a un único estándar, si las entradas y salidas se consideran como matrices multidimensionales indexadas por nj y kj, respectivamente.

A continuación, se muestran algunos ejemplos específicos de matrices de 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}}}

donde i\cdot j es el producto escalar bit a bit de las representaciones binarias de los números i y j.

Por ejemplo, si {\textstyle n\;\geq \;2} , entonces

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

confirmando lo anterior (ignorando la constante general).

Tenga en cuenta que el elemento de la primera fila y la primera columna de la matriz se denota con {\textstyle (H_{n})_{0,0}} .

H1 es precisamente el DFT de tamaño 2.

Se puede pensar que el grupo aditivo de dos elementos, Z/, está sometido a una transformación de Fourier (2).

Las matrices de Hadamard tienen funciones de Walsh en sus filas.

Sea H = Hm,n] una matriz H que satisfaga la definición anterior.

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

La transformada de Walsh produce una matriz con solo las entradas 1 y 1. Debido a la naturaleza de 1 y 1, ninguno de los cuales son números complejos, no es necesario un cálculo de números complejos.

La multiplicación irracional es necesaria para la DFT, pero no para la transformada de Hadamard. De hecho, los cambios de signo son suficientes, por lo que la multiplicación racional es innecesaria.

Todas las entradas de la primera fila (y columna) de la matriz de transformada de Walsh son 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)}

Transformada discreta de Fourier:

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

Cuando m es igual a ceros (el promedio de la primera fila), la transformada discreta de Fourier (DFT) también produce 1. A pesar de sus diferencias con la primera fila, la segunda fila revela una característica importante de la matriz: la señal en la matriz bruta inicial es de baja frecuencia, pero esto cambia a medida que avanzan las filas.

Si usamos el cálculo del cruce por cero:

Primera fila = 0 cruce por cero

Segunda fila = 1 paso por cero

Tercera fila = 2 cruces por cero

⋮

Ocho filas = 7 cruces por cero

La transformada de Hadamard es, de hecho, equivalente a una DFT multidimensional de tamaño 2 × 2 × ⋯ × 2 × 2.

Otro enfoque es ver la transformada de Hadamard como una transformada de Fourier en el grupo booleano {\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}} .

Aplicando la transformada de Fourier a grupos que son finitos (abelianos), la transformada de Fourier de una función {\displaystyle f\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} } es la función {\widehat {f}} definida por

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

donde \chi es un carácter de (\Z/2\Z)^n .

Cada carácter tiene la forma {\displaystyle \chi _{r}(a)=(-1)^{a\cdot r}} para algún {\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}} , donde una cadena de bits se multiplica por sí misma usando el producto de puntos booleanos, por lo que podemos identificar la entrada a {\widehat {f}} con {\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}} (dualidad de Pontryagin) y definir {\displaystyle {\widehat {f}}\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} } por

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

Esta es la transformada de Hadamard de f , considerando la entrada a f y {\widehat {f}} como cadenas booleanas.

En términos de la formulación anterior, donde la transformada de Hadamard multiplica un vector de 2^{n} números complejos v a la izquierda por la matriz de Hadamard H_{n} , la equivalencia se ve tomando f como entrada la cadena de bits correspondiente al índice de un elemento de v , y teniendo f como resultado el elemento correspondiente de v .

Compare esto con la transformada discreta de Fourier habitual, que cuando se aplica a un vector v de 2^{n} números complejos utiliza caracteres del grupo cíclico {\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} } .

Mientras que el campo clásico, la transformada de Hadamard se puede calcular en n\log n operaciones ( n=2^{m} ), mediante el uso de un método de transformada de Hadamard rápido.

Mecánica cuántica, la transformada de Hadamard se puede calcular en el O(1) tiempo, ya que es una puerta lógica cuántica paralelizable.

La computación cuántica depende en gran medida de la transformada de Hadamard.

Las transformadas de Hadamard 2 × 2 H_{1} son la puerta lógica cuántica conocida como puerta de Hadamard, y la aplicación de una puerta de Hadamard a cada qubit de un registro de n-qubit en paralelo es equivalente a la transformada de Hadamard H_{n} .

Computación a nivel cuántico, la puerta de Hadamard realiza una rotación de un solo qubit, mapeando los estados de base de qubit |0\rangle y |1\rangle a dos estados de superposición con igual peso de los estados de base computacional |0\rangle y |1\rangle .

Por lo general, las fases se seleccionan para garantizar

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

en la notación de Dirac. Esa es la matriz que hace la transformación, por cierto.

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

en la |0\rangle ,|1\rangle base, equivalente a la base computacional.

Los estados {\textstyle {\frac {\left|0\right\rangle +\left|1\right\rangle }{\sqrt {2}}}} y {\textstyle {\frac {\left|0\right\rangle -\left|1\right\rangle }{\sqrt {2}}}} se conocen como {\displaystyle \left|{\boldsymbol {+}}\right\rangle } y {\displaystyle \left|{\boldsymbol {-}}\right\rangle } respectivamente, Juntos, proporcionan la base polar de la computación cuántica.

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

Cuando se aplica a un cúbit 0 o 1, la puerta de Hadamard crea un estado cuántico que tiene la misma probabilidad de ser 0 o 1. (como se ve en las dos primeras operaciones). En el paradigma probabilístico tradicional de la computación, esto equivale a lanzar una moneda justa. El estado final es siempre el mismo que el estado inicial si la puerta de Hadamard se aplica dos veces seguidas (como se hace efectivamente en los dos últimos procedimientos).

Debido a la naturaleza del producto tensorial de la transformada de Hadamard, calcular la transformada cuántica de Hadamard es tan fácil como aplicar una puerta de Hadamard a cada qubit por separado. De acuerdo con esta sencilla conclusión, a diferencia de las n log n operaciones necesarias en la situación clásica, la transformada cuántica de Hadamard solo necesita log n operaciones.

La transformada de Hadamard es la piedra angular de muchos algoritmos cuánticos, ya que mapea m qubits inicializados con |0\rangle una superposición de todos los estados ortogonales de 2 m en la |0\rangle ,|1\rangle base con igual peso.

Por ejemplo, el algoritmo de Deutsch-Jozsa se basa en esta información, el algoritmo de Simon, el algoritmo de Bernstein-Vazirani, y el algoritmo de Grover.

Para empezar, el enfoque de Shor emplea una transformada de Hadamard, por no hablar de QFT (transformada cuántica de Fourier), y son, respectivamente, transformaciones de Fourier en grupos finitos y series de Fourier; la primera en {\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}} y la segunda en {\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} } .

Los árboles filogenéticos se pueden inferir a partir de datos moleculares utilizando la transformada de Hadamard.

La mecánica de la transformada filogenética de Hadamard implica el cálculo de un vector {\displaystyle \gamma (T)} que proporciona información sobre la topología y las longitudes de las ramas del árbol T utilizando el vector o matriz de patrón de sitio {\displaystyle s(T)} .

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

donde H es la matriz de Hadamard del tamaño adecuado.

La complejidad de este problema se puede reducir escribiéndolo como una serie de tres ecuaciones:

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

Debido a que esta ecuación es invertible, podemos usarla para encontrar el vector o matriz que representa la configuración típica de un