Lista de Abreviaturas

IA inteligência artificial

DNA ácido desoxirribonucléico

fig. . figura

UCP unidade central de processamento

UPF unidade de ponto flutuante

PC computador pessoal

QCL quantum computer language

E/S estrada e saída

TABELA 2.1 –Usando o comando CNot para cópia 21

TABELA 2.2 –Usando o CNot como operação XOR.. 21

TABELA 3.1 – Bases encontradas no código genético. 27

TABELA 3.2 – Enzimas de restrição e DNAs virais. 29

TABELA 4.1 – Bases e autoestados correspondentes. 35

TABELA 4.2 –Pares e autoestados correspondentes. 35

TABELA 5.1 –Cores e autoestados correspondentes. 41

Resumo

A computação é algo que ocorre em dispositivos físicos. O presente texto estuda dois tipos de computação baseados em processos de existência física bem distintos: computação quântica e computação biológica.

A computação quântica baseia-se na física de partículas. Uma única partícula quântica pode representar uma quantidade muito grande de bits permitindo processamento de informação massivamente paralelo. Por outro lado, a computação biológica baseia-se na química orgânica usando moléculas de DNA para processar informação. Considerando que cada molécula de DNA pode tomar parte em uma computação isolada, um tubo de ensaio contendo uma quantidade enorme de moléculas pode ser um sistema computacional de processamento massivamente paralelo.

Por fim, considerando-se que tanto a computação quântica como a computação biológica são computações que transcorrem de forma massivamente paralela, pode-se traçar paralelos entre as mesmas.

Palavras-chaves: computação quântica, computação molecular, computação biológica.

Abstract

Computation is something that happens on physical devices. The present text studies two kinds of computation based on clear distinct physical processes: quantum computation and biological computation.

The quantum computation is based on physics of particles. Just one quantum particle can represent a large number of bits making it possible to process information on a massive parallel way. Biological computation is based on the organic chemistry using DNA molecules in order to process information. Considering that each DNA molecule can take part in one isolated computation, a test tube containing a large number of molecules can be a massive parallel computational processing system.

To finish, considering that quantum computation and biological computation are kinds of massive parallel computation, it is possible find many common properties on both kinds of computations.

Keywords: quantum computing, molecular computing, biologic computing.

1Introdução

1.1Máquina como Sistema Físico

A computação ocorre ao longo do espaço e do tempo[WIL 97]. Sendo assim, a questão sobre o que pode ser computado depende do que pode ser fisicamente construido[AHA 98]. Não adianta construir um formalismo lógico que represente uma máquina capaz de realizar computações se esta máquina não representa uma realidade física. Sendo assim, estudaremos física, química e biologia para inferir sobre novas formas de computação e suas aplicações para a inteligência artificial.

O primeiro cientista que observou que a mecânica quântica poderia ter significado computacional foi Richard Feynman. Feynman sugere que todo sistema físico pode ser simulado por um computador exatamente e sem ruído algum. Feynman sugere ainda que: (1) o espaço e o tempo são discretos e não contínuos; (2) o universo físico é baseado em mecânica quântica; (3) simular um sistema físico é simular um sistema quântico[FEY 82]. Supondo que para todo sistema físico existe uma computação equivalente, então todo sistema físico realiza uma computação.

David Deutsch propôs que máquinas usando mecânica quântica poderiam realizar computações eficientes para problemas que máquinas clássicas poderiam realizar somente de forma extremamente ineficiente[DEU 85].

1.2Assuntos Abordados

No capítulo 2, rompe-se com a entendimento clássico do mundo físico. Serão abordados aspectos como partículas deslocalizadas que de certa forma existem em diferentes pontos do espaço ao mesmo tempo e se apresentam em superposição de estados distintos. Para o leitor que nunca estudou física quântica, o capítulo 2 será no mínimo chocante. A física quântica nega a percepção do mundo observada na escala do que os olhos dos seres humanos podem observar.

Fazendo uso da física quântica, a computação quântica abre possibilidade para resolver problemas extremamente custosos em termos de CPU de forma rápida [BAR 96] [BER 93]. Por efeito de simplicidade, será abordado um simulador de máquina quântica e serão desenvolvidos algoritmos para a máquina quântica simulada. O autor do presente trabalho desenvolveu formas simples de executar funções lógicas na máquina quântica simulada.

No capítulo 3, defende-se a idéia de que a evolução biológica é um processo de otimização sobre a informação genética. Entendendo-se que a evolução da biologia é um processo de otimização e que a maior parte da história da reprodução na biologia é assexuada, ao contrário dos algoritmos genéticos, propõem-se o uso de um algoritmo evolutivo assexuado.

A evolução biológica escolheu as moléculas de DNA para armazenar e processar a informação genética. Em princípio, pode-se fazer computação ao nível de moléculas orgânicas e inorgânicas; porém, diversos dispositivos genéticos teóricos e tecnológicos já foram desenvolvidos pela biologia. Sendo assim, o modelo de computação molecular estudado aqui é baseado em moléculas de DNA. Os processos sobre a informação do DNA servirão como fonte de inspiração para construção de modelos de computação molecular.

É interessante observar o fato de que Richard Feynman é citato como visionário da computação molecular [ADL 94] e como visionário da computação quântica [SIM 94]. Conforme a conclusão, a computação quântica e a computação biológica são indicadas para resolver a mesma classe de problemas.

2Computação Quântica

2.1O Experimento das Duas Fendas

2.1.1Apresentação do Experimento

Estudaremos o experimento das duas fendas tendo em vista que ele proporcionará base matemática e teórica para o leitor entender princípios fundamentais da computação quântica. O experimento das duas fendas foi largamente estudado na bibliografia [PEN 89] [HAW 88] [HAL 94] e serve de porta de entrada para entendermos o comportamento do elétron, do fóton e de outras partículas.

O experimento das duas fendas pode ser descrito como segue: uma lâmpada monocromática emite fótons que incidem sobre uma placa totalmente opaca que possui duas fendas paralelas. Posteriormente à placa de duas fendas paralelas, encontra-se um anteparo onde pode-se observar a precipitação dos fótons que conseguem passar pelas fendas da placa intermediária. O experimento de uma fenda é idêntico ao experimento de duas fendas; porém, o experimento de uma fenda possui uma placa intermediária com somente uma fenda.

Conforme esperado, no anteparo que recebe os fótons que ultrapassam as duas fendas, em algumas regiões, observa-se que a quantidade de fótons que precipitam sobre o anteparo é o dobro da quantidade que encontramos quando somente existe uma fenda na placa intermediária (ver figuras 2.1 e 2.4). Porém, no experimento das duas fendas, de forma contrária à física clássica, observamos regiões que recebem menos fótons do que no experimento de uma fenda! Como?

FIGURA 2.1 – Experimento das duas fendas. Os pontoes escuros são os pontos onde os fótons precipitam. Observe as regiões claras horizontais onde encontramos interferência destrutiva.

2.1.2Interferência Destrutiva

Para o anteparo que recebe os fótons, as fendas são as fontes de fótons. A fonte monocromática garante que a freqüência de onda dos fótons seja a mesma. Observe que existem pontos no anteparo que estão a distâncias diferentes de cada uma das fendas. Sendo assim, existem pontos que receberão as ondas de luz com mesma freqüência em oposição de fase. Como pode ser visto na figuram 2.2, ondas de mesma freqüência em oposição de fase se anulam mutuamente. Essa soma de ondas de mesma freqüência em oposição de fase é chamada de interferência destrutiva. Em capítulos posteriores, serão apresentadas computações que se anulam por interferência destrutiva.

Ao contrário da interferência destrutiva, a interferência construtiva é a soma de ondas com a mesma freqüência e mesma fase. Podemos ver na figura 2.3 um exemplo de interferência construtiva. Assim como serão apresentadas computações que se interferem destrutivamente, serão apresentadas computações que se interferem construtivamente.

+

=

+

=

