Laboratórios

O Algoritmo de Deutsch

Qui

25

Nov

2004


22:00

  • Imprimir
(11 votos, média 4.64 de 5) 


1. Reaquecendo os motores

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

2. O Problema de Deutsch

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(0) = 1
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

f(0) = f(1),

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

Image

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!


3. O Algoritmo de Deutsch

Vamos agora entender como Deutsch (e a física quântica), salvaram nossos salários. Não resta muita dúvida que, dependendo de resolver o problema classicamente, nós estamos demitidos; então, o natural é tentar usar os novos "recursos quânticos", postulados no último artigo.

Mas, já que vamos usar física quântica, cabem algumas modificações de linguagem. Em primeiro lugar, o que chamávamos de bits na física clássica, em física quântica são conhecidos como qubits (um acrônimo de quantum bit). Para diferenciar os bits dos qubits, vamos representar os últimos usando uma notação comum à física quântica: a notação de Dirac. Segundo ela, o qubit 0 é escrito como |0ket). Na verdade, os kets representam o estado do sistema, e portanto, lembrando do primeiro postulado, percebemos uma grande novidade aqui. Enquanto que os bits só podem ser 0 ou 1, os qubits podem ser qualquer superposição de |0

Image

em que α e β são quaisquer números complexos que satisfaçam a normalização acima.

Por estranho que pareça, isso quer dizer que um computador quântico dispõe de uma variedade muito maior de unidades de informação, pois admite uma infinidade de qubits, enquanto que o computador clássico tem que se virar com seus míseros 0’s e 1’s... Isso, como veremos, pode fazer toda a diferença.

3.1 Criando a "Caixa Preta Quântica"

Como vamos lidar com qubits, precisamos de uma "caixa preta quântica", ou seja, uma que saiba processar estados superpostos. Um processamento, por sua vez, é uma dinâmica imposta a um estado, o que na física quântica se faz através de matrizes unitárias (segundo postulado). Portanto, nossa "caixa preta quântica" deve assumir a forma de uma matriz unitária que chamaremos Uf (o índice f para lembrar que há uma forte relação entre o que a matriz Uf faz com os qubits e o que a função f faz com os bits).

Como não sabemos qual é a função f, fica difícil escrever uma matriz para Uf, mas pelo simples fato de sabermos que essa matriz deve ser unitária, algumas inferências podem ser feitas sobre a sua forma.

Em primeiro lugar, vimos que

Image

Se em vez de matrizes, estivéssemos trabalhando com números, escreveríamos essa igualdade como uu† = 1, e imediatamente alguém poderia pensar em passar o primeiro u dividindo no segundo membro da equação, resultando em u† = u−1. Com matrizes, esse procedimento segue um raciocínio um pouco diferente, mas a "cara do resultado" é exatamente a mesma:

Image

Não existe uma operação de divisão para matrizes, logo o significado de U−1 não é Image (isso é um absurdo em se tratando de matrizes). Na verdade, a matriz U−1 é chamada de matriz inversa de U, e é definida de modo a obedecer que o produto de uma matriz pela sua inversa é sempre igual à matriz identidade.

O curioso é que nem todas as matrizes têm uma matriz inversa: se você escolher uma matriz qualquer (não unitária), existe alguma chance de que você nunca encontre uma matriz que multiplicada por ela resulte na matriz identidade! Todavia, se você escolher uma matriz unitária, a equação acima mostra que sempre vai existir uma matriz inversa, e para obtê-la basta tomar a adjunta da matriz escolhida! (pode parecer que perdemos o fio da meada, mas num instante estaremos de volta ao Algoritmo de Deutsch).

Digamos que uma matriz U leva um sistema físico de um estado inicial Image a um estado final Image.

Image

O papel da matriz inversa U−1, é exatamente fazer o caminho inverso, ou seja, usando o estado final como estado de partida e aplicando U−1 sobre ele, obteremos o estado inicial como resultado:

Image

Tudo isso vem mostrar que, na física quântica, a dinâmica unitária é reversível, ou seja, assim como você sabe aonde vai chegar se souber de onde partiu, você também pode saber de onde partiu se o que você sabe é aonde chegou.

