Quantum circuit partition as a maze: emerging percolation transition via path finding

Resumo Técnico: Particionamento de Circuito Quântico como um Labirinto: Transição de Percolação Emergente via Busca de Caminho

Enunciado do Problema
Na otimização de circuitos quânticos, particularmente para dispositivos de Escala Intermediária com Ruído (NISQ), reduzir o número de portas de dois qubits (tipicamente CNOTs) é um objetivo primordial devido ao seu impacto significativo de ruído. Embora o particionamento de circuitos permita a otimização paralela em múltiplos dispositivos, as abordagens existentes frequentemente dependem de cortar portas CNOT via medições de meio de circuito e reset de qubits. Existe uma lacuna crítica em determinar se um circuito pode ser otimamente particionado em dois subcircuitos sem cortar nenhuma porta CNOT. O desafio é identificar um critério que distinga entre circuitos que são particionáveis (permitindo a ressintese independente de subcircuitos) e aqueles que não são, sem recorrer ao corte de portas.

Metodologia
Os autores formalizam o problema de particionamento de circuitos como uma tarefa de busca de caminho dentro de um "labirinto". A metodologia procede através de várias etapas principais:

1. Representação do Circuito:

   • Representação de Fios (Wire Representation - $W$): Uma grade onde as linhas correspondem aos fios de qubits e as colunas às portas CNOT. Uma célula é marcada se uma CNOT envolve aquele qubit.
   • Representação de Labirinto (Maze Representation - $M$): Uma grade transformada onde as linhas representam os espaços entre os fios de qubits (mais preenchimento/padding) e as colunas alternam entre espaço vazio e portas CNOT. Nesta representação, as portas CNOT atuam como "paredes". Um particionamento válido corresponde a um caminho contínuo da borda esquerda para a borda direita do labirinto que não intersecte essas paredes.

2. Otimização da Ordem de Qubits (Simulated Annealing):

   • Circuitos gerados aleatoriamente exibem inicialmente uma distribuição de paredes concentrada no centro do labirinto, tornando a travessia horizontal difícil.
   • Os autores empregam Simulated Annealing (SA) para permutar a ordem dos fios de qubits na representação de fios. Esta permutação é mapeada de volta para a representação de labirinto.
   • Uma função de custo é minimizada durante o SA, que penaliza interações CNOT que abrangem a região central da grade. O objetivo é empurrar as interações para as bordas superior e inferior, criando um "corredor central" livre de paredes.

3. Heurística de Busca de Caminho:

   • Uma vez que o labirinto é otimizado, um agente heurístico atravessa o labirinto. Dois agentes determinísticos (um movendo-se para cima ao atingir uma parede, outro para baixo) são lançados de cada célula na primeira coluna.
   • Os agentes são constrangidos a mover-se monotonicamente (nunca para trás no tempo ou revertendo a direção vertical) para garantir que os subcircuitos resultantes sejam cronologicamente consistentes.
   • Uma função de custo ponderada ($L_{tot}$) avalia caminhos candidatos baseando-se em três métricas: desequilíbrio de CNOT entre partições, desequilíbrio de células (área) e desvio do comprimento do caminho em relação à trajetória horizontal ideal.

4. Análise de Ciência de Redes:

   • Os autores analisam o circuito como um grafo direcionado onde nós representam eventos CNOT e arestas representam relações causais ou de emaranhamento.
   • Eles utilizam medidas de centralidade (grau e intermediação/betweenness) e dinâmica de consenso (modelo DeGroot) para quantificar a separação das regiões de qubits e a mistura do fluxo de informação antes e após a otimização por SA.

Principais Resultados

• Transição de Fase de Percolação: O estudo identifica uma transição de fase no espaço de circuitos quânticos. Existe um regime distinto onde um caminho de particionamento equilibrado e válido existe (particionável) e um regime onde nenhum caminho existe sem o corte de CNOTs (não-particionável).
• Critério de Escalonamento: A transição é governada pela razão entre o número de portas CNOT ($N_c$) e o número de qubits ($N_q$). Os autores observam que o particionamento em dois clusters de CNOT equilibrados é viável quando $N_c$ é aproximadamente igual a $N_q$. À medida que a densidade de CNOTs aumenta em relação aos qubits, o "corredor central" se fecha e o circuito torna-se não-particionável.
• Efeito do Simulated Annealing: O SA consegue reestruturar o layout do circuito, movendo as interações CNOT para a periferia e criando um corredor central de baixa densidade. Esta transformação desloca o perfil de distribuição de paredes de um perfil unimodal (Distribuição Beta) para um perfil bimodal, facilitando a existência de um corte horizontal.
• Dinâmica de Rede: A análise de centralidade mostra que, no regime particionável, o SA concentra as interações nos qubits das extremidades do registro, deixando o centro fracamente acoplado. A dinâmica de consenso confirma que, em regimes esparsos, o circuito se separa em dois clusters fracamente acoplados, enquanto em regimes densos, a informação se mistura globalmente, impedindo a separação.
• Três Regimes: A análise revela três fases distintas baseadas no escore de busca de caminho:
  1. Primeira Fase (Particionável): Um corte estritamente horizontal existe, equilibrando CNOTs e células.
  2. Regime Transiente: O caminho deve alternar entre passos verticais e horizontais para navegar pelas paredes, resultando em partições menos equilibradas.
  3. Segunda Fase (Não-particionável): Nenhum corte válido existe que separe o circuito; o agente é forçado para as bordas, deixando uma partição negligível e a outra contendo quase todo o circuito.

Significância e Alegações
O artigo afirma fornecer um arcabouço teórico e numérico para entender o particionamento de circuitos como um fenômeno de percolação. Ao mapear o problema como um labirinto, os autores estabelecem um critério escalável e prático para identificar se um circuito quântico pode ser particionado sem cortar portas CNOT.

O trabalho posiciona a capacidade de particionar um circuito sem cortar portas de emaranhamento como a primeira fase de uma transição de fase de percolação, ligando a otimização de circuitos quânticos a fenômenos críticos mais amplos, como transições de fase induzidas por medição e transições topológicas. Os autores afirmam que seu arcabouço forma uma base para o desenvolvimento algorítmico em otimização de circuitos quânticos, oferecendo um método para determinar a viabilidade de paralelizar tarefas de otimização em múltiplos dispositivos sem o overhead de medições de meio de circuito. Os resultados sugerem que para circuitos onde o número de portas de emaranhamento escala linearmente com o número de qubits, tal particionamento é teoricamente possível e pode ser identificado via o critério de percolação proposto.