Resumo Técnico: Compilação Eficiente para Máquinas de Íons Aprisionados com Transporte via Abstração Arquitetural de Grafo de Posição

1. Declaração do Problema

O artigo aborda o desafio crítico de compilar circuitos quânticos para arquiteturas de Dispositivo Quântico de Carga Acoplada (QCCD) de Íons Aprisionados (TI). Embora os sistemas TI ofereçam operações de alta fidelidade e tempos de coerência longos, eles enfrentam um gargalo único de escalabilidade: os íons devem ser fisicamente transportados entre armadilhas para realizar portas de múltiplos qubits. Esse processo de "transporte" é significativamente mais lento (microssegundos) do que a execução da porta e introduz aquecimento que degrada a fidelidade da porta.

Os paradigmas atuais de compilação para sistemas TI frequentemente dependem de uma abordagem de duas camadas:

1. Camada Lógica: Assume um modelo de conectividade todos-para-todos, otimizando o circuito sem considerar restrições físicas.
2. Camada Física: Tenta resolver cronogramas de transporte após a otimização.

Os autores argumentam que essa abordagem é falha. A otimização para contagem de portas em um modelo todos-para-todos frequentemente resulta em operações lógicas que estão fisicamente distantes, necessitando de movimentos de transporte excessivos e complexos que criam congestionamento, deadlocks e aumento de aquecimento. Compiladores específicos para TI existentes (por exemplo, QCCDSim) lutam com cenários de alto congestionamento, particularmente quando o número de qubits se aproxima da capacidade total da armadilha, frequentemente falhando em produzir cronogramas válidos.

2. Metodologia

A Abstração do Grafo de Posição

Para preencher a lacuna entre a rica literatura sobre mapeamento de qubits supercondutores e as restrições específicas do transporte de TI, os autores introduzem o Grafo de Posição.

• Definição: Um grafo direcionado $G(V, E, \psi_v, \psi_e)$ onde os vértices representam posições físicas possíveis para um íon (não apenas os próprios íons) e as arestas representam conexões.
• Rotulagem:
  • Vértices ($\psi_v$): Rotulados como Executar, Medir, Executar+Medir ou Nenhum (armazenamento), distinguindo entre armadilhas executáveis e zonas de armazenamento.
  • Arestas ($\psi_e$): Rotuladas com capacidades de movimento (Mover, Trocar, Mover+Trocar) e capacidades de execução (Executar).
• Função: Essa abstração codifica naturalmente as restrições de hardware:
  • Íons só podem trocar dentro de armadilhas executáveis.
  • Íons só podem mover-se ao longo de caminhos de transporte (segmentos/junções).
  • Junções são modeladas como subgrafos completos de grau $d$, permitindo conectividade par a par entre segmentos conectados.
  • Captura cenários de congestionamento e deadlock (por exemplo, um íon bloqueado de fundir-se porque uma armadilha está cheia) que são difíceis de modelar com grafos de acoplamento padrão.

Algoritmos: SHAPER e SHAW

Os autores propõem dois algoritmos de busca heurística construídos sobre o Grafo de Posição, adaptando técnicas de mapeamento de ponta para supercondutores (SABRE e Mapeamento Consciente de Permutação - PAM):

1. SHuttling-AWare (SHAW): Uma busca heurística que itera através da frente e das camadas estendidas do circuito. Utiliza uma função de pontuação (Equação 3) para avaliar movimentos de transporte candidatos. A pontuação equilibra:
   • A distância máxima entre qubits em um bloco de porta (priorizando o qubit mais distante).
   • A distância dos qubits até a zona executável disponível mais próxima.
   • Um componente de antecipação baseado na camada estendida.
2. SHuttling-Aware PERmutative (SHAPER): Uma extensão do SHAW que incorpora Síntese Consciente de Permutação. Antes do agendamento, ele particiona o circuito em blocos, res sintetiza-os para várias permutações de qubits e seleciona a permutação que minimiza um custo combinado de contagem de portas e congestionamento potencial de transporte.

Resolução de Deadlock e Congestionamento:
Ambos os algoritmos incluem mecanismos para escapar de mínimos locais e resolver deadlocks:

• Escape de Mínimo Local: Se nenhum movimento válido for encontrado, o algoritmo identifica uma zona executável alvo e uma ordem específica de qubits para mover, priorizando o caminho mais curto.
• Resolução de Congestionamento (Algoritmo 3): Se uma armadilha alvo estiver cheia ou um caminho bloqueado, o algoritmo move recursivamente íons bloqueadores para espaços vazios adjacentes ou de volta para as armadilhas mais próximas para liberar o caminho.

Programação Linear Inteira Mista (PLIM) como Linha de Base

