dSABRE: A SABRE-Style Router for Multi-Core Distributed Quantum Computers

Resumo Técnico: DSABRE – Um Roteador Estilo SABRE para Computadores Quânticos Distribuídos Multi-Core

Declaração do Problema
O caminho para a computação quântica tolerante a falhas exige a escalabilidade além de chips monolíticos únicos para Computadores Quânticos Distribuídos (DQCs), onde múltiplas Unidades de Processamento Quântico (QPUs ou "núcleos") pequenas são interconectadas por meio de links fotônicos ou de micro-ondas. A execução de circuitos em DQCs envolve um pipeline de compilação composto por alocação de qubits, seleção de primitivas de comunicação e roteamento/agendamento. O objetivo dominante neste contexto é minimizar o consumo de EPR (pares emaranhados), pois a geração de EPR é lenta, ruidosa e limitada em taxa em comparação com operações de portas locais.

Embora roteadores de última geração como o TELESABRE utilizem heurísticas estilo SABRE para rotear circuitos entre núcleos, eles lidam com o congestionamento de forma defensiva. O TELESABRE desencoraja o pouso em núcleos saturados por meio de penalidades e tenta recuperar-se de deadlocks descartando informações de lookahead. No entanto, em instâncias densas ou grandes, essa abordagem reativa frequentemente consome excessivos pares de EPR ou falha em convergir completamente. O desafio central abordado por este artigo é a falta de gerenciamento proativo de congestionamento e a ineficiência dos mecanismos de lookahead existentes em configurações inter-core.

Metodologia: DSABRE
O DSABRE é um roteador estilo SABRE projetado para processadores multi-core. Ele opera dentro de um layout inicial fixo (gerado pelo Qiskit SabreLayout) e foca na etapa de roteamento: ordenando SWAPs intra-core e teleportações inter-core (especificamente teledata, movendo qubits lógicos entre núcleos). O algoritmo executa um loop orientado a lookahead com quatro fases por iteração:

1. Drenagem: Executar portas 1Q e portas 2Q intra-core adjacentes.
2. Particionamento: Separar as portas da camada frontal restantes em intra-core ($F_{intra}$) e inter-core ($F_{inter}$).
3. Pontuação e Aplicação:
   • Se $F_{intra}$ não estiver vazio, selecionar o melhor SWAP intra-core.
   • Se $F_{intra}$ estiver vazio, pontuar candidatos a teleportação inter-core e candidatos de alívio proativo de congestionamento, aplicando a jogada com a menor pontuação.
4. Checkpoint/Reversão: Salvar o estado ao ocorrer progresso; se estagnar por um número definido de iterações, restaurar um checkpoint e forçar o progresso para escapar do deadlock.

Principais Contribuições e Mecanismos
O artigo identifica três mecanismos específicos que impulsionam a melhoria do DSABRE sobre o estado da arte:

1. Pontuação de Teleportação Centrada em Portas de Cinco Termos:
   Diferentemente da estimativa de energia global do TELESABRE, o DSABRE utiliza uma pontuação local, centrada em portas ($s$), para movimentos inter-core. A pontuação combina cinco termos:

   • Custo de Estágio ($d_{prep}$): SWAPs intra-core necessários para mover um qubit até uma porta de comunicação.
   • Penalidade de Capacidade ($c_{cap}$): Um termo que penaliza explicitamente a teleportação para núcleos com baixa capacidade livre, impedindo que o roteador inunde núcleos saturados.
   • Ganho de Salto ($g_{hop}$): Uma recompensa direcional para movimentos que reduzem a distância inter-core até o alvo, compensando quando a porta de pouso está longe da posição de estágio ideal.
   • Ganho de Camada Frontal ($\Delta_F$): Redução imediata na distância física para a porta atual.
   • Lookahead ($\tilde{\Delta}_E$): Uma soma ponderada por decaimento de reduções futuras de distância.