Baseando-se na física clássica, o leitor pode imaginar que se a lâmpada emitir apenas um fóton de cada vez, não teremos interferência destrutiva no anteparo. Experimentalmente, observa-se que mesmo emitindo um fóton de cada vez encontra-se interferência destrutiva[HAL 94]! Por que um único fóton sofre interferência destrutiva quando passa pela placa de duas fendas? Pode-se explicar esse fato tendo em vista que o mesmo fóton passa por todos os caminhos possíveis ao mesmo tempo enquanto se desloca! O fóton passa pelas duas fendas ao mesmo tempo e pode sofrer interferência destrutiva de si próprio! O mesmo fóton pode percorrer caminhos distantes de vários anos luz. Cada caminho que o fóton percorre é uma alternativa. O estado do fóton é função da superposição das suas alternativas [PEN 89].

O fato de que a mesma partícula pode existir ao mesmo tempo em lugares diferentes nega violentamente a intuição humana. Por que os sentidos humanos nunca evidenciaram que o mesmo corpo existe ao mesmo tempo em lugares diferentes? Roger Penrose [PEN 89] apresenta uma resposta: o nível quântico é o nível das moléculas, átomos, elétrons, fótons e partículas subatômicas. No nível quântico, o estado das partículas é descrito pela superposição de suas alternativas. Quando uma das alternativas desencadear a liberação de energia superior a um gráviton, apenas uma alternativa sobrevive enquanto que as outras alternativas desaparecem. A determinação da alternativa que sobreviverá é probabilística sendo que a probabilidade de sobrevivência de cada alternativa é o módulo quadrado de sua amplitude de probabilidade. Durante a propagação de sinais visuais, os nervos óticos do sistema nervoso humano liberam energias muito superiores a um gráviton. Sendo assim, a percepção humana de um evento destruirá a superposição de alternativas.

FIGURA 2.4 - Experimento de uma fenda. Os pontos escuros são os pontos onde os fótons precipitam. Não observa-se interferência destrutiva.

A percepção humana percebe apenas eventos de nível clássico ( não quântico ). Sendo assim, se queremos construir máquinas baseadas em mecânica quântica, elas deverão ficar isoladas da percepção humana ou qualquer outro evento que provoque geração de energia superior a um gráviton enquanto trabalham. A percepção humana ou outro tipo de medição deverá ser feito apenas ao final do trabalho da máquina quântica. No presente texto, entende-se por máquina quântica uma máquina que use mecânica quântica e que durante seu funcionamento apresente estados quânticos.

2.1.3O Estado Quântico

Para efeito de exemplo, imagina-se um sistema feito por uma caixa e uma bola sendo que a bola ou está dentro da caixa ou está fora da caixa. A bola não pode estar ao mesmo tempo dentro e fora da caixa. O conjunto de estados que a bola pode ter é “dentro da caixa” ou “fora da caixa”. Sendo assim, a bola pode estar em um de dois estados mutuamente exclusivos. Pode-se entender que o estado em que a bola está “dentro da caixa” é o estado zero (0) e que o estado em que a bola está “fora da caixa” é o estado um (1). Sendo assim, os estados 0 e 1 são mutuamente exclusivos. Os estados 0 e 1 são mutuamente exclusivos porque a física clássica a qual a bola esta presa não permite superposição dos estados “dentro da caixa” e “fora da caixa”.

Continuando o raciocínio do parágrafo anterior, substituindo a bola por um elétron, um elétron pode estar “dentro da caixa” e “fora da caixa” ao mesmo tempo. Sendo assim, o estado do elétron pode ser 0 e 1 ao mesmo tempo. O estado do elétron é uma superposição linear dos estados básicos (autoestados) 0 e 1. O estado quântico é o estado que partículas de nível quântico apresentam como superposição linear de estados básicos.

Anteriormente, observamos que a percepção humana destrói a superposição de alternativas ( autoestados ou estados básicos ) de uma partícula porque gera mais energia do que a energia de um gráviton. Chamaremos de medição o transporte de informação do nível quântico para o nível clássico. Durante a medição, a energia de um gráviton é superada. Sendo assim, a partícula perderá a superposição linear de autoestados. Durante a medição, a partícula quântica que é medida sofre uma transição de estado saindo da superposição linear de autoestados para remanescer em apenas um dos seus autoestados. Essa perda de superposição linear de autoestados é chamada de colapso do vetor de autoestados.

Voltando ao problema das duas fendas, vamos supor que existam medidores nas fendas para detectar a passagem dos fótons. Vamos supor ainda que um fóton é lançado da lâmpada por vez. Sabendo que eventualmente o mesmo fóton passa pelas duas fendas ao mesmo tempo, os detectores (medidores) deveriam detectar ao memo tempo a passagem do fóton pelas duas fendas. Isso não ocorre porque a medição destrói a superposição linear de autoestados. Sendo assim, os detectores de fótons das fendas serão disparados um a cada vez e a interferência destrutiva observada no anteparo desaparecerá [PEN 89]!

Suponha-se que a precipitação de um fóton proveniente da fenda A sobre o anteparo possua probabilidade p(a) e a precipitação de um fóton proveniente da fenda B possua probabilidade p(b). Na física clássica, poderíamos supor que a soma das probabilidades de dois eventos A e B é certamente maior que a probabilidade de cada um dos mesmos tal que:e . Onde fótons provenientes da fenda A e da fenda B em oposição de fase se anulam mutuamente, o experimento das duas fendas mostra um caso em que: p(a) > 0 e p(b) >0 e p(a) + p(b) = 0. De alguma forma, durante a interferência destrutiva, as probabilidades anulam-se mutuamente. Para entender essa estranha propriedade da mecânica quântica, estudaremos amplitudes de probabilidade mensuradas por números complexos.

2.1.4Amplitude de Probabilidade Complexa

A amplitude de probabilidade do estado de uma partícula quântica é um número complexo. Para entender melhor, voltando ao experimento das duas fendas, a probabilidade no nível clássico é o quadrado do módulo da amplitude de probabilidade. Vale lembrar que o módulo do número complexo z=x+iy é |z| = . Para efeito de exemplo, podemos calcular sobre uma partícula que possui amplitude de probabilidade para o estado K com valor de 0.3 + 0.4i ou (0.3 + 0.4i)|K> :

1. o módulo da amplitude de probabilidade é:

   

2. o quadrado do módulo da amplitude de probabilidade é 0.25. Isso significa que a partícula em medição possui uma probabilidade de ser medida no estado K de 0.25.

Assim como no nível clássico, onde o somatório das probabilidades não pode ultrapassar 1, em um sistema quântico, o somatório dos quadrados dos módulos das amplitudes de probabilidades não pode ultrapassar 1.

Módulos de amplitudes de probabilidade são sempre positivos; porém, amplitudes de probabilidade podem ser negativas. Voltando ao problema das duas fendas, supondo um ponto do anteparo em que a amplitude de probabilidade de um fóton precipitar proveniente da fenda A seja e a amplitude de probabilidade de o mesmo fóton precipitar sobre o anteparo proveniente da fenda B seja . Sendo assim, a soma das duas amplitudes de probabilidades é zero indicando interferência destrutiva. Por outro lado, o somatório dos quadrados dos módulos das amplitudes de probabilidades é 1.

2.2O Princípio da Computação Quântica

2.2.1Qubits ou Bits Quânticos

Por que estudar física quântica se queremos apenas construir e programar computadores? Os computadores existem físicamente no espaço e no tempo. Os computadores fazem o que a física permite. O estado de cada bit de nossos computadores corresponde a um estado físico de nossa máquina. Tendo entendido o comportamento dos estados quânticos poderemos construir computadores que processam bits quânticos.

