Para que servem os computadores quânticos?

Esta é uma pergunta que vem sendo cada vez mais levantada, “para que servem os computadores quânticos”.

É um fato, que já sentimos a frustração de cada vez mais precisarmos de recursos computacionais para resolver um problema. Muitos problemas importantes sâo impossíveis de ser resolvidos em computadores ditos clássicos, não porque sejam insolúveis por natureza, mas por causa da grande quantidade de recursos necessários para a sua solução.

A principal promessa da computação quântica são os novos e poderosos algoritmos, capazes de resolver problemas solúveis, mas que classicamente requerem uma quantidade colossal de recursos.

Até o presente momento, são conhecidas duas classes de algoritmos quânticos capazes de cumprir essa tão desejada façanha.

1) A primeira é baseada na transformada de Fourier quântica de Shor (Peter Shor), e inclui algoritmos notáveis para resolver os problemas de fatoração e de logaritmos discretos, com ganho exponencial de velocidade sobre os melhores algoritmos clássicos conhecidos até hoje na história.

2) A segunda classe de algoritmos é baseada no algoritmo de Grover (Lov K. Grover) para a realização de busca quântica. Esse algoritmo oferece um ganho quadrático de tempo sobre os equivalentes clássicos. Mesmo não sendo tão imapactante quanto o caso exponencial, ainda assim é expressivo se comparado com algoritmo clássico.

É importante observar que a relevância desses algoritmos está no amplo uso das técnicas de busca por meio de algoritmos clássicos, que em muitos casos podem ser facilmente adaptados para o caso quântico obtendo-se algoritmos mais rápidos.

Na imagem acina, está desenhado o esboço do que seria “estado da arte” sobre algoritmos quânticos conhecido até o momento. Como podemos ver, no centro do diagrama, está a transformada de Fourier quântica e o algoritmo quântico de busca. Importante também, é o algoritmo quântico de contagem, trata-se de uma combinação inteligente da transformada de Fourier quântica com o algoritmo de busca. Ele pode ser usado para estimar o número de soluções de um problema de busca mais rapidamente do que é possível em um computador clássico.

O algoritmo quântico de busca possui muitas potenciais aplicações: ele pode ser usado em estatística (por exemplo, para se encontrar o elemento mínimo em um conjunto de dados desordenados mais rapidamente do que é possível em um computador clássico),  para agilizar algoritmos para alguns problemas de NP (Tempo polinomial não determinístico ou Non-Deterministic Polynomial time) – especificamente, aqueles para os quais uma busca de soluções é a melhor técnica conhecida e, também, para encontrar chaves de sistemas criptográficos tal como o amplamente utilizado DES (Data Encryption Standard ou Padronização para Encriptação de Dados).

A transformada de Fourier quântica também tem muitas aplicações interessantes. Ela pode ser usada para resolver problemas de logaritmos discreto e de fatoração. Esses resultados, permitem que um computador quântico decifre muitos códigos de vários sistemas criptográficos em uso atualmente, incluindo o sistema RSA (“Rivest-Shamir-Adleman”). A transformada de Fourier quântica está intimamente relacionada a um importante problema de matemátíca,  o de se encontrar um subgrupo escondido (uma generalização do problema de se encontrar o período de uma função periódica). Não entrarei na matemática relativa a estes assuntos, pois não sou matemático e poderia cometer erros ao tentar explicar tais conceitos com maior grau de detalhes.

Atualmente existem poucos algoritmos quânticos em relação ao seu parente clássico. Mas por que existem tão poucos algoritmos quânticos melhores do que seus equivalentes clássicos?

Inventar bons algoritmos quânticos é uma questão difícil. Existem ao menos duas razões para esta pergunta:

A primeira delas é que projetar algoritrnos sejam eles quais forem (clássicos ou quânticos) não é um trabalho trivial.

Inventar algoritmos quânticos é bem mais complexo, pois, afinal de contas, necessitamos de algoritmos que sejam melhores do que as suas contrapartidas clássícas. Uma segunda razão para a dificuldade de se encontrarem bons algoritmos quânticos está no fato de que nossa intuição está adaptada para o mundo clássico e não para o mundo quântico. Se pensarmos nos problemas usando a nossa intuição, as soluções virão como algoritmos clássicos. Inventar bons algoritmos quânticos requer insights especiais e até mesmo alguns “truques matemáticos”.

Em um próximo artigo abordarei o estudo detalhado de algoritmos quânticos e a linguagem de circuitos quânticos, combinações de conjuntos discretos de componentes que descrevem o processo computacional permitindo quantificar o custo de um algoritmo em termos de variáveis como o número de portas necessárias, ou a complexidade do circuito.