Neural-powered unit disk graph embedding: qubits connectivity for some QUBO problems

Resumo Técnico: Incorporação de Grafos de Disco Unitário Impulsionada por Redes Neurais para Problemas QUBO

Declaração do Problema
O artigo aborda o desafio crítico de mapear problemas de Otimização Binária Quadrática sem Restrições (QUBO) em simuladores quânticos baseados em átomos neutros, especificamente aqueles que utilizam átomos de Rydberg (por exemplo, o protótipo Pasqal Chadoq2). Diferentemente de computadores quânticos baseados em portas ou annealers de topologia fixa (como o D-Wave), dispositivos de átomos neutros permitem o posicionamento arbitrário de qubits em espaços 2D ou 3D. No entanto, as interações físicas entre esses qubits são governadas pelo efeito de bloqueio de Rydberg: qubits separados por uma distância inferior a um específico "raio de bloqueio" ($r_b$) não podem ser excitados simultaneamente, criando um padrão de adjacência equivalente a um grafo de Disco Unitário (UD).

A dificuldade central reside no problema de incorporação de Grafo de Disco Unitário: encontrar um conjunto de coordenadas físicas para os qubits tal que:

1. Qubits adjacentes no grafo QUBO alvo estejam dentro do raio de bloqueio ($d_{ij} \leq \tilde{r}_b$).
2. Qubits não adjacentes estejam fora do raio de bloqueio ($d_{hk} > \tilde{r}_b$).
3. Todos os qubits caibam dentro das restrições físicas do registro (por exemplo, um domínio circular de raio 50 $\mu$m) e respeitem limites de separação mínima (por exemplo, 4 $\mu$m) para evitar sobreposição.

Os autores observam que, embora calcular a adjacência a partir das coordenadas seja trivial, o problema inverso — encontrar coordenadas que satisfaçam uma matriz de adjacência específica — é NP-difícil. Solucionadores clássicos frequentemente falham em encontrar incorporações viáveis para instâncias QUBO complexas ou de grande escala dentro de prazos razoáveis.

Metodologia: GEAN (Rede de Autoencoder para Incorporação de Grafos)
Os autores propõem o GEAN, uma heurística baseada em rede neural projetada para transformar uma configuração inicial de qubits, muitas vezes inviável, em uma incorporação UD válida. A abordagem trata a tarefa de incorporação como um problema de transformação de domínio, e não como uma tarefa padrão de previsão.

