Escaravelho Dourado: decifre o enigma de Allan Poe com Python

“O Escaravelho Dourado” é um pequeno conto, do escritor americano Edgar Allan Poe, publicado em 1843.

O enredo narra a história de William Legrand, supostamente picado por um escaravelho dourado. Seu servo Júpiter teme que Legrand fique louco, e com a ajuda do narrador anônimo, partem para uma aventura que envolve uma mensagem criptografada e um tesouro escondido.

Sem mais delongas, os aventureiros se depararam com a seguinte mensagem.

53‡‡†305))6;4826)4‡.)4‡);80 6;48†8¶60))85;1‡(;:‡8†83(88) 5†;46(;8896?;8)‡(;485);5

2:‡(;49562(5-4)8¶8;40692

85);)6†8)4‡‡;1(‡9;48081;8:8‡1

;48†85;4)485†528806*81(‡9;48

;(88;4(‡?34;48)4‡;161;:188;‡?;

A primeira informação é que a mensagem está em inglês. O narrador cita que, tendo decifrado inúmeras mensagens criptogradas, é essencial saber qual a linguagem em que este está escrito.

A seguir, ele faz uma contagem dos caracteres existentes.

Em Python, podemos utilizar um set para listar os caracteres únicos, como mostra o código a seguir.

strOriginal = "53‡‡†305))6;4826)4‡.)4‡);806;48†8¶60))85;1‡(;:‡8†83(88)5†;46(;8896?;8)‡(;485);5†2:‡(;49562(5-4)8¶8;4069285);)6†8)4‡‡;1(‡9;48081;8:8‡1;48†85;4)485†528806*81(‡9;48;(88;4(‡?34;48)4‡;161;:188;‡?;"

caracteres = set(strOriginal)

A seguir, podemos contar o número de vezes que cada caractere aparece na string, e imprimir o resultado:

dictCaract ={}

for ch in caracteres:
dictCaract[ch] = strOriginal.count(ch)

for i in sorted(dictCaract, key = dictCaract.get, reverse=True):
print(i, dictCaract[i])

Resultado:
8 33
; 26
4 19
‡ 16
) 16

13
5 12
6 11
( 10
1 8
† 8
0 6
2 5
9 5
: 4
3 4
? 3
¶ 2
. 1

-1

O caractere ‘8’ aparece 33 vezes, seguido pelo caractere ‘;’, 26 vezes. Em inglês, “e” é a letra mais comum, então um bom chute é considerar ‘8’ -> ‘E’. Vou utilizar maiúsculas para indicar a string trocada.

A seguir, o narrador nota que a cadeia de strings ‘;48’ aparece com grande frequência no texto, e o último caractere é “E”.

O ‘THE’ é um artigo bastante comum na língua inglesa, de modo que as substituições ‘;’ -> ‘T’, ‘4’ -> ‘H’ parecem ser um bom chute.

Em Python, é só usar a função replace:

str2 = strOriginal.replace('8','E')
str2 = str2.replace(';','T')
str2 = str2.replace('4','H')

Resulta em:

53‡‡†305))6THE26)H‡.)H‡)TE06THE†E¶60))E5T1‡(T:‡E†E3(EE)5†TH6(TEE96?TE)‡(THE5)T5†2:‡(TH9562(5-H)E¶ETH0692E5)T)6†E)H‡‡T1(‡9THE0E1TE:E‡1THE†E5TH)HE5†52EE06*E1(‡9THET(EETH(‡?3HTHE)H‡T161T:1EET‡?T

Ainda bastante ininteligível, porém, um pouco mais familiar.

Pescando algumas palavras, há um trecho assim: ‘t(ee’, que pode ser ‘tree’, indicando a substituição ‘(‘ -> ‘R’.

O trecho fica:
the tree thr‡?3h the.

A palavra ‘through’ indica novas letras ‘O’, ‘U’ e ‘G’, representadas por ‘‡’, ‘?’ e ‘3’.

No Python, letra por letra (é possível por outros meios em massa, mas assim é mais didático).

str2 = str2.replace('(','R')

str2 = str2.replace('‡','O')
str2 = str2.replace('?','U')
str2 = str2.replace('3','G')

Resultando em:

5GOO†G05))6THE26)HO.)HO)TE06THE†E¶60))E5T1ORT:OE†EGREE)5†TH6RTEE96UTE)ORTHE5)T5†2:ORTH9562R5-H)E¶ETH0692E5)T)6†E)HOOT1RO9THE0E1TE:EO1THE†E5TH)HE5†52EE06*E1RO9THETREETHROUGHTHE)HOT161T:1EETOUT

