Computação Quantica

Computação Quântica

Computação Quântica é um tema recente, que procura utilizar as descobertas da física quântica para o desenvolvimento de aplicações computacionais. Embora proposto teoricamente na década de 80, ainda não há nenhum computador que utilize de forma satisfatória a estrutura quântica da matéria nos processos de computação. Isso, ainda hoje, constitui-se numa importante linha de pesquisas.

Algoritmos quânticos

Algoritmos quânticos estão baseados no modelo computacional que utiliza a estrutura quântica da matéria no processo de computação. Os circuitos quânticos e Máquinas de Turing Quânticas são formas equivalentes para se descrever um algoritmo quântico, ficando a critério utilizar a notação que achar mais adequada. Um conceito importante para o desenvolvimento de algoritmos quânticos é o paralelismo quântico. Como o estado de um registrador quântico reflete a superposição das amplitudes dos elementos da base computacional do sistema, é possível aplicar uma operação sobre todos esses elementos ao mesmo tempo e, assim, obter uma superposição dos resultados da operação sobre os elementos da base computacional. Como o algoritmo irá tratar essa superposição de resultados para extrair a informação desejada varia de caso para caso. Porém, fica claro que esse é um grande diferencial da computação quântica perante a computação clássica. Vários algoritmos quânticos e técnicas para desenvolvimento de algoritmos quânticos foram desenvolvidos até hoje, e a explicação detalhada de todos estes é inviável dada a limitação de espaço desta proposta. Vamos, então, comentar brevemente sobre os mais importantes.

Algoritmos de Shor : O grande salto da Computação Quântica se deu quando Shor propôs algoritmos quânticos que computam fatores primos de grandes números e que calculam o logaritmo discreto de um número, ambos com complexidade polinomial .Os melhores algoritmos clássicos conhecidos até o momento para resolver esses problemas apresentam complexidade exponencial em tempo. Portanto, um computador quântico faria com que problemas hoje considerados intratáveis pudessem ser resolvidos de forma eficaz. Estes problemas são importantes pois são o cerne dos principais métodos criptográficos em uso hoje em dia.

Algoritmo de Grover : O Algoritmo de Grover resolve o problema de buscas em um banco de dados desordenado, apresentando um ganho quadrático em relação aos algoritmos clássicos. O ganho não é exponencial, como no caso dos algoritmos de Shor, porém é possível aplicar seu resultado em muitos problemas importantes, inclusive a todos os problemas da classe NP.

Passeios quânticos : Análogo quântico aos passeios aleatórios, os passeios quânticos descrevem o movimento de um caminhante condicionado a uma moeda quântica, e tendo sua posição definida por uma sobreposição de estados. Um grande diferencial dos passeios quânticos é que permitem trabalhar sobre estruturas muito conhecidas como uma linha ou, mais genericamente, sobre um grafo qualquer. Diversos algoritmos quânticos foram desenvolvidos utilizando o conceito de passeios quânticos. Alguns deles apresentam um ganho exponencial em complexidade de tempo em relação aos algoritmos clássicos.

Computação Clássica Vs Computação Quântica

Na computação clássica, o estudo da computabilidade nos permitiu classificar os problemas quanto ao modelo computacional necessário para resolvê-lo, caso isso seja possível. Esse estudo foi estendido à Computação Quântica, definindo-se modelos quânticos análogos para autômatos finitos determinísticos (AFDs), autômatos de pilha (APs) e Máquinas de Turing determinísticas (MTs). Verificou-se, porém, que varia o modo como cada modelo computacional quântico se relaciona com sua contrapartida determinística. É sabido que o conjunto das linguagens aceitas por 1-QFAs (autômatos finitos quânticos que só se movem em uma direção) é um subconjunto próprio daquelas aceitas por AFDs. Já no modelo em que é permitido mover-se nos 2 sentidos da fita de entrada (os 2-QFAs), estes aceitam um superconjunto próprio das linguagens aceitas por AFDs. Quando partimos para o estudo das linguagens livres de contexto (LLC), que são