Scalable Quantum Walk-Based Heuristics for the Minimum Vertex Cover Problem

Resumo Técnico: Heurísticas Escaláveis Baseadas em Passeio Quântico para o Problema de Cobertura Mínima de Vértices

Declaração do Problema
O problema da Cobertura Mínima de Vértices (MVC) é um desafio fundamental NP-completo em otimização combinatória, exigindo a identificação do menor subconjunto de vértices $C \subseteq V$ em um grafo $G=(V, E)$ tal que toda aresta seja incidente a pelo menos um vértice em $C$. Embora existam algoritmos exatos, eles escalam exponencialmente com o tamanho da cobertura. Estratégias de aproximação clássicas, como o emparelhamento máximo, oferecem uma razão de $\le 2$, mas Dinur e Safra estabeleceram que nenhum algoritmo de tempo polinomial pode alcançar uma razão abaixo de $\approx 1.3606$ para grafos de alto grau. Os autores visam explorar se Passeios Quânticos de Tempo Contínuo (CTQWs) podem fornecer um critério de seleção principial e de alta qualidade para a MVC que supere heurísticas clássicas, mantendo-se escalável.

Metodologia
O artigo propõe uma heurística baseada em CTQW que opera iterativamente para construir uma cobertura de vértices. A metodologia central envolve três componentes principais:

1. Formulação Quântica:

   • Hamiltoniano: O grafo é codificado em um Hamiltoniano $H$ baseado no Laplaciano Simétrico Normalizado: $H = I - D^{-1/2}AD^{-1/2}$, onde $A$ é a matriz de adjacência e $D$ é a matriz de graus. Essa normalização garante dinâmicas de propagação uniformes, reduzindo o viés em direção a vértices de alto grau.
   • Evolução: O sistema evolui sob $U(t) = e^{-iHt}$ por um tempo curto e ótimo $t_{opt}$. Os autores utilizam um esquema de codificação binária, representando $V$ vértices com $n = \lceil \log_2 V \rceil$ qubits, o que reduz significativamente os requisitos de qubits em comparação com codificações one-hot.
   • Critério de Seleção: Em cada iteração, o vértice $m$ com a maior probabilidade de transição $P(m \to \text{out}) = 1 - |[e^{i\Gamma t}]_{mm}|^2$ é selecionado e adicionado à cobertura. Aqui, $\Gamma$ é a matriz de adjacência normalizada.
   • Mecanismo de Congelamento: Para prevenir a re-seleção e isolar o vértice escolhido, um termo de penalidade energética é aplicado ao subespaço do vértice selecionado. Esse "isolamento espectral" (ou congelamento) desloca o estado selecionado para fora da ressonância, removendo-o efetivamente das dinâmicas ativas para iterações subsequentes sem deletar fisicamente arestas da matriz Hamiltoniana.

2. Derivação Clássica (Heurística Inspirada em Quantum):

   • Através de uma expansão de curto prazo da exponencial matricial $e^{i\Gamma t}$, os autores derivam analiticamente que o critério de seleção quântica se reduz a uma quantidade espectral clássica computável em tempo $O(|E|)$:
     $$s(m) = [\Gamma^2]_{mm} = \frac{1}{d_m} \sum_{j \in N(m)} \frac{1}{d_j}$$
   • Essa quantidade representa a média do inverso do grau dos vizinhos de um vértice, escalada pelo próprio grau do vértice. Ela captura informações estruturais de dois saltos, distinguindo-se de abordagens ganancias baseadas apenas em graus.

3. Implementação:

   • Hardware Quântico: O algoritmo foi implementado nas plataformas ibm_marrakesh (baseada em portas) e Bloqade (átomos neutros) da IBM. A implementação baseada em portas é limitada pela profundidade do circuito ($O(V^2)$ portas de dois qubits) a grafos pequenos ($V \lesssim 16$), enquanto a abordagem de átomos neutros utiliza um átomo por vértice.
   • Simulação Clássica: O algoritmo ganancioso espectral derivado (Algoritmo 2) foi comparado com soluções exatas de Programação Linear Inteira Mista (MILP) e heurísticas clássicas (Ganancioso por Grau, FastVC, Aproximação-2, Recozimento Simulado) em 14.680 instâncias.

