A Multilevel Framework for Partitioning Quantum Circuits

Resumo Técnico: Um Framework Multinível para Particionamento de Circuitos Quânticos

Declaração do Problema
A Computação Quântica Distribuída (DQC) oferece um caminho para sistemas quânticos escalonáveis ao conectar múltiplos Processadores Quânticos (QPUs) via emaranhamento. No entanto, executar algoritmos quânticos através desses nós distribuídos introduz sobrecargas significativas. O mapeamento ingênuo de circuitos para QPUs resulta em altos custos de comunicação, especificamente o consumo de pares emaranhados (e-bits), aumento no tempo de execução e ruído acentuado. O desafio central reside em atribuir de forma otimizada os qubits lógicos aos QPUs e determinar o método mais eficiente para cobrir operações não locais (portas que atuam sobre qubits residindo em diferentes QPUs). Embora métodos existentes abordem isso, eles frequentemente falham em capturar todo o espectro de possibilidades de teletransporte ou lutam contra a natureza NP-difícil do problema de otimização, particularmente à medida que o tamanho dos circuitos e as escalas de rede aumentam.

Metodologia
Os autores propõem um framework multinível abrangente que formaliza o particionamento de circuitos quânticos como um problema de particionamento de hipergrafo. O fluxo de trabalho consiste em várias etapas distintas:

1. Construção de Grafo e Agrupamento de Portas:

   • Os circuitos são transpilados para um conjunto de portas específico ($U(\theta, \phi, \lambda)$ e $CP(\theta)$) e convertidos em um grafo temporalmente estendido onde os nós representam qubits em passos de tempo específicos.
   • Este grafo é generalizado em um hipergrafo ao agrupar portas com base na "compatibilidade" para teletransporte de múltiplas portas. Um grupo é formado se as portas de dois qubits compartilharem um qubit de controle comum, forem contíguas e não forem interrompidas por portas de um único qubit não-diagonais no controle.
   • O framework introduz o teletransporte de estado aninhado, um protocolo inovador onde procedimentos de teletransporte de porta são parcialmente colapsados em teletransporte de estado. Isso permite que o sistema escolha dinamicamente entre teletransporte de estado e de porta ao redirecionar o "processo de término" de um procedimento de teletransporte de múltiplas portas.

2. Função Objetivo:

   • Uma função de custo única é projetada para minimizar o número de e-bits necessários. O custo de uma hiper-aresta é definido pelo número de partições abrangidas pelo conjunto receptor que não são contabilizadas pelo conjunto raiz (efetivamente contando cortes que exigem novos recursos de emaranhamento).
   • O objetivo é minimizar a soma desses custos através de todas as arestas: $\min_{\Phi} \sum_{e \in E} c_e(\Phi)$.

3. Algoritmo de Particionamento (FM Adaptado):

   • O conhecido heurístico Fiduccia-Mattheyses (FM) é adaptado para lidar com a estrutura de hipergrafo temporal e restrições de equilíbrio específicas (capacidade de qubit por QPU em cada passo de tempo).
   • Para garantir a eficiência, os autores pré-computam custos para todas as configurações possíveis de hiper-aresta e utilizam estruturas de dados auxiliares (contagens de raiz/receptor) para calcular "ganhos delta" em tempo constante.
   • Para escapar de mínimos locais inerentes às atribuições iniciais estáticas, os autores introduzem passagens exploratórias que não revertem para o melhor ganho cumulativo, permitindo que o algoritmo atravesse sequências de movimentos que temporariamente aumentam o custo para alcançar melhores ótimos globais.

