Feedback-based quantum optimization and its classical counterpart: quantum advantage and the power of classical algorithms

Resumo Técnico: Otimização Quântica Baseada em Feedback e seu Contraparte Clássico

Enunciado do Problema
Problemas de otimização combinatória, ubíquos em logística, ciência dos materiais e finanças, são geralmente classificados como NP-difíceis, exigindo custos computacionais exponenciais para serem resolvidos exatamente. Embora existam vários solucionadores quânticos e clássicos, incluindo annealers quânticos e algoritmos quânticos variacionais, há necessidade de comparar rigorosamente as abordagens quânticas com seus contrapartes clássicos para avaliar o potencial de vantagem quântica. Especificamente, o Algoritmo de Otimização Quântica Baseado em Feedback (FALQON) utiliza a teoria de controle de Lyapunov para reduzir iterativamente uma função de custo sem loops de otimização clássica. No entanto, o custo computacional do feedback iterativo em sistemas quânticos é substancial. Por outro lado, algoritmos clássicos inspirados no FALQON, como o CACAO (Algoritmo Clássico Assistido por Contradiabaticidade para Otimização), oferecem convergência mais rápida, mas podem carecer de qualidade de solução. Além disso, problemas de Otimização Binária Não Restrita de Ordem Superior (HUBO) são frequentemente resolvidos de forma ineficiente ao serem reduzidos a formas de Otimização Binária Não Restrita Quadrática (QUBO), o que aumenta o tamanho do problema. Existe uma lacuna na compreensão dos contrapartes clássicos exatos de algoritmos quânticos baseados em feedback e de sua capacidade de lidar diretamente com problemas HUBO.

Metodologia
Os autores estabelecem uma estrutura teórica baseada na correspondência quântico-clássica de sistemas de spin. Ao substituir as matrizes de Pauli $\{\hat{X}_i, \hat{Y}_i, \hat{Z}_i\}$ por vetores unitários de spin clássicos $\{m^X_i, m^Y_i, m^Z_i\}$ e utilizar equações canônicas de movimento, eles derivam contrapartes clássicas exatas para a otimização quântica baseada em feedback.

1. Derivação Teórica:

   • Lado Quântico: O artigo revisa o FALQON e sua variante inhomogênea (iFALQON), onde os parâmetros de controle são determinados pelo valor esperado de comutadores entre o Hamiltoniano do problema e os termos de acionamento.
   • Lado Clássico: Os autores derivam CC-FALQON e CC-iFALQON como os contrapartes clássicos exatos. Diferentemente da versão quântica, esses algoritmos clássicos não exigem um loop de feedback iterativo; os parâmetros de controle são calculados diretamente a partir do estado instantâneo dos spins clássicos.
   • Extensão de Ordem Superior: A estrutura é estendida para desenvolver HOT-CACAO (CACAO de Ordem Superior), que introduz termos contradiabáticos de segunda ordem, e HOT-CACAO+, que incorpora tanto o Hamiltoniano do problema quanto todos os termos contradiabáticos discutidos (de primeira e segunda ordem).

2. Avaliação Comparativa (Benchmarking):

   • Escala Pequena: Os autores realizam testes de benchmark em $N=12$ instâncias do problema 2-SAT (formulado como QUBO) para comparar a qualidade da solução e a velocidade de convergência de algoritmos quânticos (FALQON, iFALQON) com seus contrapartes clássicos (CC-FALQON, CC-iFALQON) e outras variantes clássicas (CACAO, HOT-CACAO, HOT-CACAO+).
   • Escala Grande: O estudo avalia a escalabilidade de algoritmos clássicos em $N=10.000$ instâncias do problema 3-SAT (formulado diretamente como HUBO). Os algoritmos testados incluem CC-iFALQON, CACAO, HOT-CACAO e HOT-CACAO+.
   • Análise de Dinâmica: O artigo analisa as intensidades dos parâmetros de controle e a dinâmica de energia para compreender o comportamento de convergência e o papel da não localidade versus localidade.

Principais Contribuições

