Transformada de Hadamard

A transformada de Hadamard (também conhecida como transformada de Walsh–Hadamard, transformada de Hadamard–Rademacher–Walsh, transformada de Walsh, ou transformada de Walsh–Fourier) é um exemplo de uma classe generalizada de transformadas de Fourier. Ela realiza uma operação linear simétrica, involutiva, linear sobre $2 m$ números reais (ou complexos, ou hipercomplexos, embora as próprias matrizes de Hadamard sejam puramente reais).

A transformada de Hadamard pode ser considerada como sendo construída a partir de transformadas discretas de Fourier (DFT) de tamanho 2, e é de fato equivalente a uma DFT multidimensional de tamanho $2 \times 2 \times \dots \times 2 \times 2$ . Ela decompõe um vetor de entrada arbitrário em uma superposição de funções de Walsh.

A transformada recebe o nome do matemático francês Jacques Hadamard (fr), do matemático teuto-americano Hans Rademacher e do matemático americano Joseph L. Walsh.

Definição

A transformada de Hadamard H_m é uma matriz 2^m × 2^m, a matriz de Hadamard (escalonada por um fator de normalização), que transforma 2^m números reais x_n em 2^m números reais X_k. A transformada de Hadamard pode ser definida de duas maneiras: recursivamente, ou usando a representação binária (base-2) dos índices n e k.

Recursivamente, definimos a transformada de Hadamard 1 × 1 H₀ pela identidade H₀ = 1, e então definimos H_m para m > 0 por: $H_{m} = \frac{1}{2^{m / 2}} (\begin{matrix} H_{m - 1} & H_{m - 1} \\ H_{m - 1} & - H_{m - 1} \end{matrix})$ onde a divisão por 2^m/2 é uma normalização que às vezes é omitida.

Para m > 1, também podemos definir H_m por: $H_{m} = H_{1} \otimes H_{m - 1}$ onde $\otimes$ representa o produto de Kronecker. Assim, exceto por este fator de normalização, as matrizes de Hadamard são compostas inteiramente por 1 e −1.

Equivalentemente, podemos definir a matriz de Hadamard por sua entrada (k, n) escrevendo $\begin{matrix} 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{matrix}$

onde os k_j e n_j são os elementos de bit (0 ou 1) de k e n, respectivamente. Note que para o elemento no canto superior esquerdo, definimos: $k = n = 0$ . Neste caso, temos: $(H_{m})_{k, n} = \frac{1}{2^{m / 2}} (- 1)^{\sum_{j} k_{j} n_{j}}$

Esta é exatamente a DFT multidimensional $2 \times 2 \times \dots \times 2 \times 2$ , normalizada para ser unitária, se as entradas e saídas são consideradas como matrizes multidimensionais indexadas pelos n_j e k_j, respectivamente.

Alguns exemplos das matrizes de Hadamard seguem. $\begin{matrix} H_{0} & = + (\begin{matrix} 1 \end{matrix}) \\ H_{1} & = \frac{1}{\sqrt{2}} (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}) \\ H_{2} & = \frac{1}{2} (\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & - 1 & 1 & - 1 \\ 1 & 1 & - 1 & - 1 \\ 1 & - 1 & - 1 & 1 \end{matrix}) \\ H_{3} & = \frac{1}{2^{3 / 2}} (\begin{matrix} 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{matrix}) \\ (H_{n})_{i, j} & = \frac{1}{2^{n / 2}} (- 1)^{i \cdot j} \end{matrix}$ onde $i \cdot j$ é o produto escalar bit a bit das representações binárias dos números i e j. Por exemplo, se $n \geq 2$ , então $(H_{n})_{3, 2} = (- 1)^{3 \cdot 2} = (- 1)^{(1, 1) \cdot (1, 0)} = (- 1)^{1 + 0} = (- 1)^{1} = - 1$ , concordando com o acima (ignorando a constante global). Note que o elemento da primeira linha, primeira coluna da matriz é denotado por $(H_{n})_{0, 0}$ .

H₁ é precisamente a DFT de tamanho 2. Também pode ser considerada como a transformada de Fourier no grupo aditivo de dois elementos de Z/(2).

As linhas das matrizes de Hadamard são as funções de Walsh.

Vantagens da transformada de Walsh–Hadamard

Real

De acordo com a definição acima da matriz H, aqui deixamos H = H[m,n] $H [m, n] = (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix})$

Na transformada de Walsh, apenas 1 e −1 aparecerão na matriz. Os números 1 e −1 são números reais, portanto não há necessidade de realizar um cálculo com números complexos.

Nenhuma multiplicação é necessária

