Nos dois últimos artigos estivemos ocupados construindo os pilares da física quântica. É mais do que justo que tenhamos, agora, um pouco de contemplação sobre o que edificamos até aqui. Para isso, nada melhor do que uma aplicação evidenciando a importância de cada aspecto discutido. O algoritmo de Deutsch se presta perfeitamente a esse papel, e é a "bola da vez".

Um algoritmo é uma receita usada sistematicamente para solucionar um problema. Portanto, quando falamos em algoritmo de Deutsch, está implícito que existe um "Problema de Deutsch", e é por ele que começaremos essa discussão

Suponha que você tenha uma caixa preta que opera num certo bit x (onde x = 0 ou x = 1, como usual na computação clássica).

A operação da caixa preta pode muito bem ser entendida como uma função f, que leva o bit x para um valor a ele relacionado, f(x) (também binário, ou seja, f(x) = 0 ou f(x) = 1). O problema é que não conhecemos a lei da função, e portanto não podemos descobrir quanto é f(0) e f(1) senão usando a caixa preta. Em outras palavras, sabemos que uma certa operação é internamente executada, mas não temos acesso a conhecer que operação é essa, a priori. Daí o nome "caixa preta".

O problema de Deutsch está diretamente relacionado a tentar extrair alguma informação sobre "que operação é essa". Por exemplo, se operarmos a caixa preta nos bits 0 e 1, e obtivermos os resultados

teremos aprendido que a operação escondida é equivalente a uma porta lógica NOT (a porta que inverte o sinal de 0 para 1 e de 1 para 0).

Todavia, Deutsch não exige que descubramos tanto assim sobre a caixa preta. Ele faz uma preciosa concessão ao se declarar satisfeito se descobrirmos simplesmente se a função executada é contínua ou balanceada.

Uma função contínua obedece a igualdade

enquanto que uma função balanceada se comporta segundo a desigualdade

Note que, para resolver o problema de Deutsch, não precisamos saber quanto é f(0) e f(1). Queremos simplesmente descobrir se eles são iguais ou diferentes, ou seja, se f é contínua ou balanceada.

Num computador clássico, essa concessão não alivia em nada a nossa vida. Para descobrir de que tipo é f, o melhor a fazer é primeiro executar a caixa preta sobre o bit 0, obtendo f(0); depois executar a caixa preta sobre o bit 1, obtendo f(1); só então, de posse dos dois valores, é que se efetua a comparação entre eles para descobrir se a função é contínua ou balanceada. Ou seja, o processo num computador clássico demanda duas etapas para ser realizado.

Numa primeira olhada, isso não parece um problema sério. Porém, agregando a informação de que cada etapa leva 24 hs para ser concluída, e de que você precisa descobrir o resultado em menos de 48 hs para manter o seu emprego, fica claro que você tem um problema e tanto nas mãos: o problema de Deutsch!