Outras pistas:
†83(88, ou †egree,

Deixando clara a palavra ‘degree’, e a substituição ‘†’ por ‘D’.

Outro trecho parcialmente traduzido fica ”TH6RTEE‘, evidentemente ‘thirteen’, ‘6’ -> ‘I’ e ‘‘ -> ‘N’.

O início, ‘5GOOD’, indica o ‘5’ como ‘A’.

Colocando todas as pistas no Python, temos:

str2 = str2.replace('†','D')
str2 = str2.replace('6','I')
str2 = str2.replace('*','N')

str2 = str2.replace('5','A')

Texto parcialmente decifrado:

AGOODG0A))INTHE2I)HO.)HO)TE0INTHEDE¶I0))EAT1ORT:ONEDEGREE)ANDTHIRTEEN9INUTE)NORTHEA)TAND2:NORTH9AIN2RAN-H)E¶ENTH0I92EA)T)IDE)HOOT1RO9THE0E1TE:EO1THEDEATH)HEADA2EE0INE1RO9THETREETHROUGHTHE)HOT1I1T:1EETOUT

Allan Poe para por aí, dizendo que o resto segue a mesma lógica, e realmente não é difícil. Por exemplo, ‘9INUTE)’ significa ‘MINUTES’; pelo contexto de direção, ‘NORTHEA)T’ significa ‘NORTHEAST’ e assim por diante.

Fechando a cifra:

str2 = str2.replace('0','L')
str2 = str2.replace(')','S')
str2 = str2.replace('2','B')
str2 = str2.replace('.','P')
str2 = str2.replace('¶','V')
str2 = str2.replace('1','F')
str2 = str2.replace(':','Y')
str2 = str2.replace('9','M')
str2 = str2.replace('-','C')

Resulta em:

AGOODGLASSINTHEBISHOPSHOSTELINTHEDEVILSSEATFORTYONEDEGREESANDTHIRTEENMINUTESNORTHEASTANDBYNORTHMAINBRANCHSEVENTHLIMBEASTSIDESHOOTFROMTHELEFTEYEOFTHEDEATHSHEADABEELINEFROMTHETREETHROUGHTHESHOTFIFTYFEETOUT

Como está sem pontuação e espaço, estes devem ser inseridos:

“A good glass in the Bishop’s hostel in the Devil’s seat — forty-one degrees and thirteen minutes — northeast and by north — main branch seventh limb east side — shoot from the left eye of the death’s-head — a bee-line from the tree through the shot fifty feet out.'”

[Um bom vidro no hotel do bispo na cadeira do diabo – quarenta e um graus e treze
minutos nordeste quadrante norte – tronco principal sétimo galho lado leste – atirai do
olho esquerdo da caveira – uma linha de abelha da árvore através o tiro cinqüenta pés
distante.]

Esta é uma cifra de substituição simples, onde cada palavra é trocada por um caracter específico. Sabendo o dicionário, é possível cifrar e decifrar uma mensagem. Cifras deste tipo são conhecidas desde o Império Romano, e são muito frágeis, bastando um ataque de contagem e força bruta, como demonstrados no conto. Atualmente, há métodos de chave assimétrica como o RSA, extremamente mais avançados. Porém, na época de Allan Poe, este era o melhor que existia, e o conto do “Escaravelho dourado” ajudou a popularizar a ciência da criptografia.

