Alguns Comentários sobre Transformadas Quânticas

Bernardo Lula Jr, Bruno Albert, Francisco Assis

DOI: 10.14209/sbrt.2005.403

Evento: XXII Simpósio Brasileiro de Telecomunicações (SBrT2005)

Keywords: Tranformada discreta de Fourier quântica transformada discreta de Hartley quântica

Abstract

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(n2 log n log log n) operações. Este algoritmo é exponencialmente mais eficiente que o melhor algoritmo clássico correspondente que exige O(exp(n1/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âncias de tamanho N (em geral N = 2n ). 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.

Download