QAOA em escala utilitária

Assista ao vídeo sobre QAOA em escala de serviços públicos de Olivia Lanes, ou abra o vídeo em uma janela separada em YouTube.

---

Visão geral da lição:

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

Nesta aula, vamos colocar a mão na massa com um exemplo em grande escala do problema do corte máximo, que é um problema famoso da teoria dos grafos que trata de como dividir da melhor forma um grafo em dois. Começaremos com um gráfico simples de cinco nós para desenvolver nossa intuição sobre como um computador quântico pode nos ajudar a resolver o problema e, em seguida, aplicaremos isso a uma versão do problema em escala industrial.

Esta aula servirá como uma visão geral da abordagem que adotamos para resolver esse problema. Esta não será uma explicação passo a passo do código. Juntamente com esta lição, porém, há um tutorial com código real que você pode executar para resolver o problema do corte máximo 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 terão nenhuma vantagem com essa tecnologia, pois os computadores clássicos já são muito bons em resolvê-los.

Os três casos de uso que estamos mais otimistas em explorar são:

1. simulação da natureza
2. processamento de dados com estrutura complexa
3. capital

Hoje, vamos nos concentrar no terceiro caso de uso, a otimização. Em um problema de otimização, geralmente estamos procurando o maior ou o 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 que nos interessa hoje é chamado de “max-cut”, e vamos resolvê-lo usando um algoritmo chamado Algoritmo Quântico de Otimização Aproximada (QAOA).

O que é o max-cut?

Começamos com um gráfico, que consiste em um conjunto de vértices (ou nós), alguns dos quais estão conectados por arestas. No problema, nos pedem para dividir os nós do grafo em dois subconjuntos, “cortando” as arestas que os conectam. Queremos encontrar a partição que maximize o número de arestas cortadas dessa forma — daí o nome “max-cut”

Por exemplo, a figura acima mostra um grafo de cinco nós com uma solução de corte máximo à direita. Ele corta cinco arestas, o que é o melhor que se pode conseguir com este grafo.

Como um grafo de cinco vértices é tão pequeno, não é muito difícil calcular o corte máximo de cabeça ou experimentando 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 aumenta — em parte porque o número de cortes possíveis a serem considerados cresce exponencialmente com o número de nós. E, a certa altura, isso se torna difícil até mesmo para supercomputadores, mesmo utilizando todos os algoritmos clássicos conhecidos.

Gostaríamos de encontrar uma maneira de resolver o problema do corte máximo para esses grafos maiores e mais complexos, pois o problema tem muitas aplicações práticas, incluindo a detecção de fraudes no setor financeiro, agrupamento de grafos, projeto de redes e análise de mídias sociais. O Max-cut é frequentemente encontrado como um subproblema dentro de uma abordagem específica para um problema maior. Portanto, é muito mais comum do que poderíamos ingenuamente imaginar.

---

A solução:

Agora, vamos explicar a abordagem que usamos para resolver o problema do corte máximo em um computador quântico. Vamos fazer isso usando um gráfico simples com cinco nós. Você pode acompanhar o passo a passo usando o tutorial do notebook Python. Após esse exemplo simples, o tutorial irá guiá-lo por um exemplo do problema em escala industrial.

A primeira etapa é criar nosso gráfico, definindo o número de nós e as bordas que conectam dois nós. Você pode fazer isso importando um pacote chamado rustworkx, conforme demonstrado no tutorial. O resultado será um gráfico parecido com este:

Usaremos a estrutura de padrões do Qiskit para encontrar as soluções de corte máximo para este grafo em nosso computador quântico.

Mapa

Precisamos mapear o problema em nosso computador quântico. Para fazer isso, vamos primeiro observar que a maximização do número de cortes em um gráfico pode ser matematicamente escrita 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 gráfico e $x_i$ e $x_j$ são 0 ou 1, dependendo do lado da partição em que cada nó está (um grupo é rotulado como "0" e o outro como "1"). Quando $x_i$ e $x_j$ estão no mesmo lado da partição, a expressão na soma é igual a zero. Quando eles estão em lados opostos, de modo que há um corte entre eles, a expressão é igual a um. Portanto, a maximização do número de cortes maximizará a soma.

