Simulating Quantum Walk Hamiltonians without Pauli Decomposition

Resumo Técnico: Um Algoritmo de Decomposição por Emparelhamento para Simulação de Hamiltonianos de Caminhadas Quânticas

Definição do Problema
As Caminhadas Quânticas em Tempo Contínuo (CTQWs) são um modelo universal para computação quântica com aplicações em busca espacial, otimização e preparação de estados. Embora as CTQWs em classes específicas de grafos (por exemplo, grafos circulantes, estrelas) possam ser implementadas exatamente no modelo de circuito, simular CTQWs em grafos esparsos arbitrários normalmente requer a decomposição da matriz de adjacência do grafo em componentes menores e a aplicação de Trotterização. As abordagens padrão frequentemente dependem da decomposição de Pauli, o que pode resultar em alto overhead de recursos (portas controladas e profundidade de circuito), particularmente para grafos esparsos com estruturas complexas. Os autores visam desenvolver uma primitiva de construção de circuito mais eficiente que reduza esses custos de recursos enquanto mantém a precisão da simulação.

Metodologia
O artigo propõe um algoritmo de "decomposição por emparelhamento" (matching decomposition) que gera circuitos quânticos para CTQWs em grafos esparsos inseridos em um espaço de estados. A metodologia consiste em três estágios primários:

1. Decomposição por Emparelhamento: O algoritmo decompõe o conjunto de arestas do grafo em uma coleção de emparelhamentos (conjuntos de arestas não adjacentes). Dois heurísticos são desenvolvidos para este passo:

   • Emparelhamento Guloso (Greedy Matching): As arestas são agrupadas pelo seu "posição de flip de bit" (o índice de qubit específico onde os rótulos dos vértices diferem). Arestas com distância de Hamming 1 são agrupadas por essa posição. Arestas com distância de Hamming > 1 são adicionadas gulosamente a emparelhamentos existentes se não houver conflitos de vértices.
   • Emparelhamento Consciente de Compressão (Compression-Aware Matching): Este heurístico agrupa arestas com base em sua máscara XOR completa ($\mu = u \oplus v$), independentemente da distância de Hamming. Ele emprega uma busca de múltiplas tentativas (ordenando grupos por tamanho ou randomizando) para encontrar uma configuração de emparelhamento que minimize a contagem estimada de portas Controlled-NOT (CX), priorizando emparelhamentos que permitam a máxima compressão subsequente.

2. Compressão de Grafo Iterativa: Uma vez que as arestas são atribuídas aos emparelhamentos, um novo algoritmo de compressão é aplicado a cada emparelhamento. Este processo funde arestas dentro de um emparelhamento em uma única "aresta comprimida" em um espaço de qubits reduzido.

   • O algoritmo rastreia "qubits ativos" (aqueles que permanecem no rótulo comprimido) e "qubits de redução de peso" (aqueles removidos durante a compressão que originalmente contribuíram para a distância de Hamming).
   • As arestas são fundíveis se compartilharem as mesmas máscaras XOR originais, listas de qubits ativos e listas de redução de peso, e se seus endpoints diferirem apenas em uma posição de bit específica.
   • A fusão reduz o número de qubits de controle necessários para as portas $R_x(2t)$ multicontroladas resultantes.

3. Construção de Circuito e Trotterização:

   • Cada aresta comprimida é implementada como um circuito de três estágios: (1) Transformação de base usando portas CX para lidar com qubits de redução de peso, (2) Aplicação de uma porta multicontrolada $R_x(2t)$ (ou $R_x$ simples se totalmente comprimida), e (3) Transformação de base inversa.
   • A evolução completa da CTQW é aproximada via Trotterização de primeira ordem sobre a sequência de emparelhamentos. O erro é controlado pelo número de passos de Trotter ($N$).

Principais Contribuições

• Nova Primitiva de Decomposição: A introdução de uma estratégia de decomposição baseada em emparelhamento que evita a decomposição de Pauli inteiramente para a simulação de caminhadas ao longo de emparelhamentos.
• Heurístico Consciente de Compressão: Um novo algoritmo que otimiza a seleção de emparelhamento com base no potencial de compressão do grafo, em vez de apenas na adjacência imediata das arestas.
• Técnica de Compressão de Grafo: Um método para fundir arestas dentro de um emparelhamento para reduzir o número de qubits de controle e a complexidade das portas multicontroladas, rastreando as transformações de base necessárias via "qubits de redução de peso".
• Análise Teórica: O artigo fornece condições sob as quais uma decomposição por emparelhamento permite simulação exata (ou seja, quando as matrizes de adjacência dos emparelhamentos comutam entre si). Prova-se que, para dois emparelhamentos comutarem, a união de suas arestas deve consistir apenas em vértices isolados, arestas únicas ou ciclos de 4 ($C_4$). Também demonstra-se que a re-rotulagem de vértices preserva a comutatividade de uma decomposição por emparelhamento.

Resultos
Os autores testaram seu algoritmo contra um pipeline de decomposição de Pauli padrão usando Qiskit (nível de otimização 3) em dois conjuntos de dados: grafos conectados (caminhos hamiltonianos e variações) e grafos aleatórios de Erdős-Rényi ($N \in \{8, \dots, 128\}$).

• Precisão: A diferença de operador de norma 2 entre a evolução exata da CTQW e a decomposição por emparelhamento Trotterizada foi encontrada como comparável à da decomposição de Pauli em todos os tamanhos e tipos de grafos testados. Ambos os métodos convergem em taxas semelhantes conforme o número de passos de Trotter aumenta.
• Redução de Recursos (Grafos Conectados):
  • Emparelhamento Consciente de Compressão: Para grafos de 16 a 128 vértices, este método exigiu até 70% menos portas CX e produziu circuitos 75% mais rasos que a decomposição de Pauli.
  • Emparelhamento Guloso: Para grafos de 32 a 128 vértices, este método exigiu até 43% menos portas CX e produziu circuitos 54% mais rasos que a decomposição de Pauli.
• Redução de Recursos (Grafos Erdős-Rényi): Em grafos aleatórios esparsos ($p=0.01$), a decomposição por emparelhamento guloso exigiu 25–33% menos portas CX e 37–49% de circuitos mais rasos que a decomposição de Pauli para $N \ge 32$.
• Variância: A decomposição por emparelhamento mostrou maior variância relativa na contagem de portas em comparação com a decomposição de Pauli, sugerindo sensibilidade a estruturas de grafos específicas e escolhas de emparelhamento.

Significância e Alegações
O artigo afirma que a decomposição por emparelhamento oferece uma alternativa competitiva, e frequentemente superior, à decomposição de Pauli para simular CTQWs em grafos esparsos no modelo de circuito. A principal vantagem reside na redução da contagem de portas de dois qubits (CX) e da profundidade do circuito, que são restrições críticas para dispositivos quânticos de curto prazo (near-term).

Os autores enfatizam que seu objetivo é avaliar a decomposição por emparelhamento como uma nova primitiva de construção de circuito contra um baseline amplamente utilizado. Eles observam que, embora a simulação baseada em Pauli seja um campo maduro com compiladores especializados, sua abordagem oferece ganhos práticos imediatos em toolchains padrão sem exigir técnicas de síntese avançadas específicas para Pauli. O artigo conclui modestamente que, embora o método seja eficaz, as propriedades específicas do grafo (como a distribuição de peso de Hamming) que garantem essas reduções ainda não foram totalmente caracterizadas, e trabalhos futuros são necessários para identificar os fatores estruturais precisos que maximizam a eficiência.