Resumo Técnico: Geração de Compiladores para Mapeamento e Roteamento de Qubits

1. Definição do Problema

A execução de circuitos quânticos em unidades de processamento quântico (QPUs) físicas requer a resolução do problema de mapeamento e roteamento de qubits (QMR). Um compilador deve mapear os qubits do circuito lógico para os qubits físicos do dispositivo e planejar a execução das portas, aderindo à conectividade específica e às restrições de erro do hardware alvo.

O cenário do hardware quântico é incrivelmente diverso e evolui rapidamente. Ele inclui diversas realizações físicas (circuitos supercondutores, íons aprisionados, átomos neutros), diversas topologias de conectividade (matrizes lineares, grades, armadilhas totalmente conectadas) e variados esquemas de correção de erros (desde a ausência de correção de erros em dispositivos NISQ até códigos de superfície em arquiteturas tolerantes a falhas). Atualmente, abordar um novo problema de QMR normalmente exige que pesquisadores reiniciem o processo do zero: estabelecendo resultados de dureza, identificando conexões com problemas da teoria dos grafos e desenvolvendo algoritmos de compilação especializados para cada configuração de hardware específica. Este artigo questiona se é possível sintetizar automaticamente um compilador a partir de uma especificação de restrições arquiteturais em vez de projetar manualmente um novo solver para cada arquitetura emergente.

2. Metodologia

Os autores propõem o Amaro (Abstract MApping and ROuting), um framework que unifica problemas de QMR através de uma estrutura central comum e gera compiladores automaticamente.

2.1 Formulação Abstrata: Máquinas de Estado do Dispositivo

A ideia central é que todos os problemas de QMR podem ser modelados como uma máquina de estado do dispositivo. Uma solução é vista como uma sequência de estados do dispositivo, onde cada estado captura:

• O mapeamento atual dos qubits do circuito para localizações físicas.
• O conjunto de portas executadas em paralelo naquele passo de tempo.
• As transições entre estados (por exemplo, operações de swap ou transformações de identidade).

Os autores definem um problema de QMR abstrato onde as restrições específicas de uma arquitetura de hardware ditam quais estados são válidos (realizáveis) e quais transições são permitidas.

2.2 A Linguagem Amaro

Para facilitar a especificação desses problemas abstratos, os autores projetaram a Amaro, uma linguagem de domínio específico (DSL). Um programa Amaro define um problema de QMR concreto especificando:

• RouteInfo: Restrições sobre estados válidos, especificamente como as portas são realizadas (por exemplo, mapear uma porta de dois qubits para uma aresta em um grafo de conectividade ou um caminho em uma rede).
• TransitionInfo: Restrições sobre transições válidas entre estados (por exemplo, operações de swap entre qubits adjacentes ou transições de identidade onde o mapeamento permanece estático).
• Cost: O objetivo de otimização (por exemplo, minimizar o número de portas de swap, passos de tempo ou maximizar a probabilidade de sucesso).

Programas Amaro são concisos; por exemplo, a especificação para o problema padrão NISQ requer apenas 12 linhas de código.

2.3 O Solver Paramétrico

Os autores apresentam um solver genérico e paramétrico que recebe uma especificação Amaro e instancia um compilador para aquele problema específico. O solver emprega uma abordagem aproximada e iterativa baseada em construção de estado máximo:

1. Construção de Estado Máximo: Em cada iteração, o solver tenta construir um "estado máximo" roteando o maior número possível de portas da camada frontal atual do circuito.
2. Monotonicidade e Não-Interferência: O solver utiliza duas propriedades para otimizar este processo. Se o problema for monotônico (subconjuntos de estados realizáveis também são realizáveis), uma única passagem pode encontrar um estado máximo. Se o problema for não-interferente (rotear uma porta não bloqueia outra), o estado máximo é único e independente da ordem.
3. Estratégias de Busca: Para problemas que não são não-interferentes (onde caminhos de portas podem conflitar), o solver utiliza simulated annealing para buscar a ordenação ideal de portas para maximizar o número de instruções roteadas. Da mesma forma, o solver utiliza simulated annealing para buscar o mapeamento inicial de qubits ideal.
4. Saída: O processo se repete, atualizando o mapa de qubits via transições válidas, até que todas as portas no circuito sejam roteadas.