4. Framework Multinível:

   • Inspirado em particionadores de grafos de última geração (ex: METIS, KaHyPar), o framework emprega coarsening temporal (refinamento de granularidade). Em vez de mesclar nós aleatoriamente, ele mescla passos de tempo (janela, bloco ou coarsening recursivo).
   • O processo envolve:
     • Coarsening (Refinamento de Granularidade): Redução da resolução temporal para criar um hipergrafo menor e mais grosseiro.
     • Particionamento: Resolver o problema de particionamento no grafo mais grosseiro.
     • Uncoarsening e Refinamento: Restaurar gradualmente a resolução temporal, usando a solução do nível anterior como ponto de partida e aplicando o refinamento FM em cada nível.
   • A estratégia de coarsening recursivo (mesclando passos de tempo adjacentes) é identificada como a mais eficaz, oferecendo escalonamento logarítmico no número de níveis.

5. Extração de Circuito:

   • O grafo particionado final é convertido de volta em um circuito quântico distribuído. Isso inclui o agendamento da geração de emaranhamento, processos de início e término para teletransporte, e o gerenciamento de recursos de qubits de comunicação.

Principais Contribuições

• Formalização do Teletransporte de Estado Aninhado: O artigo introduz uma visão unificada onde o teletransporte de estado e de porta são tratados como variações do mesmo procedimento, determinados pela direção do processo de término. Isso expande o espaço de design para otimizar custos de emaranhamento.
• Particionamento Temporal Multinível: A adaptação de técnicas multiníveis especificamente para a estrutura temporal de circuitos quânticos, permitindo que o problema seja resolvido em diferentes granularidades para melhorar tanto a qualidade da solução quanto o tempo de execução.
• Heurística FM Adaptada: Um algoritmo Fiduccia-Mattheyses modificado que lida eficientemente com a função de custo específica e restrições de equilíbrio de DQC, incluindo mecanismos para evitar mínimos locais através de passagens exploratórias.
• Implementação Open-Source: O framework é implementado no repositório disqco, fornecendo uma ferramenta reproduzível para compilação de circuitos quânticos distribuídos.

Resultos
O framework foi testado contra métodos de última geração, incluindo Pytket-DQC (usando fluxos de trabalho Partition, PartitionEmbed e EmbedSteinerDetached) e o método Fine-Grained Partitioning (FGP-rOEE).

• Redução de Emaranhamento: Em uma ampla gama de tipos de circuitos (CP-fraction, QFT, QAOA, Quantum Volume e benchmarks QASM), o framework multinível proposto (especificamente a variante recursiva, MLFM-R) alcançou os menores custos de emaranhamento na maioria dos casos.
• Melhoria Quantitativa: Em média, o framework reduziu os requisitos de emaranhamento em 35% comparado ao segundo melhor método.
• Escalabilidade: A abordagem multinível reduziu significativamente o tempo de execução em comparação com o FM padrão e permitiu o particionamento de circuitos muito maiores (centenas de qubits) do que os métodos concorrentes, desde que o número de partições não fosse excessivamente grande.
• Trade-offs (Compromissos): O uso de agrupamento de portas (teletransporte de múltiplas portas) reduziu significantemente a profundidade do circuito, mas aumentou a demanda por qubits de comunicação. O framework permite que os usuários ajustem esse compromisso com base nos recursos de hardware disponíveis.

Significância e Alegações
O artigo afirma que o framework multinível proposto representa um avanço significativo na compilação de circuitos quânticos distribuídos. Ao unificar vários protocolos de teletransporte (estado, porta e estado aninhado) dentro de um único objetivo de otimização e alavancar técnicas de particionamento de grafos multiníveis, os autores demonstram que é possível minimizar substancialmente o overhead de emaranhamento — o principal gargalo em DQC.

Os autores enfatem que, embora seu trabalho atual assuma conectividade todos-para-todos entre QPUs e foque em redes com menos de 20 QPUs, as técnicas principais são projetadas para serem extensíveis. Eles afirmam que este framework fornece uma base robusta para futuros stacks de compiladores de computação quântica distribuída, capazes de lidar com a complexidade de redes quânticas grandes, ruidosas e restritas. O trabalho destaca que otimizar para a minimização de emaranhamento não é apenas um exercício teórico, mas uma necessidade prática para tornar algoritmos quânticos distribuídos viáveis em hardware de curto e longo prazo.