Também podemos inverter a situação e procurar 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 assustador pensar em como passar de um gráfico 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 problema do corte máximo usando o algoritmo QAOA. Na metodologia QAOA, nosso objetivo final é obter um operador (ou, em outras palavras, um hamiltoniano) que será utilizado 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 fazer uma amostragem dessas soluções candidatas e, em seguida, avaliá-las usando a função de custo. Para isso, aproveitamos uma série de reformulações matemáticas, incluindo a notação Quadratic Unconstrained Binary Optimization (Otimização Binária Quadrática Sem Restrições), ou QUBO, que é uma maneira ú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 gráfico, aqui, cinco.

Para aplicar a 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 tenha a propriedade de que o estado fundamental corresponda ao valor mínimo da função. Portanto, para resolver nosso problema de otimização, tentaremos preparar o estado fundamental do $H$ em um computador quântico. Então, a amostragem desse estado produzirá a solução para $\min 𝑓(𝑥)$ com alta probabilidade.

Mapeamento para uma função de custo hamiltoniana

Como se vê, estamos com sorte, pois o problema QUBO está intimamente 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 o que precisamos fazer é uma simples mudança de variáveis:

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

Não abordaremos todas as etapas aqui, mas elas são explicadas no notebook anexo. No final, a minimização da expressão QUBO é a mesma que a minimização dessa expressão:

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

Reescrevendo um pouco mais, temos nossa função de custo Hamiltoniana, em que o mínimo da expressão representa o estado fundamental, Z é o operador Pauli Z 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 Pauli ZZ de dois locais, que podemos converter facilmente em portas de dois qubits em nosso circuito quântico. Terminaremos com seis objetos - ou cadeias de Pauli - em que cada um corresponde a cada uma das seis bordas do gráfico. Cada um dos cinco elementos em uma cadeia representa uma operação em um nó - a identidade, se o nó não estiver conectado a essa borda específica, e o operador Pauli Z, se estiver. No Qiskit, as cadeias de bits que representam os qubits são indexadas de trás para frente. Por exemplo, uma borda entre os nós 0 e 1 é codificada como IIIZZ, e uma borda entre 2 e 4 é codificada como ZIZII.

Construa o circuito quântico

Com nosso Hamiltoniano escrito em termos de operadores Pauli, estamos prontos para construir nosso circuito quântico, o que nos permite obter amostras de 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 de forma suficientemente lenta e com tempo suficiente, o estado final será o estado fundamental do Hamiltoniano final. O QAOA pode ser considerado como a versão discreta e trotterizada desse Algoritmo Adiabático Quântico, em que cada etapa do trotter representa uma camada do algoritmo QAOA. Portanto, em vez de evoluir de um estado para outro, em cada camada, alternaremos entre o Hamiltoniano da função de custo e o chamado Hamiltoniano "misturador", que abordaremos mais adiante nesta lição.

A vantagem do QAOA é que ele é mais rápido do que o algoritmo adiabático quântico, mas retorna soluções aproximadas em vez de soluções ideais. No limite em que o número de camadas chega ao infinito, o QAOA converge para o caso do QAA, mas é claro que isso é muito caro do ponto de vista computacional.

Para criar nosso circuito quântico, aplicaremos operadores alternados, parametrizados por $\gamma$ e $\beta$, que representarão a discretização da evolução do tempo.

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

1. o estado de teste inicial, em cinza, que é o estado básico do misturador, criado pela aplicação de uma porta Hadamard aplicada a cada qubit
2. a evolução da função de custo, que discutimos anteriormente, em roxo escuro
3. a evolução sob o Hamiltoniano do misturador, que ainda não abordamos, em roxo claro.

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