Vide o código completo no Colab: https://colab.research.google.com/drive/1l1MztHdxUHdJl1yW4NZzn1heDUvoSoJJ?usp=sharing

Visite o meu blog pessoal https://ideiasesquecidas.com/

Conto ‘Golden Bug’, de Edgar Allan Poe https://poestories.com/read/goldbug

Conto em português, “O Escaravelho Dourado”

Certificado – Quantum Excellence

Compartilhando o Certificado de Quantum Excellence da IBM, para quem passou pelo Summer School deste ano.

Vide comentários sobre essas duas semanas de treinamento aqui: https://medium.com/arnaldo-gunzi-quantum/comments-on-qiskit-summer-school-2021-quantum-machine-learning-4ff5523c6761

Outro post que pode ser de interesse: https://medium.com/arnaldo-gunzi-quantum/how-to-get-the-qiskit-developer-certificate-8dcd3b31fcb0

Agradeço a todos pela ajuda e suporte de sempre!

Comentários sobre o Qiskit Summer School 2021 – Quantum Machine Learning

O Qiskit Summer School é um evento patrocinado pela IBM, para divulgação de computação quântica. Qiskit é o nome da linguagem desenvolvida pela IBM. Este ano, foi a segunda edição do evento, e o tema foi Quantum Machine Learning.

Uma primeira curiosidade, é que este ano foram 5000 vagas (ano passado, 2000), e essas acabaram em poucos minutos após a abertura das inscrições. Bastante gente reclamou que entrou exatamente no horário de abertura e já via o número de vagas esgotada. Isso mostra o interesse crescente pelo tema – e o privilégio de assistir as aulas.

Foram duas semanas de aulas, e 5 rodadas de laboratórios – cada qual com número variável de exercícios valendo nota.

Resumo rápido do conteúdo.


Semana 1:

  • Circuitos básicos
  • Algoritmos simples
  • Ruído em computadores quânticos
  • Machine learning clássico
  • Quantum classifier
  • QAOA

Mais da metade da semana 1 foi de conteúdo básico, só no finalzinho que realmente começou a ficar divertido. O conteúdo até falou de machine learning clássico (redes neurais, backpropagation), mas o foco foi em cima de Support Vector Machines, uma técnica de classificação um pouco diferente.

Por fim, introdução à técnica de otimização QAOA, que é um misto de quântico com clássico: a representação do problema é por um circuito quântico, porém a otimização dos parâmetros, via métodos clássicos.

O lab dos circuitos básicos foi tranquilo, o da parte SVM e QAOA deu um pouco mais de trabalho, mas nada impossível. Não posso divulgar minhas respostas, por enquanto. Vou esperar a IBM liberar oficialmente o conteúdo do curso para o público em geral.


Semana 2:

  • Classificadores lineares
  • Quantum kernel
  • Treinamento de circuitos quânticos
  • Hardware e ruído
  • Capacidade e circuitos avançados
  • Encerramento e discussões sobre rumos futuros

A melhor parte do curso foi a semana 2. Conhecimento de ponta, com conteúdo que não tem nem três anos desde a primeira citação.

O Support Vector Machine tem uma limitação, que é o fato de ser linear. É possível fazer um truque para contornar: pegar os mesmos dados e representá-los de forma não linear, através de um feature map. O kernel é uma generalização do feature map, para uma função mais complexa.

Pode haver vantagem quântica exponencial se a função for complicada para representar classicamente e simples de representar quanticamente – mas isso também não é garantido sempre.

Carregar dados em estados quânticos pode ter custo exponencial, o que pode jogar por terra qualquer vantagem quântica – uma solução possível é utilizar um esquema aproximado de dados, perdendo uma parte pequena da informação.

Muito impressionante é uma pesquisadora chamada Amira Abbas. Ela deu umas três aulas ou mais. Bastante didática, nova (assim como todos ali), realmente manjava do conteúdo – para quem se interessa pelo tema, vale a pena acompanhá-la.

