Neural optimization for quantum architectures: graph embedding problems with Distance Encoder Networks

Enunciado do Problema

O artigo aborda o desafio de mapear problemas de otimização combinatória em hardware quântico baseado em átomos neutros. Especificamente, foca no problema do Grafo de Disco Unitário Constrained (CUDG). Em arquiteturas quânticas de átomos neutros, os qubits são representados por átomos de Rydberg posicionados em um registro 2D ou 3D. Suas interações são governadas por um "efeito de bloqueio", que cria um padrão de conectividade equivalente a um Grafo de Disco Unitário (UDG).

A dificuldade central reside na tarefa de incorporação: encontrar as coordenadas espaciais de $n$ qubits de modo que as interações físicas resultantes (determinadas pelas distâncias interatômicas) reproduzam uma matriz de adjacência desejada (padrão de conectividade) ao mesmo tempo em que satisfazem restrições de hardware rigorosas:

1. Distância mínima ($D_{min}$): Os átomos não podem ser posicionados mais próximos do que um limiar específico (por exemplo, 4 $\mu$m) devido às limitações das pinças ópticas.
2. Raio máximo de interação ($D_{adj}$): Os qubits que interagem devem estar dentro de uma faixa de distância específica (por exemplo, $\approx$10,26 $\mu$m).
3. Tamanho do registro ($L$): Todos os átomos devem caber dentro de uma área circular de raio $L$ (por exemplo, 50 $\mu$m).
4. Maximização da Lacuna de Adjacência: A solução deve maximizar a diferença entre a distância mínima de pares não adjacentes e o raio de interação de pares adjacentes para garantir robustez.

Este problema é NP-difícil e não convexo. Solucionadores clássicos (como Programação Quadrática com Restrições Inteira Mista ou Programação Não Linear) lutam com a escalabilidade e frequentemente falham em encontrar soluções viáveis para instâncias de grafos maiores dentro de prazos razoáveis.

Metodologia

Os autores propõem um Framework de Otimização Aprimorado por Redes Neurais centrado em uma arquitetura personalizada chamada Rede Codificadora de Distância (DEN) e uma Função de Perda de Incorporação Especializada (ELF).

1. A Rede Codificadora de Distância (DEN)

A DEN é um autoencoder modificado projetado para aprender uma transformação espacial não linear.

• Entrada: Coordenadas iniciais dos vértices do grafo ($\vec{p}_i$), geradas via uma fase de pré-processamento.
• Arquitetura:
  • Autoencoder Treinável: Comprime as coordenadas de entrada através de camadas totalmente conectadas com ativações ReLU e dropout, e depois as reconstrói em um novo conjunto de coordenadas ($\vec{p}^f_i$).
  • Calculadora de Distância de Pesos Fixos: Um componente não treinável que recebe as coordenadas reconstruídas e calcula as distâncias euclidianas ao quadrado entre todos os pares de vértices ($||\vec{p}^f_i - \vec{p}^f_j||^2$). Esta camada usa pesos fixos ($\pm 1, 0$) para realizar subtração de vetores e quadratura, garantindo que a rede outpute métricas de distância válidas.
• Inicialização por Pré-processamento: Dois métodos são usados para gerar coordenadas iniciais:
  • Escala: Escalonamento de coordenadas aleatórias para caber no raio do domínio $L$.
  • Fruchterman-Reingold: Um algoritmo de layout baseado em forças que usa forças atrativas/repulsivas baseadas na matriz de adjacência do grafo.

2. A Função de Perda de Incorporação (ELF)

Em vez de usar backpropagation padrão em um conjunto de dados estático, a rede é treinada para minimizar uma função de perda personalizada que codifica as restrições do CUDG diretamente. A ELF combina dois componentes baseados na Função de Perda de Classificação por Margem:

• $ELF_{min}$: Impõe limites inferiores. Penaliza casos onde vértices adjacentes estão muito distantes ou vértices não adjacentes estão muito próximos (violando a separação mínima para pares não interagentes).
• $ELF_{max}$: Impõe limites superiores. Penaliza casos onde vértices adjacentes excedem o raio de interação ou vértices não adjacentes estão muito próximos.
• Objetivo: A perda total direciona a rede a encontrar coordenadas onde as restrições de distância são satisfeitas (viabilidade) enquanto maximiza implicitamente a "lacuna de adjacência" (a margem entre distâncias viáveis e inviáveis).