• Arquitetura:
  • Entrada/Saída: A rede recebe coordenadas iniciais 2D ou 3D $(x_i, y_i, z_i)$ para $n$ qubits e produz coordenadas transformadas $(x'_i, y'_i, z'_i)$.
  • Componente Autoencoder: Uma rede simétrica totalmente conectada (entrada $\to$ camadas ocultas $\to$ saída) transforma as coordenadas. A camada de saída utiliza uma ativação tanh escalada para o domínio físico ($\pm 50$ $\mu$m).
  • Camada Diferenciável de Distância: Uma camada esparsa especializada e não treinável calcula a distância euclidiana entre todos os pares de qubits com base nas coordenadas transformadas. Isso permite que a rede "veja" as restrições geométricas durante o treinamento.
• Função de Perda: O objetivo do treinamento não é minimizar o erro de previsão, mas satisfazer simultaneamente quatro restrições físicas. A função de perda é a soma de quatro termos de penalidade:
  1. Limite Global: Penaliza pares que excedem o raio máximo do registro (100 $\mu$m).
  2. Separação Mínima: Penaliza pares mais próximos que a distância física mínima (4 $\mu$m).
  3. Restrição de Adjacência: Penaliza qubits adjacentes que estão muito distantes ($> \tilde{r}_b$).
  4. Restrição de Não Adjacência: Penaliza qubits não adjacentes que estão muito próximos ($\leq \tilde{r}_b + \epsilon$).
• Otimização: O modelo é treinado usando o otimizador AdamW. O conjunto de treinamento consiste em uma única amostra (a instância QUBO específica), e a rede itera para encontrar um conjunto de coordenadas que minimize a perda, resolvendo efetivamente o problema de incorporação para aquele grafo específico.

Principais Contribuições

1. Heurística Neural para Incorporação NP-Difícil: O artigo introduz uma aplicação inovadora de autoencoders para resolver o problema de incorporação de grafos de Disco Unitário com restrições, contornando as limitações de solucionadores clássicos exatos para grafos maiores ou mais complexos.
2. Integração de Restrições Físicas: A metodologia incorpora explicitamente as limitações físicas do hardware de átomos neutros (raio de bloqueio, separação mínima e tamanho do registro) diretamente na função de perda e na arquitetura da rede neural.
3. Flexibilidade Dimensional: A abordagem é demonstrada tanto em 2D quanto em 3D. Os autores mostram que estender a rede para 3D permite a incorporação de grafos com maior conectividade (cliques maiores e graus mais elevados) que são impossíveis de incorporar em 2D devido aos limites de empacotamento geométrico.
4. Limites Teóricos: O artigo identifica condições necessárias para a incorporabilidade em 2D com base no Teorema de Thue sobre empacotamento de círculos, estabelecendo que o tamanho máximo da clique para incorporação em 2D é 7 e o grau máximo é 18 sob os parâmetros específicos da máquina ($\tilde{r}_b \approx 10.26$ $\mu$m).

Resultados
Os autores avaliaram o GEAN contra o solucionador Gurobi (um solucionador quadrático clássico de última geração) em três tipos de instâncias QUBO:

• Antenas QUBO MIS: Dados reais de posições de antenas em Turim. O GEAN incorporou com sucesso componentes conectados (até 87 qubits em 3D) onde o Gurobi falhou em encontrar uma solução viável dentro do limite de tempo de 2 minutos.
• Dobramento de Proteínas: Instâncias modeladas como problemas de Conjunto Independente Máximo. O GEAN encontrou incorporações viáveis para todas as instâncias testadas, enquanto o Gurobi falhou na instância $G_{17,7}$.
• Coloração de Grafos: Um problema de 3-coloração mapeado para um grafo de 21 qubits. O GEAN encontrou uma incorporação 3D viável em 767 épocas, enquanto o Gurobi falhou em convergir.

Métricas de Desempenho:

• Velocidade: O GEAN encontrou consistentemente soluções dentro de 2 minutos em hardware de consumo padrão, mesmo para a instância 3D mais complexa de 87 qubits.
• Viabilidade: Em casos onde o Gurobi falhou em encontrar qualquer incorporação viável dentro do limite de tempo, o GEAN teve sucesso.
• Qualidade: As coordenadas transformadas satisfizeram todas as restrições físicas (distância mínima, distância máxima e separação do raio de bloqueio), convertendo efetivamente configurações iniciais "inviáveis" (frequentemente derivadas de layouts de Fruchterman-Reingold) em layouts válidos prontos para hardware.

Significado e Alegações
O artigo alega que o GEAN fornece uma ponte prática entre formulações teóricas de QUBO e as realidades físicas do hardware quântico de átomos neutros. Ao aproveitar redes neurais para otimizar o posicionamento de qubits, o método:

• Supera Limitações Clássicas: Supera solucionadores exatos tradicionais (como o Gurobi) na busca por incorporações viáveis para grafos complexos dentro de prazos práticos.
• Minimiza Sobrecarga de Recursos: Diferentemente de abordagens que exigem átomos auxiliares de "fio" ou estruturas de rede fixas, o GEAN utiliza a flexibilidade total do registro, exigindo o número mínimo de qubits físicos necessários para o problema.
• Habilita Escalabilidade: A capacidade de resolver esses problemas de incorporação rapidamente permite que pesquisadores testem problemas QUBO não triviais no hardware atual, que possui contagens limitadas de qubits, sem ser limitado pelo próprio processo de incorporação.

Os autores concluem que, embora o modelo esteja atualmente ajustado a parâmetros específicos de máquina, o framework é adaptável a outras restrições de hardware e poderia abrir caminho para a resolução de classes mais amplas de problemas de otimização além da simples incorporação. Trabalho futuro é proposto para caracterizar ainda mais os limites das incorporações UD viáveis e validar essas descobertas em hardware quântico real.