Voltando ao problema de Deutsch... Não sabemos escrever a matriz Uf, mas não resta dúvida que, seja ela qual for, a dinâmica imposta deve ser reversível. Por outro lado, a função f não precisa ser reversível. Por exemplo, a caixa preta poderia muito bem seguir a prescrição: f(0) = 0 e f(1) = 0. Neste caso, a saída independe da entrada, isto é, não podemos descobrir a entrada olhando somente para a saída; logo, f é irreversível. Aliás, é fácil ver que se f fosse necessariamente reversível, consequentemente seria também balanceado, e todo o problema de Deutsch estaria resolvido sem demandar qualquer esforço.

Enfim, chegamos ao dilema: é possível incorporar, numa matriz reversível, os efeitos de uma função não necessariamente reversível?

A resposta é "sim", mas há um custo. Em vez de considerar somente o qubit |x

Com isso, podemos definir uma matriz Uf unitária (consequentemente reversível), quer f seja reversível ou não. A matriz Uf é definida como

Image

É verdade que o objeto acima não tem cara de matriz (onde estão as linhas e as colunas?). Não escrevemos em forma matricial porque a notação acima é mais sugestiva do processo de evolução (mas é equivalente à forma matricial). Note que a expressão define muito bem a dinâmica que Uf impõe sobre os qubits |xf desconhecido: do lado esquerdo da seta temos os estados iniciais e do lado direito os estados resultantes da aplicação de Uf. Dessa forma, é fácil ver que nada acontece com o estado da primeira "moeda", mas o estado da segunda "moeda" é modificado ou não, dependendo do que faz a função f sobre o estado da primeira "moeda".

Você vai notar o símbolo Image, que pode causar desconforto. De fato, esse símbolo indica adição módulo 2, ou seja, a adição de números binários. Tudo o que precisamos saber sobre isso, por enquanto, é que

Image

Ou seja, o símbolo Image é uma forma compacta de escrever:

Image

Mas será que a dinâmica Uf , definida na equação (1), é realmente reversível?

Para checar, vamos escolher alguns possíveis |xUf . Antes, porém, vale destacar o seguinte: embora os qubits de entrada |x

Image

Todavia, isso não esclarece nada sobre a reversibilidade. Para melhorar esse cenário, vamos ainda pensar em tudo o que pode acontecer com f(x) e calcular, para cada caso, o ket Image que ficou "mal resolvido" nas evoluções anteriores.

No caso de f ser contínua, há duas possibilidades: (i) f(0)=f(1)=0 e (ii) f(0)=f(1)=1. Esses são casos mais interessantes pois mostram que saber apenas o valor de f (0 no caso (i) e 1 no caso (ii)), não determina o valor de x (que pode ser 0 ou 1, indistintamente). Assumindo cada um desses casos, as evoluções anteriores se reduzem a

Image

Para cada tabela, nunca há dois resultados iguais do lado direito da seta, logo, cada saída corresponde a uma, e somente uma, entrada. Disto fica claro que, conhecendo-se a saída, pode-se descobrir inequivocamente a entrada, ou seja, a dinâmica Uf, definida na equação (1), é reversível mesmo quando a função f não é!!

No caso de f ser balanceada, há duas outras possibilidades: (iii) f(0)=0 e f(1)=1; e (iv) f(0)=1 e f(1)=0. Fica para o leitor verificar que as mesmas conclusões tiradas nos casos (i) e (ii) continuam valendo, porém agora o resultado é menos surpreendente porque que as próprias funções f já são reversíveis.

Depois de verificar todos os casos, você vai estar convencido de que o análogo quântico da caixa preta é muito bem descrito por Uf (e vamos assumir que, assim como no caso clássico, o processamento quântico leva 24 hs para terminar, contados a partir da entrada dos estados). Além disso, pode-se mostrar que se nos restringirmos a entrar somente com estados não superpostos, de nada vai ter adiantado toda essa generalização, pois ainda não conseguiremos resolver o problema em menos de 48 horas. Enfim, já que nos esforçamos tanto para construir essa "Caixa Preta Quântica", vamos ver o que ela tem que a primeira não tinha.


3.2 Usando a "Caixa Preta Quântica"

Basicamente, o que podemos fazer agora (e não podíamos antes) é entrar |x

Image

Agora, basta substituir esses estados no lado direito da equação (1). Façamos isso passo a passo, começando com a substituição do estado |y

Image

Como f(x) só pode ser 0 ou 1, Image, o que simplifica a primeira soma binária. Além disso, o fator comum Image pode ser colocado em evidência, levando o estado acima à forma

Image