O Hamiltoniano do misturador é a simples soma das operações Pauli-X em cada nó do gráfico. O Qiskit permite que você use um operador de mixer diferente e personalizado, se desejar, mas usaremos o padrão aqui. Portanto, mais uma vez, você pode ver que, com o Qiskit, grande parte do trabalho é eliminado para nós, tornando trivial a criação do Hamiltoniano do misturador e do 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 uma discretização da evolução temporal do sistema, conforme descrito anteriormente. O padrão alternado vem da decomposição de Trotter e aproxima as funções exponenciais de matrizes não comutáveis. Em geral, quanto mais camadas ou etapas incluirmos, mais próximos estaremos da evolução em tempo contínuo, como no QAA, portanto, em teoria, mais preciso será o resultado. Mas, para este exemplo, começaremos com uma amostragem de apenas uma camada. Lembre-se de que o Hamiltoniano da função de custo e o misturador são parametrizados, mas ainda precisamos encontrar os valores ideais para $\gamma$ e $\beta.$

Otimizar

Embora o circuito que acabamos de criar pareça bastante simples e seja útil para construir um entendimento intuitivo, 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 possam ser executadas diretamente no hardware. As portas nativas são aquelas que podem ser executadas diretamente nos qubits. Diz-se que esses circuitos são 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 circuitos. Queremos ter certeza de que o circuito está otimizado para nossa finalidade.

Lembre-se de nossa lição 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.
• Desenrolamento das instruções no circuito quântico para as instruções nativas de hardware que o backend entende.
• Roteamento de quaisquer qubits no circuito que interagem com qubits físicos adjacentes uns aos outros.

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

No entanto, antes de fazer a transpilação, precisamos escolher em qual backend executaremos nosso circuito, pois o transpilador otimiza de forma diferente para processadores diferentes. Esse é mais um motivo pelo qual é importante usar um transpilador automatizado. Você não gostaria de passar pelo processo demorado de otimizar seu circuito manualmente, apenas para perceber que, na verdade, deseja executar seu circuito em um processador diferente com propriedades diferentes.

Passe o backend de sua preferência pela função de transpilador e especifique o nível de otimização. No tutorial, você selecionará o nível 3, que é o nível mais alto e mais completo.

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

Executar

Até o momento, transpilamos o circuito deixando os parâmetros gama e beta sozinhos, mas não é possível executar o circuito sem especificar esses parâmetros. No fluxo de trabalho do QAOA, os parâmetros ideais do QAOA são encontrados em um loop de otimização iterativo, em que executamos uma série de avaliações de circuitos e, em seguida, usamos um otimizador clássico para encontrar os parâmetros 𝛽 e 𝛾 ideais. No entanto, precisamos começar de algum lugar, portanto, fazemos uma estimativa inicial de $\gamma=\pi/2$ e $\beta=\pi.$

modos de execução

Agora, estamos quase prontos para executar o circuito - eu prometo! Mas, primeiro, é importante observar que você pode enviar seu trabalho de várias maneiras diferentes, que são chamadas de modos de execução.

• Modo de execução: É feita uma única chamada à primitiva Estimator ou Sampler sem um gerenciador de contexto. Os circuitos e as entradas são agrupados em blocos primitivos unificados (PUBs) e enviados como uma tarefa de execução ao computador quântico.

• Modo de lote: Um gerenciador de vários trabalhos para executar com eficiência um experimento composto por um conjunto de trabalhos independentes. Use o modo em lote para enviar vários trabalhos primitivos simultaneamente

• Modo de sessão: Uma janela dedicada para executar uma carga de trabalho com vários trabalhos. Isso permite que os usuários façam experiências com algoritmos variacionais de forma mais previsível e até mesmo executem vários experimentos simultaneamente, aproveitando o paralelismo na pilha. Use sessões para cargas de trabalho iterativas ou experimentos que exijam acesso dedicado. Consulte Executar trabalhos em uma sessão para obter exemplos.

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

Voltemos ao problema de otimização. Precisamos encontrar valores melhores de gama e beta do que apenas nossas primeiras suposições aproximadas. Faremos isso inserindo nossa função de custo e essas suposições iniciais em um otimizador scipy COBYLA.

