Resumo Técnico: Otimização Quântica Baseada em Feedback com Baixa Profundidade e Medição

Definição do Problema

O Algoritmo de Otimização Quântica Baseado em Feedback (FALQON) é um algoritmo híbrido quântico-clássico projetado para resolver problemas de otimização combinatória sem a necessidade de otimização de parâmetros clássicos. Embora evite as dificuldades de treinamento inerentes aos Algoritmos Quânticos Variacionais (VQAs), o FALQON padrão sofre de uma profundidade de circuito proibitiva. Essa profundidade surge porque o algoritmo requer um pequeno passo de tempo discreto ($\Delta t$) para garantir a diminuição monotônica do valor esperado do Hamiltoniano do problema; passos maiores introduzem erros de decomposição de Trotter que causam oscilações e impedem a convergência.

Para abordar isso, Arai et al. propuseram o SO-FALQON (FALQON de Segunda Ordem), que utiliza uma expansão de Taylor de segunda ordem da diferença da função de custo. Isso permite um $\Delta t$ maior, reduzindo significativamente a profundidade do circuito. No entanto, o SO-FALQON introduz um overhead de medição substancial, exigindo a estimativa de dois Hamiltonianos complexos adicionais ($B_k$ e $C_k$) em cada camada. Isso aumenta a contagem de medições por passo em aproximadamente 2,3 vezes em relação ao FALQON original, criando um novo gargalo para dispositivos de Escala Intermediária com Ruído (NISQ) com recursos limitados.

Metodologia: BLS-FALQON

Os autores propõem o BLS-FALQON (FALQON com Busca de Linha de Backtracking), uma variante heurística inspirada na teoria de Busca de Linha de Backtracking (BLS). O método visa alcançar a baixa profundidade de circuito do SO-FALQON, evitando seu alto overhead de medição.

Mecanismo Central

Ao contrário do SO-FALQON, que calcula um coeficiente de controle de segunda ordem $\beta^{(SO)}$ exigindo medições de Hamiltonianos complexos, o BLS-FALQON retém o coeficiente de controle de primeira ordem $\beta^{(FO)}$, mas o ajusta dinamicamente usando um mecanismo de backtracking:

1. Passo Inicial: O algoritmo calcula o coeficiente de primeira ordem padrão $\beta^{(FO)}_{k+1} = -A_k$, onde $A_k$ é o valor esperado do comutador $[H_d, H_p]$.
2. Monitoramento: Em cada passo, o algoritmo também estima o valor esperado do Hamiltoniano do problema, $E_k = \langle H_p \rangle$.
3. Gatilho de Backtracking: Se $E_k$ falhar em diminuir monotonicamente (ou seja, $E_k > E_{k-1}$), indicando uma potencial má direção devido a erros de Trotter ou ruído, o algoritmo aciona um loop de backtracking.
4. Correção: O coeficiente de controle é iterativamente escalonado por um fator negativo $\tau \in (-1, 0)$:
   $$\beta^{(FO)}_k \leftarrow \tau \beta^{(FO)}_k$$
   O sinal negativo inverte a direção do controle para corrigir a má direção, enquanto a redução da magnitude suprime as oscilações. O estado é re-preparado e $E_k$ é reavaliado até que uma diminuição monotônica seja observada.

Eficiência de Medição

Uma vantagem teórica fundamental é que o BLS-FALQON não requer a estimativa dos Hamiltonianos complexos $B_k$ e $C_k$. Para problemas como Max-Cut, onde o Hamiltoniano do problema $H_p$ consiste em strings de Pauli $ZZ$ de 2-locais, a estimativa de $E_k$ pode ser absorvida nos subconjuntos de comutação por qubit já utilizados para $A_k$. Consequentemente, para tamanhos de grafo $n \ge 12$, as bases de medição por passo para o BLS-FALQON são idênticas às do FALQON original, evitando o overhead de 2,3x do SO-FALQON.

Principais Contribuições