A DFT precisa de multiplicação irracional, enquanto a transformada de Hadamard não. Nem mesmo multiplicação racional é necessária, pois apenas inversões de sinal são necessárias.

Algumas propriedades são semelhantes às da DFT

Na matriz da transformada de Walsh, cada linha e cada coluna é uma função de Walsh, na qual o número de mudanças de sinal aumenta consecutivamente. Isto é, na primeira linha e primeira coluna, há zero mudanças de sinal (todas as entradas são iguais a 1). Na segunda, há uma mudança de sinal; na terceira, duas mudanças de sinal; e assim por diante. $H [m, n] = (\begin{matrix} 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{matrix})$ Compare isso com uma transformada discreta de Fourier $e^{- j 2 π m n / N}$ , na qual cada linha $i$ contém $i - 1$ cruzamentos por zero.

Em uma transformada discreta de Fourier, quando $m$ é igual a zero (correspondendo à primeira linha), o resultado também é 1. Para linhas subsequentes, podemos observar uma característica da matriz de que a frequência do sinal começa baixa na primeira matriz linha e aumenta nas linhas seguintes, até a última linha.

Relação com a transformada de Fourier

A transformada de Hadamard é de fato equivalente a uma DFT multidimensional de tamanho $2 \times 2 \times \dots \times 2 \times 2$ .

Outra abordagem é ver a transformada de Hadamard como uma transformada de Fourier no grupo booleano $(ℤ / 2 ℤ)^{n}$ . Usando a transformada de Fourier em grupos (abelianos) finitos, a transformada de Fourier de uma função $f : (ℤ / 2 ℤ)^{n} \to ℂ$ é a função $\hat{f}$ definida por $\hat{f} (χ) = \sum_{a \in (ℤ / 2 ℤ)^{n}} f (a) \bar{χ} (a)$ onde $χ$ é um caráter de $(ℤ / 2 ℤ)^{n}$ . Cada caráter tem a forma $χ_{r} (a) = (- 1)^{a \cdot r}$ para algum $r \in (ℤ / 2 ℤ)^{n}$ , onde a multiplicação é o produto escalar booleano em strings de bits, então podemos identificar a entrada de $\hat{f}$ com $r \in (ℤ / 2 ℤ)^{n}$ (dualidade de Pontryagin) e definir $\hat{f} : (ℤ / 2 ℤ)^{n} \to ℂ$ por $\hat{f} (r) = \sum_{a \in (ℤ / 2 ℤ)^{n}} f (a) (- 1)^{r \cdot a}$

Esta é a transformada de Hadamard de $f$ , considerando a entrada de $f$ e $\hat{f}$ como strings booleanas.

Em termos da formulação acima, onde a transformada de Hadamard multiplica um vetor de $2^{n}$ números complexos $v$ à esquerda pela matriz de Hadamard $H_{n}$ , a equivalência é vista tomando $f$ para receber como entrada a string de bits correspondente ao índice de um elemento de $v$ , e tendo $f$ como saída o elemento correspondente de $v$ .

Compare isso com a transformada discreta de Fourier usual que, quando aplicada a um vetor $v$ de $2^{n}$ números complexos, usa em vez disso caracteres do grupo cíclico $ℤ / 2^{n} ℤ$ .

Complexidade computacional

No domínio clássico, a transformada de Hadamard pode ser computada em $n \log n$ operações ( $n = 2^{m}$ ), usando o algoritmo da transformada rápida de Hadamard.

No domínio quântico, a transformada de Hadamard pode ser computada em tempo $O (1)$ , pois é uma porta lógica quântica que pode ser paralelizada.

Aplicações em computação quântica

A transformada de Hadamard é extensivamente usada em computação quântica. A transformada de Hadamard 2 × 2 $H_{1}$ é a porta lógica quântica conhecida como porta de Hadamard, e a aplicação de uma porta de Hadamard a cada qubit de um registrador de $n$ qubits em paralelo é equivalente à transformada de Hadamard $H_{n}$ .

Porta de Hadamard

Em computação quântica, a porta de Hadamard é uma rotação de um qubit, mapeando os estados da base de qubits $| 0 ⟩$ e $| 1 ⟩$ para dois estados de superposição com peso igual dos estados da base computacional $| 0 ⟩$ e $| 1 ⟩$ . Normalmente as fases são escolhidas de modo que $H = \frac{| 0 ⟩ + | 1 ⟩}{\sqrt{2}} ⟨ 0 | + \frac{| 0 ⟩ - | 1 ⟩}{\sqrt{2}} ⟨ 1 |$

