Resolvendo o Problema do Caixeiro Viajante via Computação Quântica Adiabática

Problema do Caixeiro Viajante

O Problema do Caixeiro Viajante, do inglês Traveling Salesman Problem (TSP) é um clássico problema quando se estuda otimização combinatória e teoria de grafos. Suas origens remontam ao século XIX com as contribuições dos matemáticos Sir William R. Hamilton e Thomas Penyngton Kirkman a uma área da matemática conhecida como cálculo Icosiano, em particular um problema dentro desse estudo que consistia em encontrar o menor caminho entre os vértices sobre a superfície de um dodecaedro sólido que na atualidade é conhecido como jogo Icosiano, tal caminho é conhecido como ciclo Hamiltoniano.

O TSP possui diversas formulações, uma das primeiras definições do problema foi elaborada pelo matemático Karl Menger na década de 30 sob o nome de Menssenger Problem que é um problema que pode ser reduzido como o caixeiro viajante, no caso é uma variação do TSP. Em geral pode-se enunciar o problema do caixeiro viajante da seguinte através da seguinte pergunta:

Dado um conjunto de cidades, qual o menor caminho a ser percorrido de modo que todas as cidades sejam visitadas uma única vez, retornando a cidade inicial?

A atração por esse problema é notada por sua interdisciplinaridade e importância econômica com diversas, com uma gama de aplicações em diversas áreas, principalmente em setores do ramo da logística. Por exemplo uma empresa de entregas tem alguns endereços para enviar os produtos e deseja fazer isso da melhor forma possível de forma que seja economizado tempo e custos de viajem no processo.

Uma das características fundamentais do TSP é que esse problema faz parte da classe de problemas computacionais NP-Difícil, ou seja, os algoritmos exatos existentes o resolvem em tempo determinístico não polinomial, geralmente em tempo que cresce fatorialmente ou exponencialmente com o aumento da dimensão do problema. Por exemplo um dos primeiros métodos desenvolvidos para resolver o problema do caixeiro viajante é chamado de Método exaustivo ou força bruta. Esse algoritmo consiste em calcular todas as combinações de rotas e então fazer comparações entre cada uma para obter aquela que corresponde a rota de menor caminho, no fim do dia, para um problema com N cidades a serem visitadas número de rotas é N!, dessa forma o problema calcula a solução em um tempo na ordem de O melhor método exato que existe atualmente apresenta complexidade de tempo de solução exponencial, da ordem , esse é devido ao algoritmo de programação dinâmica Held-Karp. Mesmo com o melhor método exato resolver o problema em um computador pessoal é computacionalmente custoso a medida que as dimensões do problema aumentam, dessa forma uma outra classe de algoritmos podem ser empregados para tentar resolver problemas NP, os chamados métodos heurísticos.

Os algoritmos heurísticos são métodos empregados quando se deseja uma solução aproximada. Existem diversos algoritmos que dão uma boa aproximação para resolver o problema do caixeiro viajante, por exemplo temos o annealing simulado, algoritmos genéticos, algoritmo do guloso, etc… Outra abordagem heurística que pode ser explorada é oferecida pela computação quântica adiabática.

Computação Quântica Adiabática

A computação quântica adiabática é um modelo alternativo à computação quântica via portas lógicas quânticas. O modelo de portas lógicas foi um dos primeiros modelos da computação quântica a ser idealizado, nesse tipo de computação quântica se tem um controle sobre a evolução do sistema de qubits. É definido um circuito lógico em que a evolução temporal dos qubits pode ser controlada através das chamadas portas lógicas quânticas que no contexto da mecânica quântica são operadores unitários que alteram o estado dos qubits. Já na computação quântica adiabática há menos controle sobre a evolução do sistema, que faz isso de forma natural. O sistema evolui de forma adiabática, de acordo com o teorema do Adiabático e o procedimento do Annealing Quântico, até que a a energia que corresponde ao estado fundamental de um problema de otimização seja atingida.