Uma discussão bastante interessante foi a de capacidade. Em machine learning clássico, temos sempre o dilema underfitting (modelo fraco demais) – overfitting (parâmetros demais, o que causa perda de generalização). Sempre achei que isso era apenas dependendo do tamanho do modelo, mas foi demonstrado, através de experimento de labels aleatórios, que os dados também influem. Desde então, está havendo diversas propostas de medir a capacidade não só em função do tamanho, mas de características bem específicas dos dados também.

Sobre os labs: em geral, não foi difícil. Era basicamente seguir o roteiro dado pelos professores. Algumas poucas linhas, e a maioria já estava pronto. Tenho a impressão de que o Summer School foca mais na aula e no conteúdo teórico, e menos nos labs em si. Para códigos difíceis, a IBM lança os desafios.

Agradeço à IBM pela iniciativa, pelo conteúdo de mais alto nível disponibilizado, e parabenizo pela liderança no tema.

No formulário de feedback, era pedido uma foto para ajudar na divulgação do evento, e esta foi a que enviei.


Ideias Analíticas Avançadas
Um mundo melhor através do Analytics

Inovação e computação quântica

Bati um papo sobre computação quântica com o Rafael Veríssimo, fundador da startup Brazil Quantum.

A computação quântica é uma forma fundamentalmente diferente de fazer computação. Ao invés dos tradicionais bits (0 ou 1), temos qubits, utilizando propriedades quânticas como sobreposição e emaranhamento.

Não são todos os problemas em que há ganho em usar tal abordagem. Algumas das aplicações possíveis são: simulação de moléculas químicas, criptografia (tanto quebrar a criptografia atual quanto criar uma criptografia indecifrável por natureza) e otimização combinatória.

É uma tecnologia potencialmente disruptiva, que talvez se torne uma realidade nos próximos 10 anos.

Também falamos do projeto que estamos fazendo na empresa: o Trim Quântico. Como modelar o algoritmo do Trim, que roda em todas as empresas de papel, utilizando as técnicas citadas. A Klabin é pioneira na indústria nacional ao estudar este tipo de tecnologia.

Festival #InovaKlabin.

Proof of work na vida real

O protocolo “proof of work” é utilizado atualmente em criptomoedas, e foi originalmente concebido para evitar spams. Mas o interessante é que, antes mesmo de existir o conceito computacional, a lógica já era aplicada faz muito tempo na sociedade e na natureza: diplomas, certificados, e até a plumagem do pavão. Vejamos como.


O proof of work consiste na entidade “A” mostrar, sinalizar, provar a uma entidade “B” que um trabalho foi feito (daí o nome, prova de trabalho).

Uma utilidade: evitar spams. Hoje em dia, é muito barato computacionalmente mandar um milhão de e-mails de uma só vez. Se, a cada e-mail enviado fosse necessária uma prova de trabalho (digamos, resolver um problema matemático difícil), haveria um limite natural: a capacidade de processamento do computador.

Para funcionar, o proof of work deve ser assimétrico: um problema difícil de resolver, porém, fácil de conferir o resultado.

Interessante notar também que a Teoria dos Números tem inúmeros problemas desta natureza. O que sempre foi apenas uma curiosidade inútil, agora tem uma aplicação prática.

Ex. Encontre x, y e z tais que x^2 -3y + 8z^3 = 2727.

É chatinho achar a solução, porém, é muito fácil conferir se a resposta dada é verdadeira ou não.

  • x = 5
  • y = 14
  • z = 7

Outra característica: é difícil de falsificar, no sentido de encontrar uma solução fácil que engane o sistema.

Em criptomoedas, o proof of work é utilizado para garantir que todas as transações no bloco foram verificadas.


Pensando bem, um diploma de uma boa faculdade é uma prova de trabalho também. É difícil de conseguir: 4 ou mais anos estudando, assinalando presença em aula, fazendo as atividades, etc. E o diploma é fácil de conferir: basta checar as informações junto à entidade emissora.

Uma certificação emitida por uma associação profissional, idem. Tem de gerência de projetos, de qualidade, várias de TI. Cursos online, a mesma coisa.

