Laboratórios
O Algoritmo de Deutsch
Qui 25 Nov 2004 22:00 |
- Detalhes
- Categoria: Laboratório de Física Quântica
- Atualização: Quarta, 13 Janeiro 2010 23:47
- Autor: Mendonça
- Acessos: 17585
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
f(1) = 0
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!
- Anterior
- Próximo >>