Optimizing Parallel Execution of Commuting Pauli Product Rotations

Resumo Técnico: Otimização da Execução Paralela de Rotações de Produtos de Pauli Comutativas

Declaração do Problema
Na Computação Quântica Tolerante a Falhas (FTQC), especificamente dentro de arquiteturas de código de superfície equipadas com cirurgia de rede, a duração mínima teórica do circuito é determinada pelo número de grupos mutuamente comutativos de Rotações de Produtos de Pauli (PPRs). Embora PPRs mutuamente comutativos possam teoricamente ser executados em paralelo, o hardware prático impõe restrições estritas aos "pontos de acesso" ou "portas" por qubit lógico. Em um código de superfície padrão, cada patch lógico fornece um número limitado de bordas X e Z (tipicamente duas de cada) para interfacear com informações lógicas.

Quando um conjunto de PPRs comutativos excede o orçamento de portas por qubit (por exemplo, exigindo três medições X simultâneas em um único qubit quando apenas duas portas estão disponíveis), o grupo deve ser dividido em etapas sequenciais. Essa divisão infla a profundidade do circuito além do mínimo teórico derivado apenas das relações de comutação. Ferramentas de compilação existentes frequentemente focam na conectividade da camada física ou na redução de ruído, mas não abordam adequadamente essa restrição específica da camada lógica onde operações comutativas são forçadas à serialização devido à saturação de portas.

Metodologia
Os autores propõem um framework de compilação que otimiza a execução paralela de PPRs sem aumentar a sobrecarga de qubits lógicos. A abordagem assume que o circuito de entrada já foi compilado em uma sequência de Medições de Produtos de Pauli (PPMs) via o paradigma de Computação Baseada em Pauli (PBC), onde portas de Clifford são comutadas para o final e absorvidas nas medições, deixando rotações não-Clifford e medições de estados de recurso.

O artigo introduz duas heurísticas primárias para reduzir a profundidade limitada por hardware:

1. Reorganização de Cliques:

   • O circuito de entrada é inicialmente particionado em conjuntos maximais de produtos mutuamente comutativos (cliques).
   • Os autores observam que a ordem dos produtos dentro de um clique afeta como eles são reagrupados quando as restrições de hardware são aplicadas.
   • A heurística envolve permutar a ordem dos produtos comutativos dentro de um grupo e reavaliar o agrupamento. Ao amostrar permutações aleatórias (especificamente trocando pares comutativos adjacentes), o algoritmo busca uma configuração onde os grupos resultantes limitados por hardware sejam menores em número ou mais equilibrados em relação ao uso de portas.

2. Reestruturação de Geradores:

   • Dentro de um grupo mutuamente comutativo, o conjunto de produtos atua como um conjunto gerador para o operador lógico líquido. Qualquer conjunto gerador equivalente realiza a mesma operação lógica.
   • Os autores exploram o fato de que as PPRs são convertidas em PPMs ao anexar uma medição na base Z em um estado de recurso único para cada rotação. Essa estrutura permite a substituição de um produto $P_i$ por um produto equivalente $P_i \otimes P_j$ (onde $P_j$ é outro produto no grupo), efetivamente reescrevendo o gerador.
   • O objetivo é selecionar um novo conjunto gerador que minimize a frequência de caracteres não-identidade (X, Y, Z) em qubits específicos, reduzindo assim a "pressão de portas".
   • Como enumerar todos os $O(2^{s^2})$ conjuntos geradores é intratável, os autores empregam uma heurística gulosa. Esta heurística seleciona pares de Paulis para multiplicar de modo que o produto resultante reduza a contagem de um tipo específico de porta em qubits que atualmente excedem o limite de hardware (por exemplo, reduzindo contagens de X em um qubit com 3 requisitos de X para 2).

Integração e Fluxo de Trabalho
A abordagem proposta combina essas estratégias. Primeiro, aplica a reorganização de cliques para gerar múltiplas variações do circuito de entrada. Para cada variação, aplica a reestruturação gulosa de geradores para minimizar o uso de portas. Finalmente, constrói grupos comutativos limitados por hardware para cada variação e seleciona a configuração que produz a profundidade de circuito mínima.

Resultados
Os autores avaliaram seus métodos na suíte QASMBench, compilando circuitos nos formatos Clifford+T e Clifford+Rz, e subsequentemente convertendo-os em PPRs.

• Redução de Profundidade: As heurísticas combinadas alcançaram uma redução média de profundidade limitada por hardware de 10–20% em comparação com uma linha de base sem reordenação. Em casos específicos, as reduções atingiram até 50%.
• Escalabilidade: Os ganhos de desempenho foram observados escalando com o orçamento de portas por qubit. À medida que o número de portas X/Z disponíveis aumentava, a redução de profundidade melhorava, eventualmente saturando perto de 20 portas. Isso sugere que as heurísticas permanecem eficazes mesmo à medida que as arquiteturas de hardware evoluem para expor mais pontos de acesso.
• Sensibilidade: Os autores notaram que as reduções de profundidade diminuem à medida que a densidade de pesos de Pauli não triviais aumenta (levando a cliques comutativos menores). Além disso, aumentar o número de passagens de reorganização produziu retornos decrescentes, com a maioria dos ganhos realizados nas primeiras poucas passagens.

Significância e Alegações
O artigo afirma abordar um gargalo específico na compilação lógica para códigos de superfície: a serialização de operações comutativas devido a portas de acesso físico limitadas. Ao formalizar o problema de paralelismo limitado por portas e propor heurísticas de tempo polinomial (reorganização de cliques e reestruturação de geradores), os autores demonstram que reduções significativas de profundidade são possíveis sem aumentar a contagem de qubits lógicos ou exigir soluções de roteamento complexas.

Os autores afirmam explicitamente que sua análise assume roteamento sem restrições (isto é, eles não modelam a sobrecarga de rotear qubits lógicos para portas específicas). Eles reconhecem que aplicar essas melhorias em arquiteturas com restrições de roteamento, como códigos de superfície planares, requer análise adicional e é deixado para trabalhos futuros. O trabalho serve como uma prova de conceito para otimização de paralelismo motivada por hardware que aproveita as propriedades algébricas de grupos de Pauli comutativos.