Optimizing QAOA circuit transpilation with parity twine and SWAP network encodings

Resumo Técnico: Otimização da Transpilação de Circuitos QAOA com Parity Twine e Codificações de Redes SWAP

Definição do Problema
Os atuais processadores quânticos supercondutores (QPUs) sofrem com a conectividade limitada de qubits, sendo tipicamente restritos a interações de vizinhos próximos em topologias específicas (ex: redes heavy-hex). A execução de algoritmos como o Quantum Approximate Optimization Algorithm (QAOA), que frequentemente requer interações de dois qubits densas ou totalmente conectadas, exige um processo de transpilação. Este processo mapeia qubits lógicos para qubits físicos e insere portas SWAP para satisfazer as restrições de conectividade. No entanto, as portas SWAP são decompostas em múltiplas portas de dois qubits (ex: três CNOTs), que são a principal fonte de ruído e erro em dispositivos de curto prazo (near-term). Embora codificações estruturadas como redes SWAP e Parity Twine Chains (PTC) ofereçam benefícios analíticos de recursos para grafos totalmente conectados, sua aplicação a grafos esparsamente conectados (não totalmente conectados) permanece subótima. Além disso, encontrar o mapeamento inicial de qubits ideal (um problema de isomorfismo de subgrafo) para minimizar a contagem de portas em tais cenários esparsos é um problema NP-difícil, e os resolvedores existentes, como o SATMapper, enfrentam limitações de escalabilidade e tempo de execução.

Metodologia
Os autores propõem uma abordagem híbrida combinando estratégias de codificação estruturada com uma heurística de simulated annealing (SA) para otimizar o mapeamento inicial de qubits lógicos para físicos.

1. Codificações:

   • Rede SWAP: Um cronograma de roteamento estruturado em uma cadeia 1D onde camadas alternadas de portas SWAP de vizinhos próximos movem os qubits lógicos para criar as adjacências necessárias.
   • Parity Twine Chains (PTC): Um método que codifica informação de paridade Z de múltiplos qubits em qubits físicos únicos via paridade. Isso permite que interações não locais sejam executadas como rotações locais de um único qubit ($R_Z$), reduzindo a contagem de portas de dois qubits em comparação com as redes SWAP. O método utiliza uma estratégia de decodificação onde medições são realizadas na base de paridade, e o pós-processamento clássico recupera a cadeia de bits lógica, evitando a necessidade de portas CNOT adicionais para retornar à base computacional.

2. Otimização por Simulated Annealing (SA):

   • Os autores introduzem um algoritmo baseado em SA para resolver o problema de isomorfismo de subgrafo para ambas as codificações SWAP e PTC.
   • Função de Custo: A função de custo é combinatória e não suave, avaliando o número de portas de dois qubits que podem ser podadas (removidas) do circuito. Ela verifica, camada por camada, se os pares de qubits mapeados correspondem a arestas nativas no grafo de acoplamento do hardware. Se uma interação necessária estiver ausente no grafo do problema, as portas correspondentes no cronograma de codificação são omitidas.
   • Processo: O algoritmo alterna iterativamente pares de rótulos de qubits para encontrar uma permutação que minimize a contagem total de portas de dois qubits e a profundidade do circuito. Esta abordagem é escolhida porque métodos baseados em gradiente são inadequados para o espaço de busca discreto, e métodos exatos são computacionalmente proibitivos.

3. Benchmarking e Modelagem de Ruído:

   • O método é testado contra transpiladores padrão (Qiskit-T, Qiskit-P, Qiskit-AI, TKET) e o SATMapper.
   • As simulações de ruído utilizam um modelo de ruído depolarizante atuando sobre as portas de dois qubits dentro de um protocolo Linear Ramp QAOA (LR-QAOA) para problemas de Weighted MaxCut (WMC).
   • A validação experimental é realizada em dispositivos quânticos da IBM (ibm_fez e ibm_kingston).

Principais Contribuições

