Breve introdução à computação quântica/Teoria da computação

A encarnação moderna da ciência da computação foi prenunciada pelo grande matemático Alan Turing. Ele desenvolveu em detalhes uma noção abstrata do que se poderia agora chamar de computador programável, um modelo de computação conhecido como Máquina de Turing. Esse cientista demonstrou a existência da Máquina de Turing Universal que pode ser usada para simular qualquer outra máquina de Turing. Ademais, ele afirmou que a Máquina de Turing Universal captura completamente o significado de se realizar uma tarefa por meios algorítmicos. Isto é, se um algoritmo pode ser realizado em qualquer peça de hardware, então existe um algoritmo equivalente para uma Máquina de Turing Universal que realiza exatamente a mesma tarefa que o algoritmo original. Esta declaração, conhecida como a tese de Church-Turing, asserta a equivalência entre o conceito físico de que classes de algoritmos podem ser executados em algum dispositivo físico com o rigor matemático de uma Máquina de Turing Universal. A larga aceitação desta tese levou ao desenvolvimento de uma rica teoria de ciência da computação.

Este módulo tem a seguinte tarefa pendente: Inserir figura 1: Ilustração da Máquina de Turing.

O que foi observado em meados de 1970 é que parecia que o modelo de computação da Máquina de Turing (fig. 1) era ao menos tão poderoso quanto qualquer outro modelo de computação, no sentido de que um problema que podia ser resolvido eficientemente em algum modelo de computação também poderia ser resolvido eficientemente no modelo da Máquina de Turing. Esta observação foi codificada em uma versão fortalecida da tese de Church-Turing:

Qualquer processo algorítmico pode ser simulado eficientemente usando-se a máquina de Turing.

O primeiro grande desafio à tese forte de Church-Turing surgiu também em meados de 1970, quando Robert Solovay e Volker Strassen mostraram que é possível testar se um inteiro é primo ou composto usando-se um algoritmo randômico. Isto é, o teste de Solovay-Strassen para primalidade usava aleatoriedade como parte essencial do algoritmo. O algoritmo não determinava se um dado inteiro era primo ou composto com certeza. Ao invés disso, o algoritmo podia determinar que um número era provavelmente primo (ou, do contrário, composto). Repetindo o teste de Solovay-Strassen algumas vezes é possível determinar com aproximada certeza se um número é primo ou composto. Na época que o teste foi proposto não havia nenhum teste determinístico para primalidade conhecido. Assim, parecia que computadores com acesso a um gerador aleatório de números seria capaz de eficientemente realizar tarefas computacionais sem soluções eficientes em uma máquina de Turing determinística convencional. Este desafio parece ser facilmente resolvido por uma simples modificação na tese forte de Church-Turing: Qualquer processo algorítmico pode ser simulado eficientemente usando-se uma máquina de Turing probabilística. Esta modificação ad hoc da tese forte de Church-Turing leva a um sentimento delicado. Não seria o caso de que algum dia ainda outro modelo de computação permitiria resolver eficientemente problemas que não são eficientemente solucionáveis com o modelo de computação de Turing? Motivado por esta questão, em 1985 David Deutsch questionou se as leis da física poderiam ser usadas para derivar uma versão ainda mais forte da tese de Church-Turing. Ele esforçou-se em definir um dispositivo computacional que seria capaz de eficientemente simular um sistema físico arbitrário. Uma vez que as leis da física são quânticas, ele foi naturalmente levado a considerar dispositivos computadores baseados nos princípios da mecânica quântica. O que modelo de computador quântico de Deutsch desencadeou (ver apêndice) foi um desafio à forma forte da tese de Church-Turing. Deutsch questionou se é possível que um computador quântico eficientemente resolva problemas que não têm solução eficiente em um computador clássico, mesmo em uma máquina de Turing probabilística. Este memorável primeiro passo foi aprimorado na década subseqüente por muitas pessoas, e tem-se hoje uma vasta e bela teoria, já subdividida em vários ramos.