2. Alívio Proativo de Congestionamento:
   O DSABRE mantém um vetor de demanda explícito sobre os núcleos. Antes que um núcleo se torne saturado (alta demanda, baixa capacidade), o roteador gera proativamente "candidatos de alívio" para teleportar qubits ociosos para longe de núcleos de alta demanda. Esses movimentos são pontuados dentro da mesma função objetivo (com $\Delta_F=0$) e competem diretamente com movimentos orientados por portas. Isso previne a "cascata de despejo" que leva ao deadlock em sistemas reativos.

3. Conjunto Estendido Inter-Core em Camadas BFS:
   O SABRE padrão constrói conjuntos de lookahead em ordem topológica, o que pode misturar fios não relacionados. O TELESABRE usa camadas BFS, mas pondera portas arbitrariamente. O DSABRE constrói o conjunto de lookahead inter-core camada por camada usando Busca em Largura (BFS) no DAG. Crucialmente, dentro de cada camada, portas que compartilham um fio com a frente são emitidas primeiro. O decaimento do lookahead é aplicado com base na profundidade da BFS ($\gamma^{dep(g)}$), garantindo que sucessores de curto prazo dominem o sinal e que o conjunto respeite as dependências do DAG mais estritamente do que a ordenação topológica.

Resultados Experimentais
Os autores avaliaram o DSABRE contra o TELESABRE e o pytket-dqc (um roteador baseado em teleportação de portas) em 18 circuitos MQT-Bench com 25, 36 e 64 qubits lógicos, utilizando arquiteturas de grade de grades (B-grid e H-grid).

• Redução de EPR: O DSABRE reduz o consumo geométrico médio de EPR em 41–44% comparado ao TELESABRE e em 16–68% comparado ao pytket-dqc.
• Escalabilidade: Em um circuito Aleatório de 64 qubits, o TELESABRE falhou em convergir em todas as sementes, enquanto o DSABRE completou o roteamento. Uma varredura de escalabilidade em circuitos de Transformada Quântica de Fourier (QFT) até 360 qubits confirmou que o DSABRE mantém sua vantagem conforme o tamanho do circuito e a arquitetura escalam.
• Estudos de Ablação:
  • Remover a penalidade de capacidade aumentou o EPR geométrico médio em ~59% (25q) e ~59% (64q), identificando-a como o componente mais crítico.
  • Desabilitar o alívio proativo de congestionamento aumentou o EPR em 23,4% no conjunto de 64q, com circuitos densos (AE, QFT) vendo um aumento superior a 100%.
  • Substituir o conjunto estendido em camadas BFS por ordenação topológica aumentou o EPR em 3–11%, com ganhos crescendo para circuitos maiores.
• Sensibilidade ao Custo: À medida que o custo relativo da teleportação ($c_{tele}$) aumenta (simulando hardware de link fotônico), a lacuna de desempenho entre DSABRE e TELESABRE se amplia, com o DSABRE economizando até ~39% mais EPRs em altas razões de custo.

Significado e Alegações
O artigo alega que o roteamento distribuído se beneficia menos de fórmulas complexas de pontuação por candidato e mais de garantir que sinais de lookahead e restrições de capacidade arquitetural entrem na mesma etapa de pontuação. Ao integrar alívio proativo de congestionamento e uma pontuação consciente de capacidade, o DSABRE evita os deadlocks e o consumo excessivo de EPR que afligem roteadores reativos e defensivos.

Os autores posicionam o DSABRE como complementar a métodos de alocação estática (como particionamento de hipergrafos) e agendadores conscientes do tempo. Eles observam que, embora o DSABRE atualmente use apenas teledata (teleportação de estado), ele é projetado para ser um motor de roteamento robusto que pode ser combinado com outras primitivas ou passagens de execução em rajada em trabalhos futuros. Os resultados sugerem que o gerenciamento explícito de capacidade é um componente necessário para a escalabilidade da compilação quântica distribuída.