Resumo Técnico: QUACOD – Otimização Quântica via Descida de Coordenadas para Agendamento Escalável de Drones

1. Formulação do Problema

O artigo aborda o Problema de Agendamento de Drones, um componente crítico da logística de última milha, onde o objetivo é atribuir rotas pré-calculadas a uma frota de drones idênticos para minimizar o tempo máximo de conclusão ($C_{max}$) de toda a frota.

As principais restrições e características do problema incluem:

• Restrições de Bateria: Os drones devem recarregar entre rotas consecutivas, introduzindo um tempo de recarga não desprezível ($c$) que impacta significativamente o tempo total de conclusão.
• Complexidade Combinatória: O problema é NP-difícil, relacionado ao Problema do Caixeiro Viajante, com um espaço de soluções que cresce exponencialmente à medida que o número de rotas ($n$) e drones ($q$) aumenta.
• Limitações de Hardware: A aplicação prática é dificultada pelos atuais dispositivos Quânticos de Escala Intermediária e Ruidosos (NISQ), que carecem da contagem de qubits necessária para codificar diretamente problemas de agendamento em larga escala em Recozimento Quântico ou Algoritmos Quânticos Variacionais (VQA). Abordagens quânticas existentes, como QUADRO, limitam-se a instâncias muito pequenas (por exemplo, menos de 11 drones).

2. Metodologia: QUACOD

Os autores propõem o QUACOD (Otimização Quântica via Descida de Coordenadas), um framework híbrido quântico-clássico projetado para resolver problemas de agendamento em larga escala sob restrições estritas de qubits.

A. Formulação do Problema e Transformação QUBO

O problema de agendamento é inicialmente modelado como uma minimização de $C_{max}$ sujeita a restrições de atribuição (cada rota atribuída a exatamente um drone) e restrições de capacidade. Para tornar isso compatível com a otimização quântica, os autores transformam o problema em um formato de Otimização Binária Quadrática sem Restrições (QUBO):

1. Tratamento de Restrições: Restrições de igualdade (atribuição de rotas) são convertidas em termos de penalidade adicionados à função objetivo.
2. Transformação do Objetivo: Em vez de minimizar diretamente $C_{max}$, os autores utilizam uma heurística derivada da observação de que minimizar a soma dos desvios quadráticos dos tempos de conclusão individuais dos drones ($T_j$) em relação ao tempo de conclusão médio ($T/q$) minimiza efetivamente $C_{max}$. Isso elimina restrições de desigualdade complexas.
3. Objetivo Final: A função QUBO resultante minimiza a soma dos desvios quadráticos de $T_j$ mais a penalidade por rotas não atribuídas.

B. O Algoritmo QUACOD

Para superar a limitação da escassez de qubits, o QUACOD adapta a estratégia de otimização de Descida de Coordenadas:

• Decomposição: Em vez de otimizar todas as $n \times q$ variáveis binárias simultaneamente, o algoritmo seleciona iterativamente um pequeno subconjunto de rotas ($N$) e drones ($Q$).
• Seleção de Variáveis: Os subconjuntos são escolhidos de modo que:
  • O número de variáveis ($|N| \times |Q|$) não exceda os qubits disponíveis ($m$).
  • O subconjunto inclua o drone com o tempo de conclusão mais alto (gargalo) e o drone com o tempo de conclusão mais baixo (subcarregado) para facilitar a redistribuição.
  • A seleção garanta soluções não triviais (pelo menos uma rota esteja atualmente atribuída a cada drone selecionado).
• Sub-rotina Quântica: O subproblema selecionado é resolvido usando um Solver Variacional de Autovalores Quânticos (VQE) com um ansatz eficiente em hardware (camada única com rotações $R_y$ e emaranhamento linear $CZ$).
• Iteração: Variáveis não selecionadas são fixadas, e o processo se repete até a convergência.

C. Ansatz Eficiente em Hardware