Aqui você pode ver o valor da função de custo ao longo das iterações. Ele começa um pouco instável e sobe e desce, mas depois se estabiliza em um valor baixo. Usaremos os valores que o scipy encontrou e que correspondem à avaliação mais baixa da função de custo.

Agora que conseguimos reduzir nossa função de custo ao encontrar melhores valores para nossos parâmetros, vamos simular nosso circuito usando os novos valores que encontramos para gama e beta. Listei aqui os valores específicos que estou usando, mas lembre-se: quando você tentar fazer isso ou mesmo apenas executar novamente o mesmo notebook do tutorial, esses valores podem variar um pouco. Agora vamos executar nosso circuito otimizado com esses valores e encontrar nossa solução candidata para o problema do corte máximo.

No estágio de pós-processamento, analisaremos os dados e exibiremos esses resultados para ver se nosso algoritmo quântico encontrou as soluções corretas.

Pós-processamento

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

As cadeias de bits representam como cada um dos nós foi dividido em dois grupos (rotulados como "0" e "1") pelo corte. Deve haver quatro soluções que forneçam o valor máximo de corte de bordas. Esses quatro são mostrados em roxo. Você pode ver imediatamente que quatro soluções são muito mais prováveis do que qualquer uma das outras. A solução mais alta e, portanto, mais provável da cadeia de bits é 0,1,0,1,1. (Lembre-se: a ordem dos qubits está invertida nas cadeias de bits do gráfico!)

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

Portanto, esta é, de fato, uma solução de corte máximo. Mas não é o único! Devido à simetria deste gráfico, há várias soluções corretas. Em vez de os nós 0 e 3 ficarem dentro do corte, poderíamos incluir os nós 2 e 4. Você pode ver que tudo o que precisei fazer foi girar o meu corte para incluir esses novos pontos. O número de arestas cortadas continua sendo cinco. Verifica-se que existem, no máximo, quatro soluções de corte, já que cada uma das duas soluções que observamos também tem um par “oposto”, em que os nós roxos são cinza e os nós cinza são roxos — assim, o corte permanece o mesmo, mas cada nó, na prática, troca de lado na partição.

Vamos dar uma olhada novamente no histograma e nas quatro soluções mais prováveis por um momento. Idealmente, seriam cada uma das quatro soluções de corte máximo verdadeiras. O problema é que o algoritmo, na verdade, não identificou a quarta e última solução como uma das quatro respostas mais prováveis. Era a quinta opção mais provável. A quarta solução identificada pelo algoritmo está incorreta — se você a desenhasse, veria que ela tem apenas quatro cortes.

Mas lembre-se: esse é um algoritmo aproximado. Ele não é infalível e não está correto 100% do tempo. Você precisa empregar parte de seu próprio conhecimento e compreensão para verificar a sanidade das soluções.

Esse erro pode ocorrer em vários lugares:

1. Pode ser a natureza aproximada do próprio algoritmo e o pequeno número de camadas que empreguei.
2. Pode ser um erro de amostragem finito, que pode ser reduzido se eu aumentar o número de fotos em meu experimento.
3. Também pode ser um erro de leitura, já que a quarta solução real está apenas um bit fora do padrão.

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

No entanto, não podemos esquecer que havia 32 sequências de bits possíveis e que as quatro soluções reais estavam entre as cinco melhores candidatas. E só usamos duas camadas para chegar a essa conclusão. Em geral, se quiséssemos aumentar nossas chances de encontrar o melhor corte máximo todas as vezes, poderíamos aumentar a profundidade da camada. Isso envolve algumas sutilezas, mas isso fica para uma aula posterior.

---

Em escala comercial

Agora que você já teve uma ideia de como é resolver um pequeno problema de corte máximo em um computador quântico, desafio você a fazer isso em grande escala. Siga o tutorial no link para ver quantos cortes é possível obter em um grafo de 125 nós.