Improving the efficiency of QAOA using efficient parameter transfer initialization and targeted-single-layer regularized optimization with minimal performance degradation

Resumo Técnico: Melhorando a Eficiência do QAOA via Transferência de Parâmetros e Otimização com Regularização Direcionada

Definição do Problema
O Algoritmo de Otimização Aproximada Quântica (QAOA) é um forte candidato para resolver Problemas de Otimização Combinatória (COPs), especificamente o problema de Corte Máximo (MaxCut), em dispositivos quânticos de curto prazo. No entanto, o QAOA enfrenta desafios significativos à medida que o tamanho do problema ($n$) e a profundidade do circuito ($p$) aumentam. O cenário de otimização torna-se altamente não convexo, caracterizado por um espaço de soluções que cresce exponencialmente ($2^n$) e um número de parâmetros que aumenta linearmente ($2p$). Essa complexidade frequentemente prende otimizadores clássicos em mínimos locais subótimos, particularmente para famílias de grafos ponderados, levando a razões de aproximação ($r$) insatisfatórias. Além disso, a otimização total de todos os $2p$ parâmetros é computacionalmente dispendiosa, exigindo tempo e recursos substanciais, o que dificulta a demonstração prática da vantagem quântica.

Metodologia
Os autores propõem uma estratégia híbrida combinando inicialização por transferência de parâmetros com otimização de camada única direcionada e regularização L2 para aumentar a eficiência do QAOA, minimizando a degradação do desempenho.

1. Inicialização por Transferência de Parâmetros:

   • A abordagem aproveita a observação de que parâmetros otimizados para instâncias de problemas similares tendem a se agrupar.
   • Um grafo "doador" ($G_1$) com um pequeno número de nós ($n_d = 8$) é totalmente otimizado. A inicialização deste doador utiliza o Recozimento Quântico Trotterizado (TQA) com $t=0,75$, seguido de otimização total usando o otimizador Adagrad.
   • Esses parâmetros otimizados $\{\gamma^*_i, \beta^*_i\}$ são transferidos para um grafo "receptor" ($G_2$) com $n_a \ge n_d$ nós dentro da mesma família de grafos.

2. Otimização de Camada Única Direcionada:

   • Em vez de reotimizar todos os $2p$ parâmetros para o grafo receptor, o método identifica uma camada específica "direcionada" ($p_k$) que produz a melhor razão de aproximação quando otimizada individualmente.
   • Para uma profundidade fixa de $p=15$, os autores testaram sistematicamente cada camada $p_k \in [1, 15]$ para determinar a camada ótima mais provável para diferentes famílias de grafos (3-Regular, Erdős–Rényi, Barabási–Albert).
   • Apenas os parâmetros desta camada única são otimizados usando o otimizador COBYLA (Constrained Optimization By Linear Approximation), enquanto todas as outras camadas permanecem fixas em seus valores transferidos.

3. Regularização (L2/Ridge):

   • Para abordar a inconsistência onde a otimização de camada única direcionada ($r_s$) ocasionalmente supera a otimização total ($r_f$) devido ao otimizador ficar preso em mínimos locais durante o processo de otimização total, os autores introduzem a regularização L2 (Ridge).
   • Um termo de penalidade $\lambda \sum (\gamma_k^2 + \beta_k^2)$ é adicionado à função de custo. Isso suaviza o cenário da solução, ajudando o otimizador a escapar de mínimos locais e melhorando a confiabilidade da otimização total ($r_f$).

Principais Contribuições e Resultados
O estudo foi conduzido através de três famílias de grafos não ponderados (3-Regular, Erdős–Rényi, Barabási–Albert) e três famílias ponderadas, utilizando grafos com contagens de nós variando de 8 a 24.

• Desempenho em Grafos Não Ponderados:

  • Para grafos 3-Regular não ponderados (u3R), a abordagem de transferência de parâmetros alcançou uma razão de aproximação média de 0,9443 para a otimização de camada única direcionada ($r_s$), comparado a 0,9551 para a otimização total ($r_f$). Isso representa 98,88% do desempenho ótimo.
  • Crucialmente, esta abordagem proporcionou um aceleração computacional de 8,06× em comparação com a otimização total.
  • Tendências semelhantes foram observadas para os grafos Erdős–Rényi não ponderados (uER) e Barabási–Albert não ponderados (uBA), onde $r_s$ permaneceu consistentemente próximo de $r_f$ enquanto reduzia significativamente o tempo de otimização ($\tau$).

• Desempenho em Grafos Ponderados:

  • 3-Regular Ponderado (w3R): O método apresentou bom desempenho, com a inicialização isolada ($r_n$) frequentemente excedendo o limiar clássico de Goemans-Williamson ($r_{GW} \ge 0,878$). A otimização direcionada melhorou ainda mais esses resultados.
  • Erdős–Rényi Ponderado (wER): A abordagem teve dificuldades com números maiores de nós ($n_a \ge 14$), onde $r_s$ caiu abaixo do limiar $r_{GW}$. Para essas famílias ponderadas mais complexas, a otimização total continuou sendo necessária para obter soluções de alta qualidade.
  • Barabási–Albert Ponderado (wBA): Esta família mostrou um comportamento híbrido; embora a otimização total fosse ligeiramente mais eficiente, a otimização direcionada permaneceu uma alternativa viável.

• Impacto da Regularização:

  • Sem regularização, a otimização de camada única direcionada superou a otimização total em 8,92% dos casos de teste (indicando que a otimização total ficou presa em mínimos locais).
  • A aplicação da regularização L2 reduziu essa inconsistência para 3,81%, melhorando significativamente a robustez da otimização total.

• Comparação de Otimizadores e Inicialização:

  • Entre vários otimizadores (COBYLA, POWELL, GSLS, NELDER-MEAD, SPSA), o COBYLA foi identificado como o mais adequado, oferecendo precisão comparável com o menor tempo de otimização.
  • A inicialização por transferência de parâmetros superou consistentemente o TQA e a inicialização aleatória tanto na razão de aproximação quanto no número de passos de otimização necessários.

Significância e Alegações
O artigo demonstra que a inicialização eficiente de parâmetros combinada com a otimização de camada única direcionada pode melhorar significativamente a eficiência do QAOA com mínima degradação de desempenho.

Os autores alegam que esta estratégia equilibra efetivamente o compromisso entre precisão e custo computacional. Ao transferir parâmetros de instâncias pequenas, totalmente otimizadas, para instâncias maiores e mais complexas, o método fornece um ponto de partida "próximo do ótimo" que reduz o espaço de busca. A subsequente otimização de uma única camada estrategicamente escolhida refina a solução sem o custo exponencial da reotimização total.

O trabalho destaca que, embora esta abordagem seja altamente eficaz para famílias de grafos não ponderados e ponderados específicos (como w3R), ela não é uma solução universal para todas as topologias ponderadas (especificamente wER), onde a complexidade do cenário de custo ainda exige a otimização total. A introdução da regularização L2 é apresentada como uma estratégia de mitigação crítica para estabilizar o cenário de otimização, garantindo que a otimização total não tenha um desempenho inferior em relação aos métodos seletivos. Em última análise, o estudo sugere um caminho para tornar o QAOA mais prático para problemas combinatórios de maior escala, reduzindo o overhead computacional clássico associado ao ajuste de parâmetros.