Hoje em dia, está mais fácil checar certificações. No meu LinkedIn, na parte de “Licenses and certificates”, basta ir no “See credential” para ser direcionado à instituição que garante o certificado.

Tudo isso, por conta de assimetria de informação. Sendo o mundo vasto, não conhecemos as pessoas, e se suas habilidades são suficientes para um serviço. Com essas provas de trabalho, o risco diminui: pelo menos, há um indício forte de que a pessoa conhece do tema – não é garantia absoluta, mas é melhor do que nada.


Até na natureza, o proof of work é importante. Por que algumas gazelas, mesmo fugindo de um leão, dão saltos altos, extravagantes e desnecessários? Uma teoria da evolução diz que esse tipo de salto é como um proof of work dos machos para as fêmeas do bando: “olha só, eu sou tão rápido e forte que estou pouco me lixando para esse leão feroz, até esnobo ele. Fiquem comigo, gatinhas”.

Outro exemplo é o das penas do pavão. Por qual motivo ele teria penas tão chamativas? Há uma desvantagem enorme em carregar tantas penas desnecessárias, que chegam a ter 2 m de altura: mais volume, mais peso, chama mais atenção dos predadores. É um sinal difícil de falsificar, e também funciona como um proof of work: “olha só, mesmo com toda essa parafernália, sou forte o bastante para sobreviver aos predadores”.

O proof of work é tão importante, que pode surgir de formas inesperadas: cartas escritas à mão. Na era pré-internet, era comum enviar cartas e cartões postais, acredite se quiser. Depois do e-mail, ninguém mais se dá ao trabalho de escrever uma carta, levar até os correios e postar. A contrapartida é que é tão fácil enviar mensagens hoje em dia, que estamos transbordando de informação.

Por ironia do destino, uma prova de trabalho difícil de falsificar é escrever uma carta à mão (não imprimir), e mandar para o destinatário. Tem infinito mais valor do que o spam enviado à milhares de pessoas ao mesmo tempo.

“Se eu não te conheço e você deseja me enviar uma mensagem, deve provar que gastou, digamos, dez segundos de tempo de CPU, apenas para mim e apenas para esta mensagem”, Cynthia Dwork e Moni Naor, criadores do protocolo proof of work.

Veja também:

https://en.wikipedia.org/wiki/Proof_of_work

Alan Turing é homenageado na nova nota de 50 libras

Para quem gosta de matemática e computação, Alan Turing é um dos nomes mais importantes da história, com contribuições que perduram até hoje.

Turing abstraiu o conceito de computação, e provou que é possível criar uma “máquina de Turing universal”. Ao invés de ter um dispositivo específico para cada operação, o mesmo dispositivo poderia ser programado para fazer as mais diversas operações imagináveis.

Os computadores modernos são máquinas de Turing universais em sua essência.

A tese de Turing-Church, de que todas funções computáveis podem ser computadas por máquinas de Turing universais, continua um problema aberto até hoje.

Ele foi um dos pioneiros da inteligência artificial, com o teste de Turing, uma espécie de jogo da imitação: será que quem escreveu este texto foi uma pessoa ou uma máquina?

Finalmente, ajudou a salvar centenas de milhares de vidas de soldados aliados, ao decifrar o Enigma, código criptográfico nazista. Não é exagero. Por exemplo, os códigos decifrados deram a segurança de que os nazistas não sabiam onde seria o local do desembarque, no Dia D.

Apesar de tudo isso, Turing foi perseguido por ser homossexual, e tirou a própria vida em decorrência de um tratamento forçado a que fora submetido.

Um dia vou conseguir uma nota dessas, só para deixar na carteira como homenagem à este grande gênio da humanidade.

Recomendação de filme: O Jogo da Imitação, no Prime Video:

https://amzn.to/31qsfhG

Veja também:

thttps://ideiasesquecidas.com/2020/11/21/codigos-genetica-e-puzzles/

A fábula inacabada dos pardais

