QAOA em escala de utilidade

Assista ao vídeo sobre QAOA em escala de utilidade por Olivia Lanes, ou abra o vídeo em uma janela separada no YouTube.

Visão geral da aula:

Até agora neste curso, esperamos ter fornecido a você uma base sólida do framework e das ferramentas necessárias para resolver problemas em escala de utilidade em um computador quântico. Agora, finalmente vamos ver essas ferramentas em ação.

Nesta aula, vamos colocar a mão na massa com um exemplo em escala de utilidade do problema Max-Cut, que é um problema famoso na teoria dos grafos envolvendo como particionar melhor um grafo em dois. Começaremos com um grafo simples de cinco nós para desenvolver nossa intuição sobre como um computador quântico pode nos ajudar a resolver o problema, e depois aplicaremos isso a uma versão em escala de utilidade do problema.

Esta aula servirá como uma visão geral ampla da abordagem que usamos para resolver esse problema. Não será um passo a passo de código. Acompanhando esta aula, porém, há um tutorial com código real que você pode executar para resolver o problema Max-Cut em um computador quântico.

O Problema

Como lembrete, nem todos os problemas computacionais são adequados para a computação quântica. Os "problemas fáceis" não vão ganhar nenhuma vantagem com essa tecnologia porque os computadores clássicos já são perfeitamente capazes de resolvê-los.

Os três casos de uso sobre os quais somos mais otimistas de explorar são:

1. simular a natureza
2. processar dados com estrutura complexa
3. otimização

Hoje, vamos nos focar no terceiro caso de uso: otimização. Em um problema de otimização, geralmente estamos buscando o maior ou menor valor possível para uma determinada função. A dificuldade de encontrar esses extremos com métodos clássicos pode aumentar exponencialmente à medida que o tamanho do problema cresce.

O problema de otimização de interesse hoje é chamado de Max-Cut, que vamos resolver usando um algoritmo chamado Quantum Approximate Optimization Algorithm (QAOA).

O que é Max-Cut?

Começamos com um grafo, que consiste em uma coleção de vértices (ou nós), alguns dos quais estão conectados por arestas. No problema, somos solicitados a dividir os nós do grafo em dois subconjuntos "cortando" as arestas que os conectam. Queremos encontrar a partição que maximiza o número de arestas que são cortadas dessa forma — daí o nome "Max-Cut."

Por exemplo, a figura acima mostra um grafo de cinco nós com uma solução Max-Cut à direita. Ela corta cinco arestas, que é o melhor que se pode fazer com esse grafo.

Como um grafo de cinco nós é tão pequeno, não é muito difícil calcular o Max-Cut mentalmente ou tentando alguns cortes em um pedaço de papel. Mas como você pode imaginar, o problema se torna cada vez mais difícil à medida que o número de vértices cresce — em parte porque o número de cortes possíveis a considerar cresce exponencialmente no número de nós. E em um certo ponto, isso se torna difícil até mesmo para supercomputadores com quaisquer algoritmos clássicos conhecidos.

Gostaríamos de uma forma de resolver o problema Max-Cut para esses grafos maiores e mais complicados, porque o problema tem muitas aplicações práticas, incluindo detecção de fraudes em finanças, agrupamento de grafos, design de redes e análise de redes sociais. O Max-Cut é frequentemente encontrado como subproblema dentro de uma abordagem específica para um problema maior. Portanto, é muito mais comum do que poderíamos ingenuamente pensar.

A Solução

Agora, vamos percorrer a abordagem que usamos para resolver o problema Max-Cut em um computador quântico. Faremos isso com um grafo simples de cinco nós. Você pode acompanhar usando o tutorial em notebook Python. Depois desse exemplo simples, o tutorial vai guiá-lo por um exemplo em escala de utilidade do problema.

O primeiro passo é criar nosso grafo definindo o número de nós e as arestas que conectam dois nós. Você pode fazer isso importando um pacote chamado rustworkx, como demonstrado no tutorial. O resultado será um grafo que se parece com isso:

Vamos usar o framework de padrões Qiskit para encontrar as soluções Max-Cut para esse grafo em nosso computador quântico.

Mapear

Precisamos mapear o problema no nosso computador quântico. Para fazer isso, vamos primeiro notar que maximizar o número de cortes em um grafo pode ser matematicamente escrito como:

$$\max\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {x_i + x_j - 2x_ix_j}$$

Onde $i$ e $j$ são nós no grafo, e $x_i$ e $x_j$ são 0 ou 1, dependendo de qual lado da partição cada nó está (um grupo é rotulado "0" e um é rotulado "1"). Quando $x_i$ e $x_j$ estão no mesmo lado da partição, a expressão na soma é igual a zero. Quando estão em lados opostos, ou seja, há um corte entre eles, a expressão é igual a um. Portanto, maximizar o número de cortes vai maximizar a soma.

Podemos também virar isso ao contrário e buscar o mínimo multiplicando cada um dos valores por menos um.

$$\min\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {2x_ix_j - x_i - x_j}$$

Agora estamos prontos para mapear. Pode ser um pouco intimidador pensar em como ir de um grafo como o que acabamos de desenhar para um circuito quântico. Mas vamos dar um passo de cada vez.

Lembre-se, vamos tentar resolver o Max-Cut usando o QAOA. Na metodologia QAOA, em última análise queremos ter um operador (ou, em outras palavras, um Hamiltoniano) que será usado para representar a função de custo do nosso algoritmo híbrido, bem como um circuito parametrizado (o ansatz) que usamos para representar possíveis soluções para o problema.

QUBO

Podemos amostrar essas soluções candidatas e avaliá-las usando a função de custo. Para fazer isso, aproveitamos uma série de reformulações matemáticas, incluindo a notação de Otimização Binária Irrestrita Quadrática — ou QUBO, na sigla em inglês — que é uma forma útil de codificar problemas de otimização combinatória. No QUBO, queremos encontrar:

$$\min\limits_{x\in\{0,1\}^n} x^TQx$$

onde $Q$ é uma matriz $n\times n$ de números reais, $n$ corresponde ao número de nós em nosso grafo, aqui, cinco.

Para aplicar o QAOA, precisamos formular nosso problema como um Hamiltoniano — que é uma função ou matriz que representa a energia total de um sistema. Especificamente, queremos criar um Hamiltoniano de função de custo que tem a propriedade de que o estado fundamental corresponde ao valor mínimo da função. Portanto, para resolver nosso problema de otimização, vamos tentar preparar o estado fundamental de $H$ em um computador quântico. Então, amostrar desse estado vai produzir a solução para $\min 𝑓(𝑥)$ com alta probabilidade.

Mapeando para um Hamiltoniano de função de custo

Acontece que temos sorte, porque o problema QUBO está muito relacionado e é, na verdade, computacionalmente equivalente a um dos Hamiltonianos mais famosos e onipresentes da física: o Hamiltoniano de Ising.

Para escrever o problema QUBO como o Hamiltoniano de Ising, tudo que precisamos fazer é uma simples mudança de variáveis:

$$x_i = \frac{1-z_i}{2}.$$

Não vamos percorrer todos os passos aqui, mas eles são explicados no notebook em anexo. No final, a minimização da expressão QUBO é a mesma que a minimização desta expressão:

$$\min_{x\in\{0,1\}^n} x^TQx\Longleftrightarrow \min_{z\in\{-1,1\}^n}z^TQz + b^Tz$$

Reescrevendo novamente um pouco e temos nosso Hamiltoniano de função de custo, onde o mínimo da expressão representa o estado fundamental, Z é o operador Z de Pauli, e $b$ é um coeficiente escalar real:

$$H_C=\sum_{ij}Q_{ij}Z_iZ_j + \sum_i b_i Z_i$$

