Aplicando BQM – Exemplos Introdutórios

Formulação do problema

Problemas de Otimização resolvidos usando solucionadores e Kit de desenvolvimento Ocean da D-Wave são geralmente formulados como problemas de variável Binária chamados BQM (Binary Quadratic Models). Nesse tipo de formulação há duas formas equivalentes de expressar a função Objetivo ou Energia do problema que queremos minimizar : QUBO (Quadratic Unconstrained Binary Optimization) e Ising Model.

Em geral um BQM apresenta uma forma quadrática e suas variáveis assumem valores binários como na expressão

nesse caso, e são os coeficientes lineares associados a e da expressão e é o coeficiente quadrático que acopla as variáveis binárias e .

Na formulação QUBO os valores binários que as variáveis assumem são 0 (Não, False) ou 1 (Sim, True) e a expressão matemática que representa esse modelo é

a função acima está na forma matricial, é uma matriz triangular superior, os termos na diagonal principal representam os coeficientes lineares associados a e os termos acima da diagonal principal, com são os coeficientes de acoplamento entre as variáveis e , típico de um problema BQM. Na forma escalar a equação para o QUBO fica

Por outro lado, a formulação do Modelo de Ising, inspirada no modelo que é estudado na mecânica estatística, possui variáveis binárias que assumem valores -1 (spin down ) +1 (spin up ) e uma função objetivo escrita seguindo esse modelo geralmente apresenta as seguinte forma

nessa equação são os coeficientes lineares, os os coeficientes de acoplamento e são as variáveis binárias.

 

Minor Embeddig

Podemos representar uma função Objetivo como as que foram descritas na seção anterior em grafos simples. Grafos são um conjunto formado por vértice e arestas . Dada uma função objetivo na forma de um BQM, podemos associar aos vértices os coeficientes lineares e as arestas associamos os coeficientes quadráticos. Por simplicidades consideremos a seguinte função objetivo

o grafo que retém  as informações sobre essa função é

Finalmente com um processo chamado Minor Embedding podemos usar grafos para mapear uma função objetivo nos qubits que compõe o computador quântico da D-Wave, de acordo é claro com a topologia de cada dispositivo (2000Q ou Advantage).

A seguir são apresentados exemplos simples dessas duas formulações:

Problema de Satisfatibilidade (SAT)

Neste tipo de problema todas as variáveis assumem valores binários 0 ou 1, podemos também associar aos estados “Spin down” e “Spin up”.  Problemas desse tipo oferecem respostas para perguntas do tipo “Este pacote deveria ser enviado neste caminhão?”

Consideremos a forma normal conjuntiva em duas variáveis:

essa forma é satisfeita se as disjunções forem satisfeitas. Se 

se 

Para esse caso podemos usar um modelo QUBO em duas variáveis para escrever a função objetivo

com duas variáveis podemos fazer uma tabela que representa os possíveis estados

Note que os estados que satisfazem o problema da forma normal  conjuntiva são os estados 1 e 4, portanto a função objetiva para esse problema deve favorecer estes casos, isto é, seu valor deve ser mínimo para os estados 1 e 4 enquanto que para os outros seu valor deve ser maior.

Na construção da função objetivo primeiramente notamos que para o estado 0 a função obtém o valor 0, ou seja, já está satisfeita para qualquer um dos coeficientes e . Com os estados 2 e 3 podemos definir tanto quanto como um valor positivo, por exemplo :. Por último o estado 4 fixa o valor do coeficiente de acoplamento em e dessa forma a função objetivo na forma de um QUBO que representa esse problema é

e a tabela com seus valores e grafo associado

Exemplo formulação de Ising

Considere agora duas variáveis binárias e e queremos que o valor de seja idêntico ao de . O vínculo que expressa esse problema é:

a essa expressão podemos construir uma tabela com os possíveis estados

Usando a formulação de Ising a função Objetivo para duas variáveis fica

Com a equação do vínculo podemos reformular o problema de minimização da seguinte maneira

Como as variáveis assumem valores -1 ou +1 então

Aqui tomamos o quadrado para que os estados de menor valor sejam favorecidos. Dessa expressão podemos minimizar apenas o termo , pois estamos interessados nos estados de menor energia. Antes disso notemos que a diferença entre os estados entre a energia dos estados fundamentais e de maior energia é 4. Podemos definir o gap de energia entre esses dois estados igual a 1 e fazendo isso a função objetiva do problema se torna:

cujo grafo associado é