Este texto é do início do livro “Superinteligência”, de Nick Bostrom. É uma fábula que ilustra o perigo de termos máquinas mais inteligentes do que seres humanos, num futuro a médio prazo.

Era a temporada de construção dos ninhos, e depois de dias de trabalho árduo, os pardais sentaram-se ao cair da noite relaxando e cantando. “Somos tão pequenos e fracos… Imaginem como a vida seria mais fácil se tivéssemos uma coruja que nos ajudasse a construir nossos ninhos!”.

“Sim!”, disse outro. “E poderíamos usá-la também para cuidar de nossos idosos e jovens. Ela também poderia nos dar conselhos e vigiar o gato do bairro”.

Então Pastus, o pardal mais velho, falou: “Vamos enviar patrulhas e tentar encontrar uma corujinha abandonada em algum lugar; talvez, um ovo de coruja. Esta poderia ser a melhor coisa que já nos aconteceu, pelo menos desde a abertura do depósito de grãos da cidade”. O bando ficou excitado com a ideia e começou a gorjear a plenos pulmões em aprovação.

Somente Scronkfinkle, um pardal de um olho só, com temperamento irritadiço, não estava convencido da sabedoria daquele empreendimento. Ele disse: “Isto será nossa ruína. Deveríamos aprender um pouco sobre domesticação de corujas antes de trazermos uma criatura dessas para o nosso meio.”

Pastus respondeu: “domar uma coruja dever ser coisa extremamente difícil. Já será extremamente dificíl encontrar um ovo, então vamos começar por aí. Depois que tivermos conseguido criar uma coruja, poderemos pensar em assumir esse outro desafio.”

“Há uma falha nesse plano!” gritou Scronkfinkle, mas seus protestos foram em vão – o bando já tinha levantado voo. Apenas dois ou três pardais ficaram para trás.

Juntos, começaram a tentar descobrir como corujas poderiam ser domesticadas. Logo perceberam que Pastus tinha razão – era um desafio extremamente difícil, especialmente na ausência de uma coruja de verdade para praticar. No entanto, esforçavam-se o mais que podiam temendo que o bando retornasse com um ovo de coruja antes que uma solução para aquele “problema de controle” tivesse sido encontrada.

Não se sabe como a história termina, mas o autor dedica este livro a Scronkfinkle e seus seguidores.

Veja também:

O que é GPT3 e por que isso importa? (ideiasesquecidas.com)

O inverno e a primavera da Inteligência Artificial (ideiasesquecidas.com)

https://ideiasesquecidas.com/2020/12/08/alphafold-dobramento-de-proteinas-e-origami/

Roadmap – Computação quântica.

Segue no link um artigo que escrevi com os amigos da Brazil Quantum – um roadmap para os que gostam deste ramo nascente do conhecimento.

São alguns livros, como Quantum Computing Explained, de David McMahon;

Linguagens como o #qiskit;

e sites como o do magnífico prof Scott Aaronson, um dos maiores especialistas do mundo.

https://brazilquantum.medium.com/roadmap-de-estudos-em-computa%C3%A7%C3%A3o-qu%C3%A2ntica-fda5a1d0964c

O presente é digital. O futuro será analógico.

Muito se fala do mundo digital de hoje, mas, se o presente é digital, o futuro será analógico.

Primeiro. a Computação quântica utiliza as propriedades quânticas dos átomos, como superposição e emaranhamento. Esta tem o potencial de quebrar toda a criptografia do mundo atual.

É como se eu pegasse todas as alternativas de um problema, computasse cada uma delas em paralelo e viesse apenas com a resposta correta.

Analógico x Digital (Fonte: Wikipedia)

Segundo: computação neuromórfica. Hoje em dia, temos um software digital imitando redes neurais humanas. A nova técnica procura ir direto ao ponto, criar um hardware, o memristor, que imita um neurônio biológico.

As vantagens seriam em consumo de energia e tamanho várias ordens de grandeza menores.

Todas essas pesquisas estão engatinhando, porém, o futuro é promissor.