• Codificações Otimizadas por SA: A introdução de uma estratégia de simulated annealing para otimizar a ordenação inicial de qubits para ambas as codificações PTC e SWAP, visando especificamente grafos não totalmente conectados.
• Escalabilidade: Demonstração de que a abordagem SA escala efetivamente para grandes quantidades de qubits (até 200 qubits em simulação), oferecendo uma vantagem de tempo de execução de ordens de magnitude sobre o SATMapper, mantendo uma qualidade de solução comparável.
• Decodificação PTC: Uma descrição detalhada de uma estratégia de decodificação para PTC que elimina a necessidade de portas CNOT que aumentam a profundidade do circuito para retornar à base computacional.
• Validação Experimental: A primeira implementação experimental da codificação PTC em hardware quântico real.

Resultos

• Redução de Contagem de Portas e Profundidade: Para circuitos QAOA com densidades de aresta ($E_d$) acima de limiares específicos, PTC+SA e SWAP+SA superam significativamente os transpiladores padrão.
  • Para uma instância de 120 qubits com 25% de conectividade, o método proposto alcançou uma redução de 87% na profundidade do circuito e uma redução de 29% nas portas de dois qubits em comparação com o transpiler Qiskit (nível de otimização 3).
  • O limiar para o PTC+SA superar o Qiskit-T em contagem de portas diminui conforme o tamanho do sistema aumenta (de $E_d \approx 0,35$ para 20 qubits até $E_d \approx 0,13$ para 120 qubits).
• Eficiência de Tempo de Execução: O método SA converge para soluções de alta qualidade em segundos para problemas de 200 qubits, enquanto o SATMapper requer centenas a milhares de segundos.
• Resiliência ao Ruído:
  • Simulação: Em simulações de ruído, o PTC mostrou uma probabilidade de sucesso ($p_{gs}$) maior que o SWAP para níveis de ruído baixos a moderados devido ao menor número de portas, embora a razão de aproximação ($r$) tenha permanecido semelhante para ambos.
  • Hardware Real (ibm_fez): A codificação PTC estendeu o alcance de experimentos úteis de LR-QAOA. Soluções ótimas foram encontradas para tamanhos de problema de até 20 qubits usando PTC, comparado a apenas 15 qubits com SWAP. A distinção em relação à amostragem aleatória manteve-se até 22 qubits para PTC versus 20 qubits para SWAP.
  • Hardware Real (ibm_kingston): Para um problema de 20 qubits com $E_d = 0,298$, o SWAP+SA alcançou a melhor razão de aproximação (melhoria de 20,83% sobre o aleatório), superando o PTC+SA (13,99%). Os autores observam que, embora o PTC utilize menos portas, a codificação de pares lógicos em um único qubit físico pode ser mais sensível ao acúmulo de ruído em cenários não totalmente conectados.
• Comparação de Transpiladores: Transpiladores padrão (como o Qiskit-T) frequentemente minimizam a contagem de portas às custas de um aumento significativo na profundidade do circuito, o que exacerba o ruído. Os métodos propostos mantêm circuitos compactos com menor profundidade.

Significância e Alegações
O artigo afirma apresentar a primeira demonstração de que as codificações SWAP e PTC superam os métodos de transpilação padrão em cenários de conectividade reduzida. Também constitui a primeira implementação experimental da codificação PTC em hardware quântico real.

Os autores enfatizam que, embora as codificações estruturadas ideais sejam bem conhecidas para grafos totalmente conectados, sua aplicação a grafos parcialmente conectados através da proposta otimização baseada em SA produz reduções significativas de recursos. Eles concluem que, para sistemas de até 20 qubits, a codificação PTC melhora o desempenho em hardware real, estendendo o tamanho viável do problema para LR-QAOA. No entanto, eles observam modestamente que, em experimentos não totalmente conectados no ibm_kingston, o SWAP+SA às vezes superou o PTC+SA, sugerindo que o compromisso entre contagem de portas e sensibilidade ao ruído depende fortemente da estrutura de codificação específica e da topologia do problema. O trabalho estabelece um caminho prático para a execução de QAOA em dispositivos de curto prazo com restrição de conectividade e redução de overhead.