1. Inovação Algorítmica: Introdução do BLS-FALQON, que integra uma estratégia modificada de busca de linha de backtracking para ajustar heuristicamente o coeficiente de controle de primeira ordem, eliminando a necessidade de estimativa de Hamiltoniano de segunda ordem.
2. Análise Teórica:
   • Limites de Erro: Prova de que o mecanismo de backtracking termina em um número finito de passos, garantindo que um passo de descida válido exista mesmo se a direção inicial estiver incorreta devido a erros de Trotter.
   • Paisagens Quadráticas: Análise mostrando que, embora o coeficiente heurístico possa não ser o vértice exato ideal (como no SO-FALQON), ele satisfaz a condição de descida, garantindo estabilidade de convergência.
3. Redução de Recursos: Demonstração de que o método alcança uma redução significativa nas contagens totais de medição, mantendo profundidades de circuito comparáveis ao estado da arte do SO-FALQON.

Resultados Experimentais

Simulações Numéricas

As simulações foram conduzidas em grafos 3-regulares não ponderados com $n \in \{8, \dots, 20\}$ vértices utilizando o framework Qiskit. O alvo foi uma razão de aproximação de $r_{GW} = 0,932$ (o limite de Goemans-Williamson).

• Overhead de Medição: O BLS-FALQON reduziu a contagem total de medições em 37,7% em comparação ao SO-FALQON e em 88,1% em comparação ao FALQON padrão.
• Profundidade de Circuito: O BLS-FALQON exigiu aproximadamente 2,5% mais camadas que o SO-FALQON para atingir a razão de aproximação alvo, um aumento marginal atribuído à natureza heurística do coeficiente de backtracking. No entanto, essa profundidade ainda foi aproximadamente 11 vezes menor que a do FALQON padrão.
• Escalabilidade: A economia de medição permaneceu consistente conforme a escala do problema aumentava.

Experimentos em Hardware Quântico Real

Os experimentos foram realizados no computador quântico Tianyan-176, utilizando o processador quântico supercondutor Zuchongzhi2. Os testes foram limitados a instâncias de pequena escala ($n \in \{4, 6, 8\}$) com um máximo de $L=10$ camadas devido às restrições de tempo de coerência.

• Tempo de Execução: O BLS-FALQON reduziu o tempo médio estimado de execução de hardware em 43% em relação ao SO-FALQON. Essa redução é atribuída diretamente ao menor número de bases de medição necessárias por passo.
• Robustez: Sob ruído realista de hardware, o BLS-FALQON alcançou a maior razão de aproximação média entre os três algoritmos e exibiu as bandas de convergência mais estreitas para $n=4$ e $n=6$.
• Impacto do Ruído: O mecanismo de backtracking forneceu um efeito corretivo contra o ruído induzido pelo hardware. Quando o ruído causou um aumento espúrio em $E_k$, o escalonamento de sinal alternado de $\beta$ identificou um coeficiente de descida válido sem exigir medições adicionais de Hamiltoniano, compensando parcialmente a má direção do controle.

Significância e Alegações

O artigo afirma que o BLS-FALQON aborda com sucesso o compromisso entre profundidade de circuito e overhead de medição na otimização quântica baseada em feedback. Ao utilizar a teoria de busca de linha de backtracking, o método:

• Mantém Baixa Profundidade: Alcança profundidades de circuito comparáveis à melhor abordagem existente (SO-FALQON), tornando-o viável para dispositivos NISQ onde o tempo de coerência é limitado.
• Reduz o Custo de Medição: Reduz significativamente a contagem total de medições em comparação ao SO-FALQON, o que é crítico para reduzir a complexidade de tempo total em hardware real, onde as operações de medição consomem muito tempo.
• Aumenta a Estabilidade: O mecanismo de backtracking atua como um estabilizador contra erros de decomposição de Trotter e ruído de hardware, garantindo convergência monotônica onde métodos de primeira ordem padrão poderiam oscilar.

Os autores concluem que o BLS-FALQON é um algoritmo prático e eficaz para problemas de otimização combinatória de pequena escala em hardware NISQ atual, oferecendo uma melhoria equilibrada tanto em profundidade de circuito quanto em eficiência de medição. Eles observam que, embora permaneça uma lacuna entre os resultados de hardware e as simulações ideais devido às limitações atuais dos dispositivos, o design do algoritmo é robusto e escalável.