Um bit clássico pode estar somente em um de dois estados básicos mutuamente exclusivos. Ao contrário, um bit quântico pode estar em uma superposição de estados básicos. Voltando ao sistema em que o elétron pode estar dentro e fora da caixa ao mesmo tempo, supondo que o elétron tem uma amplitude de probabilidade Z de estar dentro da caixa ( estado zero ou |0> ) e uma amplitude de probabilidade W de estar fora da caixa ( estado um ou |1> ), descreveremos o estado do elétron na forma como segue: Z|0> + W|1> que deve ser entendido como superposição linear dos autoestados zero e um com amplitudes de probabilidade Z e W respectivamente. Vale observar que |Z|² + |W|² = 1. O estado de um bit quântico é a superposição linear de seus autoestados.

O estado de um conjunto de dois bits quânticos pode ser descrito pela seguinte superposição linear de autoestados: x|00> + y|01> + z|10> + w|11> em que |x|² + |y|² + |z|² + |w|² =1. Apenas por lembrete, x,y,z e w são amplitudes de probabilidade complexas. Bits quânticos são chamados de qubits. Um conjunto de N qubits pode apresentar um estado que é superposição linear de 2^N autoestados. De certa forma, um conjunto de N qubits pode estar em 2^N estados diferentes ao mesmo tempo.

O estado dos bits de uma máquina clássica ou quântica deve ter uma correspondência física. Nenhuma das diversas fontes de consultas propôs a construção de máquinas quânticas baseadas em elétrons dentro ou fora de caixas. Por outro lado, podemos encontrar na bibliografia propostas para construção de máquinas quânticas em que o estado dos qubits corresponde ao spin de elétrons. O spin de um elétron pode ser -1/2 ou +1/2. Sendo assim, o spin de um elétron pode ser descrito pela superposição de autoestados: c₁| -1/2 > + c₂| +1/2 >. Substituindo-se -1/2 e +1/2 por 0 e 1 respectivamente, encontra-se: c₁|0> + c₂|1> sendo que c₁ e c₂ são amplitudes de probabilidade.

2.2.2Notação

O bit quântico ou qubit é representado por um sistema quântico de dois estados que é constituído por apenas uma partícula. Um sistema quântico de dois estados é descrito por um vetor unitário complexo no espaço de Hilbert C². O espaço de Hilbert é um espaço vetorial complexo. Os dois estados do sistema quântico são representados por: |0> e |1>. O estado |0> é representado pelo vetor complexo (1,0) em C² enquanto que o estado |1> é representado pelo vetor (0,1). Os vetores (1,0) e (0,1) ou |0> e |1> constituem a base ortogonal no espaço de Hilbert[AHA 98].

Apenas para efeito de exemplo, abordaremos um registrador quântico de 3 qubits. Esse registrador é representado pela superposição linear de seus oito autoestados como segue:

c₁|000> + c₂|001> + c₃|010> + c₄|011> + c₅|100> +c₆|101> + c₇|110> + c₈|111>.

Para efeito de notação, consideremos: x₁ = |000>, x₂ = |001>, x₃ = |010> ... x₈ = |111>. Lembrando que c₁..c₈ são amplitudes de probabilidade, =1. O estado de um registrador quântico de n qubits é a superposição linear de 2ⁿ autoestados. Uma superposição uniforme de autoestados é uma superposição linear de estados onde todos os autoestados apresentam a mesma amplitude de probabilidade. A superposição uniforme de autoestados pode ser descrita como:

Uma operação f feita sobre um registrador quântico que apresenta superposição uniforme de autoestados pode ser descrita como:

Apenas para efeito de exemplo, apresentaremos a operação de incremento f:

f (c₁ |000> + c₂|001> + c₃|101>) => c₁ |001> + c₂ |010> + c₃ |110> .

No exemplo anterior, de certa forma, foram feitos três incrementos em paralelo usando apenas um único registrador quântico de três qubits.

Por fim, abordaremos um exemplo com o operador de negação NOT [AHA 98]:

NOT |0> = |1>

NOT |1> = |0>

NOT( c₁|0> + c₂|1> ) = c₁|1> + c₂|0>

NOT( c₁|001> + c₂|111> ) = c₁|110> + c₂|000>

2.2.3Correlação

A correlação ( do inglês, entanglement ) de estados surge naturalmente entre a interação entre partículas. No presente parágrafo, vamos supor que o estado inicial de duas partículas correlacionadas é o que segue: c₁|00> + c₂|11>. Vamos supor ainda que resulta da medição da primeira partícula o estado |0>. Por estarem correlacionadas as duas partículas, com a medição da primeira partícula, o vetor de estados do sistema composto pelas duas partículas entra em colapso caindo no estado |00>. Sendo assim, a medição sobre uma partícula de um sistema de partículas correlacionadas provoca o colapso de estado de todo o sistema de partículas imediatamente mesmo que as partículas estejam separadas por vários anos luz.

Considerando o exemplo do parágrafo anterior, se, por acaso, a medição da primeira partícula resultasse em |1>, então o estado da segunda cairia obrigatoriamente no estado |1>. A segunda partícula simplesmente não poderia ser fisicamente medida no estado |0> tendo em vista que não existe um estado c₃|10> inicial.

A informação quântica é extremamente frágil. É impossível impedir iterações entre um sistema quântico e o ambiente em que está inserido. Essa iteração provoca perda na natureza quântica em um processo chamado de decoerência [AHA 98]. Para manter a computação coerente, é necessário isolar os registradores quânticos impedindo que else se correlacionem com o ambiente [OME 88]. A decoerência é uma questão de tempo. Quanto maior for o espaço de tempo envolvido, maiores serão as chances de verificarmos decoerência.

Para manter a computação coerente, os registradores quânticos não podem dissipar calor. A dissipação de calor provocaria a correlação entre o registrador quântico e o ambiente causando decoerência. Sendo assim, a entropia do sistema de computação quântica não pode crescer. Lembrando que a entropia é incrementada nos processos irreversíveis, a computação quântica é reversível e adiabática [OME 88].

2.2.4 Interações Locais e Não Locais

As interações locais são as interações que estamos acostumados na física clássica e na física relativista. Uma interação local é uma interação que envolve contato direto ou uma interação com um meio intermediário que provoca interação por contato direto com um meio físico final. As interações de contato direto são as interações que estamos acostumados nas nossas vidas. A gravidade, a percepção de ondas eletromagnéticas pelos nossos aparelhos de televisão e troca de calor entre corpos são exemplos de interações locais. As ondas eletromagnéticas se propagam no vácuo a velocidade da luz perdendo energia a medida que se afastam da fonte.

Interações locais não são interações que ocorrem entre corpos próximos. O emissor e receptor de uma mesma onda eletromagnética podem estar separados por vários anos luz sendo que o tempo de propagação do sinal entre o emissor e o receptor é necessariamente igual ou superior ao tempo de propagação da velocidade da luz no vácuo. As interações locais podem ser verificadas entre corpos separados por distâncias arbitrariamente grandes.

A força gravitacional é uma interação local porque é mediada por partículas chamadas grávitons que viajam entre elementos que gravitam. Assim como os fótons, os grávitons não podem viajar acima da velocidade da luz.

Considerando exclusivamente as interações locais, se dois eventos ocorrem a uma distância de espaço e tempo de forma que mesmo viajando a velocidade da luz o efeito de um evento não pode alcançar o outro, podemos afirmar que os eventos estão espacialmente separados ( do inglês, spacelike separated ).

De forma geral, podemos caracterizar as interações locais da forma como segue: (1) podem ser intermediadas por outras entidades como partículas ou campos; (2) não se propagam mais rápido que a velocidade da luz; (3) a sua influência diminui com a distância.

As forças eletromagnéticas, gravitacionais, nucleares fortes e fracas são responsáveis por interações locais. Sendo assim, todas as quatro forças conhecidas do universo produzem somente interações locais. De onde vêm as interações não locais?

