Learning quantum Hamiltonians at any temperature in polynomial time

Resumo Técnico: Aprendizado de Hamiltonianos Quânticos a Qualquer Temperatura em Tempo Polinomial

Declaração do Problema
O artigo aborda o problema do aprendizado de Hamiltonianos para sistemas quânticos locais. Dado um sistema de $n$ qubits descrito por um Hamiltoniano local $H = \sum_{a=1}^m \lambda_a E_a$, onde os termos de interação $E_a$ são operadores de Pauli conhecidos, distintos e não-identidade com localidade limitada, e os coeficientes $\lambda_a$ são intensidades de interação desconhecidas em $[-1, 1]$, o objetivo é estimar os $\lambda_a$'s. O algoritmo tem acesso a cópias do estado de Gibbs $\rho = e^{-\beta H} / \text{tr}(e^{-\beta H})$ a uma temperatura inversa conhecida $\beta > 0$. O objetivo é produzir estimativas $\hat{\lambda}_a$ tais que $|\hat{\lambda}_a - \lambda_a| \leq \epsilon$ para todo $a$, usando um número de amostras e um tempo de execução que sejam polinomiais no tamanho do sistema $n$ (e no número de termos $m$) e em $1/\epsilon$.

Antes deste trabalho, embora limites de complexidade de amostragem polinomiais fossem conhecidos [AAKS20], os algoritmos computacionais correspondentes eram ineficientes (tempo exponencial) para regimes gerais de baixa temperatura. Algoritmos eficientes existiam apenas para altas temperaturas (pequeno $\beta$) [HKT22] ou para termos de Hamiltoniano comutativos [AAKS21]. A questão aberta central era se o aprendizado de Hamiltonianos em baixas temperaturas (grande $\beta$) poderia ser resolvido em tempo polinomial em $n$.

Metodologia
Os autores propõem um algoritmo computacionalmente eficiente baseado na hierarquia de Soma de Quadrados (SoS). A estratégia técnica central envolve três componentes principais:

1. Formulação de um Sistema de Restrições Polinomiais:
   Em vez de inverter diretamente o mapa dos parâmetros para as marginais locais (o que é computacionalmente difícil), os autores definem um sistema de restrições que os parâmetros verdadeiros devem satisfazer. Este sistema inclui:

   • Limites nos parâmetros: $-1 \leq \lambda'_a \leq 1$.
   • Restrições de comutador: Garantindo que o Hamiltoniano candidato $H'$ comute com o estado de Gibbs $\rho$ (isto é, $[H', \rho] \approx 0$).
   • Restrições polinomiais "planas": Substituindo a exponencial de matriz $e^{-\beta H'}$ por uma aproximação polinomial de baixo grau $p(H' | P)$ atuando em observáveis locais. Especificamente, eles impõem que, para operadores de Pauli locais $P, Q$, a expectativa $\text{tr}(Q e^{-\beta H'} P e^{\beta H'} \rho)$ esteja próxima de $\text{tr}(PQ\rho)$.

2. Aproximação Polinomial Plana da Exponencial:
   Um obstáculo técnico chave é que as aproximações padrão de séries de Taylor de $e^{-\beta x}$ crescem muito rapidamente fora do intervalo de aproximação, tornando-as inadequadas para regimes de baixa temperatura onde as diferenças de autovalores podem ser grandes. Os autores constroem uma nova aproximação polinomial "plana" $p(x)$ que:

   • Aproxima bem $e^{-\beta x}$ no intervalo $[-1, 1]$.
   • Cresce a uma taxa exponencial controlada e lenta ($e^{\eta \beta |x|}$) fora deste intervalo.
     Esta construção é inspirada em técnicas iterativas de "descascamento" usadas nos limites de Lieb-Robinson. Isso permite a substituição da exponencial de matriz nas restrições por um polinômio de baixo grau nas incógnitas $\lambda'_a$.

3. Tradução entre Polinômios e Comutadores Aninhados:
   Os autores estabelecem uma tradução formal entre polinômios escalares multivariados e comutadores aninhados de operadores. Usando a fórmula de Hadamard, eles mostram que termos como $e^{-\beta H'} P e^{\beta H'}$ podem ser expressos como polinômios nos autovalores de $H'$, que correspondem a comutadores aninhados $[H', P]_\ell$. Eles provam que identidades polinomiais no domínio escalar se traduzem em identidades envolvendo comutadores aninhados até termos de erro pequenos, desde que os operadores sejam locais.

