Role of overparametrization in quantum approximate optimization

Resumo Técnico: O Papel da Sobreparametrização na Otimização Aproximada Quântica

Definição do Problema
Os Algoritmos de Otimização Aproximada Quântica (VQAs) são uma abordagem proeminente para resolver problemas em dispositivos quânticos de Escala Intermediária com Ruído (NISQ), que são limitados por tempos de coerência curtos e erros de porta. Uma questão crítica aberta neste campo é determinar os recursos quânticos mínimos (especificamente a profundidade do circuito) necessários para resolver problemas práticos de forma eficiente. Embora a sobreparametrização — o uso de um número de parâmetros que excede um determinado limiar — tenha sido demonstrada no aprendizado de máquina clássico e em alguns contextos quânticos para melhorar a convergência e evitar platôs estéreis (barren plateaus), ela frequentemente exige profundidades de circuito que excedem as capacidades dos dispositivos NISQ. Este trabalho investiga se a sobreparametrização é tanto suficiente quanto necessária para obter soluções de alta probabilidade para problemas de otimização combinatória usando o Algoritmo de Otimização Aproximada Quântica (QAOA).

Metodologia
Os autores definem a sobreparametrização usando o conceito de Dimensão Quântica Efetiva (EQD), que quantifica a expressividade de um circuito variacional com base no posto da matriz de Informação de Fisher Quântica (QFI). Um circuito é considerado sobreparametrizado quando o aumento do número de parâmetros (profundidade) não aumenta mais a EQD.

O estudo foca em dois problemas de otimização combinatória NP-difíceis representativos:

1. MAX-CUT: Investigado em grafos 2-regulares (anéis de discordâncias), grafos $k$-regulares e grafos aleatórios não ponderados.
2. MAX-2-SAT: Investigado em instâncias aleatórias com densidades de cláusulas variáveis.

Para cada problema, os autores comparam a profundidade de sobreparametrização ($p_c$, onde a EQD satura) contra a profundidade ótima ($p^*$, a profundidade mínima necessária para alcançar uma solução dentro de uma tolerância de erro de energia $\epsilon$). Eles empregam simulações numéricas com estratégias heurísticas de camada por camada e inicializações de parâmetros aleatórios para rastrear erros de energia e probabilidades de sucesso através de diferentes profundidades de circuito.

Principais Contribuições e Resultados

• MAX-CUT em Grafos 2-Regulares:

  • Os autores fornecem uma prova analítica de que, para um número par de qubits $n$, a profundidade ótima do QAOA escala como $p^* = \lfloor n/2 \rfloor$.
  • Resultados numéricos confirmam que a profundidade de sobreparametrização $p_c$ coincide exatamente com esta profundidade ótima ($p_c = p^*$) para sistemas até $n=20$.
  • Conclusão: Para esta classe específica de problemas, a sobreparametrização é tanto suficiente quanto necessária para encontrar soluções com alta probabilidade.

• MAX-CUT em Grafos Gerais (Regulares e Aleatórios):

  • A análise numérica mostra que, para a maioria das instâncias, a solução ótima é encontrada exatamente em ou nas proximidades imediatas da profundidade de sobreparametrização.
  • A probabilidade de sucesso de encontrar uma solução exibe um aumento abrupto ao transitar do regime subparametrizado para o regime sobreparametrizado.
  • Conclusão: A sobreparametrização é suficiente para o sucesso de alta probabilidade. Embora não seja estritamente necessária para cada instância individual, é estatisticamente necessária para a fração dominante das instâncias.

• MAX-2-SAT:

  • Em forte contraste com o MAX-CUT, a maioria das instâncias de MAX-2-SAT é resolvida bem dentro do regime subparametrizado ($p/p_c \ll 1$).
  • Para $n=7$, aproximadamente 85% das instâncias foram resolvidas com profundidades de circuito tão baixas quanto metade da profundidade de sobreparametrização.
  • A profundidade ótima escala como $p^* \sim \sqrt{2^n}$, enquanto a profundidade de sobreparametrização escala como $p_c \sim 2^n$. Consequentemente, a razão $p^*/p_c$ diminui exponencialmente com o tamanho do problema.
  • Conclusão: A sobreparametrização não é necessária para resolver instâncias de MAX-2-SAT; altas probabilidades de sucesso são alcançadas com circuitos significativamente mais rasos.

Significância e Alegações
O artigo afirma que a relação entre a sobreparametrização e a profundidade ótima do circuito é dependente do problema.

• Para o MAX-CUT, a sobreparametrização atua como um limiar crítico; a profundidade necessária para saturar a expressividade do circuito (EQD) alinha-se com a profundidade necessária para resolver o problema.
• Para o MAX-2-SAT, os resultados destacam o potencial do QAOA no regime subparametrizado. Como esses problemas podem ser resolvidos com circuitos muito mais rasos do que a profundidade de sobreparametrização, o QAOA pode ser mais viável para os dispositivos NISQ atuais do que sugerido anteriormente por estudos focados exclusivamente em regimes sobreparametrizados.

Os autores enfatizam que, embora a sobreparametrização garanta a convergência em certos frameworks teóricos, ela não é um requisito universal para todos os problemas combinatórios. Esta descoberta sugere que, para classes de problemas específicas como o MAX-2-SAT, soluções eficientes em termos de recursos podem ser encontradas sem os circuitos profundos que tipicamente induzem ruído e problemas de treinabilidade (como os platôs estéreis) em hardware de curto prazo. No entanto, os autores também observam que, mesmo no regime subparametrizado, limitações de treinabilidade como platôs estéreis ainda podem persistir para grandes tamanhos de problemas.