Título: Transformadas Quânticas de Fourier e de Hartley
Autores: Lula Jr., Bernardo; Albert, Bruno B.; Assis, Francisco M. de
Resumo: Uma descoberta notável ocorrida na área da teoria da informação e computação quântica foi a prova de existência de um algoritmo quântico para fatoração de inteiros de n − bits com complexidade O(n^2 log n log log n) operações. Este algoritmo é exponencialmente mais eficiente que o melhor algoritmo clássico correspondente que exige O(exp(n^1/3 log^2/3 )) operações. A razão para a eficiência do algoritmo quântico mencionado é a existência de um algoritmo para o cálculo da transformada de Fourier quântica (QFT) de complexidade O((log N)^2 ) enquanto o melhor algoritmo clássico (FFT) tem complexidade O(N log N) para uma instância de tamanho N (em geral N = 2^n ). Este artigo focaliza de modo tutorial a QFT e introduz as transformadas de Hartley quânticas definindo-as e verificando algumas de suas propriedades mais importantes.
Palavras-chave: Tranformada discreta de Fourier quântica; transformada discreta de Hartley quântica
Páginas: 6
Código DOI: 10.21528/CBRN2005-228
Artigo em PDF: CBRN2005_228.pdf
Arquivo BibTex: CBRN2005_228.bib