E a terceira e melhor tecnologia analógica de todas: Cérebro humano.

Somos capazes de projetar coisas, criar as mais belas músicas, imaginar histórias, ensinar outras pessoas.

E fazer o futuro tecnológico, porém humano, acontecer.

Trilha sonora:

(98) Pink Floyd – Wish You Were Here – YouTube

AlphaFold, dobramento de proteínas e origami

O DeepMind, a mesma empresa da inteligência artificial que venceu os mestres do jogo Go, surpreende o mundo novamente.

Ela acaba de vencer o CASP – Critical Assessment of Protein Structure Prediction, uma competição para prever a estrutura de proteínas, com o seu algoritmo AlphaFold.

O CASP existe faz anos, e sempre tem um vencedor. Qual a diferença?

A diferença é que o AlphaFold foi muito superior aos demais, atingindo um nível de acurácia nunca antes visto, e rivalizando com técnicas laboratoriais (como o Raio-X) extremamente mais demoradas e caras.

O que é dobramento de proteínas?

Muito se fala do famoso DNA, a molécula em dupla-hélice que é o livro da vida. Entretanto,o DNA sozinho não faz nada. A informação contida neste, através de suas bases (A,G,C,T), tem que ser transcrita e levada ao ribossomos, onde são transformadas em proteínas.

Um conjunto de três bases forma um aminoácido. O conjunto se dobra em estruturas 3D complexas, que aí sim, tem função no organismo – um hormônio, um anticorpo, etc.

Proteínas são os blocos constituintes da vida, existentes em seres humanos, animais, plantas.

É como dobrar um origami de um cisne. O DNA é o papel desdobrado, onde somente as marcas de dobra são visíveis.

O problema é: a partir das marcas das dobras, como montar o origami completo, dadas as interações físicas e químicas entre os aminoácidos. O problema é extremamente complexo, porque a cadeia pode ter milhares de aminoácidos, e todos influenciam em todos.

O DeepMind é famoso por utilizar redes neurais profundas do começo ao fim, porém, dessa vez, a abordagem foi mista.

Utilizaram: 1- redes neurais de atenção para chegar em fragmentos candidatos; e 2 – algoritmos clássicos (Gradient Descent) para otimização global.

Também esperava-se um esforço computacional gigantesco, fosse puramente redes neurais profundas, mas a abordagem descrita utilizou apenas ~200 GPUS, algo relativamente modesto nos dias de hoje.

Obviamente, fizeram uma quantidade gigantesca de pesquisa para chegar nessas soluções, dentre as inúmeras outras arquiteturas possíveis.

Aplicações do dobramento de proteínas: entender doenças e projetar remédios.

Os métodos atuais permitem obter a estrutura de uma proteína ao cabo de um ano e com um custo de 120 mil dólares. O AlphaFold fornece o resultado em meia hora.

Ainda há um longo caminho a percorrer, para tornar o AlphaFold capaz de resolver problemas de verdade. O CASP é basicamente um jogo controlado, e o algoritmo funciona bem apenas no contexto do desafio proposto.

Mas o futuro é promissor. Na palavra de um dos pesquisadores, “o AlphaFold vai mudar tudo”.

Referências.

https://news.efinancialcareers.com/uk-en/325021/google-deepmind-pay

https://deepmind.com/blog/article/alphafold-a-solution-to-a-50-year-old-grand-challenge-in-biology

https://www.businessinsider.com/deepmind-google-protein-folding-ai-alphafold-technology-2020-12

https://www.kdnuggets.com/2019/07/deepmind-protein-folding-upset.html

https://visao.sapo.pt/exameinformatica/noticias-ei/ciencia-ei/2020-12-02-inteligencia-artificial-da-deepmind-faz-descoberta-cientifica-revolucionaria/

IBM Q Challenge – Inverno 2020

Finalizei a participação no IBM Q Challenge Fall 2020, resolvendo 4 questões de 5.