Note ainda que, se f(x) = 0, os colchetes resultam em [|0f(x) = 1, os colchetes resultam em −[|0f(x) (|0Uf, com aquele |y

Image

Resta ainda substituir o estado |x

Image

É claro que todas essas etapas são meras conveniências matemáticas, objetivando uma melhor compreensão do caminho abstrato que leva ao resultado real (obtido experimentalmente). Porém, na prática, a caixa preta não substitui primeiro um estado e depois o outro, e também ela não precisa se preocupar em simplificar as expressões (afinal, quem disse que ela precisa de expressões?!). No mundo real, o resultado simplesmente "acontece" depois de 24 hs que alimentamos a caixa.

As linhas matemáticas acima são abstrações lógicas com o único compromisso de conduzir ao resultado correto. Se o caminho que a natureza percorre é o mesmo caminho que mostramos matematicamente, realmente não sabemos (mas é extremamente provável que não seja); tudo que sabemos é que a matemática vem se mostrando uma excelente ferramenta para chegar a resultados concordantes com os experimentos, e é por isso que continuamos a usá-la. Há muito para se dizer sobre essa "inexplicável eficiência da matemática nas ciências naturais", mas isso é uma outra longa história... Para quem estiver interessado, a referência [3] é um excelente ponto de partida.

Voltemos à equação (3), há coisas fantásticas impressas nesse estado de duas "moedas". O estado da primeira "moeda" (termo entre colchetes) mostra que os valores de f(0) e f(1) estão simultaneamente calculados, aparecendo nos expoentes de (-1). Já o estado da segunda "moeda" (termo entre parêntesis), não tem nada a ver com a função f, portanto não nos preocuparemos com ele.

O fato de termos obtido f(0) e f(1) na expressão do estado da primeira "moeda" representa algo sem precedentes clássicos. Ao alimentarmos a caixa preta com estados superpostos, forçamo-la a calcular f(0) e f(1) de uma só vez – um fenômeno conhecido como "Paralelismo Quântico" – devido a associação natural com a computação paralela clássica (vários processadores dividindo entre si a responsabilidade de realizar partes distintas de uma mesma tarefa, concluindo-a assim mais rapidamente).

Porém, há ainda um problema sobre esse estado. Embora seja aparente que a função foi calculada simultaneamente em 0 e em 1, a equação (3) não é um objeto real. Trata-se ainda de uma linha de argumentação matemática que não se manifesta empiricamente. O objeto fisicamente significante (real), é o resultado de uma medida realizada sobre um estado como este. Mas, como vimos no terceiro postulado, quando medimos um estado de superposição, obtemos um auto-estado ou outro, nunca a superposição.

Trocando em miúdos, não vamos conseguir acessar toda a informação tão claramente impressa na equação (3). Isso, simplesmente porque essa equação só existe para nós e para a nossa matemática, e como dissemos, a natureza não deve seguir a nossa linha de raciocínio lógico.

Mas nem tudo está perdido, ainda podemos fazer um "remendo" ao estado da equação (3), tal que obtenhamos ainda um outro objeto matemático abstrato, mas dessa vez, medindo-o (transformando-o então em algo fisicamente concreto), vamos conseguir extrair a informação que procurávamos.

O "remendo" é mais uma vez operar uma certa dinâmica ao estado da primeira "moeda", deixando inalterado o estado da segunda. Essa dinâmica (porta lógica de Hadamard), é expressa por uma nova matriz unitária, mas vamos aqui apresentá-la usando a mesma notação que usamos para Uf

Image

Introduzindo-a na equação (3), resulta

Image

E colocando em evidências os kets |0

Image

em que A e B são os seguintes números

Image

Veja que resultado incrível acabamos de obter:

Se a função f for contínua, então vemos Image, levando o estado acima a forma

Image

Por outro lado, se a função f for balanceada, acontece que Image, resultando no estado

Image

Tanto num caso, quanto no outro, o estado da primeira "moeda" não é mais uma superposição, por isso uma medida quântica pode nos informar com certeza se temos "cara" ou "coroa". Assim, se o resultado da medida acusar o colapso para |0

Mesmo tendo concluído a apresentação do algoritmo, ainda há espaço para alguns esclarecimentos. Note que o sinal de A e B ficou indeterminado nos estados acima. Na verdade, o sinal está associado aos valores individuais de f(0) e f(1), mas o problema de Deutsch não exigia que descobríssemos esses valores (mas tão somente que disséssemos se eles eram iguais ou diferentes entre si).

Além disso, ainda que soubéssemos o sinal correto, esse figuraria como uma fase global para os estados, e fases assim podem ser suprimidas da expressão do estado, pois não levam a qualquer modificação sobre os resultados das medidas.

Em suma, o algoritmo de Deutsch não nos informa sobre os valores de f(0) e f(1) individualmente, mas mesmo assim é capaz de revelar se esses valores são iguais ou diferentes – um resultado que só a física quântica poderia nos dar.


4. Conclusões

Este texto encerra a primeira rodada de um total de três artigos. Em cada um deles busquei mostrar para o leitor não especializado alguns resultados e conceitos de grande importância na física quântica.

O que acabamos de ver, foi o primeiro algoritmo de uma especialização da teoria quântica, hoje chamada computação quântica. Neste algoritmo, Deutsch demonstrou, com um exemplo simples, que computadores quânticos têm ampliado o poder computacional dos computadores clássicos. De fato, isso era algo esperado, pois sendo a física clássica uma particularização da física quântica, os computadores clássicos também deveriam ser limitações dos computadores quânticos.

Mas convenhamos, embora o Algoritmo de Deutsch mostre algo extremamente novo sobre o que os computadores quânticos podem fazer, descobir se uma função é contínua ou balanceada em 1 dia (em vez de 2 dias) é, no mínimo, uma aplicação "sem graça". Contudo, isso nao é regra para outros algoritmos da computação quântica moderna. Há, por exemplo, um algoritmo de fatoração devido a Shor [4]. Este, demonstra que é possível fatorar qualquer número inteiro em um tempo exponencialmente mais curto do que o requerido pelos algoritmos clássicos de fatoração; isso pode significar uma redução de milhares de anos de processamento clássico para alguns dias (ou até horas) de processamento quântico!

Quem conhece o protocolo de criptografia RSA, entende as implicações disso; toda a segurança desse esquema se sustenta no fato de que, para os computadores clássicos, é muito difícil (leva muito tempo) fatorar números inteiros muito grandes. Logo, computadores quânticos rodando o algoritmo de Shor são uma ameaça ao RSA. Porém, há ainda muito a ser feito até que um computador quântico capaz de rodar o algoritmo de Shor para números inteiros muito grandes se torne uma realidade (alguns físicos nem acreditam que isso seja possível), mas o importante é que, até o presente momento, ninguém encontrou uma barreira fundamental para refutar esse sonho. Portanto, continuamos sonhando.

Vale ainda salientar que a quebra do RSA não tem nada a ver com a criptografia quântica. Para essa última, nem computadores quânticos são uma ameaça. Por isso, alguns dizem tratar-se de um esquema absolutamente seguro, inquebrável. Talvez essa seja uma sentença muito forte, e na referência [5] você pode entender o porque.

Enfim, esperamos que esses primeiros artigos tenham sido úteis para mostrar o valor da teoria quântica. Esta não é um amontoado de fórmulas e abstrações vãs, mas uma ciência preciosa, que nos ensina a lidar (à nossa forma), com um mundo imperceptível aos nossos sentidos, mas incontestavelmente real.

Se você se sente convencido disto, o convite está feito para seguirmos adiante. A idéia agora é estabelecer em terreno mais firme (e isso pode significar um pouco mais matemático), as bases da física quântica. A teoria pura, independente de aplicações, também é bastante bela. Eu espero poder deixar essa "beleza intrínseca" à vista de quem quiser apreciá-la nos próximos artigos.

REFERÊNCIAS

[1] J. Preskill, Physics 229: Advanced Mathematical Methods of Physics Quantum Computation and Information, http://www.theory.caltech.edu/people/preskill/ph229, California Institute of Technology (1998).

[2] M. A. Nielsen e I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press (2000).

[3] E. P. Wigner, The Unreasonable Effectiveness of Mathematics in the Natural Sciences, Communications in Pure and Applied Mathematics, vol. 13, No. I (Fevereiro 1960); edição online (http://www.dartmouth.edu/~matc/MathDrama/reading/Wigner.html).

[4] P. W. Shor, Polynomial time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26, 1484 (1997).

[5] M. A. Nielsen, What’s wrong with those quantum cryptosystems?, http://www.qinfo.org/people/nielsen/blog/archive/000124.html, postado em blog em 17 de Agosto de 2004.

Download do artigo

Este artigo encontra-se à disposição para download no formato PDF (117 Kb).

рулетка +в онлайн казино azartplayпанасоник официальный сайт интернет магазинлобановский александр видеоcrmэлектрорубанок ценазаземление ценаbroker mfx