Uma breve introdução à computação quântica

Em 1900, o matemático David Hilbert alfinetou a comunidade acadêmica propondo alguns problemas matemáticos. Dentre esses, o Entscheidungsproblem (“Problema da decisão”) levantava a seguinte pergunta:

Dado um conjunto de premissas, é possível dizer se elas implicam em uma determinada conclusão?

E ela, naturalmente, trouxe consigo algumas outras como:

Há como testar se a resposta para essa pergunta é “Sim” ou “Não”?

Existe alguma forma automática de descobrir se a resposta para essa pergunta é “Sim” ou “Não”?

Em uma resposta ao problema da decisão, Alan Turing desenvolveu uma máquina hipotética e, através dela, concluiu que não é possível determinar “Sim” ou “Não” de forma computacional. Essa máquina, posteriormente chamada de “Máquina de Turing”, pode ser definida como um computador de propósito geral, capaz de implementar qualquer sistema computacional.

Dessa forma, ela é a base para todos os computadores clássicos que conhecemos hoje. Além disso, esses computadores com poder igual ao dela, são classificados como Turing-Complete. No entanto, a Máquina de Turing possui algumas limitações. Ao longo do tempo, descobriu-se que há alguns problemas e funções que não são computáveis por ela.

Em 1939, em um artigo, Alan introduziu um modelo mais poderoso de sua máquina e isso inspirou a ideia de modelos computacionais que consigam computar problemas que a máquina de turing não consegue. Por exemplo, o problema da parada. A posteriori, esses modelos foram batizados pelo termo "Hipercomputação", mas também são conhecidos como máquinas super-Turing. Uma das propostas de modelos super-Turing na qual são lançadas grandes apostas, é chamado de Computação Quântica.

Em 1982, Richard Feynman publicou um artigo defendendo que a tese de Church-Turing não é aplicável no nível da física quântica. Apesar disso, foi a partir dos algoritmos de Shor e Grover que a vantagem quântica tomou uma forma palpável.

O primeiro, trata fatoração de primos de uma forma bastante eficiente se comparada a algoritmos clássicos.

A segunda, trata de pesquisas em listas desestruturadas. Enquanto algoritmos clássicos fazem busca em O(n), o algoritmo de Grover faz em O(√n).

Há um longo caminho pela frente e certamente não encontraremos um computador quântico na Lan House da esquina hoje, no qual possamos treinar nossas redes neurais com speedup exponencial. Todavia, esses computadores já existem e estão razoavelmente acessíveis para todos nós.

Há até os que são focados em problemas do mercado e já estão disponíveis para compra, mas esse é o assunto do nosso próximo post. Fica de olho!

Fontes:

http://www.ic.unicamp.br/~bit/arquivos/tg.pdf

Alan Turing: Crash Course Computer Science #15

Alan Turing — Celebrating the life of a genius

Turing & The Halting Problem — Computerphile