Para fornecer uma linha de base ótima para comparação, os autores formulam o problema de agendamento TI como um Programa Linear Inteiro Misto. Essa formulação resolve cronogramas ótimos para circuitos pequenos (até 8 qubits), mas é computacionalmente intratável para instâncias maiores devido à escalabilidade exponencial.

3. Contribuições Principais

1. Abstração do Grafo de Posição: Um quadro unificador que estende o conceito de grafo de acoplamento para modelar restrições de QCCD, permitindo a adaptação de algoritmos de mapeamento supercondutores para sistemas TI.
2. Algoritmos SHAPER e SHAW: Heurísticas inovadoras que compilam com sucesso circuitos para arquiteturas extremas onde ferramentas de ponta (como QCCDSim) falham devido a congestionamento ou deadlocks.
3. Tratamento de Congestionamento e Deadlock: O primeiro algoritmo baseado em transporte capaz de resolver congestionamento em arquiteturas QCCD 2D e utilizar totalmente o espaço de armadilha disponível, alcançando 100% de utilização em cenários onde concorrentes falham.
4. Conexão Teórica: O trabalho vincula o problema de transporte TI ao Problema de Reconfiguração de Tokens (TRP) e Roteamento Cooperativo (MAPF), fornecendo uma base teórica para futuras melhorias algorítmicas.
5. Avaliação Abrangente: Um estudo de benchmarking através de vários tipos de circuitos (QAOA, QFT, TFIM, TFXY) e arquiteturas (Tipo-H, G2x3, etc.), comparando com QCCDSim e um solucionador ótimo PLIM.

4. Resultados Experimentais

Os autores avaliaram seus métodos contra o QCCDSim (o estado da arte atual para agendamento TI) e a linha de base PLIM.

• Circuitos de Pequena Escala (8 qubits):
  • Taxa de Sucesso: SHAPER e SHAW resolveram todas as configurações. O QCCDSim falhou em 50% dos casos (marcado como 'X').
  • Desempenho: O SHAPER produziu cronogramas 2,14 vezes mais rápidos em média do que o QCCDSim (melhor caso: 3,7x). O SHAW foi 1,58 vezes mais rápido em média.
  • Lacuna de Otimalidade: Comparado à solução ótima PLIM, a lacuna do SHAPER foi de ~97%, enquanto a lacuna do QCCDSim foi de ~285%.
• Circuitos de Grande Escala (16–128 qubits):
  • Escalabilidade: O QCCDSim falhou sempre que a contagem de qubits do circuito igualou ou excedeu a capacidade total da armadilha (alta utilização). SHAPER e SHAW geraram com sucesso cronogramas válidos mesmo com 100% de utilização.
  • Aceleração: Para circuitos de 16–20 qubits, o SHAPER foi 1,936 vezes mais rápido em média (redução de 42,5% no tempo de operação). Para circuitos de 32–128 qubits, o SHAPER foi 1,68 vezes mais rápido em média.
  • Melhor Caso: O SHAPER alcançou até 4x de aceleração sobre o QCCDSim em configurações específicas.
• Fidelidade: Devido à redução do tempo de transporte e do aquecimento, SHAPER e SHAW produziram consistentemente maior fidelidade de circuito do que o QCCDSim, particularmente em casos onde os tempos de operação eram comparáveis.
• Tempo de Execução: Embora SHAPER/SHAW levem mais tempo para compilar (segundos a minutos) em comparação com o QCCDSim (milissegundos), eles produzem cronogramas de execução significativamente melhores. O tempo de execução da compilação escala com um expoente de ~3,5–3,98, ligeiramente melhor que o ~3,90 do QCCDSim.

5. Significado e Alegações

O artigo afirma que o Grafo de Posição é uma abstração necessária para quebrar a suposição "todos-para-todos" que aflige a compilação TI atual. Ao integrar restrições físicas diretamente no processo de mapeamento, os autores demonstram que:

• É possível compilar para arquiteturas extremas (alta densidade de íons) onde métodos anteriores falham.
• Congestionamento e deadlocks podem ser resolvidos algoritmicamente sem simplificar excessivamente as restrições de hardware.
• Existe um compromisso entre tempo de compilação e qualidade de execução; as heurísticas propostas oferecem um equilíbrio superior, reduzindo o tempo total de execução e erros induzidos por aquecimento.

Os autores observam modestamente que, embora suas heurísticas não sejam ótimas (como evidenciado pela lacuna em relação à solução PLIM), elas representam um passo significativo para tornar os sistemas TI baseados em QCCD escaláveis e confiáveis. Eles sugerem que trabalhos futuros poderiam envolver modelos de fidelidade calibrados por hardware e maior adaptação de algoritmos baseados em teoria dos grafos (por exemplo, busca baseada em conflitos) ao quadro do grafo de posição.