IBM Quantum Challenge (Fall 2020)
Por: Arnaldo Gunzi (Gestor de projetos analíticos e de inovação na Klabin).
A seguir, um relato completo sobre a minha participação no IBM Quantum Challenge — Outono de 2020.
Este é um desafio aberto a todos, realizado uma vez por ano ou mais, e é uma oportunidade excelente para aprender sobre este tema que irá disruptar o mundo em futuro próximo.
Introdução — Algoritmo de Grover
O tema foi utilizar o algoritmo de Grover e memória quântica (QRAM) para resolver alguns desafios, no Qiskit (linguagem de programação quântica da IBM).
O Grover é uma das aplicações práticas da computação 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. É aí que entra o potencial prático do algoritmo, porque problemas de otimização são onipresentes na indústria, logística e comércio.
Porém, há uma limitação teórica. Há um ganho quadrático do Grover em relação à computação clássica. Um ganho quadrático não é muita coisa, porque problemas dessa natureza escalam facilmente para milhões de variáveis e restrições. 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?
O desafio foi dividido em três semanas, com exercícios sendo liberados aos poucos. A primeira semana foi fácil, a segunda foi média, a terceira, muito difícil.
Semana 1 — Aquecimento
A primeira semana envolveu noções básicas de circuito. Assim como em computação clássica, os blocos fundamentais de computação são portas lógicas quânticas.
Em computação clássica, os bits podem assumir valor zero ou um.
Já em computação quântica, o qubit pode assumir 0, 1, ou qualquer sobreposição entre esses dois valores, segundo algumas regras.
Em computação clássica, o half adder e o full adder são blocos computacionais, feitos de portas simples, e utilizados para fazer aritmética.
O exercício foi criar um full adder, utilizando portas lógicas quânticas. A resposta não é muito diferente da computação clássica, mas a diferença é fazer isso no Qiskit, linguagem da IBM.
O segundo exercício envolveu um algoritmo de Grover simples, e a questão era saber em o número de passos ótimo para maximizar a chance de encontrar a solução correta.
Semana 2 — Apagar luzes
O terceiro exercício foi relativo a uma aplicação do algoritmo de Grover para um problema de otimização.
Por enquanto, este ainda só pode ser utilizado em problemas pequenos, e mesmo assim, já deu um trabalhão enorme.
Especificamente, é o problema do Lights-out.
Um tabuleiro 3x3 começa com algumas luzes acesas. Quando eu toco em uma célula, a célula tocada, os vizinhos acima, abaixo, direita e esquerda trocam de sinal (de aceso para apagado e vice-versa).
Qual a sequência de passos para apagar todo o tabuleiro, utilizando o algoritmo de Grover?
Não vou entrar em detalhes do circuito, mas imagine que eu tenho 9 variáveis de decisão (tocar em cada uma das células). Cada variável vai gerar uma ação (apagar ou acender os vizinhos). Portanto, a solução consiste em colocar as variáveis em superposição, testando de uma só vez todas as combinações possíveis, e um detector para amplificar somente a solução correta.
O próximo exercício utilizava o mesmo tabuleiro, porém 4 deles ao mesmo tempo!
Para tal, há diversas soluções possíveis (como rodar um de cada vez), mas o exercício pedia para usar o conceito de memória quântica (QRAM).
É um conceito análogo ao do Grover. Utilizo dois qubits para representar os 4 endereços, coloco os qubits em sobreposição, e para cada combinação de endereços, atrelo um dos circuitos a serem testados.
Esse deu bastante trabalho, mas a minha resposta foi aceita no final. Note que fui mais rápido que a maioria dos outros participantes. À medida que esses foram completando o exercício, o percentual foi caindo.
Semana 3 — Asteroides
O quinto desafio foi bastante complicado. Envolvia usar o Grover para resolver um problema de otimização, batizado de “asteroides”.
É dado um tabuleiro 4x4, e seis estrelas dispostas aleatoriamente neste.
Qual o número mínimo de raios verticais ou horizontais para cobrir todos os asteroides?
Além disso, imagine fazer isso para 16 ao mesmo tempo! O objetivo era encontrar o tabuleiro que necessitava de 4 passos.
Uma limitação adicional: no máximo, utilizar 28 qubits.
A forma de atacar o problema é semelhante à semana anterior: QRAM para codificar o endereço. Para cada endereço, um Grover, adicionalmente um somador para contar o número de raios utilizados, um detector (utilizando o velho truque do kickback), uncomputar tudo.
Utilizei:
- 4 qubits para codificar o endereço
- 6 qubits para representar os 6 asteroides (uma opção seria representar cada uma das 16 casas do tabuleiro, porém, não iria caber em 28 qubits)
- 8 qubits para representar os 8 movimentos possíveis (4 horizontais e 4 verticais)
- 4 qubits para criar um circuito somador
- 2 qubits para fazer kickback (um para a QRAM e outro para o Grover)
- 4 qubits auxiliares (entram para ajudar na computação)
Aí, entram as dificuldades. Enquanto no lights-out havia uma única resposta correta, nos asteroides, é possível ter várias respostas corretas (que cobrem todos os asteroides).
Algumas limitações do algoritmo de Grover ficam evidentes. O número ótimo de passos deste depende do número de soluções. Mas, se eu sei o número de soluções, para que usar o Grover para encontrar a solução? É um problema circular, que pode ser resolvido por aproximações — porém, se eu tiver que rodar o Grover várias vezes, não há ganho…
Isso sem entrar na polêmica do oráculo: construir um oráculo que sabe a resposta pode ser mais “caro” que utilizar o Grover. É uma boa discussão, para outro dia.
Outro problema: é possível “enganar” o sistema da IBM. Digamos, é bem fácil resolver o problema com computação clássica, e criar um circuito quântico que dê a resposta correta. Não tem como detectar isso de forma automática, e não duvido que muita gente tenha feito, mesmo que inadvertidamente.
Por isso mesmo, a IBM colocou que irá verificar, manualmente, as 10 respostas com melhor colocação após o desafio.
Bom, em resumo, fiquei a semana inteira varando noites para rodar o circuito acima, mas, por algum motivo, ele não funcionou muito bem. Finalizei com 4 de 5 exercícios.
Um desafio deste tipo, com tamanha qualidade, não seria possível anos atrás, onde eventos deste tipo eram presenciais. Hoje, temos condições de estar em contato com o que há de mais avançado no mundo, encarando inúmeras pessoas de altíssimo nível — americanos, europeus, sul-coreanos, indianos, japoneses.
Vi poucos brasileiros no cenário, o que é uma pena. Vamos formar uma comunidade, a fim de estudar o tema?
Agradeço a IBM pela oportunidade de aprender um pouco mais sobre este nascente ramo do conhecimento.