em notação de Dirac. Isso corresponde à matriz de transformação $H_{1} = \frac{1}{\sqrt{2}} (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix})$ na base $| 0 ⟩, | 1 ⟩$ , também conhecida como base computacional. Os estados $\frac{| 0 ⟩ + | 1 ⟩}{\sqrt{2}}$ e $\frac{| 0 ⟩ - | 1 ⟩}{\sqrt{2}}$ são conhecidos como $| + ⟩$ e $| - ⟩$ respectivamente, e juntos constituem a base polar em computação quântica.

Operações da porta de Hadamard

$\begin{matrix} H (| 0 ⟩) & = \frac{1}{\sqrt{2}} | 0 ⟩ + \frac{1}{\sqrt{2}} | 1 ⟩ = : | + ⟩ \\ H (| 1 ⟩) & = \frac{1}{\sqrt{2}} | 0 ⟩ - \frac{1}{\sqrt{2}} | 1 ⟩ = : | - ⟩ \\ H (| + ⟩) & = H (\frac{1}{\sqrt{2}} | 0 ⟩ + \frac{1}{\sqrt{2}} | 1 ⟩) = \frac{1}{2} (| 0 ⟩ + | 1 ⟩) + \frac{1}{2} (| 0 ⟩ - | 1 ⟩) = | 0 ⟩ \\ H (| - ⟩) & = H (\frac{1}{\sqrt{2}} | 0 ⟩ - \frac{1}{\sqrt{2}} | 1 ⟩) = \frac{1}{2} (| 0 ⟩ + | 1 ⟩) - \frac{1}{2} (| 0 ⟩ - | 1 ⟩) = | 1 ⟩ \end{matrix}$

Uma aplicação da porta de Hadamard em um qubit 0 ou 1 produzirá um estado quântico que, se observado, será 0 ou 1 com igual probabilidade (como visto nas duas primeiras operações). Isso é exatamente como jogar uma moeda justa no modelo probabilístico padrão de computação. No entanto, se a porta de Hadamard for aplicada duas vezes em sucessão (como é efetivamente feito nas duas últimas operações), então o estado final é sempre o mesmo que o estado inicial.

Transformada de Hadamard em algoritmos quânticos

Calcular a transformada de Hadamard quântica é simplesmente a aplicação de uma porta de Hadamard a cada qubit individualmente devido à estrutura de produto tensorial da transformada de Hadamard. Este resultado simples significa que a transformada de Hadamard quântica requer $\log_{2} N$ operações, comparado ao caso clássico de $N \log_{2} N$ operações.

Para um sistema de $n$ qubits, portas de Hadamard agindo em cada um dos $n$ qubits (cada um inicializado para $| 0 ⟩$ ) pode ser usado para preparar estados de superposição quântica uniforme quando $N$ é da forma $N = 2^{n}$ . Neste caso com $n$ qubits, a porta de Hadamard combinada $H_{n}$ é expressa como o produto tensorial de $n$ portas de Hadamard: $H_{n} = \underset{n vezes}{\underset{⏟}{H \otimes H \otimes \dots \otimes H}}$

O estado de superposição quântica uniforme resultante é então: $H_{n} | 0 ⟩^{\otimes n} = \frac{1}{\sqrt{2^{n}}} \sum_{j = 0}^{2^{n} - 1} | j ⟩$ Isso generaliza a preparação de estados quânticos uniformes usando portas de Hadamard para qualquer $N = 2^{n}$ .

A medição deste estado quântico uniforme resulta em um estado aleatório entre $| 0 ⟩$ e $| N - 1 ⟩$ .

Muitos algoritmos quânticos usam a transformada de Hadamard como um passo inicial, pois como explicado anteriormente, ela mapeia n qubits inicializados com $| 0 ⟩$ para uma superposição de todos os 2ⁿ estados ortogonais na base $| 0 ⟩, | 1 ⟩$ com peso igual. Por exemplo, isso é usado no algoritmo de Deutsch–Jozsa, no algoritmo de Simon, no algoritmo de Bernstein–Vazirani e no algoritmo de Grover. Note que o algoritmo de Shor usa tanto uma transformada de Hadamard inicial quanto a transformada quântica de Fourier, que são ambos tipos de transformadas de Fourier em grupos finitos; a primeira em $(ℤ / 2 ℤ)^{n}$ e a segunda em $ℤ / 2^{n} ℤ$ .

A preparação de estados de superposição quântica uniforme no caso geral, quando $N$ ≠ $2^{n}$ é não trivial e requer mais trabalho. Uma abordagem eficiente e determinística para preparar o estado de superposição $| Ψ ⟩ = \frac{1}{\sqrt{N}} \sum_{j = 0}^{N - 1} | j ⟩$ com uma complexidade de portas e profundidade de circuito de apenas $O (\log_{2} N)$ para todos $N$ foi recentemente apresentada. Esta abordagem requer apenas $n = ⌈ \log_{2} N ⌉$ qubits. Importantly, nem qubits ancilla nem quaisquer portas quânticas com múltiplos controles são necessários nesta abordagem para criar o estado de superposição uniforme $| Ψ ⟩$ .