3. Principais Contribuições

• Formulação Abstrata: Uma visão unificada de problemas de QMR baseada em máquinas de estado de dispositivo, fornecendo uma maneira uniforme de pensar sobre diversas restrições de hardware.
• Linguagem de Especificação (Amaro): Uma DSL que permite a expressão concisa de restrições arquiteturais únicas, permitindo a definição de novos problemas de QMR com código mínimo.
• Solver Paramétrico: Um algoritmo genérico e poderoso que instala automaticamente um compilador a partir de uma especificação Amaro. Ele equilibra qualidade de solução e tempo de execução através de métodos aproximados (construção de estado máximo e simulated annealing).
• Avaliação Empírica: Uma avaliação abrangente através de sete estudos de caso distintos, variando de arquiteturas NISQ a código de superfície tolerante a falhas e qubits lógicos intercalados.

4. Resultados Experimentais

Os autores avaliaram os compiladores gerados contra solvers especializados escritos à mão de última geração em um conjunto de benchmarks de 243 circuitos de aplicação.

• NISQ (NISQMR): O compilador gerado é competitivo com o Qiskit (usando o algoritmo Sabre) e o QSynth2. Ele iguala ou supera o Qiskit em aproximadamente 48% dos benchmarks e encontra soluções ótimas em 66/73 casos onde o QSynth2 termina.
• Erro Variável (NISQ-VE): Ao considerar taxas de erro variáveis em links, o compilador gerado pelo Amaro produz soluções com probabilidades de sucesso equivalentes ao Qiskit em média, demonstrando a capacidade de otimizar para confiabilidade em vez de apenas contagem de portas.
• Código de Superfície (SCMR): O compilador gerado supera a ferramenta especializada DASCOT, encontrando melhores soluções em 57% dos casos e igualando ou superando-a em 92% dos casos em que ambos terminam.
• Matrizes de Átomos Reconfiguráveis (RAA): O solver supera significativamente o compilador Enola, encontrando soluções de maior qualidade em 97% dos casos em que pelo menos uma ferramenta termina.
• Qubits Lógicos Intercalados (ILQ): O solver produz soluções de qualidade estritamente superior ao compilador guloso (greedy) de linha de base em 93% dos casos.
• Íons Aprisionados (TIQMR): O solver supera significativamente o algoritmo Shaper, reduzindo custos em pelo menos 50% em todos os casos em que ambos terminam e resolvendo 27 benchmarks onde o Shaper falha.

Em termos de tempo de execução, os compiladores gerados geralmente convergem para soluções de alta qualidade dentro de minutos (por exemplo, atingindo um limiar de 10% da melhor solução em ~300–600 segundos para 80% dos benchmarks), tornando-os adequados para compilação de escala industrial.

5. Significância e Alegações

O artigo afirma que a diversidade do hardware quântico exige uma mudança do desenvolvimento de compiladores especializados manuais para a síntese automatizada. Ao identificar a estrutura central comum dos problemas de QMR, o Amaro permite que pesquisadores e desenvolvedores especifiquem restrições para novas arquiteturas (incluindo esquemas tolerantes a falhas emergentes) e gerem automaticamente compiladores competitivos.

Os autores enfatizam que sua abordagem simplifica o desenvolvimento de compiladores quânticos para arquiteturas novas e emergentes. Embora os compiladores gerados sejam aproximados e não garantam a otimalidade (visto que QMR é NP-difícil), eles demonstram ser altamente competitivos com solvers especializados e feitos à mão tanto em qualidade de solução quanto em tempo de execução. O trabalho sugere que uma abordagem de "escrever uma vez, gerar muitos" é viável para a pilha de compilação quântica, potencialmente acelerando a adaptação do software quântico ao cenário de hardware em rápida mudança.