Nos parágrafos anteriores não discutimos o colapso do vetor de autoestados. Durante a medição, o vetor de autoestados de um sistema de partículas correlacionadas sofre o colapso de autoestados. O colapso do vetor de estados não envolve força de nenhum tipo. Lembrando que o colapso do vetor de autoestados pode interferir em partículas correlacionadas divididas por diversos anos luz de forma imediata, podemos observar uma grande diferença entre interação que ocorre durante o colapso do vetor de auto estados e as interações provocadas pelas quatro forças físicas conhecidas. As interações provocadas pelas quatro forças do universo conhecidas dependem da velocidade de propagação luz enquanto que a interação provocada pelo colapso do vetor de autoestados não depende de propagação de sinais a velocidade da luz e nem de um meio conhecido para propagar seus sinais.

Não é fácil definir o que as interações não locais são. É mais fácil definir o que elas não são: (1) não são intermediadas por outras entidades; (2) não dependem da velocidade da luz; (3) a sua influência não diminui com a distância. O colapso do vetor de autoestados é um tipo de interação não local.

O presente tópico foi escrito com base na seção 9.3 do livro Explorations in Quantum Computing [WIL 97].

2.3Quantum Computing Language

2.3.1Introdução

Por que simular computadores quânticos em máquinas convencionais? Simulando computadores quânticos poderemos ter uma idéia das dificuldades a serem enfrentadas no desenvolvimento de novos algoritmos destinados a computadores quânticos. É interessante observar que antes do primeiro computador quântico ser construído, teremos diversos algoritmos específicos para computadores quânticos rodando em simulação. Além disso, através de simulações, teremos uma idéia muito aproximada do que poderemos esperar ao construir computadores quânticos.

Em geral, vale a pena simular um sistema quando a simulação é imensamente menos custosa e ainda assim permite estudarmos os aspectos de interesse do sistema real. Esse é exatamente o motivo pelo qual trabalharemos com simuladores de máquinas quânticas.

Existem diversos pacotes para simulação de computadores quânticos. No entendimento do autor do presente texto, os mais interessantes são Open Qubit [OPE 2000] e QCL ( Quantum Computer Language)[OME 88][OME 2000]. A maior desvantagem do Open Qubit frente ao QCL é a sua dificuldade de operação tendo em vista que o Open Qubit é uma biblioteca C. Sendo assim, Open Qubit exige muito de seu usuário para implementar seus primeiros programas simples. Por ser interpretada, a linguagem QCL permite que seu usuário entre com comandos e funções de forma iterativa e ainda verifique o estado de cada registrador da máquina virtual. O QCL é ideal para o ensino de linguagem de programação de computador quântico.

2.3.2Introdução à linguagem QCL

O QCL prevê uma máquina híbrida composta por uma máquina clássica semelhante aos bem conhecidos PCs e uma máquina de estados quânticos. O usuário se comunica somente com a máquina clássica. A máquina clássica requisita operações e medições à máquina de estados quânticos. Traçando uma analogia, os PCs modernos possuem unidades de ponto flutuante (UPF) integradas à CPU. Os comandos de salto e controle não pertencem a UPF. A UPF apenas realiza as instruções relativas as operações de ponto flutuante. Da mesma forma, o QCL prevê uma máquina clássica que realiza os testes, desvios, E/S e possui registradores convencionais em contato com uma máquina de estados quânticos que realiza as operações quânticas.

O presente texto não é um tutorial de QCL. Se o leitor desejar aprofundar-se na linguagem QCL existe excelente bibliografia [OME 88] [OME 2000] sobre o assunto.

Para efeito de exemplo, consideraremos o programa QCL que segue:

int Teste() {

int i; // aloca uma variável inteira na máquina clássica

int d; // aloca uma variável inteira na máquina clássica

qureg x[2]; // aloca um registrador quântico de dois bits na // máquina quântica

Mix(x); // força a superposição linear uniforme de // autoestados no registrador quântico x.

for i=1 to 5 { // o controle do laço é feito na máquina clássica

Not(x); // nega o conteúdo do registrador quântico x na // máquina quântica

}

measure x,d; // mede o valor na máquina quântica do registrador // x e envia o resultado a máquina clássica

// na máquina clássica, armazena o valor recebido em d.

return d; // retorna o valor da variável d da máquina clássica

No exemplo acima, observe que os comandos destinados a máquina clássica e a máquina quântica aparecem intercalados. A função Teste nega cinco vezes o conteúdo do registrador quântico x. Isso foi feito apenas para mostrar que o controle de laço é executado na máquina clássica enquanto que as operações quânticas são executadas na máquina quântica.

Quando o autor do presente texto começou a estudar QCL, não existia nem mesmo a operação lógica quântica AND. Como veremos mais adiante, a operação AND não é reversível e incrementa a entropia do sistema. Sendo assim, a operação quântica AND implementada pelo autor do presente texto difere ligeiramente da operação lógica AND de uma máquina clássica para permitir a reversibilidade e impedir o incremento da entropia. Diversos algoritmos que serão apresentados aqui foram implementados pelo autor do presente trabalho.

2.3.3Primeiros Passos em QCL

No presente tópico, serão estudados os aspectos mais básicos da linguagem QCL de interesse para a computação quântica. QCL possui diversos comandos existentes nas linguagens procedurais mais conhecidas; porém, deseja-se aprofundar a análise somente nos comandos úteis para a computação quântica. No presente tópico, serão estudados os comandos Mix, Not, CNot, qureg e measure. Será feito uso extensivo de exemplos para esclarecer a funcionalidade dos comandos aqui apresentados.

Para carregar o programa digitaremos a linha de comando como segue:

wind:~/qcl-0.4.0-bin$ qcl-static –bits=4

[0/4] 1 |0000>

qcl>

A opção -bits=4 especifica que queremos trabalhar com uma máquina que possui quatro qubits no total. A mensagem [0/4] significa que zero dos quatro qubits foram alocados. Ao lado, 1|0000> significa que o autoestado da máquina |0000> apresenta amplitude de probabilidade um. O prompt qcl> indica que já podemos entrar com novos comandos. No próximo passo, alocaremos um registrador quântico de dois qubits.

qcl> qureg x[2]

qcl> dump

: STATE: 2 / 4 qubits allocated, 2 / 4 qubits free

1 |0000>

O comando qureg x[2] aloca o registrador x com dois qubits. O comando dump devolve o estado da máquina. Como pode ser observado na saída do comando dump, 2 / 4 ou dois dos quatro qubits estão alocados e os outros 2 / 4 ou dois dos quatro qubits estão livres. Por fim, vemos que a máquina continua no estado 1|0000>. No próximo passo, começaremos a trabalhar com registradores quânticos:

qcl> Mix(x)

[2/4] 0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0011>

Os dois qubits mais a direita de cada autoestado correspondem aos dois qubits do registrador x. O comando Mix força a superposição linear uniforme de autoestados no registrador que é passado como argumento quando este está no estado em que todos os qubits estão em zero. Observe que todos os autoestados apresentam 0.5 como amplitude de probabilidade. Lembrando que a probabilidade de medição de um autoestado é o módulo quadrado de sua amplitude de probabilidade, a probabilidade de cada um dos quatro autoestados é |0.5|² = 0.25. No próximo passo, alocaremos mais um registrador.

qcl> qureg y[1]

qcl> dump

: STATE: 3 / 4 qubits allocated, 1 / 4 qubits free

0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0011>

O comando qureg y[1] aloca o registrador quântico y com 1 qubit. O comando dump nos revela que três dos quatro bits quânticos estão alocados. Os dois qubits mais a direita de cada autoestado correspondem aos dois qubits do registrador x e o terceiro bit da direita para esquerda é o registrador y. No próximo passo, executaremos nossa primeira função lógica.

qcl> CNot(y,x)

[3/4] 0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0111>

O comando CNot(y,x) nega os autoestados y correspondentes aos autoestados em que x possui seus bits todos em 1. O comando CNot é um comando de negação controlada. A semântica do comando CNot é baseada na semântica da porta lógica quântica proposta por Toffoli [BAR 95] chamada de Controlled Not ou simplesmente CNot. Observe que se podemos garantir que o registrador y começa em zero, CNot apresenta a mesma semântica da porta lógica AND em que y é a saída e x é a entrada. No exemplo anterior, observe que foram feitas quatro operações em paralelo. Para facilitar o entendimento, os bits referentes ao registrador y foram grafados em negrito. Se negarmos o resultado encontrado em y, teremos o resultado da operação x[0] NAND x[1] em y:

qcl> Not(y)

[3/4] 0.5 |0100> + 0.5 |0110> + 0.5 |0101> + 0.5 |0011>

Novamente, os bits referentes ao registrador y foram grafados em negrito. A importância do exemplo anterior deve-se ao fato de que qualquer função lógica pode ser descrita como uma composição de NANDs. No passo seguinte, declararemos uma variável inteira d e mediremos o estado de x. Vale lembrar que somente um autoestado sobrevive após a medição.

qcl> int d

qcl> measure x,d

[3/4] 1 |0011>

qcl> print d

: 3

O comando measure x,d mede x e carrega a variável d com o valor medido. O valor do autoestado de x que será medido depende da probabilidade de cada autoestado. Se x estiver em superposição linear uniforme de autoestados, cada autoestado tem a mesma probabilidade de ser encontrado. Sendo assim, poderemos encontrar 0,1,2 ou 3 com a mesma probabilidade. No exemplo anterior, o autoestado medido foi |11>; porém, qualquer outro autoestado de x poderia ter sido medido com a mesma probabilidade.

2.3.4Gerando Números Realmente Aleatórios

Considerando que a física envolvida na medição é não determinista, podemos construir uma função que gera zero ou um de forma aleatória.

int BitAleatorio() {

int d; // aloca uma variável inteira na máquina clássica.

qureg x[1]; // aloca um registrador quântico de um bit na máquina

// quântica.

Mix(x); // força a superposição linear uniforme de

// autoestados no registrador quântico x.

// x = c₁|0> + c₂|1> ; c₁ = c_{2 .}

measure x,d; // mede o valor na máquina quântica do registrador x e //envia o resultado à máquina clássica

// na máquina clássica, armazena o valor recebido em d.

return d; // retorna o valor da variável d da máquina clássica .

}

2.3.5XOR em QCL

Foi estudado anteriormente como fazer a operação lógica NAND em QCL. No presente tópico, apenas para efeito de exemplo, será estudado como fazer a operação lógica XOR em QCL. Sendo assim, primeiramente, serão alocados os registradores quânticos:

qcl> qureg x[1]

qcl> qureg y[1]

qcl> qureg z[1]

Com os três comandos acima, foram alocados os registradores quânticos x,y e z com um qubit cada. No próximo passo, a superposição linear uniforme de autoestados para todas as combinações possíveis de x e y será forçada.

qcl> Mix(x&y)

[3/4] 0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0011>

Cada autoestado acima tem a seguinte notação: |0zyx>. Conforme mostra a tabela que segue, o comando CNot será usado para copiar o conteúdo de x em z.

TABELA 2.1 – Usando o comando CNot para cópia.

Para copiar o conteúdo de x em z, será usado o comando CNot(z,x):

qcl> CNot(z,x)

[3/4] 0.5 |0000> + 0.5 |0010> + 0.5 |0101> + 0.5 |0111>

Os bits referentes a z e x foram grifados em negrito. Supondo que x e y sejam registradores quânticos unários, a operação lógica CNot(x,y) é idêntica à operação x:= x xor y. Esta propriedade pode ser observada na tabela que segue.

TABELA 2.2 – Usando o CNot como operação XOR.

Sendo assim, o comando que segue concluirá o exemplo.

qcl> CNot(z,y)

[3/4] 0.5 |0000> + 0.5 |0110> + 0.5 |0101> + 0.5 |0011>

O conteúdo de z foi grifado em negrito. Pode-se verificar que z = x xor y.

2.3.6Teste de Igualdade

Por si só, a operação lógica xor é um teste que retorna 1 quando seus operandos são diferentes. Sendo assim, a operação lógica xor é um teste de diferença. Para testar se dois operandos são iguais, faremos z = not ( x xor y ). Apenas por experiência, segue a seqüência de comandos QCL para encontrar z = not ( x xor y ):

qcl> qureg x[1]

qcl> qureg y[1]

qcl> qureg z[1]

qcl> Mix(x&y)

[3/4] 0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0011>

qcl> CNot(z,x)

[3/4] 0.5 |0000> + 0.5 |0010> + 0.5 |0101> + 0.5 |0111>

qcl> CNot(z,y)

[3/4] 0.5 |0000> + 0.5 |0110> + 0.5 |0101> + 0.5 |0011>

qcl> Not(z)

[3/4] 0.5 |0100> + 0.5 |0010> + 0.5 |0001> + 0.5 |0111>

Por conveniência, o conteúdo de z foi grafado em negrito. Observe que z está no estado 1 quando x e y são iguais.

Pode-se observar que ausência de funções do tipo AND e OR dificulta a programação de funções lógicas em QCL. Por esse motivo, foi implementada a biblioteca boolean.qcl que possui as funções quAnd, quNand, quOr e quNor. Esta biblioteca é apresentada no Anexo 1.

No anexo 2, encontra-se uma implementação feita em QCL pelo autor do presente trabalho para resolver o problema np-completo SAT. Nessa implementação, as funções lógicas fazem uso da biblioteca boolean.qcl.

2.3.7Informação e Qubits

Quantos bits um único qubit pode representar? Em princípio, infinitos. O número de bits que um qubit representa depende do número de qubits e de que forma a que este qubit está relacionado. Supondo que os autoestados são representados na forma |0dee> em que d é o dado e ee é o endereço, aborda-se o seguinte exemplo:

qcl> dump

: STATE: 3 / 4 qubits allocated, 1 / 4 qubits free

0.5 |0000> + 0.5 |0110> + 0.5 |0001> + 0.5 |0111>

No exemplo acima, encontramos o dado 0 para os endereços 00 e 01 e o dado 1 para os endereços 10 e 11. No exemplo acima, representa-se 4 bits dispondo de 3 qubits. Supondo que dispõe-se de 9 qubits na forma |0deeeeeeee> em que d é o dado e eeeeeeee é o endereço, tem-se 8 qubits para o endereço resultando em 2⁸ ou 256 endereços possíveis. Continuando o raciocínio, podemos representar 256 bits com apenas 9 qubits. Usando-se esse raciocínio, pode-se concluir que com n qubits podemos representar 2^n-1 bits. Sendo assim, com 21 qubits pode-se representar 2^21-1 bits ou 1 megabit ou 128 kbytes.

2.3.8Medindo a Solução Desejada

Dado um registrador quântico em superposição linear de autoestados, como medir o autoestado desejado? No presente tópico, será apresentada uma técnica para incrementar o módulo da amplitude de probabilidade dos autoestados de maior interesse. Sendo assim, obteremos maior probabilidade de medir o autoestado desejado ao final da computação quântica. A técnica apresentada aqui é uma variação do algoritmo de Grover [GRO 96].

No diretório onde o simulador QCL é instalado, encontra-se o diretório lib. No diretório lib encontra-se o arquivo grover.qcl que possui a função diffuse. A função diffuse será usada juntamente com o comando CPhase para amplificar a amplitude de probabilidade do autoestado desejado.

Lembrando que a amplitude de probabilidade é um número complexo, ela pode ser descrita por um ponto no plano. O comando CPhase realiza uma rotação condicionada na amplitude de probabilidade possuindo dois parâmetros: a ângulo de rotação e o registrador que determina a condição. O comando CPhase rotaciona a amplitude de probabilidade para todo autoestado que apresenta o registrador que determina a condição com bits todos em 1. Segue o exemplo de uso do comando CPhase:

qcl1> include "grover.qcl"

qcl1> qureg x[3]

qcl1> Mix(x)

[3/6] 0.353553 |000000> + 0.353553 |000100> + 0.353553 |000010> +

0.353553 |000110> + 0.353553 |000001> + 0.353553 |000101> +

0.353553 |000011> + 0.353553 |000111>

qcl1> CPhase(pi,x)

[3/6] 0.353553 |000000> + 0.353553 |000100> + 0.353553 |000010> +

0.353553 |000110> + 0.353553 |000001> + 0.353553 |000101> +

0.353553 |000011> + -0.353553 |000111>

Observe que no exemplo acima a amplitude de probabilidade do autoestado |000111> sofreu rotação de 180 graus. Usando a função diffuse, amplifica-se a amplitude de probabilidade dos autoestados que apresentam amplitude de probabilidade negada.

qcl1> diffuse(x)

[3/6] -0.176777 |000000> + -0.176777 |000100> + -0.176777 |000010> +

-0.176777 |000110> + -0.176777 |000001> + -0.176777 |000101> +

-0.176777 |000011> + -0.883883 |000111>

No exemplo acima, observe que o módulo da amplitude de probabilidade do autoestado |000111> sofreu um grande incremento.

3Computação Biológica

3.1Evolução Biológica

3.1.1Introdução

A biologia tem sido fonte de inspiração para a inteligência artificial notadamente nas áreas de vida artificial, redes neurais e algoritmos evolutivos. A evolução da biologia é um processo de otimização natural dos seres vivos em que os melhor adaptados sobrevivem.

A forma como a vida processa informação em seu código genético é fonte de inspiração para novas formas de computação baseadas em processamento de moléculas de DNA. O estudo dos processos genéticos é útil para o estudo da computação biológica.

3.1.2 Resumo da Evolução da Vida na Terra

Primeiros milhões de anos após a formação da Terra: os relâmpagos e a luz ultravioleta do sol estavam decompondo as moléculas da atmosfera primitiva rica em hidrogênio. Novas moléculas de complexidade gradualmente maior combinavam-se na atmosfera. Os produtos da química atmosférica precipitavam-se no oceano que conseqüentemente se tornava quimicamente mais complexo [SAG 83].O Jardim do Éden molecular estava pronto. Caoticamente, a primeira molécula capaz de fazer cópias grosseiras de si mesma é formada. Toda uma estrutura de herança e evolução e toda atividade biológica que tivemos contato está baseada em uma molécula ancestral do ácido desoxirribonucléico, o DNA. Molécula principal da vida na Terra, o DNA tem a forma de uma escada em que cada degrau pode conter um de quatro tipos de nucleotídeos diferentes que são as quatro letras do alfabeto genético. Considerando que são necessários dois bits para representar uma de quatro alternativas possíveis ,cada letra do alfabeto genético carrega 2 bits de informação.

A vida é uma conseqüência da química orgânica. Na origem do universo e na origem da química, não foram definidas as regras da biologia. As regras da biologia emergem das regras da química. As regras do todo emergem das regras das partes. O comportamento do todo emerge do comportamento das partes. Considerando a química um sistema simples e a biologia um sistema complexo, o sistema complexo emerge do sistema simples. O aparecimento da vida é um exemplo de auto-organização.

No oceano primitivo não existiam predadores; existiam somente moléculas se duplicando. A evolução ao nível molecular seguia de forma implacável. Com o passar de milhões de anos, moléculas especializadas se agruparam formando as primeiras células primitivas [SAG 83].

A vida na Terra apareceu logo depois de sua formação. A Terra foi formada há 4.6 bilhões de anos atrás enquanto que a vida apareceu há 4 bilhões de anos. Considerando as dimensões de tempo, a vida apareceu pouco depois da formação da terra. Toda biologia da Terra possui código genético descrito na mesma cadeia de DNA com 4 nucleotídeos [SAG 83]. Seres humanos, árvores e bactérias são descritos pelo mesmo alfabeto genético. Darwin não poderia estar mais certo. O motivo pelo qual os organismos são diferentes está no fato de que suas instruções em seus códigos genéticos são diferentes ainda que seus alfabetos sejam os mesmos [SAG 77].

É interessante observar que o DNA é um sistema que armazena informação de forma digital. Por que a seleção natural escolheu um sistema de armazenamento de informação digital? Para efeito de cópia ou replicação, a informação digital é regenerada enquanto que a informação analógica é amplificada. Quando a informação analógica é replicada, os ruídos ou erros presentes na informação analógica são igualmente replicados ou até amplificados. De forma contrária, durante replicação, a informação digital pode ser regenerada e os ruídos podem ser filtrados. Sendo assim, a informação digital é mais resistente contra erros se queremos transportá-la através do espaço ou do tempo.

Os segredos da evolução são mutação, tempo, replicação e morte. A mutação é uma alteração de um nucleotídeo que é passado para a geração seguinte. A maior parte das mutações são desfavoráveis para o indivíduo enquanto que uma pequeníssima parte torna o indivíduo melhor adaptado melhorando suas chances de propagar seu DNA. A morte é responsável pela eliminação dos indivíduos menos adaptados contribuindo para a evolução. Considerando que o código genético é digital, a mutação também ocorre de forma digital.

Para Manfred Eigen [EIG 97], todo sistema que possua auto-replicação, mutação e metabolismo está sujeito a evolução. Sem a auto-replicação, a informação seria perdida a cada geração. Sem a mutação, a informação seria inalterável e não poderia emergir. Sem o metabolismo, o sistema cairia em equilíbrio significando a morte do ser vivo.

De forma mais abstrata, se queremos implementar um algoritmo de otimização, basta implementar a replicação e mutação de soluções e alguma pressão seletiva que selecione as soluções de maior interesse. A evolução é um processo de otimização. O ambiente em que o seres vivos habitam impõem uma pressão que seleciona os mais adaptados naturalmente. A pressão seletiva implicará na evolução das soluções.

Nenhum dos segredos da vida dependem de um determinado substrato. Algoritmos e heurísticas não dependem de substrato. Considerando que a vida é um processo algorítmico ou heurístico, então a vida não depende de substrato. Para que a vida evolua, basta que exista reprodução, mutação, morte e seleção ao longo do tempo e do espaço. Todos os segredos da vida estão espalhados pelo universo. Dentro de computadores podemos facilmente construir ambientes com os segredos da vida. É importante observar que a vida não depende de espaço e tempo contínuos tendo em vista que a continuidade não é necessária para a reprodução, morte e mutação.

Moléculas com funções especializadas formaram colônias que resultaram nas primeiras células. Há 3 bilhões de anos, os primeiros seres multicelulares evoluiram a partir de células vegetais. É importante observar que árvores e seres humanos são colônias de células. Cada célula também é uma colônia de seres vivos descendentes dos seres vivos que existiram no mar primitivo da Terra. O fato de que as mitocôndrias tenham seu próprio DNA sugere fortemente que elas sejam descendentes de organismos independentes do mar primitivo da Terra. Somos uma colônia de células em que cada célula também é uma colônia.

Há 2 bilhões de anos atrás, nas mesmas regras que ditam a evolução da vida, o sexo apareceu. O sexo é a troca de código genético entre organismos independentes. Com o sexo, segmentos de DNA podem ser trocados tornando o processo evolutivo tremendamente mais rápido. Antes do sexo, a única maneira de evoluir era por mutação. Os seres que podem trocar DNA tem a possibilidade de evoluir muito mais rápido do que aqueles que tem que esperar por uma mutação fortuita. Podemos afirmar que um dos segredos da evolução é o sexo. Não é por acaso que seres humanos apresentam grande interesse por troca de segmentos de código genético [SAG 77].

Há 1 bilhão de anos atrás, a atmosfera da Terra foi alterada de forma irreversível. Os vegetais da Terra fabricaram quantidades enormes de oxigênio molecular que foi lançado na atmosfera. As células vegetais possuem cloroplastos que são responsáveis por converter luz solar, água e dióxido de carbono em carboidratos e oxigênio. A atmosfera perdia suas características primitivas como a presença abundante de hidrogênio. O oxigênio, molécula altamente reativa com diversas moléculas orgânicas, foi um gás letal para a maior parte dos seres vivos desprotegidos [SAG 83].

Há 600 milhões de anos, o domínio das algas sobre o planeta foi perdido na revolução cambriana para uma enorme diversidade de novos e mais complexos seres vivos. Até então, a evolução ocorria principalmente no nível de estrutura celular e bioquímica. Pouco depois, apareceu o primeiro peixe e o primeiro vertebrado. Plantas migraram para a terra e a evolução seguiu seu curso [SAG 83]

Os organismos vivos mais simples que conhecemos são os viróides que possuem menos de 10.000 átomos. Provavelmente os viróides são descendentes de organismos mais complexos sendo dependentes de organismos maiores para se reproduzir. Os organismos vivos de forma independente mais simples que se tem conhecimento são conhecidos por PPLO que possuem cerca de 50.000.000 de átomos [SAG 83].

3.1.3A Heurística da Evolução

Uma heurística não exige uma solução para cada entrada de seu domínio. Quando uma heurística encontra uma solução, não existe garantia de que a solução encontrada seja única ou ótima. Quando uma heurística não encontra uma solução, não existe garantia que a solução procurada não exista [JAM 84].

É interessante observar que o processo evolutivo que ocorreu e está ocorrendo em nosso planeta não garante que determinada espécie evoluirá a ponto de garantir a existência de seus descendentes. Processos algorítmicos garantem uma solução para cada entrada de seu domínio quando esta existe. Supondo que o problema de uma espécie seja evoluir e garantir a descendência, as leis que regem a seleção natural e o processo evolutivo planetário não oferecem garantia de solução para tal problema ainda que eventualmente possam levar a uma solução. Sendo assim, a evolução baseada na seleção natural é um processo heurístico. Vale observar ainda que espécies que sobrevivem à seleção natural não estão necessariamente em seu nível adaptativo ótimo.

Observando que o sexo apareceu somente há dois bilhões de anos atrás, concluímos que a evolução seguiu o seu curso durante mais de 2 bilhões de anos sem a existência de sexo. A evolução não depende do sexo. Antes do aparecimento do sexo, cada organismo vivo era descendente exclusivamente de seu indivíduo pai. Com o aparecimento do sexo, códigos genéticos de diferentes indivíduos carregando mutações que ocorreram em paralelo podem ser combinados para gerar um novo indivíduo. Sendo assim, enquanto que seres assexuados são resultado de mutações que ocorreram em série ao longo do tempo, seres sexuados são resultado de mutações que ocorreram em paralelo. O processamento em paralelo da informação genética determina uma maior velocidade evolucionária.

Vale lembrar que a evolução não depende do sexo. O sexo nasceu da evolução. A heurística da vida não depende do sexo. O sexo permite evolução em paralelo. A seleção natural preservou o processamento em paralelo do código genético.

3.1.4Um Algoritmo Evolutivo Quântico

Foi observado na seção 3.1.2 que para implementar um algoritmo evolutivo simples basta implementar reprodução, mutação e pressão seletiva. Na presente secção, será proposta uma forma de implementar um algoritmo evolutivo simples em uma máquina quântica.

Supondo a otimização da solução inicial |S>. Replicando-se e mutando-se cada um dos N filhos de |S> encontraremos a superposição que segue:

F = |S> + |S₁> + |S₂> + |S₃> + ... + |S_N>.

Basta um único registrador para armazenar todo o conjunto de filhos de |S>. Cada filho de |S> é um autoestado de F. A pressão seletiva pode ser simulada por uma função de avaliação que testa se |S_n> obedece a um critério de aptidão determinado. A medição sobre F provocará o colapso dos autoestados. Neste algoritmo, o colapso do vetor de autoestados é a morte de todas as soluções menos a sobrevivente.

O processo pode ser repetido indefinidamente. Ainda que simples, o algoritmo proposto é extremamente veloz tendo em vista que a função de avaliação será feita em paralelo.

3.1.5 Fundamentos de Codificação Genética

A molécula de DNA é uma escada de nucleotídeos. Cada nucleotídeo é feito por 3 partes: uma base nitrogenada ( púrica ou pirimídica ), um açúcar e um ácido fosfórico [NOR 81]. O nucleotídeo leva o nome da base que é a parte que carrega informação. O DNA é uma longa seqüência do tipo ...-fosfato-açúcar-fosfato-açúcar-fosfato-... onde as bases estão ligadas nos açúcares da seqüência[FEL 88].

TABELA 3.1 - Bases encontradas no código genético

Usando a fórmulaem que p é a probabilidade do evento, podemos calcular quantos bits cada nucleotídeo carrega. A probabilidade de que um determinado nucleotídeo apareça é de ¼ ou 0.25. Sendo assim, cada nucleotídeo carrega bits de informação. Vale observar que os nucleotídeos são complementares. Adenina é complementar de Citosina e Guanina é complementar de Timina.

Um códon é definido por um conjunto de 3 nucleotídeos. Sendo assim, existem 4*4*4=64 códons diferentes. Cada códon corresponde a um tipo de aminoácido diferente. O problema é que existem somente 20 tipos de aminoácidos, tornando o código redundante. Existem diferentes códons para o mesmo aminoácido permitindo que uma mutação transforme um códon em um códon equivalente ou sinônimo sendo esta uma mutação neutra. Na década de 50, incorretamente foram feitas propostas de modelos genéticos em que códons mais comuns poderiam usar menos nucleotídeos bem ao estilo do código de compressão de Huffman. A idéia geral do código de compressão de Huffman é representar com menos bits os eventos mais freqüentes e representar com mais bits os eventos menos freqüentes. A redundância existente no código genético permite alguma proteção contra mutações. Em simulações feitas por computador, David Haig e Laurence D. Hurst mostraram que o código redundante do DNA está quase no nível ótimo no que tange à proteção a mutações [HAY 98].

Considerando que o DNA humano possui cerca de 5 bilhões de nucleotídeos [SAG 77] e que cada códon é composto de 3 nucleotídeos, podemos concluir que o DNA humano possui cerca de 1.7 bilhões de códons. Para facilitar o cálculo, supomos que os códons referentes aos 20 aminoácidos sejam equiprováveis. Sendo assim, o número de bits necessário para representar o DNA humano será debits ou 918 megabytes! A quantidade de DNAs diferentes de tamanho de bits é de exatos .

3.1.6 DNA e Técnicas de Programação

Toda vida que conhecemos e subseqüentemente toda inteligência biológica que conhecemos está baseada em DNA. Entender o funcionamento, o protocolo e as regras em que o DNA é escrito e interpretado são essenciais no entendimento da vida. Se queremos falar de vida e inteligência artificial deveremos falar sobre a computacionalidade do DNA. No presente tópico, pretende-se examinar aspectos que possam ser importantes sobre o código genético para cientistas da computação.

Em um computador, um programa é um conjunto de dados e instruções que operam sobre esses dados. Vale observar que o próprio programa é uma informação contida na memória do computador. Podemos olhar o DNA como uma memória que possui dados e instruções analogamente à memória de um computador.

Ainda que as regras básicas de formação do DNA de uma árvore, bactéria ou um primata sejam semelhantes, a semântica ou significado associado a certos códons ou genes pode variar. Na genética bacteriana, existem conjuntos de genes que são ativados em conjunto por um único operador. A ativação de um gene resulta na fabricação de um composto de aminoácidos. Quando um operador é ativado, todo o seu conjunto de genes é ativado. A ativação de um operador lembra a chamada de função que resulta na execução das instruções que descrevem a respectiva função. O operador pode ser ativado ou suprimido por um outro gene chamado de regulador situado em outro lugar do genoma.

O gene é composto por uma seqüência de códons. Considerando que cada códon corresponde a um aminoácido, cada gene corresponde a um composto de aminoácidos. O gene regulador exerce função de controle. O gene regulador controla a ativação ou supressão do gene operador. Quando um gene operador é ativado, ele desencadeia a ativação de todo o conjunto de genes a que pertence.

Abordando um exemplo, vamos supor um gene regulador que comanda um gene operador que ativa a produção de enzimas que metabolizam um açúcar. Apenas haverá sentido disparar a produção dessas enzimas quando existir a presença de açúcares. O gene regulador deverá reagir à presença do açúcar ativando o gene operador que é responsável pela produção de enzimas que metabolizarão o açúcar e deverá desativar o gene operador na falta de açúcares. É interessante observar que um gene somente pode estar em dois estados lógicos mutuamente exclusivos que são “ativado” e “desativado”.

O DNA não é o único lugar onde existe informação. O estado bioquímico de uma bactéria pode ser um tipo de memória sobre a qual os reguladores fazem seus testes. No exemplo do açúcar, os estados de memória em relação ao açúcar poderiam ser hipoglicêmico, normal ou hiperglicêmico.

Podemos olhar uma bactéria como um hardware em que a informação do seu DNA é o seu software. Ao olhar a tabela apresentada acima, fica evidente a semelhança entre funções biológicas que encontramos em bactérias e funções que encontramos em computadores.

Quando trabalha-se com textos em computadores, é comum trabalhar com longas seqüências de caracteres em código ASCII. Cada letra do alfabeto possui um correspondente no código ASCII. Para o fim de linha, comumente usamos um caractere terminador de índice 13 (0DH ou ENTER ou CR). Abordando a comparação do DNA com uma longa seqüência de caracteres, assim como nas seqüências ASCII, também existe um símbolo terminador no DNA que pode ser um dos códons UAA, UAG ou UGA em bactérias. Existem indicações de que UAA é um códon de terminação no homem [NOR 81].

Em uma seqüência de caracteres longa, a supressão de um único bit ou de um conjunto de bits não múltiplos de 8 (bytes) acarreta um descompasso de sua leitura tornando-a ininteligível perdendo até os símbolos terminadores. Da mesma forma, a perda de um nucleotídeo ou um conjunto de nucleotídeos não múltiplos de 3 acarreta na perda de longas seqüências de código incluindo os terminadores.

Quando um computador está pr'ocurando por vírus em sua memória, ele varre toda a memória procurando por uma seqüência definida de bytes que identifique a presença de um determinado tipo de vírus na máquina. Em uma bactéria, a situação é extremamente semelhante. Quando uma bactéria é invadida por um DNA estranho ( de origem viral ), o DNA estranho poderá ser interceptado por uma enzima de restrição que varrerá o DNA até encontrar uma seqüência de códons previamente definida. Em caso afirmativo, o DNA será quebrado. Por exemplo, sempre que a enzima Eco R1 encontra uma seqüência do tipo GAATC, o DNA será quebrado [NOR 81].

TABELA 3.2 - Enzimas de restrição e DNAs virais

Considerando que as enzimas são processadores de moléculas, já que podem quebrar e compor moléculas, se as moléculas que uma enzima processa possuem informação, a enzima está processando não apenas moléculas que carregam informação como está processando a própria informação.

3.2Computação Molecular

3.2.1Introdução

No tópico anterior, foi observado que enzimas podem processar informação. No presente capítulo, será estudada a proposta de Leonard Adleman [ADL 94][ADL 96] para a construção de um computador molecular. Adleman é professor atuante nos departamentos de ciência de computação e de biologia molecular da University of Southern California [ADL 2000].

A idéia básica do computador molecular é: cada molécula mergulhada em um tubo de ensaio pode ser uma unidade de processamento de informação. Sendo assim, um tubo de ensaio contendo as moléculas certas é um sistema de processamento de informação massivamente paralelo.

3.2.2Modelo Abstrato

No presente tópico, será estudado um modelo abstrato de computação molecular. Esse modelo foi desenvolvido baseando-se nas propriedades químicas do DNA. Nesse modelo, um tubo de ensaio contém moléculas de DNA representadas por palavras no alfabeto {A,C,G,T}. As operações permitidas sobre um tubo de ensaio são as que seguem:

1. Separação ou Extração: dado um tubo de ensaio contendo palavras do alfabeto {A,C,G,T}, a operação +(T,s) separa todas as palavras que contenham a seqüência s enquanto que -(T,s) separa todas as palavras que não contenham a seqüência s.

   Exemplo:

   T1 = { ACGT , ACCT , ATCG, ATCC }

   Operando-se T2 = +(T1,CG) e T3 = -(T1,GC) encontra-se:

   T2 = { ACGT , ATCG } e T3 = { ACCT , ATCC }

2. Mescla: dados os tubos T1 e T2, U(T1,T2) = T1 U T2.

   Exemplo:

   T2 = { ACGT , ATCG } e T3 = { ACCT , ATCC }

   T4 = U(T2,T3) = { ACGT , ACCT , ATCG, ATCC }

3. Detecção: dado um tubo de ensaio T, responde “sim” se existe no tubo ao menos uma molécula de DNA e responde “não” se não existe nenhuma molécula de DNA no tubo.

   Exemplo:

   T1 = { ACGT , ATCG } e T2 = {}

   Detect(T1) = “sim” e Detect(T2) = “não”

4. Amplificação: dado um tubo T1, a amplificação gera outros dois tubos T2 e T3 idênticos a T1. A notação é a que segue: T1 = T2(T1) = T3(T1).

Com as quatro operações apresentadas anteriormente, podemos escrever programas de computação molecular. A seguir, será apresentado um programa bastante simples:

Imput(T)

T1 = - (T,G)

Detect (T1)

O programa apresentado testa se no tubo T existe alguma molécula que não contenha o símbolo G. O próximo programa será ligeiramente mais complexo:

Imput(T)

T1 = - (T,G)

T2 = - (T1,C)

T3 = - (T2,T)

Detect (T3)

O programa listado acima testa se existem moléculas formadas exclusivamente de símbolos A.

Devem ser feitas considerações sobre o fato de que não é simples construir um computador molecular com a operação de amplificação. A operação de amplificação consome matéria e exige ligações químicas covalentes o que dificulta o processo.

No presente capítulo, foi abordado um modelo de computação molecular baseado em moléculas de DNA; porém, é possível usar outros tipos de moléculas mantendo as mesmas abstrações apresentadas até aqui.

Apesar das restrições apresentadas, no próximo tópico, resolveremos um problema np-completo: testar se um grafo é colorível com apenas 3 cores de forma que dois vértices ligados por arestas não apresentem a mesma cor. Se o leitor não souber o que é um problema np-completo, recomenda-se a leitura do anexo 1.

3.2.3Exemplo de Aplicação

3.2.3.1Objetivo

A aplicação a ser abordada no presente tópico é testar se dado um grafo é possível colorir os vértices com apenas três cores de tal forma que dois vértices ligados por uma aresta não apresentem a mesma cor.

3.2.3.2Definição do Algoritmo

Dado um grafo G de arestas A₁, A₂ ,.., A_z, seja:

n é o número de vértices;

z é o número de arestas;

S = {r₁, g₁, b₁,r₂, g₂, b₂, ..., r_n, g_n, b_n} ;

a entrada do programa T em que

T = { |& = { c₁, c₂, ..., c_n} & [c_i = r_i ou c_i = b_i ou c_i = g_i], i = 1,2, ..., n }

Apenas para efeito de exemplo, a palavra r₁b₂g₃ representa a situação em que o vértice 1 é vermelho (r), o vértice 2 é azul (b) e o vértice 3 é verde (g). A entrada T contém todas as possíveis colorações para o grafo.

Seja o programa:

Input(T)

for k = 1 to z. Let A_k = <i,j>:

T_red = +(T,r_i) and T_{blue or green} = -(T,r_i)

T_blue = +(T_{blue or green},b_i) and T_green = -(T_{blue or green},b_i)