Aprendizado de máquina quântico

A transformada de Hadamard encontrou aplicações em aprendizado de máquina quântico, particularmente em redes neurais híbridas quântico-clássicas. Pesquisadores da Universidade de Illinois Chicago demonstraram uma abordagem inovadora que implementa operações de rede neural convolucional no domínio da frequência usando hardware quântico.

Convolução quântico-clássica híbrida

A abordagem é baseada no teorema da convolução da transformada de Hadamard, que afirma que a convolução diádica entre dois vetores é equivalente à multiplicação elemento a elemento de suas representações da transformada de Hadamard. Esta propriedade permite o cálculo eficiente de camadas convolucionais em computadores quânticos, uma vez que calcular a transformada de Hadamard requer apenas a aplicação de uma porta de Hadamard a cada qubit individualmente.

Em uma arquitetura de rede neural convolucional híbrida quântico-clássica, os cálculos da transformada de Hadamard podem ser descarregados para hardware quântico enquanto mantém o processamento clássico para outras operações. Esta abordagem, apresentada na Conferência Internacional sobre Aprendizado de Máquina (ICML) 2023, demonstrou melhorias na eficiência computacional: no conjunto de dados MNIST, a rede baseada na transformada de Hadamard alcançou 99,31% de precisão de teste com 57,1% menos operações de multiplicação-acumulação (MACs) em comparação com CNNs convencionais, enquanto no ImageNet-1K, uma ResNet-50 baseada na transformada de Hadamard excedeu a precisão da linha de base em 0,59% usando 11,5% menos parâmetros e 12,6% menos MACs.

Vantagem computacional

A vantagem quântica decorre da paralelizabilidade das portas de Hadamard. Enquanto o cálculo clássico da transformada de Hadamard requer O(n log n) operações usando o algoritmo da transformada rápida de Hadamard, a implementação quântica pode calcular a transformada em tempo O(1) aplicando portas de Hadamard a todos os qubits simultaneamente. Esta aceleração exponencial na etapa da transformada torna a convolução no domínio da frequência particularmente atraente para aplicações de aprendizado de máquina quântico.

Aplicações em filogenética molecular (biologia evolutiva)

A transformada de Hadamard pode ser usada para estimar árvores filogenéticas a partir de dados moleculares. A Filogenética é o subcampo da biologia evolutiva focado em entender as relações entre os organismos. Uma transformada de Hadamard aplicada a um vetor (ou matriz) de frequências de padrões de sítio obtidas a partir de um alinhamento de sequências múltiplas de DNA pode ser usada para gerar outro vetor que carrega informações sobre a topologia da árvore. A natureza invertível da transformada filogenética de Hadamard também permite o cálculo de verossimilhanças de sítio a partir de um vetor de topologia de árvore, permitindo usar a transformada de Hadamard para estimativa de máxima verossimilhança de árvores filogenéticas. No entanto, esta última aplicação é menos útil do que a transformação do vetor de padrões de sítio para o vetor de árvore porque existem outras maneiras de calcular verossimilhanças de sítio que são muito mais eficientes. No entanto, a natureza invertível da transformada filogenética de Hadamard fornece uma ferramenta elegante para a filogenética matemática.

A mecânica da transformada filogenética de Hadamard envolve o cálculo de um vetor $γ (T)$ que fornece informações sobre a topologia e comprimentos de ramo para a árvore $T$ usando o vetor ou matriz de padrão de sítio $s (T)$ .

$γ (T) = H^{- 1} (\ln (H s (T)))$ onde $H$ é a matriz de Hadamard do tamanho apropriado. Esta equação pode ser reescrita como uma série de três equações para simplificar sua interpretação:

$\begin{matrix} r & = H s (T) \\ ρ & = \ln r \\ γ (T) & = H^{- 1} ρ \end{matrix}$

A natureza invertível desta equação permite calcular um vetor (ou matriz) de padrão de sítio esperado da seguinte forma:

$s (T) = H^{- 1} (\exp (H γ (T)))$

Podemos usar o modelo de substituição de dois estados de Cavender–Farris–Neyman (CFN) para DNA codificando os nucleotídeos como caracteres binários (as purinas A e G são codificadas como R e as pirimidinas C e T são codificadas como Y). Isso torna possível codificar o alinhamento de sequências múltiplas como o vetor de padrão de sítio $s (T)$ que pode ser convertido em um vetor de árvore $γ (T)$ , como mostrado no seguinte exemplo:

Exemplo mostrando a transformada de Hadamard para uma árvore específica (valores para o exemplo trabalhado adaptados de Waddell et al. 1997)
Índice	Padrão binário	Padrões de alinhamento	$γ (T)$	$ρ = H^{- 1} γ (T)$	$r = \exp (ρ)$	$s (T) = H^{- 1} ρ$
0	0000	RRRR e YYYY	−0.475	0	1	0.6479
1	0001	RRRY e YYYR	0.2	−0.5	0.6065	0.1283
2	0010	RRYR e YYRY	0.025	−0.15	0.8607	0.02
3*	0011	RRYY e YYRR	0.025	−0.45	0.6376	0.0226
4	0100	RYRR e YRYY	0.2	−0.45	0.6376	0.1283
5*	0101	RYRY e YRYR	0	−0.85	0.4274	0.0258
6*	0110	RYYR e YRRY	0	−0.5	0.6065	0.0070
7	0111	RYYY e YRRR	0.025	−0.9	0.4066	0.02

O exemplo mostrado nesta tabela usa o esquema simplificado de três equações e é para uma árvore de quatro táxons que pode ser escrita como ((A,B),(C,D)); no formato newick. Os padrões de sítio são escritos na ordem ABCD. Esta árvore particular tem dois ramos terminais longos (0.2 substituições de transversão por sítio), dois ramos terminais curtos (0.025 substituições de transversão por sítio) e um ramo interno curto (0.025 substituições de transversão por sítio); assim, seria escrita como ((A:0.025,B:0.2):0.025,(C:0.025,D:0.2)); no formato newick. Esta árvore exibirá atração de ramo longo se os dados forem analisados usando o critério de máxima parársimonia (assumindo que a sequência analisada é longa o suficiente para que as frequências de padrões de sítio observadas estejam próximas das frequências esperadas mostradas na coluna $s (T) = H^{- 1} ρ$ ). A atração de ramo longo reflete o fato de que o número esperado de padrões de sítio com índice 6 — que suportam a árvore ((A,C),(B,D)); — excede o número esperado de padrões de sítio que suportam a árvore verdadeira (índice 4). Obviamente, a natureza invertível da transformada filogenética de Hadamard significa que o vetor de árvore $γ (T)$ corresponde à árvore correta. A análise de parcimônia após a transformação é, portanto, estatisticamente consistente, assim como seria uma análise de máxima verossimilhança padrão usando o modelo correto (neste caso, o modelo CFN).

Note que o padrão de sítio com 0 corresponde aos sítios que não mudaram (após codificar os nucleotídeos como purinas ou pirimidinas). Os índices com asteriscos (3, 5 e 6) são "informativos para parcimônia". Os índices restantes representam padrões de sítio onde um único táxon difere dos outros três táxons (então eles são equivalentes aos comprimentos de ramos terminais em uma árvore filogenética de máxima verossimilhança padrão).

Se alguém deseja usar dados de nucleotídeos sem recodificar como R e Y (e, finalmente, como 0 e 1), é possível codificar os padrões de sítio como uma matriz. Se considerarmos uma árvore de quatro táxons, há um total de 256 padrões de sítio (quatro nucleotídeos elevados à quarta potência). No entanto, simetrias do modelo de três parâmetros de Kimura (ou modelo K81) nos permitem reduzir os 256 padrões de sítio possíveis para DNA para 64 padrões, tornando possível codificar os dados de nucleotídeos para uma árvore de quatro táxons como uma matriz 8 × 8 de maneira semelhante ao vetor de 8 elementos usado acima para padrões de sítio de transversão (RY). Isso é realizado recodificando os dados usando o grupo de Klein quatro:

Codificação do grupo de Klein quatro para a transformada filogenética de Hadamard
Nucleotídeo 1	Nucleotídeo 2	Nucleotídeo 3	Nucleotídeo 4
A (0,0)	G (1,0)	C (0,1)	T (1,1)
C (0,0)	T (1,0)	A (0,1)	G (1,1)
G (0,0)	A (1,0)	T (0,1)	C (1,1)
T (0,0)	C (1,0)	G (0,1)	A (1,1)

Como com os dados RY, os padrões de sítio são indexados em relação à base no primeiro táxon escolhido arbitrariamente, com as bases nos táxons subsequentes codificadas em relação a essa primeira base. Assim, o primeiro táxon recebe o par de bits (0,0). Usando esses pares de bits, pode-se produzir dois vetores semelhantes aos vetores RY e então preencher a matriz usando esses vetores. Isso pode ser ilustrado usando o exemplo de Hendy et al. (1994), que é baseado em um alinhamento de sequências múltiplas de quatro pseudogenes de hemoglobina de primatas:

Exemplo de alinhamento de sequências codificado (de Hendy et al. 1994) (valores são contagens de 9879 sítios)
	0	8	16	24	32	56
0	8988	9	10	12	24	90
1	41	9		**
2	45		13
3	54*			14		3
4	94				20
5			1
6	2				2
7	356		1		1	75

O número muito maior de padrões de sítio na coluna 0 reflete o fato de que a coluna 0 corresponde a diferenças de transição, que se acumulam mais rapidamente do que diferenças de transversão em praticamente todas as comparações de regiões genômicas (e definitivamente se acumulam mais rapidamente nos pseudogenes de hemoglobina usados para este exemplo trabalhado). Se considerarmos o padrão de sítio AAGG, ele seria codificado como padrão binário 0000 para o segundo elemento do par de bits do grupo de Klein e 0011 para o primeiro elemento. neste caso, o padrão binário baseado no primeiro elemento corresponde ao índice 3 (então linha 3 na coluna 0; indicado com um asterisco simples na tabela). Os padrões de sítio GGAA, CCTT e TTCC seriam codificados exatamente da mesma maneira. O padrão de sítio AACT seria codificado com padrão binário 0011 baseado no segundo elemento e 0001 baseado no primeiro elemento; isso produz índice 1 para o primeiro elemento e índice 3 para o segundo. O índice baseado no segundo par de bits do grupo de Klein é multiplicado por 8 para produzir o índice da coluna (neste caso, seria a coluna 24). A célula que incluiria a contagem de padrões de sítio AACT é indicada com dois asteriscos; no entanto, a ausência de um número no exemplo indica que o alinhamento de sequências não inclui padrões de sítio AACT (da mesma forma, padrões de sítio CCAG, GGTC e TTGA, que seriam codificados da mesma maneira, estão ausentes).

Outras aplicações

A transformada de Hadamard também é usada em criptografia de dados, bem como em muitos algoritmos de processamento de sinais e compressão de dados, como JPEG XR e MPEG-4 AVC. Em aplicações de compressão de vídeo, geralmente é usada na forma da soma das diferenças transformadas absolutas. Também é uma parte crucial de um número significativo de algoritmos em computação quântica. A transformada de Hadamard também é aplicada em técnicas experimentais como RMN, espectrometria de massa e cristalografia. É adicionalmente usada em algumas versões de hash sensível à localidade, para obter rotações de matriz pseudo-aleatórias.

Ver também

Ligações externas

Ritter, Terry (agosto de 1996). «Walsh–Hadamard Transforms: A Literature Survey»
Akansu, Ali N.; Poluri, R. (julho de 2007). «Walsh-Like Nonlinear Phase Orthogonal Codes for Direct Sequence CDMA Communications» (PDF). IEEE Transactions on Signal Processing. 55 (7): 3800–6. Bibcode:2007ITSP...55.3800A. doi:10.1109/TSP.2007.894229
Pan, Jeng-shyang Data Encryption Method Using Discrete Fractional Hadamard Transformation (28 de maio de 2009)
Lachowicz, Dr. Pawel. Walsh–Hadamard Transform and Tests for Randomness of Financial Return-Series (7 de abril de 2015)
Beddard, Godfrey; Yorke, Briony A. (janeiro de 2011). «Pump-probe Spectroscopy using Hadamard Transforms» (PDF). Consultado em 28 de abril de 2012. Arquivado do original (PDF) em 18 de outubro de 2014
Yorke, Briony A.; Beddard, Godfrey; Owen, Robin L.; Pearson, Arwen R. (setembro de 2014). «Time-resolved crystallography using the Hadamard transform». Nature Methods. 11 (11): 1131–1134. PMC 4216935. PMID 25282611. doi:10.1038/nmeth.3139

Referências