Agora que temos nosso Hamiltoniano, precisamos reescrevê-lo em termos de operadores ZZ de Pauli de dois locais, que podemos facilmente converter em portas de dois qubits no nosso circuito quântico. Acabaremos com seis objetos — ou strings de Pauli — onde cada um corresponde a cada uma das seis arestas no grafo. Cada um dos cinco elementos em uma string representa uma operação em um nó — a identidade se o nó não estiver conectado a essa aresta em particular, e o operador Z de Pauli se estiver. No Qiskit, as bitstrings que representam qubits são indexadas ao contrário. Por exemplo, uma aresta entre os nós 0 e 1 é codificada como IIIZZ, e uma aresta entre 2 e 4 é codificada como ZIZII.

Construir o circuito quântico

Com nosso Hamiltoniano escrito em termos de operadores de Pauli, estamos prontos para construir nosso circuito quântico, que nos permite amostrar boas soluções usando um computador quântico:

O algoritmo QAOA se inspira no Teorema Adiabático, que afirma que se começarmos no estado fundamental de um Hamiltoniano dependente do tempo, se o Hamiltoniano evoluir devagar o suficiente, e dado tempo suficiente, o estado final será o estado fundamental do Hamiltoniano final. O QAOA pode ser pensado como a versão discreta e trotterizada desse Algoritmo Adiabático Quântico, onde cada passo de Trotter representa uma camada do algoritmo QAOA. Então, em vez de evoluir de um estado para o outro, em cada camada vamos alternar entre o nosso Hamiltoniano de função de custo e um Hamiltoniano chamado "misturador", que vamos cobrir mais adiante nesta aula.

A vantagem do QAOA é que é mais rápido do que o algoritmo adiabático quântico, mas retorna soluções aproximadas em vez das ótimas. No limite onde o número de camadas vai ao infinito, o QAOA converge para o caso do QAA, mas, claro, isso é muito computacionalmente caro.

Para criar nosso circuito quântico, vamos aplicar operadores alternados, parametrizados por $\gamma$ e $\beta$, que vão representar a discretização da evolução temporal.

Portanto, as três partes principais do circuito QAOA são:

1. o estado de teste inicial, em cinza, que é o estado fundamental do misturador, criado aplicando uma porta Hadamard em cada qubit
2. a evolução da função de custo, que já discutimos anteriormente, em roxo escuro
3. a evolução sob o Hamiltoniano misturador, que ainda não cobrimos, em roxo claro.

Nosso Hamiltoniano inicial é chamado de Misturador porque seu estado fundamental é a superposição de todas as possíveis bitstrings de interesse: portanto, impondo uma mistura de todas as soluções possíveis no início.

O Hamiltoniano misturador é a simples soma de operações de Pauli-X em cada nó do grafo. O Qiskit permite que você use um operador misturador personalizado diferente, se desejar, mas vamos usar o padrão aqui. Então, novamente, você pode ver que com o Qiskit, muito do trabalho é removido para nós, tornando trivial descobrir o Hamiltoniano misturador e o estado inicial. O único trabalho que tivemos que fazer foi encontrar a função de custo.

Cada iteração desses operadores é chamada de camada. Essas camadas podem ser vistas como discretização da evolução temporal do sistema, como descrito anteriormente. O padrão alternado vem da decomposição de Trotter e aproxima as funções exponenciais de matrizes que não comutam. Em geral, quanto mais camadas ou passos incluirmos, mais próximos estaremos da evolução contínua do tempo, como no QAA, então em teoria, quanto mais preciso o resultado. Mas para este exemplo, começaremos apenas amostrando com uma camada. Lembre-se, tanto o Hamiltoniano de função de custo quanto o misturador são parametrizados; ainda precisamos encontrar valores ótimos para $\gamma$ e $\beta$.

Otimizar