O dispositivo que faz esse tipo de computação é chamado de Computador Quântico Adiabático, devido ao teorema do adiabático, ou ainda Quantum annealer já que o processo físico responsável pela evolução do sistema é um Annealing Quântico.

Computador Quântico Adiabático – Quantum Annealer

Uma da pioneiras no desenvolvimento de Quantum Annealers é a empresa canadense D-Wave. Em 2011 a empresa lançou o primeiro modelo comercial, o D-Wave One cuja Unidade de Processamento Quântica (QPU) possui 128 qubits físicos. Desde então vêm melhorando cada vez mais seus dispositivos aumentando o número de qubits e conectividade entre eles. Em 2013 lançou o D-Wave Two com 512 qubits, em 2015 o D-Wave 2X com 1152 qubits e em 2017 o D-Wave 2000Q com 2048 qubits. Seu Hardware mais recente, o D-Wave Advantage lançado em 2020, dispõe de 5760 qubits físicos com QPU arranjada de acordo com a topologia Pegasus, em que cada qubits é conectado a outros 15, formando grupos de 16 qubits.

Os QPU’s que constituem os computadores quânticos adiabáticos da D-Wave são construídos baseados em tecnologia supercondutora, através dos dispositivos conhecidos como SQUIDs (Superconducting Quantum Interference Devices). Os efeitos quânticos, que de praxe estão associados à computação quântica, são devidos as propriedades microscópicas da supercondutividade. Os próprios qubits nada mais são que loops supercondutores.

Dentre as limitações dos Quantum Annealers estão a sua suscetibilidade à ruídos, a baixa conectividade entre os qubits físicos na topologia do chip processador, isto é, as conexões esparsas acabam por limitar o tamanho dos problemas que podem ser executados, pois se não há interação entre dois qubits distantes vários qubits são necessários para representar uma única variável lógica. O processo que associa as variáveis lógicas do problema aos qubits físicos é chamado de Minor Embedding. A imagem a seguir ilustra essa ideia de Minor Embedding onde um problema com 10 qubits lógicos é associado a topologia Pegasus.

Outra limitação que os Quantum Annealers estão sujeitos é a restrição quanto aos tipos de problemas que podem ser executados : Problemas de Otimização e Sampling que podem ser formulados como modelos quadráticos como o modelo de Ising ou QUBO. Esses tipos de problemas representam uma grande diversidade de tarefas reais e de interesse industrial e acadêmica, como o caixeiro viajante, resolução de equações lineares, agendamento, entre outros. Dessa forma os quantum annealers possuem uma significante aplicabilidade em vários setores da sociedade.

Annealing Quântico

Os computadores quânticos adiabáticos empregam uma técnica conhecida como Annealing Quântico. Essa técnica é um método heurístico que busca pelo mínimo de uma função, inspirado na técnica clássica annealing simulado onde um problema de otimização é simulado como um problema termodinâmico e a otimização é feita fazendo com que a temperatura do sistema diminua gradativamente até que o estado fundamental seja atingido. No annealing quântico é definido uma hamiltoniana de spins dependente do tempo para o sistema de acordo com um modelo físico chamado modelo de Ising de Campo Transverso, nessa Hamiltoniana são codificadas duas funções, a Hamiltoniana inicial que representa os estados em superposição dos qubits e a Hamiltoniana final que representa o problema que se deseja otimizar.

Para o Quantum annealer da D-Wave pode ser escrita como:

Após o processo de otimização espera-se que o estado do sistema colapse para o estado fundamental da hamiltoniana final, já que a energia desse estado é a menor possível isso corresponde a solução do problema de otimização. O que garante que o estado colapsado esteja no estado fundamental é o Teorema do Adiabático que diz que:

Um sistema físico permanece em seu autoestado instantâneo, não degenerado, ao longo da evolução temporal, se nele é aplicada uma perturbação suficientemente pequena.

Ou seja, quando o sistema é iniciado no estado fundamental de se o processo de reduzir o campo magnético transverso for realizado de maneira adiabática, isto é, lenta o suficiente, então o estado fundamental é preservado e ao se fazer a medição no final do processo ele representará o estado fundamental de dando a solução da otimização do problema.