Principais Contribuições

• Conexão Física: O trabalho estabelece um link físico direto entre dinâmicas de transporte quântico e o problema da MVC, demonstrando que vértices com altas probabilidades de transição correspondem naturalmente a elementos de cobertura estruturalmente relevantes.
• Eficiência de Recursos: Ao empregar codificação binária, o algoritmo quântico requer apenas $\lceil \log_2 V \rceil$ qubits, uma redução significativa em relação aos $V$ qubits exigidos por formulações padrão de QAOA.
• Algoritmo Clássico Inspirado em Quantum: A contribuição principal é a derivação de uma heurística clássica (Algoritmo 2) que reproduz o desempenho do algoritmo quântico com complexidade $O(|E|)$ por iteração, tornando-o escalável para grafos com $V \sim 10^5$ vértices sem exigir hardware quântico.
• Benchmarking Abrangente: O estudo fornece validação extensa em conjuntos de grafos Erdős–Rényi, Barabási–Albert e Regulares, bem como em redes do mundo real do repositório SNAP.

Resultados

• Desempenho vs. Heurísticas Clássicas: Em 14.680 instâncias de benchmark ($N \in [4, 150]$), a abordagem baseada em CTQW (e seu equivalente espectral clássico) alcançou uma razão média de aproximação de 1.015, superando significativamente o Ganancioso por Grau (1.023) e o Recozimento Simulado (1.027). A vantagem foi mais pronunciada em Grafos Regulares, onde o critério espectral resolveu efetivamente empates que confundiram métodos baseados em graus.
• Instâncias Difíceis: Em famílias estruturalmente difíceis (grafos Crown, grafo de Petersen, grafos 3-regulares aleatórios), a razão no pior caso foi de 1.143, bem abaixo do limiar de inaproximabilidade teórico de $\approx 1.3606$.
• Escalabilidade: Em grandes escalas ($V \in [10^3, 10^5]$), o algoritmo ganancioso espectral alcançou o melhor tamanho de cobertura (razão 1.000 relativa ao melhor solucionador virtual) em 100% das 210 instâncias. Ele superou o Ganancioso por Grau (razão média 1.047) e o Recozimento Simulado (razão média 1.072).
• Validação em Hardware: No hardware da IBM, o algoritmo produziu soluções exatas para $V=4$, mas sofreu com erros de porta em $V=32$ devido a circuitos profundos. No entanto, os resultados confirmaram que a codificação binária é viável para pequenos $V$ e que a análise de passeio quântico serve como um mecanismo de descoberta para o critério clássico.
• Redes do Mundo Real: Em oito redes do mundo real (incluindo grafos de estradas e colaboração), o método ganancioso espectral igualou o melhor solucionador virtual em todos os casos, alcançando uma melhoria de 5,3% sobre o Ganancioso por Grau na rede rodoviária da Pensilvânia.

Significado e Alegações
O artigo postula que a análise de passeio quântico serve principalmente como um mecanismo de descoberta. Embora a simulação quântica completa seja intratável para grafos grandes em dispositivos NISQ atuais devido a restrições de profundidade de circuito, o princípio estrutural que ela codifica — o peso espectral de dois saltos do Laplaciano normalizado — transfere-se limpa e eficientemente para um algoritmo clássico eficiente.

Os autores afirmam que esse critério inspirado em quantum oferece uma heurística robusta e agnóstica à topologia que supera consistentemente os métodos clássicos padrão, particularmente em cenários onde informações locais de grau são insuficientes (por exemplo, grafos regulares ou redes com graus degenerados). O trabalho demonstra que dinâmicas quânticas podem revelar regras de seleção clássicas que não são imediatamente óbvias apenas da teoria dos grafos, fornecendo uma nova ferramenta para otimização combinatória que é tanto de alta qualidade quanto computacionalmente escalável. O artigo permanece modesto quanto à implementação em hardware quântico, reconhecendo que os níveis atuais de ruído limitam a execução quântica direta a grafos muito pequenos, mas enfatiza o valor prático imediato da heurística clássica derivada.