Embora o circuito que acabamos de criar pareça bastante simples e seja útil para construir uma compreensão intuitiva, lembre-se de que o chip quântico não entende o que é a porta QAOA. Precisamos transformar isso em uma série de portas "nativas" de um e dois qubits que podem ser executadas diretamente no hardware. Portas nativas são aquelas que podem ser executadas diretamente nos qubits. Tais circuitos são ditos escritos na Arquitetura de Conjunto de Instruções (ISA) do backend.

A biblioteca Qiskit oferece uma série de passagens de transpilação que atendem a uma ampla gama de transformações de circuito. Queremos ter certeza de que o circuito está otimizado para nosso propósito.

Lembre-se da nossa aula anterior que o processo de transpilação envolve várias etapas:

• Mapeamento inicial dos qubits no circuito (ou seja, variáveis de decisão) para qubits físicos no dispositivo.
• Desdobramento das instruções no circuito quântico para as instruções nativas do hardware que o backend entende.
• Roteamento de quaisquer qubits no circuito que interagem para qubits físicos que são adjacentes uns aos outros.

E como sempre, mais detalhes sobre isso podem ser encontrados na documentação.

Antes de transpilar, porém, precisamos escolher em qual backend executaremos nosso circuito, pois o transpilador otimiza de forma diferente para diferentes processadores. Esta é mais uma razão pela qual é importante usar um transpilador automatizado — você não vai querer passar pelo processo demorado de otimizar seu circuito manualmente, apenas para perceber que na verdade quer executar seu circuito em um processador diferente com propriedades diferentes.

Passe seu backend escolhido pela função do transpilador e especifique seu nível de otimização. No tutorial, você vai selecionar o nível 3, que é o mais alto e mais completo.

E com isso, temos um circuito transpilado que está pronto para ser executado no hardware!

Executar

Até agora, transpilamos o circuito deixando os parâmetros gama e beta de lado — mas não podemos realmente executar o circuito sem especificar esses parâmetros. No fluxo de trabalho QAOA, os parâmetros QAOA ótimos são encontrados em um loop de otimização iterativo, onde executamos uma série de avaliações de circuito e usamos um otimizador clássico para encontrar os parâmetros $\beta$ e $\gamma$ ótimos. No entanto, precisamos começar em algum lugar, então fazemos uma estimativa inicial de $\gamma=\pi/2$ e $\beta=\pi$.

Modos de Execução

Agora, estamos quase prontos para executar o circuito — prometo! Mas primeiro, é importante notar que você pode enviar seu job de várias formas diferentes, que são chamadas de modos de execução.

• Modo job: Uma única solicitação primitiva do estimator ou do sampler é feita sem um gerenciador de contexto. Circuitos e entradas são empacotados como blocos unificados primitivos (PUBs) e enviados como uma tarefa de execução no computador quântico.

• Modo batch: Um gerenciador de múltiplos jobs para executar eficientemente um experimento composto por um conjunto de jobs independentes. Use o modo batch para enviar múltiplos jobs primitivos simultaneamente.

• Modo sessão: Uma janela dedicada para executar uma carga de trabalho com múltiplos jobs. Isso permite que os usuários experimentem com algoritmos variacionais de forma mais previsível, e até mesmo executem múltiplos experimentos simultaneamente, aproveitando o paralelismo na pilha. Use sessões para cargas de trabalho iterativas ou experimentos que requerem acesso dedicado. Veja Executar jobs em uma sessão para exemplos.

Para um experimento QAOA, uma sessão seria uma boa escolha se você tiver acesso a ela, pois precisamos amostrar nosso circuito várias vezes com diferentes valores de parâmetros para encontrar o ótimo.

De volta ao problema de otimização. Precisamos encontrar valores melhores de gama e beta do que nossas estimativas iniciais grosseiras. Faremos isso plugando nossa função de custo e essas estimativas iniciais em um otimizador scipy COBYLA.

Aqui você pode ver o valor da função de custo ao longo das iterações. Começa um pouco caótico e sobe e desce, mas depois se estabiliza em um valor baixo. Vamos usar os valores que o scipy encontrou que correspondem à avaliação mais baixa da função de custo.