O artigo emprega um ansatz VQE específico consistindo em dois blocos de rotação $R_y$ separados por uma cadeia linear de portas de emaranhamento $CZ$. Este design é escolhido por sua compatibilidade com dispositivos NISQ e sua capacidade de produzir soluções de alta qualidade com uma única camada, evitando circuitos profundos e altos custos computacionais associados ao QAOA.

3. Contribuições Principais

1. Algoritmo Inovador: Introdução do QUACOD, uma abordagem híbrida que decompõe o agendamento de drones de alta complexidade em subproblemas gerenciáveis solucionáveis pelo hardware quântico atual.
2. Escalabilidade: Demonstração de que a descida de coordenadas pode preencher a lacuna entre a vantagem quântica teórica e as limitações práticas do NISQ, permitindo a solução de problemas significativamente maiores do que os tratados por métodos anteriores.
3. Validação de Desempenho: Evidências empíricas mostrando que o QUACOD supera o estado da arte (QUADRO) tanto na qualidade da solução (tempos de conclusão mais baixos) quanto na escalabilidade.
4. Eficiência de Hardware: Validação de que circuitos eficientes em hardware são eficazes para otimização combinatória, apoiando a viabilidade de implantação quântica a curto prazo.

4. Resultados Experimentais

Os autores avaliaram o QUACOD usando simulações clássicas de hardware quântico (Qiskit) em dois conjuntos de dados:

• Comparação com QUADRO (Conjunto de Dados Augerat):

  • O QUACOD foi testado em seis instâncias com números variados de drones e rotas.
  • Resultados: O QUACOD consistentemente encontrou soluções com tempos máximos de conclusão mais baixos do que as abordagens híbridas e puramente quânticas do QUADRO.
  • Escalabilidade: Enquanto o QUADRO falhou em agendar instâncias com mais de 11 drones, o QUACOD lidou com sucesso com instâncias de até 50 drones e 1.000 rotas (5 vezes mais drones e 35 vezes mais rotas do que os limites do QUADRO).

• Benchmark em Larga Escala (Conjunto de Dados de Agendamento de Máquinas Paralelas):

  • Experimentos foram conduzidos em instâncias variando de 200 a 3.000 rotas e de 5 a 100 drones.
  • O QUACOD resolveu com sucesso a maioria das instâncias em larga escala usando apenas 20 qubits para a simulação quântica.
  • Limitações: As duas maiores instâncias (3.000 rotas, 100 drones) falharam devido a restrições de memória clássica (RAM) necessárias para armazenar os termos $O(n^2q^2)$ da função objetivo QUBO, e não devido a limitações de hardware quântico.

5. Significado e Alegações

O artigo afirma que o QUACOD representa um passo significativo em direção a aplicações quânticas práticas na era NISQ ao:

• Superar Barreiras de Recursos: Demonstra que problemas logísticos complexos podem ser resolvidos com qubits limitados, aproveitando estratégias de decomposição clássica (descida de coordenadas).
• Aplicabilidade Prática: O método alcança escalabilidade superior em comparação com frameworks quânticos existentes, tornando-o um candidato viável para o gerenciamento de frotas de drones no mundo real, onde os tamanhos das frotas são grandes.
• Alinhamento com Hardware: Ao utilizar ansatzes eficientes em hardware, a abordagem alinha-se com as capacidades dos dispositivos quânticos atuais e de futuro próximo.

Limitações Reconhecidas

Os autores notam modestamente várias limitações:

• Lacunas Teóricas: Não há provas teóricas formais quanto à taxa de convergência ou garantias de convergência da implementação específica de descida de coordenadas utilizada.
• Teoria VQE: Não existem provas teóricas que sustentem a vantagem específica do VQE sobre métodos clássicos para esta classe de problemas de otimização; os resultados são empíricos.
• Simplificação do Modelo: O modelo de agendamento de drones assume drones idênticos e rotas pré-calculadas, simplificando a complexidade de sistemas logísticos do mundo real que podem envolver frotas heterogêneas e roteamento dinâmico.