• Contrapartes Clássicas Exatas: O artigo introduz CC-FALQON e CC-iFALQON, fornecendo as primeiras formulações clássicas exatas de algoritmos de otimização quântica baseados em feedback derivadas da correspondência de sistemas de spin.
• Teoria Clássica de Ordem Superior: Desenvolve HOT-CACAO e HOT-CACAO+, estendendo o algoritmo CACAO com termos contradiabáticos de ordem superior e a inclusão explícita do Hamiltoniano do problema.
• Resolução Direta de HUBO: Demonstra-se que os algoritmos clássicos propostos resolvem problemas HUBO diretamente, sem a necessidade de métodos de redução de ordem (que tipicamente introduzem variáveis auxiliares e degradam o desempenho).
• Dinâmica Quântica vs. Clássica: O estudo esclarece os comportamentos contrastantes das dinâmicas quântica e clássica em relação ao acionamento inhomogêneo, atribuindo as diferenças à natureza global da dinâmica quântica versus a natureza local das atualizações clássicas.

Resultados

• Qualidade da Solução vs. Velocidade de Convergência:
  • Vantagem Quântica em Qualidade: O FALQON demonstra qualidade de solução superior (menor densidade de energia final) em comparação com seu contraparte clássico CC-FALQON e outros algoritmos clássicos em instâncias de pequena escala, sugerindo uma potencial vantagem quântica na exploração da paisagem de otimização global.
  • Vantagem Clássica em Velocidade: Os algoritmos clássicos geralmente exibem convergência significativamente mais rápida do que os algoritmos quânticos. Notavelmente, o CC-FALQON mostra convergência muito lenta, enquanto HOT-CACAO e HOT-CACAO+ convergem rapidamente.
• Efeitos de Inhomogeneidade:
  • No cenário quântico, o acionamento homogêneo (FALQON) supera o acionamento inhomogêneo (iFALQON).
  • No cenário clássico, a tendência se inverte: o acionamento inhomogêneo (CC-iFALQON) alcança energia mais baixa do que o acionamento homogêneo (CC-FALQON). Isso é atribuído ao descompasso entre a dinâmica quântica global e os parâmetros locais, versus a compatibilidade do acionamento inhomogêneo com atualizações clássicas locais.
• Escalabilidade e Desempenho HUBO:
  • Em instâncias de 3-SAT de grande escala ($N=10.000$), o HOT-CACAO+ alcança a menor densidade de energia final entre todos os métodos testados.
  • Embora o HOT-CACAO+ converja mais lentamente do que o HOT-CACAO, ele atinge estados de energia mais baixos, indicando uma compensação entre velocidade de convergência e qualidade da solução.
  • A análise de escalabilidade revela que o HOT-CACAO+ é o único método que melhora consistentemente a densidade de energia à medida que o tamanho do sistema aumenta, enquanto outros métodos estagnam. Isso destaca a necessidade de combinar termos contradiabáticos de ordem superior com o Hamiltoniano do problema para otimização de grande escala e alta ordem.

Significado e Alegações
O artigo afirma que suas descobertas destacam os papéis distintos da "quantidade" e das abordagens clássicas. A otimização quântica baseada em feedback (FALQON) mostra potencial para alcançar soluções de maior qualidade ao alavancar correlações globais, enquanto algoritmos clássicos, particularmente aqueles aprimorados com termos contradiabáticos de ordem superior (HOT-CACAO+), oferecem convergência rápida e escalabilidade superior para problemas HUBO.

Os autores afirmam que os algoritmos clássicos são altamente promissores para otimização combinatória porque evitam a sobrecarga iterativa e os custos de medição de estados intermediários associados às implementações quânticas. Além disso, a capacidade de lidar diretamente com interações de ordem superior sem redução de ordem torna essas abordagens clássicas particularmente eficientes para formulações HUBO. O artigo conclui que, embora os algoritmos quânticos possam oferecer vantagens na qualidade da solução, os algoritmos clássicos fornecem uma alternativa poderosa e escalável, e comparações sistemáticas sob orçamentos computacionais iguais permanecem uma direção necessária para trabalhos futuros.