3. Estratégia de Treinamento

O framework trata cada instância de grafo como uma tarefa de treinamento independente. A rede é treinada por um número fixo de épocas (por exemplo, 3000) usando o otimizador AdamW. O processo itera para encontrar a melhor incorporação viável, atualizando o parâmetro alvo "lacuna de adjacência" ($\alpha$) sempre que uma solução viável melhor é encontrada.

Contribuições Principais

1. Framework Inovador: Introdução de uma abordagem de otimização aprimorada por redes neurais especificamente adaptada para o problema CUDG em arquiteturas quânticas de átomos neutros.
2. Rede Codificadora de Distância (DEN): Uma arquitetura especializada de autoencoder que integra uma calculadora de distância de pesos fixos para outputar diretamente distâncias euclidianas ao quadrado, permitindo que restrições sejam aplicadas diretamente a propriedades geométricas.
3. Função de Perda de Incorporação (ELF): Uma formulação de perda personalizada que traduz restrições geométricas rígidas (inequações sobre distâncias) em um objetivo de otimização diferenciável, permitindo que a rede aprenda configurações espaciais viáveis.
4. Tratamento da Não Convexidade: A abordagem aproveita as capacidades de aproximação de redes neurais para navegar no espaço de soluções não convexo do problema CUDG, onde solucionadores clássicos frequentemente falham.

Resultados Experimentais

Os autores avaliaram o framework em um conjunto de dados de 200 instâncias de grafos (variando de $n=10$ a $n=100$ vértices) contra o solucionador clássico Ipopt.

• Viabilidade: O framework baseado em DEN superou significativamente o Ipopt na busca por incorporações viáveis. Enquanto o Ipopt falhou em encontrar soluções para muitas instâncias (especialmente à medida que $n$ aumentava), o modelo DEN encontrou com sucesso incorporações viáveis para uma porcentagem muito maior do conjunto de dados, incluindo instâncias com até 100 vértices no espaço 3D.
• Dimensionalidade: O modelo encontrou soluções viáveis mais facilmente em 3D ($N=3$) do que em 2D ($N=2$), provavelmente devido ao aumento dos graus de liberdade.
• Tempo de Computação: O tempo de treinamento do modelo DEN escalou linearmente com o número de vértices. Mesmo quando o Ipopt recebeu significativamente mais tempo (10x o tempo de treinamento do DEN), ele ainda falhou em resolver instâncias que o DEN resolveu rapidamente.
• Lacuna de Adjacência: Embora o modelo DEN se destacasse em encontrar soluções viáveis, o solucionador clássico (quando bem-sucedido) às vezes produzia incorporações com uma lacuna de adjacência maior. Os autores observam que otimizar a lacuna permanece um desafio para a abordagem neural.

Significado e Alegações

O artigo afirma que o framework proposto fornece uma alternativa viável aos solucionadores clássicos para problemas de incorporação em hardware quântico, particularmente onde os métodos clássicos lutam com não convexidade e escalabilidade.

• Impacto Prático: Permite o mapeamento de problemas QUBO complexos para arquiteturas de átomos neutros, um passo crítico para a utilização dessas máquinas quânticas.
• Generalizabilidade: Os autores sugerem que a arquitetura DEN e a estratégia ELF são generalizáveis para outros problemas de otimização envolvendo restrições de distância euclidiana e modelagem de inequações.
• Trabalho Futuro: O artigo reconhece modestamente limitações, especificamente em relação à maximização da lacuna de adjacência e à necessidade de ajuste de hiperparâmetros. Propõe trabalho futuro para melhorar a utilização de GPU (via mini-lotes) e para refinar a otimização do parâmetro de lacuna de adjacência.

Os autores enfatizam que, embora a abordagem atual não garanta a lacuna de adjacência ótima, sua contribuição primária é a capacidade de encontrar soluções viáveis para um conjunto mais amplo de instâncias de grafos do que anteriormente possível com métodos clássicos.