↑ Compare com a Figura 1 em Townsend, W.J.; Thornton, M.A. (2001). «Walsh spectrum computations using Cayley graphs». Proceedings of the 44th IEEE 2001 Midwest Symposium on Circuits and Systems (MWSCAS 2001). MWSCAS-01. 1. IEEE. pp. 110–113. ISBN 0-7803-7150-X. doi:10.1109/mwscas.2001.986127
1 2 Kunz, H.O. (1979). «On the Equivalence Between One-Dimensional Discrete Walsh–Hadamard and Multidimensional Discrete Fourier Transforms». IEEE Transactions on Computers. 28 (3): 267–8. doi:10.1109/TC.1979.1675334
↑ Fourier Analysis of Boolean Maps– A Tutorial –, pp. 12–13 ^{[ligação inativa]}
↑ Lecture 5: Basic quantum algorithms, Rajat Mittal, pp. 4–5
↑ Nielsen, Michael A.; Chuang, Isaac (2010). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 978-1-10700-217-3. OCLC 43641333
↑ Alok Shukla and Prakash Vedula (2024). «An efficient quantum algorithm for preparation of uniform quantum superposition states». Quantum Information Processing. 23:38 (1): 38. Bibcode:2024QuIP...23...38S. arXiv:2306.11747. doi:10.1007/s11128-024-04258-4
↑ «Hadamard transform». Wikipedia
1 2 3 4 5 6 Hongyi Pan; Xin Zhu; Salih Furkan Atici; Ahmet Enis Cetin (2023). A Hybrid Quantum-Classical Approach based on the Hadamard Transform for the Convolutional Layer. International Conference on Machine Learning. 202. PMLR. pp. 26891–26903. arXiv:2305.17510
↑ Hendy, Michael D.; Penny, David (dezembro de 1989). «A Framework for the Quantitative Study of Evolutionary Trees». Systematic Zoology. 38 (4). 297 páginas. JSTOR 2992396. doi:10.2307/2992396
↑ Hendy, Michael D.; Penny, David (janeiro de 1993). «Spectral analysis of phylogenetic data». Journal of Classification (em inglês). 10 (1): 5–24. ISSN 0176-4268. doi:10.1007/BF02638451
↑ Székely, L. A., Erdős, P. L., Steel, M. A., & Penny, D. (1993). A Fourier inversion formula for evolutionary trees. Applied mathematics letters, 6(2), 13–16.
↑ Felsenstein, Joseph (novembro de 1981). «Evolutionary trees from DNA sequences: A maximum likelihood approach». Journal of Molecular Evolution (em inglês). 17 (6): 368–376. Bibcode:1981JMolE..17..368F. ISSN 0022-2844. PMID 7288891. doi:10.1007/BF01734359
↑ Citação:
↑ Chor, Benny; Hendy, Michael D.; Holland, Barbara R.; Penny, David (1 de outubro de 2000). «Multiple Maxima of Likelihood in Phylogenetic Trees: An Analytic Approach». Molecular Biology and Evolution (em inglês). 17 (10): 1529–1541. ISSN 1537-1719. PMID 11018159. doi:10.1093/oxfordjournals.molbev.a026252
↑ Matsen, Frederick A.; Steel, Mike (1 de outubro de 2007). Ané, Cécile, ed. «Phylogenetic Mixtures on a Single Tree Can Mimic a Tree of Another Topology». Systematic Biology (em inglês). 56 (5): 767–775. ISSN 1076-836X. PMID 17886146. arXiv:0704.2260. doi:10.1080/10635150701627304
↑ Waddell, Peter J; Steel, M.A (dezembro de 1997). «General Time-Reversible Distances with Unequal Rates across Sites: Mixing Γ and Inverse Gaussian Distributions with Invariant Sites». Molecular Phylogenetics and Evolution (em inglês). 8 (3): 398–414. Bibcode:1997MolPE...8..398W. PMID 9417897. doi:10.1006/mpev.1997.0452
↑ Steel, M. A.; Hendy, M. D.; Penny, D. (1 de dezembro de 1993). «Parsimony Can Be Consistent!». Systematic Biology (em inglês). 42 (4): 581–587. ISSN 1063-5157. doi:10.1093/sysbio/42.4.581
1 2 3 Hendy, M. D.; Penny, D.; Steel, M. A. (12 de abril de 1994). «A discrete Fourier analysis for evolutionary trees.». Proceedings of the National Academy of Sciences (em inglês). 91 (8): 3339–3343. Bibcode:1994PNAS...91.3339H. ISSN 0027-8424. PMC 43572. PMID 8159749. doi:10.1073/pnas.91.8.3339
↑ Miyamoto, M. M.; Koop, B. F.; Slightom, J. L.; Goodman, M.; Tennant, M. R. (1 de outubro de 1988). «Molecular systematics of higher primates: genealogical relations and classification.». Proceedings of the National Academy of Sciences (em inglês). 85 (20): 7627–7631. Bibcode:1988PNAS...85.7627M. ISSN 0027-8424. PMC 282245. PMID 3174657. doi:10.1073/pnas.85.20.7627

[1] Compare com a Figura 1 em Townsend, W.J.; Thornton, M.A. (2001). «Walsh spectrum computations using Cayley graphs». Proceedings of the 44th IEEE 2001 Midwest Symposium on Circuits and Systems (MWSCAS 2001). MWSCAS-01. 1. IEEE. pp. 110–113. ISBN 0-7803-7150-X. doi:10.1109/mwscas.2001.986127