Foram três semanas, onde os exercícios foram sendo liberados aos poucos. O tema deste ano foi o algoritmo de Grover e memória quântica (QRAM). Os desafios foram progressivamente mais difíceis: a primeira semana foi fácil, a segunda foi média, a terceira, extremamente difícil.

O Grover é uma das aplicações práticas da comp. quântica: como encontrar a resposta correta, numa base não estruturada (é como achar um número de telefone específico numa lista telefônica).

É possível formular problemas de otimização de forma a serem resolvidos pelo método citado.

Há um ganho quadrático do Grover em relação à computação clássica. Um ganho quadrático não é muita coisa – o ideal seria um ganho exponencial como o algoritmo de Shor (que potencialmente pode comprometer toda a criptografia atual). Porém, mesmo assim, quem sabe num futuro próximo surja alguma aplicação interessante?

Qual o menor número de linhas horizontais ou verticais para cobrir todas as estrelas? No caso, três linhas verticais resolvem

O quinto desafio foi bastante complicado. Envolvia usar o Grover para resolver um problema de otimização, batizado de “asteroides”. O objetivo era fazer para uma superposição de 16 tabuleiros diferentes, ao mesmo tempo (guardando na QRAM), e encontrar o tabuleiro que necessitava de mais passos.

Agradeço à IBM pela oportunidade de aprender um pouco mais sobre este nascente ramo do conhecimento.

IBM Quantum Challenges – IBM Quantum Experience

P, NP, PSPACE e BQP

Um breve resumo dessa sopa de letrinhas da complexidade computacional.

P –  Problemas que podem ser RESOLVIDOS em tempo polinomial.

NP – Problemas que podem ser VERIFICADOS em tempo polinomial.

NP complete – Os problemas mais difíceis da classe NP.

PSPACE – Problemas que necessitam de uma quantidade polinomial de memória.

BQP – Problemas de podem ser resolvidos eficientemente num computador quântico.

Uma explicação mais elaborada.

P – São os problemas “fáceis” de serem resolvidos.

NP – São os problemas “fáceis” de serem verificados. Ou seja, dada uma resposta, é fácil verificar se ela atende ou não o problema. Porém, não é necessariamente fácil chegar à solução.

Portanto, podem existir problemas que são fáceis de verificar, porém difíceis de resolver.

Exemplo simples. Rearrumar a palavra a seguir:

lrsdhreeaaamb

É bem mais difícil encontrar a solução do que verificar que “desembaralhar” é a resposta.

Os problemas mais difíceis de todos os NP são chamados NP-Completos. Diversos problemas da vida real, como o da Satisfiabilidade, são NP-Completos.

Existe também o NP-Hard, que são problemas pelo menos tão difíceis quanto os NP-completo. Problemas de otimização são assim. NP-Completo é achar uma solução, o NP-Hard, achar a melhor solução. O famoso problema do Caixeiro-Viajante é um exemplo de problema de otimização.

Um grande problema não resolvido do mundo é se P = NP. Até hoje, não foi possível provar que são iguais ou não diferentes. É, inclusive, um dos desafios do milênio do Instituto Clay, valendo 1 milhão de dólares!

O BQP são problemas resolvíveis por um computador quântico. Suspeita-se que seja possível resolver problemas mais difíceis que a classe P, porém sem resolver o NP-completo.

Portanto, a figura que representa os graus de complexidade é apenas uma ideia. Se P for igual a NP, nem precisaríamos de computador quântico! Bastaria usar esse algoritmo, que resolve problemas difíceis de forma fácil.

O problema P vs NP é complicado de provar, não à toa, até hoje não foi resolvido.

Porém, até hoje os problemas difíceis continuam difíceis, o que é um forte indício de que P é diferente de NP, e que problemas difíceis continuarão difíceis – e que computadores quânticos serão muito úteis.

https://pt.wikipedia.org/wiki/BQP

https://en.wikipedia.org/wiki/P_versus_NP_problem

Ideias técnicas com uma pitada de filosofia

https://ideiasesquecidas.com/

Entre no grupo de estudos de Computação Quântica:

https://www.facebook.com/groups/1013309389112487