Resumo Técnico: Abordagens Variacionais Quânticas para o Problema do Conjunto Independente Máximo em Escala de Utilidade

Definição do Problema

O problema do Conjunto Independente Máximo (MIS - Maximum Independent Set) busca o maior subconjunto de vértices em um grafo não direcionado tal que nenhum par de vértices seja adjacente. É um problema canônico NP-difícil com aplicações em atribuição de frequências, análise de interação proteica e design de VLSI. Embora os resolvedores clássicos exatos (branch-and-bound, programação inteira) tenham dificuldades com instâncias difíceis além de algumas centenas de vértices, a computação quântica oferece potenciais heurísticas. No entanto, algoritmos variacionais baseados em portas enfrentam desafios significativos na era NISQ (Noisy Intermediate-Scale Quantum), incluindo contagem limitada de qubits, tempos de coerência curtos e o fenômeno do "platô estéril" (barren plateau), onde os gradientes desaparecem exponencialmente.

Um desafio estrutural específico surge para grafos grandes e densos, onde o MIS constitui uma fração minúscula do total de vértices (ex: 15 de 180). Nesses casos, a solução ótima ocupa uma região exponencialmente pequena do espaço de Hilbert. Abordagens padrão, que iniciam com superposição uniforme, atribuem amplitude desprezível ao MIS, o que frequentemente faz com que os circuitos variacionais convirjam para bacias de energia subótimas das quais é difícil escapar sem mudanças coordenadas de múltiplos qubits.

Metodologia

Os autores propõem uma estrutura em camadas combinando pré-processamento de circuito, otimização variacional e pós-processamento clássico para enfrentar esses desafios através de três instâncias de referência: 64, 99 e 180 nós.

1. Pré-processamento e Construção de Circuito

• Reordenação de Vértices: Para minimizar o overhead de SWAP e melhorar a eficiência do emaranhamento, os autores comparam três estratégias de reordenação: BFS ponderada pelo acoplamento, Reverse Cuthill-McKee (RCM) e Reordenação Espectral (usando o vetor de Fiedler). A reordenação espectral é adotada por superar consistentemente as outras em instâncias densas, agrupando vértices estruturalmente próximos, minimizando assim a distância de índice entre qubits fortemente acoplados.
• Esparsificação Baseada em Distância: Aplicada especificamente aos circuitos QAOA, esta técnica remove interações de longo alcance da construção do circuito (mantendo apenas arestas onde $|i-j| \le k$) enquanto avalia a energia usando o Hamiltoniano completo. Isso reduz significativamente a profundidade do circuito, tornando as simulações tratáveis em simuladores de Matrix Product State (MPS).
• Algoritmos: O estudo compara o Variational Quantum Eigensolver (VQE) usando um ansatz EfficientSU2 e o Quantum Approximate Optimization Algorithm (QAOA). Os otimizadores incluem COBYLA e Simultaneous Perturbation Stochastic Approximation (SPSA). O objetivo de Conditional Value at Risk (CVaR) é utilizado para focar a otimização na cauda de menor energia da distribuição de medição.

2. Pipeline de Pós-processamento Clássico

Um pipeline de heurística de duas etapas converte as medições quânticas brutas em candidatos válidos de MIS:

• Supressão Guiada por Histórico: Uma Média Móvel Exponencial (EMA) rastreia a frequência de qubits estando no estado $|0\rangle$ entre as bitstrings de melhor desempenho. Isso gera máscaras de supressão para remover vértices sobre-selecionados (violando a independência) e adicionar vértices sub-selecionados.
• Correção Gananciosa (Greedy) e Extensão de Maximalidade: Um algoritmo ganancioso de duas passagens primeiro repara conjuntos infactíveis removendo violações de alto peso, e então estende o conjunto para a maximalidade, adicionando vértices compatíveis em ordem crescente de grau.

3. Inicialização de Superposição Assistida por Ancilla (Instância de 180 Nós)

Para a instância de 180 nós, o VQE padrão estagna no tamanho 14 (o MIS conhecido é 15). Para superar isso, os autores introduzem uma nova técnica de inicialização:

• Seleção de Sementes (Seeds): O pós-processamento clássico identifica múltiplos conjuntos independentes diversos e quase-ótimos de tamanho 14.
• Superposição de Ancilla: Em vez de iniciar de uma única semente ou de uma superposição uniforme, o circuito prepara uma superposição quântica uniforme dessas $m$ soluções distintas de tamanho 14 usando qubits ancilla como um registro de índice.
• Ansatz Preservador de Excitação: O estado evolui sob um ansatz composto por portas de simulação fermiônica (fSim) que conservam o peso de Hamming total (número de excitações). Isso restringe a busca ao subespaço de configurações de tamanho 14, eliminando a necessidade de termos de penalidade e refinando o cenário de energia para uma otimização de grão fino.
• Busca em Paralelo Quântico: Os parâmetros variacionais são otimizados coletivamente através de todos os ramos de sementes simultaneamente. A distribuição resultante é então processada pelo heurístico clássico, que pode estender conjuntos de tamanho 14 para o MIS de tamanho 15.

Principais Resultados

Instâncias de Referência (64, 99 e 180 Nós)

• Instância de 64 Nós: O VQE com SPSA e CVaR recupera com sucesso todos os 9 MIS distintos certificados (tamanho 10) em execuções repetidas. O QAOA recupera menos conjuntos (0–5 por execução) e falha em atingir o tamanho 10 com a Estratégia 2 (conduzindo todos os conjuntos recuperados à maximalidade), destacando a importância da diversidade de soluções.
• Instância de 99 Nós: O VQE recupera até 10 MIS distintos (tamanho 7) por execução, amostrando uma fração significativa das 56 soluções certificadas. O QAOA não é perseguido devido aos limites de esparsificação do simulador MPS.
• Instância de 180 Nós: O VQE padrão (Fase 1) converge para o tamanho 14, mas não consegue atingir o tamanho 15. A Fase 3 assistida por ancilla (VQE preservador de excitação) descobre com sucesso o MIS de tamanho 15. Estudos de ablação confirmam que heurísticas clássicas aplicadas a sementes únicas, ou circuitos preservadores de excitação inicializados a partir de sementes únicas, falham em encontrar o MIS de tamanho 15. Apenas a superposição quântica de múltiplas sementes quebra a barreira do ótimo local.

Validação de Hardware (IBM Quantum ibm_marrakesh)

• VQE: Usando parâmetros transferidos diretamente de simulação sem ruído (sem reotimização de hardware), o VQE recupera aproximadamente 50% da diversidade do MIS sem ruído com 40% do orçamento de shots. Para a instância de 64 nós, 3 MIS distintos (tamanho 10) foram encontrados; para a instância de 99 nós, 5 MIS distintos (tamanho 7) foram encontrados.
• QAOA: Sob o mesmo protocolo de transferência de parâmetros, o QAOA recuperou zero conjuntos independentes válidos no hardware. Os autores atribuem isso ao efeito cumulativo da largura de banda limitada do circuito (exigindo cadeias de SWAP profundas), otimização clássica rasa e ruído de hardware.

Significância e Alegações

O artigo afirma as seguintes contribuições e significância:

1. Simulação em Escala de Utilidade: Tanto quanto se saiba, a simulação MPS de 180 qubits representa a maior escala na qual algoritmos variacionais baseados em portas resolveram o problema do MIS para a otimalidade.
2. Avanço Metodológico: A principal contribuição é a técnica de superposição de ancilla. Ela fornece uma estrutura principiológica para quebrar os ótimos locais que prendem tanto heurísticas clássicas quanto abordagens variacionais padrão. Ao inicializar uma superposição quântica uniforme sobre múltiplas sementes clássicas quase-ótimas e evoluí-las sob um ansatz preservador de excitação, o método realiza uma "busca paralela híbrida quântica-clássica". Isso permite a descoberta de soluções (tamanho 15) que são inacessíveis aos métodos de semente única.
3. Robustez ao Ruído: A validação de hardware demonstra que o pipeline de heurística de bitstring é robusto a condições realistas de ruído, recuperando diversidade significativa de soluções sem reotimização consciente do hardware.
4. Alegações Modestas sobre Vantagem Quântica: Os autores declaram explicitamente que não reivindicam vantagem computacional quântica para estas instâncias específicas. Os circuitos estudados são eficientemente simuláveis classicamente via MPS (dimensão de ligação $\chi_{max} = 2$) devido à sua estrutura de emaranhamento baixa. A significância reside em demonstrar que a metodologia funciona e fornece uma base para futuras implementações de hardware onde ansätze mais profundos e maiores populações de sementes possam gerar uma verdadeira vantagem quântica.

O trabalho estabelece que a descoberta do MIS no caso de 180 nós é consequência de uma busca paralela quântica sobre múltiplas inicializações quase-ótimas, e não apenas do pós-processamento clássico. Esta estrutura é apresentada como uma abordagem escalável para problemas de otimização combinatória que admitem uma formulação de Ising.