[kunz-2] 1 2 Kunz, H.O. (1979). «On the Equivalence Between One-Dimensional Discrete Walsh–Hadamard and Multidimensional Discrete Fourier Transforms». IEEE Transactions on Computers. 28 (3): 267–8. doi:10.1109/TC.1979.1675334

[3] Fourier Analysis of Boolean Maps– A Tutorial –, pp. 12–13 ^{[ligação inativa]}

[4] Lecture 5: Basic quantum algorithms, Rajat Mittal, pp. 4–5

[Nielsen-Chuang-5] Nielsen, Michael A.; Chuang, Isaac (2010). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 978-1-10700-217-3. OCLC 43641333

[shukla2024efficient-6] Alok Shukla and Prakash Vedula (2024). «An efficient quantum algorithm for preparation of uniform quantum superposition states». Quantum Information Processing. 23:38 (1): 38. Bibcode:2024QuIP...23...38S. arXiv:2306.11747. doi:10.1007/s11128-024-04258-4

[hadamard_wiki-7] «Hadamard transform». Wikipedia

[pan2023hybrid-8] 1 2 3 4 5 6 Hongyi Pan; Xin Zhu; Salih Furkan Atici; Ahmet Enis Cetin (2023). A Hybrid Quantum-Classical Approach based on the Hadamard Transform for the Convolutional Layer. International Conference on Machine Learning. 202. PMLR. pp. 26891–26903. arXiv:2305.17510

[9] Hendy, Michael D.; Penny, David (dezembro de 1989). «A Framework for the Quantitative Study of Evolutionary Trees». Systematic Zoology. 38 (4). 297 páginas. JSTOR 2992396. doi:10.2307/2992396

[10] Hendy, Michael D.; Penny, David (janeiro de 1993). «Spectral analysis of phylogenetic data». Journal of Classification (em inglês). 10 (1): 5–24. ISSN 0176-4268. doi:10.1007/BF02638451

[11] Székely, L. A., Erdős, P. L., Steel, M. A., & Penny, D. (1993). A Fourier inversion formula for evolutionary trees. Applied mathematics letters, 6(2), 13–16.

[12] Felsenstein, Joseph (novembro de 1981). «Evolutionary trees from DNA sequences: A maximum likelihood approach». Journal of Molecular Evolution (em inglês). 17 (6): 368–376. Bibcode:1981JMolE..17..368F. ISSN 0022-2844. PMID 7288891. doi:10.1007/BF01734359

[13] Citação:

[14] Chor, Benny; Hendy, Michael D.; Holland, Barbara R.; Penny, David (1 de outubro de 2000). «Multiple Maxima of Likelihood in Phylogenetic Trees: An Analytic Approach». Molecular Biology and Evolution (em inglês). 17 (10): 1529–1541. ISSN 1537-1719. PMID 11018159. doi:10.1093/oxfordjournals.molbev.a026252

[15] Matsen, Frederick A.; Steel, Mike (1 de outubro de 2007). Ané, Cécile, ed. «Phylogenetic Mixtures on a Single Tree Can Mimic a Tree of Another Topology». Systematic Biology (em inglês). 56 (5): 767–775. ISSN 1076-836X. PMID 17886146. arXiv:0704.2260. doi:10.1080/10635150701627304

[16] Waddell, Peter J; Steel, M.A (dezembro de 1997). «General Time-Reversible Distances with Unequal Rates across Sites: Mixing Γ and Inverse Gaussian Distributions with Invariant Sites». Molecular Phylogenetics and Evolution (em inglês). 8 (3): 398–414. Bibcode:1997MolPE...8..398W. PMID 9417897. doi:10.1006/mpev.1997.0452

[17] Steel, M. A.; Hendy, M. D.; Penny, D. (1 de dezembro de 1993). «Parsimony Can Be Consistent!». Systematic Biology (em inglês). 42 (4): 581–587. ISSN 1063-5157. doi:10.1093/sysbio/42.4.581

[:0-18] 1 2 3 Hendy, M. D.; Penny, D.; Steel, M. A. (12 de abril de 1994). «A discrete Fourier analysis for evolutionary trees.». Proceedings of the National Academy of Sciences (em inglês). 91 (8): 3339–3343. Bibcode:1994PNAS...91.3339H. ISSN 0027-8424. PMC 43572. PMID 8159749. doi:10.1073/pnas.91.8.3339

[19] Miyamoto, M. M.; Koop, B. F.; Slightom, J. L.; Goodman, M.; Tennant, M. R. (1 de outubro de 1988). «Molecular systematics of higher primates: genealogical relations and classification.». Proceedings of the National Academy of Sciences (em inglês). 85 (20): 7627–7631. Bibcode:1988PNAS...85.7627M. ISSN 0027-8424. PMC 282245. PMID 3174657. doi:10.1073/pnas.85.20.7627