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

Sonhe como uma máquina

Continuando a descrição de marcos da Inteligência Artificial, em 2015 o mundo conheceu o DeepDream, publicado pelo Google.

Uma foto antiga minha no algoritmo

São imagens psicodélicas geradas por uma rede neural, como se fossem sonhos. Não à toa, o algoritmo original foi batizado “Inception” (viu o filme?).

De forma mais generalizada, o método utilizado é o de Transfer Style.

Uma rede neural convencional é capaz de classificar imagens, como detectar cachorros em fotos. Modificamos essa rede que com outra métrica, para classificar o quão similar o padrão de uma parte da tela é em relação a outra. É bem complicado definir o que é padrão e o que é imagem, mas imagine que as pinceladas fortes de Van Gogh são um padrão.

Desse modo, a rede “aprende” a desenhar como Van Gogh ou outro artista.

Colocar uma foto normal na entrada, e voilá, temos uma foto estilizada.

Há alguns sites que permitem experimentos.

https://deepdreamgenerator.com/ ou https://dreamscopeapp.com

É difícil chegar a bons resultados.

Trilha sonora: Sweet Dreams – Eurythmics

Arnaldo Gunzi.

Ideias técnicas com uma pitada de filosofia

https://ideiasesquecidas.com/

𝗗𝗲𝗲𝗽𝗠𝗶𝗻𝗱

Quando se fala de Inteligência Artificial, vale a pena ficar de olho na empresa britânica DeepMind.

Ela alcançou notoriedade ao desenvolver o AlphaGo, programa computacional que derrotou o campeão mundial do jogo Go, em 2016. O Go é uma espécie de xadrez chinês, porém, bastante mais complexo.

A DeepMind foi adquirida pelo Google em 2014.

Atualmente, ela atua em identificação de doenças oculares, economia de energia nos servidores do Google, e a difícil área de dobramento de proteínas, entre outros.

Documentário AlphaGo x Lee Sedol

Site da empresa:

https://deepmind.com