Agora que conseguimos reduzir nossa função de custo encontrando melhores valores dos nossos parâmetros, vamos executar nosso circuito usando os novos valores que encontramos para gama e beta. Listei os valores específicos que estou usando aqui, mas lembre-se, quando você tentar isso ou mesmo apenas reexecutar o mesmo notebook tutorial, esses valores podem mudar um pouco. Agora vamos executar nosso circuito otimizado com esses valores e encontrar nossa solução candidata para o nosso problema Max-Cut.

Na etapa de pós-processamento, vamos analisar os dados e exibir esses resultados para ver se nosso algoritmo quântico encontrou as soluções corretas.

Pós-processar

Agora vamos traçar um histograma dos dados para ver a solução final:

As bitstrings representam como cada um dos nós foi particionado em dois grupos (rotulados "0" e "1") pelo corte. Deve haver quatro soluções que todas dão o valor máximo de arestas cortadas. Essas quatro são mostradas em roxo. Você pode ver imediatamente que 4 soluções são muito mais prováveis do que qualquer uma das outras. A bitstring mais alta e, portanto, mais provável é 0,1,0,1,1. (Lembre-se — a ordem dos qubits é invertida nas bitstrings do gráfico!)

A partir desse gráfico, podemos pegar a bitstring mais provável e representá-la como um grafo particionado, com o corte passando por cinco arestas:

Então, esta é de fato uma solução Max-Cut. Mas não é a única! Por causa da simetria desse grafo, existem múltiplas soluções corretas. Em vez de ter os nós 0 e 3 dentro do corte, poderíamos ter os nós 2 e 4 incluídos. Você pode ver que tudo que precisava fazer era girar meu corte para incluir esses novos pontos. O número de arestas cortadas continua sendo cinco. Acontece que há quatro soluções de max-cut, já que cada uma das duas soluções que notamos também tem uma parceira "oposta", onde os nós roxos são cinzas e os nós cinzas são roxos — então o corte permanece o mesmo, mas cada nó efetivamente troca para o lado oposto da partição.

Vamos olhar novamente para o histograma e as quatro soluções mais prováveis por um momento. Idealmente, cada uma seria uma das quatro soluções Max-Cut verdadeiras. O problema é que o algoritmo na verdade não identificou a quarta e última solução como sendo uma das 4 respostas mais prováveis. Era a quinta mais provável. A quarta solução que o algoritmo identificou está incorreta — se você a desenhasse, veria que a solução tem apenas quatro cortes.

Mas lembre-se: este é um algoritmo aproximado. Não é infalível e não está correto 100% do tempo. Você tem que usar seu próprio conhecimento e entendimento para verificar as soluções.

Esse erro pode surgir de vários lugares:

1. Pode ser a natureza aproximada do algoritmo em si e o pequeno número de camadas que empreguei.
2. Pode ser um erro de amostragem finita; isso poderia ser reduzido se eu aumentasse o número de shots no meu experimento.
3. Pode também ser um erro de leitura, já que a quarta solução real difere em apenas um bit.

Esse tipo de análise de erros é o que é necessário para se tornar um praticante de computação quântica. Você precisa entender o desempenho do hardware e como isso pode contribuir para certos tipos de erros e como corrigi-los.

No entanto, não vamos esquecer que havia 32 possíveis bitstrings, e que as quatro soluções reais estavam incluídas nos cinco melhores candidatos. E usamos apenas duas camadas para encontrar isso. Em geral, se quiséssemos aumentar nossas chances de encontrar o melhor Max-Cut toda vez, poderíamos aumentar a profundidade das camadas. Há algumas sutilezas nisso, mas isso é para uma aula posterior.

Em escala de utilidade

Agora que você teve um gostinho do processo de resolver um pequeno problema Max-Cut em um computador quântico, eu o desafio a fazer isso em escala. Acompanhe no tutorial vinculado para ver quantos cortes você consegue obter em um grafo de 125 nós.