Quantum circuit evolutionary framework applied on set partitioning problem

Resumo Técnico: Framework Evolutivo de Circuitos Quânticos Aplicado ao Problema de Partição de Conjuntos

Definição do Problema
O artigo aborda o Problema de Partição de Conjuntos (SPP), um desafio conhecido de otimização combinatória NP-difícil. O SPP envolve dividir um conjunto de elementos em subconjuntos mutuamente exclusivos e exaustivos para minimizar o peso total, garantindo que cada elemento pertença a exatamente um subconjunto. Aplicações práticas incluem o agendamento de tripulações de companhias aéreas. Para resolver isso em hardware quântico, os autores formulam o SPP como um problema de Otimização Binária Quadrática sem Restrições (QUBO), que é subsequentemente mapeado para um Hamiltoniano de Ising. O estudo visa especificamente as limitações dos atuais Algoritmos Quânticos Variacionais (VQAs), como o Variational Quantum Eigensolver (VQE), que frequentemente sofrem com "platôs estéreis" — um fenômeno onde os gradientes desaparecem exponencialmente à medida que o número de qubits aumenta, levando à estagnação da convergência.

Metodologia
Os autores propõem um framework de Evolução de Circuito Quântico (QCE) que se afasta da abordagem padrão do VQE. Diferentemente do VQE, que utiliza uma topologia de circuito fixa (ansatz) com parâmetros variados otimizados por um otimizador clássico, o framework QCE evolui a própria topologia do circuito. O estudo avalia duas estratégias distintas dentro deste framework:

1. Evolução de Circuito Quântico sem Ansatz (AF-QCE):

   • Inspirada em literatura anterior [13], esta abordagem começa com um circuito mínimo (um único portão aleatório) e evolui iterativamente sem um ansatz pré-definido.
   • A evolução baseia-se em operações de mutação: INSERIR (adicionar um portão), EXCLUIR (remover um portão), TROCAR (substituir um portão) e MODIFICAR (ajustar parâmetros do portão).
   • Uma população de circuitos é gerada, medida e o circuito de melhor desempenho é selecionado como o progenitor para a próxima geração, garantindo a redução monótona da função de custo.

2. Ansatz com Termo Evolutivo Pseudo-Contradiabático (APCD-QCE):

   • Esta abordagem incorpora uma estrutura inspirada na física no ansatz para melhorar a convergência. Utiliza um Hamiltoniano $H_T(\lambda) = H_{ad}(\lambda) + H_{pcd}(\lambda)$, onde $H_{ad}$ representa um Hamiltoniano de evolução temporal adiabática e $H_{pcd}$ é um termo evolutivo pseudo-contradiabático.
   • O operador unitário é definido como $U = U_{ad}U_{pcd}$. O componente $U_{ad}$ é fixo (um passo de Trotter), enquanto $U_{pcd}$ é evoluído usando a mesma estratégia de mutação evolutiva do AF-QCE.
   • A preparação do estado inicial utiliza $|+\rangle^{\otimes n}$, e configurações específicas de parâmetros ($\beta=0, \delta=0.5$) são aplicadas para facilitar a exploração do espaço de Hilbert.

Configuração Experimental
Os experimentos foram conduzidos usando a biblioteca Qiskit em um simulador de alto desempenho (KUATOMU) sob dois cenários:

• Sem Ruído: 35 instâncias do SPP (variando de 6 a 20 qubits) foram testadas.
• Com Ruído: As simulações incluíram canais de erro de despolarização ($\epsilon = 0.01$) em qubits específicos para imitar as limitações de dispositivos NISQ.
• Comparação: As estratégias QCE foram comparadas com o VQE padrão (usando um ansatz de emaranhamento linear de dois locais e o otimizador COBYLA).
• Métrica: O desempenho foi medido usando a Razão de Aproximação ($R$), definida como a razão entre um valor de referência clássico (solver Gurobi) e o valor esperado mínimo encontrado pelo algoritmo quântico.

Principais Resultados

• Superioridade sobre o VQE: Em cenários sem ruído, tanto o AF-QCE quanto o APCD-QCE superaram significativamente o VQE. O desempenho do VQE degradou-se rapidamente à medida que o número de qubits aumentava (falhando frequentemente em convergir para instâncias $\ge 10$ qubits), enquanto as abordagens evolutivas mantiveram um desempenho superior.
• Desempenho do APCD-QCE: A estratégia APCD-QCE demonstrou os resultados mais robustos, alcançando uma razão de aproximação de 1,00 (ótima) em 25 das 35 instâncias. Evitou efetivamente a estagnação da convergência na maioria dos casos onde o VQE e o AF-QCE tiveram dificuldades.
• Limites de Escalabilidade: Apesar das melhorias, os desafios de escalabilidade persistiram. Para instâncias de 20 qubits (especificamente 20.1, 20.6 e 20.7), todos os métodos, incluindo o APCD-QCE, mostraram sinais de estagnação da convergência, com a razão de aproximação caindo significativamente.
• Impacto do Ruído: Nas simulações com ruído, o desempenho degradou-se para todos os algoritmos, particularmente em instâncias menores. No entanto, os frameworks QCE geralmente mantiveram desempenho comparável ou superior ao do VQE.

Significado e Alegações
O artigo afirma que o framework QCE proposto oferece uma alternativa promissora aos algoritmos variacionais de ansatz fixo para problemas de otimização inteira. As principais contribuições incluem:

• Mitigação da Estagnação: O framework, particularmente a variante APCD-QCE, demonstra uma capacidade notável de evitar a estagnação da convergência associada aos platôs estéreis nos VQAs padrão.
• Eliminação de Otimizadores Clássicos: Ao evoluir a topologia do circuito diretamente, o procedimento contorna a necessidade de otimizadores clássicos (como o COBYLA) para ajustar parâmetros, abordando um gargalo nos fluxos de trabalho atuais de VQA.
• Caminho para a Escalabilidade: Embora não seja uma solução completa para a estagnação de 20 qubits, os resultados sugerem que circuitos de topologia variável fornecem um "caminho interessante" para resolver problemas de otimização em maior escala. Os autores observam que a estratégia APCD-QCE é "quase imune" aos efeitos de estagnação da convergência dado um número suficientemente grande de gerações, embora escapar de mínimos locais na paisagem de mutação permaneça um desafio.

Os autores concluem que, embora o método enfrente obstáculos de escalabilidade com o aumento do número de qubits, a integração de termos inspirados na física (pseudo-contradiabáticos) na busca evolutiva de circuitos produz resultados encorajadores para resolver problemas combinatórios em dispositivos NISQ.