Formulação QUBO e aplicação no TSP

Modelo QUBO

O problema a ser executado em um computador quântico adiabático é codificado na Hamiltoniana final . Geralmente os problemas são formulados como modelos quadráticos binários que podem ser uma equação do tipo Ising ou QUBO. O modelo do tipo Ising pode ser observado na equação anterior

Em que pode ser -1 ou 1, é o termo linear da expressão e é o termo de acoplamento entre as variáveis lógicas em i e j. O modelo QUBO (Quadratic Uncostrained Binary Optimization) é equivalente ao modelo de Ising e sua representação é dada por:

Aqui que pode ser 0 ou 1, é o termo linear da expressão e é o termo de acoplamento entre as variáveis lógicas em i e j com . Ambos os modelos são equivalentes entre si através da transformação .

A formulação QUBO também pode ser representada matricialmente da seguinte forma:

Definimos então a matriz QUBO e a hamiltoniana é então escrita como

A partir da hamiltoniana formulada como uma QUBO ou Ising é possível construir um grafo que representa o problema, como exemplo considere a hamiltoniana:

Cujo grafo nesse exemplo é:

Esse grafo codifica a informação da hamiltoniana do problema e a partir desses grafos as variáveis lógicas podem ser associadas aos qubits físicos dos quantum annealers por meio do processo de Minor Embedding.

Formulação do TSP como um QUBO

A primeira etapa para implementar o TSP no computador quântico é formulá-lo como uma função objetivo, ou Hamiltoniana do tipo QUBO, adicionando em seguida vínculos energéticos que está sujeito, esses vínculos tem o objetivo de penalizar estados não desejados, e então definimos uma matriz QUBO.

Dados N cidades e as distâncias entre elas podemos construir a Hamiltoniana que fornece a distância total a ser percorrida. Seja a distância entre a cidade i e a cidade j e a variável lógica que representa a possibilidade do caixeiro viajante estar na cidade i no instante t, temos a seguinte expressão:

Essa expressão é o que se deseja minimizar e o resultado obtido do computador é a configuração das variáveis lógicas que representem o estado de menor energia do problema. Como vínculos exigimos que : Mais de uma cidade não pode ser visitada no mesmo instante t, isto é

Além disso, uma cidade não pode ser visitada mais de uma vez:

Dessa forma empregamos o chamado método de penalidades para adicionar os vínculos à Hamiltoniana e ter uma expressão do tipo QUBO. Aplicando esse método, a hamiltoniana do problema se torna:

Nessa expressão temos a somado com as penalidade, termos quadráticos entre parênteses. As penalidades devem ser elevadas ao quadrado pois se o vínculo for satisfeito então não é adicionado energia a Hamiltoniana total, por outro lado se o termo dentro do parênteses for negativo ou positivo (não satisfazendo os vínculos) então o quadrado garante que energia é adicionada a Hamiltoniana elevando seu valor. O é conhecido como parâmetro de Lagrange, e sua função é balancear as penalidades e .

Essa expressão representa o problema do caixeiro viajante na formulação QUBO, dela é possível obter a matriz QUBO do problema.

A execução no Computador Quântico Adiabático consiste então em aplicar a matriz QUBO nos Samplers disponíveis pela D-Wave, com isso pode-se obter a rota correspondente a um determinado parâmetro de Lagrange.

Por fim podemos resumir as etapas de execução de um problema no Quantum Annealer:

1 – Codificar o problema de otimização como uma Hamiltoniana no modelo tipo Ising ou Qubo.

2 – Fazer o Minor Embedding da Hamiltoniana na QPU, ou seja, representamos o problema na topologia dos qubits do dispositivo.

3 – Processo de Annealing Quântico é realizado.

4 – Finalmente a solução do problema é uma amostragem da configuração das variáveis lógicas que representa o estado de menor energia, o mínimo da Hamiltoniana.