4. Relaxamento de Soma de Quadrados e Identificabilidade:
   O sistema resultante de restrições é um conjunto de desigualdades polinomiais de baixo grau. Os autores resolvem este sistema usando um relaxamento de Soma de Quadrados (SoS) de grau-$d$, que pode ser formulado como um Programa Semidefinido (SDP).

   • Viabilidade: Eles provam que os parâmetros verdadeiros satisfazem o sistema (até ruído de amostragem).
   • Identificabilidade: Eles fornecem uma prova SoS de que qualquer solução do sistema deve estar próxima dos parâmetros verdadeiros. Isso depende de uma filosofia de "prova para algoritmos". Um passo crucial envolve mostrar que a variância de operadores locais sob o estado de Gibbs é limitada inferiormente por um valor diferente de zero (um análogo quântico de propriedades em modelos gráficos clássicos), garantindo que os parâmetros sejam identificáveis.
   • Eficiência: Ao analisar a estrutura específica das provas SoS, eles mostram que apenas um subconjunto esparsos de monômios é necessário, permitindo que o SDP seja resolvido em tempo polinomial em $m$ e $1/\epsilon$ (com uma dependência exponencial em $\beta$ no grau, mas polinomial em $n$).

Resultados Chave
O artigo apresenta o Teorema 1.1, que afirma que para qualquer temperatura inversa constante $\beta > 0$ (especificamente $\beta \geq \beta_c$ para alguma constante universal), existe um algoritmo que aprende os coeficientes do Hamiltoniano com precisão $\epsilon$ com probabilidade $99/100$.

• Complexidade de Amostragem: $n \geq \text{poly}(m, (1/\epsilon)^{2O(\beta)})$.
• Tempo de Execução: $n^{O(1)}$ (especificamente $\text{poly}(m, \log(1/\delta)) \cdot (1/\epsilon)^{2O(\beta)}$).

O algoritmo funciona para Hamiltonianos de "baixa interseção", uma classe que inclui Hamiltonianos geometricamente locais em reticulados e aqueles definidos em grafos expansores.

Significado e Afirmações
Os autores afirmam resolver completamente o problema aberto do aprendizado eficiente de Hamiltonianos em baixas temperaturas.

• Resolução de Questões Abertas: O resultado fornece uma resposta positiva à questão de se o aprendizado de Hamiltonianos em baixas temperaturas é solúvel em tempo polinomial [AAKS20; HKT22; Alh23; AA23]. Também responde negativamente à hipótese de que estados de Gibbs de baixa temperatura podem ser pseudorrandômicos (Questão 3 em [AA23]) e positivamente à questão de se o aprendizado é possível sob independência condicional aproximada (Questão 2 em [AA23]).
• Ferramenta Algorítmica: O trabalho demonstra que ferramentas sofisticadas da teoria de otimização, especificamente a hierarquia de Soma de Quadrados, podem superar barreiras no aprendizado de muitos corpos quânticos que anteriormente pareciam intratáveis devido à dificuldade de calcular funções de partição.
• Independência de Limites Clássicos: Os autores observam que, embora o aprendizado de Hamiltonianos clássico (aprendizado de modelos gráficos não direcionados) exija tempo exponencial em $\beta$, o cenário quântico não herda necessariamente essa dificuldade, apesar da não-comutatividade e não-localidade dos sistemas quânticos.
• Praticidade: O artigo reconhece que, embora o algoritmo seja teoricamente eficiente (polinomial em $n$), a dependência de $\beta$ no expoente do tempo de execução e da complexidade de amostragem significa que ele não é atualmente prático para temperaturas muito baixas ou sistemas grandes. No entanto, estabelece uma possibilidade teórica onde nenhuma existia antes.

O artigo não propõe novos arranjos experimentais ou aplicações práticas imediatas, mas enquadra o resultado como um avanço fundamental na compreensão da complexidade computacional da caracterização de sistemas quânticos, particularmente relevante para a validação de simuladores quânticos analógicos que frequentemente operam em regimes de baixa temperatura.