thumb|300px|O produto de uma função booleana e uma matriz de Hadamard é seu espectro de Walsh:Compare com a Figura 1 em (1, 0, 1, 0, 0, 1, 1, 0) × H(8) = (4, 2, 0, −2, 0, 2, 0, 2) thumb|300px|Transformada rápida de Walsh–Hadamard, uma maneira mais rápida de calcular o espectro de Walsh de (1, 0, 1, 0, 0, 1, 1, 0). thumb|300px|A função original pode ser expressa por meio de seu espectro de Walsh como um polinômio aritmético
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 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 . 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 (), do matemático teuto-americano Hans Rademacher e do matemático americano Joseph L. Walsh.
Definição
A transformada de Hadamard Hm é uma matriz 2m × 2m, a matriz de Hadamard (escalonada por um fator de normalização), que transforma 2m números reais xn em 2m números reais Xk. 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 H0 pela identidade H0 = 1, e então definimos Hm para m > 0 por:
onde a divisão por 2m/2 é uma normalização que às vezes é omitida.
Para m > 1, também podemos definir Hm por:
onde 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
onde os kj e nj são os elementos de bit (0 ou 1) de k e n, respectivamente. Note que para o elemento no canto superior esquerdo, definimos: . Neste caso, temos:
Esta é exatamente a DFT multidimensional , normalizada para ser unitária, se as entradas e saídas são consideradas como matrizes multidimensionais indexadas pelos nj e kj, respectivamente.
Alguns exemplos das matrizes de Hadamard seguem.
onde é o produto escalar bit a bit das representações binárias dos números i e j. Por exemplo, se , então , concordando com o acima (ignorando a constante global). Note que o elemento da primeira linha, primeira coluna da matriz é denotado por .
H1 é 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]
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. Compare isso com uma transformada discreta de Fourier , na qual cada linha contém cruzamentos por zero.
Em uma transformada discreta de Fourier, quando é 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 .
Outra abordagem é ver a transformada de Hadamard como uma transformada de Fourier no grupo booleano .Fourier Analysis of Boolean Maps– A Tutorial –, pp. 12–13 Lecture 5: Basic quantum algorithms, Rajat Mittal, pp. 4–5 Usando a transformada de Fourier em grupos (abelianos) finitos, a transformada de Fourier de uma função é a função definida por
onde é um caráter de . Cada caráter tem a forma para algum , onde a multiplicação é o produto escalar booleano em strings de bits, então podemos identificar a entrada de com (dualidade de Pontryagin) e definir por
Esta é a transformada de Hadamard de , considerando a entrada de e como strings booleanas.
Em termos da formulação acima, onde a transformada de Hadamard multiplica um vetor de números complexos à esquerda pela matriz de Hadamard , a equivalência é vista tomando para receber como entrada a string de bits correspondente ao índice de um elemento de , e tendo como saída o elemento correspondente de .
Compare isso com a transformada discreta de Fourier usual que, quando aplicada a um vetor de números complexos, usa em vez disso caracteres do grupo cíclico .
Complexidade computacional No domínio clássico, a transformada de Hadamard pode ser computada em operações (), usando o algoritmo da transformada rápida de Hadamard.
No domínio quântico, a transformada de Hadamard pode ser computada em tempo , 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 é 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 em paralelo é equivalente à transformada de Hadamard
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 e para dois estados de superposição com peso igual dos estados da base computacional e . Normalmente as fases são escolhidas de modo que
em notação de Dirac. Isso corresponde à matriz de transformação
na base , também conhecida como base computacional. Os estados e são conhecidos como e respectivamente, e juntos constituem a base polar em computação quântica.
Operações da porta de Hadamard
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 operações, comparado ao caso clássico de operações.
Para um sistema de qubits, portas de Hadamard agindo em cada um dos qubits (cada um inicializado para ) pode ser usado para preparar estados de superposição quântica uniforme quando é da forma . Neste caso com qubits, a porta de Hadamard combinada é expressa como o produto tensorial de portas de Hadamard:
O estado de superposição quântica uniforme resultante é então:
Isso generaliza a preparação de estados quânticos uniformes usando portas de Hadamard para qualquer .
A medição deste estado quântico uniforme resulta em um estado aleatório entre e
Muitos algoritmos quânticos usam a transformada de Hadamard como um passo inicial, pois como explicado anteriormente, ela mapeia n qubits inicializados com para uma superposição de todos os 2n estados ortogonais na base 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 e a segunda em .
A preparação de estados de superposição quântica uniforme no caso geral, quando ≠ é não trivial e requer mais trabalho. Uma abordagem eficiente e determinística para preparar o estado de superposição <math display="block"> |\Psi\rangle = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} |j\rangle </math> com uma complexidade de portas e profundidade de circuito de apenas para todos foi recentemente apresentada. Esta abordagem requer apenas
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)