Transformada de Hadamard

A transformada de Hadamard (também conhecida como "transformada de Walsh-Hadamard") é um exemplo de uma classe generalizada de uma transformada de Fourier . Tem o nome do matemático francês Jacques Hadamard e realiza uma operação linear e involutiva com uma matriz ortogonal e simétrica em números reais de $2 m$ (ou complexos , embora as matrizes utilizadas tenham coeficientes reais). Essas matrizes são matrizes de Hadamard .

A transformada de Hadamard pode ser vista como derivada de uma transformada discreta de Fourier e na verdade é o equivalente a uma transformada discreta multidimensional de um tamanho de $2 \times 2 \times ... \times 2 \times 2$ . Ele decompõe um vetor de entrada arbitrário em uma superposição de funções Walsh .

Definição formal

A transformada de Hadamard $H m$ usa uma matriz de $2 m \times 2 m$ (uma matriz de Hadamard ) multiplicada por um fator de normalização e transforma 2 m de números reais $x n$ em 2 m de números reais $X k$ . A transformação pode ser definida de duas maneiras: recursivamente ou usando uma representação binária dos índices n e k .

Definição recursiva

Recursivamente, definimos uma primeira transformação $1 \times 1$ por meio de uma matriz $H 0$ que é a matriz identidade com apenas um elemento (1). Em seguida, definimos $H m$ para $m > 0$ graças à seguinte relação:

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

onde $1 / \sqrt 2$ é um fator de normalização que às vezes é omitido. Assim, com exceção da normalização, os coeficientes da matriz são iguais a 1 ou -1.

Definição direta

De forma equivalente, podemos definir o elemento $( k , n )$ de uma matriz de Hadamard graças a e , onde $k$ $j$ e $n$ $j$ são o bit $j$ (0 ou 1) de $k$ e $n,$ respectivamente . Neste caso, temos ${\ displaystyle k = k_ {m-1} 2 ^ {m-1} + k_ {m-2} 2 ^ {m-2} + \ cdots + k_ {1} 2 + k_ {0}}$ ${\ displaystyle n = n_ {m-1} 2 ^ {m-1} + n_ {m-2} 2 ^ {m-2} + \ cdots + n_ {1} 2 + n_ {0}}$

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

Interpretação

Esta é uma transformada de Fourier discreta $2 \times 2 \times ... \times 2 \times 2$ normalizada para ser unitária, considerando as entradas e saídas como matrizes multidimensionais indexadas por $n j$ e $k j$ .

Exemplos

As primeiras matrizes Hadamard são fornecidas por:

{\ displaystyle ~ H_ {0} = 1}

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

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

{\ displaystyle H_ {3} = {\ frac {1} {2 ^ {3/2}}} {\ begin {pmatrix} {\ 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 & - 1 \ end {array}} \ end {pmatrix}}}

As linhas de uma matriz de Hadamard formam funções de Walsh .

Formulários

No tratamento da computação quântica ,a transformação de Hadamard, mais frequentemente referida como o " portão de Hadamard " neste contexto, é uma rotação de um qubit . Permite transformar os estados e do qubit em dois estados sobrepostos com igual peso: e . Em geral, as fases são escolhidas de forma que: ${\ displaystyle | 0 \ rangle}$ ${\ displaystyle | 1 \ rangle}$ ${\ displaystyle | 0 \ rangle}$ ${\ displaystyle | 1 \ rangle}$

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

em notação de Dirac . Isso corresponde à matriz de transformação:

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

na base de , . ${\ displaystyle | 0 \ rangle}$ ${\ displaystyle | 1 \ rangle}$

Um grande número de algoritmos quânticos usa a transformada de Hadamard como uma primeira etapa, uma vez que ela transforma n qubits inicializados em uma superposição de todos os 2 n estados ortogonais expressos na base , com pesos iguais. ${\ displaystyle | 0 \ rangle}$ ${\ displaystyle | 0 \ rangle}$ ${\ displaystyle | 1 \ rangle}$

Por exemplo, o algoritmo de Shor usa essa transformação.

Outras aplicações

A transformação é usada em criptografia, então falamos de pseudo-transformação de Hadamard . Também é usado para gerar números aleatórios a partir de uma distribuição gaussiana. Ele também é usado na compressão de dados, como no algoritmo H.264 e para operações de processamento de sinal.

Notas e referências