Fault-tolerant cost of shallow QAOA on near-symmetric optimization problems

Resumo Técnico: Custo tolerante a falhas de QAOA de baixa profundidade em problemas de otimização quase simétricos

Enunciado do Problema
Montanaro e Zhou [1] demonstraram que circuitos de Algoritmo de Aproximação Quântica (QAOA) de profundidade um podem encontrar a solução plantada de certos Problemas de Satisfação de Restrições (CSPs) quase simétricos com uma probabilidade constante $\Omega(1)$. Em contraste, realizações explícitas desses problemas exibem um aparente escalonamento de tempo exponencial para solvers clássicos fortes. Embora isso sugira um speedup empírico exponencial, os requisitos de recursos para implementar esses circuitos em computadores quânticos tolerantes a falhas precoces permanecem incertos. Os Hamiltonianos de custo para esses problemas contêm $\Theta(n^\ell)$ cláusulas (onde $\ell \ge 5$), o que implica um escalonamento de contagem de portas não-Clifford de $\tilde{O}(n^\ell)$ ao serem compilados usando síntese padrão de Clifford+$T$. Esse escalonamento coloca problemas relevantes além do alcance de hardware tolerante a falhas de curto prazo.

Metodologia
Os autores analisam o custo de recursos tolerantes a falhas de circuitos QAOA de profundidade um aplicados a essas instâncias quase simétricas, focando especificamente na síntese da camada de separador de fase. A análise procede através de três etapas principais:

1. Correspondência de Fase e Escalonamento de Ângulo: Os autores revisitam a condição de correspondência de fase necessária para uma probabilidade de sucesso constante. Para funções de custo simétricas sob permutações de variáveis em relação a uma solução plantada, o ângulo do separador de fase $\gamma$ deve escalar como $\gamma = \Theta(n^{1-\ell})$ para garantir a interferência construtiva das cascas de Hamming dominantes.
2. Síntese de Pequenos Ângulos: Aproveitando o fato de que $\gamma$ encolhe com o tamanho do sistema, os autores aplicam técnicas de síntese de rotação Clifford+$T$ de pequeno ângulo (especificamente aquelas de Bothe et al. [9]). Eles utilizam formulações de quase-probabilidade e mistura de probabilidade onde rotações de pequenos ângulos são aproximadas pela identidade com alta probabilidade, e apenas uma pequena fração das rotações requer síntese não-Clifford.
3. Compilação Explícita de Cláusulas e Análise de Vazamento: Os autores transitam do modelo de oráculo de valor (onde apenas valores de custo $C(x)$ são consultados) para um modelo de lista de cláusulas explícita necessário para a compilação do circuito. Eles analisam os coeficientes de Fourier da função de custo derivada da lista de cláusulas explícita para determinar se o processo de compilação inadvertidamente revela a solução.
4. Construção de Instância Deceptiva: Para testar a robustez do speedup contra ataques clássicos que exploram a estrutura explícita, os autores constroem instâncias quase simétricas "não-plantadas". Essas instâncias apresentam uma casca de Hamming exponencialmente grande contendo um subproblema NP-difícil, com um landscape de custo projetado para atrair algoritmos de busca local.

Contribuições Principais e Resultados

• Escalonamento Não-Clifford Quadrático: O resultado principal é que o custo não-Clifford por circuito para QAOA de profundidade um nessas instâncias reduz-se a $\tilde{O}(n^2)$, independente da localidade das cláusulas $\ell$ e da taxa de esparsidade. Essa redução ocorre porque a massa de fase total ($m\gamma$, onde $m$ é o número de cláusulas) escala linearmente com $n$, e o custo de síntese de pequeno ângulo depende do quadrado dessa massa de fase. Consequentemente, tamanhos de problema que anteriormente eram considerados inviáveis devido ao escalonamento $\tilde{O}(n^\ell)$ tornam-se viáveis em dispositivos de falhas tolerantes iniciais (ver Fig. 2).
• Vazamento Clássico em Famílias Plantadas: Para as famílias plantadas estudadas em Ref. [1], os autores mostram que a lista de cláusulas explícita necessária para a compilação expõe a solução plantada. A condição de correspondência de fase ($F'(1/2) \neq 0$) fixa os sinais dos coeficientes de Fourier de grau um (campos locais) da função de custo. Esses sinais revelam diretamente a solução plantada $s$ via um simples escaneamento clássico de tempo linear da lista de cláusulas. Assim, embora o QAOA tenha sucesso com probabilidade constante, a implementação explícita torna o problema classicamente trivial.
• Existência de Instâncias Não-Plantadas Difíceis: Os autores demonstram que o regime de pequeno ângulo e o escalonamento de custo $\tilde{O}(n^2)$ não são contingentes à existência de uma solução plantada. Eles constroem instâncias quase simétricas sem uma solução plantada onde:
  • O ótimo global reside dentro de uma casca de Hamming exponencialmente grande.
  • Encontrar o ótimo exato dentro dessa casca é NP-difícil.
  • O landscape de custo é "deceptivo", prendendo algoritmos de busca local e solvers de MaxSAT de propósito geral em setores subótimos separados por altas barreiras de energia.
  • O QAOA de profundidade um no pequeno ângulo concentra sua saída na casca ótima com o mesmo custo não-Clifford de $\tilde{O}(n^2)$.
  • Nesses casos não-plantados, os coeficientes de grau um são uniformes e não revelam a solução, preservando a dificuldade para algoritmos clássicos que não exploram a estrutura de simetria específica.

Significância
O artigo estabelece que o speedup empírico de QAOA de baixa profundidade em problemas quase simétricos pode ser realizado com significativamente menores recursos tolerantes a falhas do que o previamente assumido, especificamente $\tilde{O}(n^2)$ portas não-Clifford em vez de $\tilde{O}(n^\ell)$. Isso torna esses circuitos de baixa profundidade e pequeno ângulo um alvo realista para o hardware inicial tolerante a falhas.

No entanto, os autores observam modestamente um trade-off crítico: o mecanismo que permite a síntese de pequeno ângulo (campos locais coerentes) simultaneamente expõe a solução a ataques clássicos em cenários plantados. A significância do trabalho reside em identificar um regime onde o QAOA de baixa profundidade oferece um caminho eficiente em recursos para otimização, enquanto também destaca que as propriedades estruturais específicas que permitem essa eficiência podem ser uma faca de dois gumes. Os autores concluem que a questão central aberta é se esse regime de "baixo custo" de pequeno ângulo pode ser estendido para circuitos mais profundos ou estruturas de problemas diferentes onde a solução permanece oculta de ataques clássicos de baixo grau, alcançando uma vantagem quântica genuína que seja tanto barata para tolerância a falhas quanto resistente ao clássico.