Résumé Technique : Convergence de l'expansion des cumulants et algorithme en temps polynomial pour les fermions faiblement interagissants

1. Énoncé du Problème

L'article traite du défi computationnel consistant à estimer le logarithme de la fonction de partition, $\log Z$, pour des systèmes fermioniques faiblement interagissants à une température inverse $\beta$ fixée. Le système est composé de $N$ modes fermioniques sur un réseau de dimension $d$, régi par un hamiltonien $H = H_0 + V$, où $H_0$ est un hamiltonien quadratique (libre) et $V$ représente un potentiel d'interaction faible.

Bien que l'échantillonnage de Gibbs quantique ait récemment démontré que les états thermiques de tels systèmes peuvent être préparés en temps polynomial, un algorithme classique mathématiquement rigoureux avec un temps d'exécution polynomial pour calculer la fonction de partition est resté indisponible. Les approches classiques existantes, telles que le Monte Carlo quantique diagrammatique (QMC), reposent sur des méthodes de Monte Carlo par chaîne de Markov (MCMC) dont l'efficacité dépend de temps de mélange inconnus, empêissant ainsi des garanties rigoureuses de temps polynomial. Inversement, les méthodes rigoureuses d'expansion de clusters ont historiquement été limitées aux systèmes de spins à haute température ou à des limites spécifiques non interagissantes, échouant à s'appliquer directement aux fermions faiblement interagissants où l'état non perturbé est un état gaussien corrélé plutôt qu'un état produit.

L'objectif est de fournir un algorithme classique capable d'approximer $\log Z$ avec une erreur additive de $\epsilon N$ (c'est-à-dire une erreur $\epsilon$ par mode) avec un temps d'exécution polynomial en la taille du système $N$ et l'inverse de la précision $1/\epsilon$.

2. Méthodologie

2.1 Expansion des cumulants et analyse de convergence

Les auteurs commencent par l'expansion des cumulants du logarithme de la fonction de partition :
$$\log(Z/Z_0) = \sum_{s=1}^{\infty} \frac{(-1)^s}{s!} \sum_{P_1, \dots, P_s \in \mathcal{P}} v_{P_1} \dots v_{P_s} \int_{[0,\beta]^s} d\tau_1 \dots d\tau_s \, E_c(\{P_i, \tau_i\}_{i \in [s]})$$
où $E_c$ désigne la partie connectée de la fonction de corrélation ordonnée dans le temps. Les expansions diagrammatiques standards expriment $E_c$ comme une somme de diagrammes de Feynman connectés. Cependant, le nombre de ces diagrammes croît de manière factorielle ($\sim (2s)!$), ce qui conduit à une complexité quasi-polynomiale si l'on évalue chaque terme individuellement.

Pour surmonter cela, l'article introduit une expansion par déterminant d'arbre (tree-determinant expansion). Celle-ci réorganise la somme sur les diagrammes de Feynman connectés en une somme sur des arbres étiquetés (en utilisant les identités de graphes d'arbres de la théorie quantique des champs rigoureuse). Plus précisément, le cumulant est exprimé comme :
$$E_c(\{P_i, \tau_i\}) = \sum_{T \in \mathcal{T}([s])} \sum_{\chi \in A(T)} \alpha_{T,\chi} \left( \prod_{(i,j) \in T} g_{\tau_i, \tau_j}(P_i, P_j, \chi_{ij}) \right) h_\tau(P_1, \dots, P_s, T, \chi)$$
Ici, la somme porte sur les arbres $T$ plutôt que sur les diagrammes. Le nombre d'arbres croît selon $s^{s-2}$ (formule de Cayley), ce qui, combiné au préfacteur $1/s!$, résulte en une croissance exponentielle plutôt que factorielle. Le terme $h_\tau$ encapsule les contractions restantes comme une combinaison linéaire de déterminants de matrices construites à partir de la fonction de Green non interagissante.

2.2 Preuve de convergence

Les auteurs prouvent que cette série converge exponentiellement vite lorsque l'intensité de l'interaction $U$ est inférieure à un seuil $C(\beta)$ indépendant de $N$. La preuve repose sur deux composantes techniques clés :

1. Bornes de déterminant : En utilisant une inégalité de Gram généralisée et des applications d'immersion spécifiques pour la fonction de Green, ils établissent une borne uniforme sur les déterminants apparaissant dans $h_\tau$, montrant qu'ils croissent au plus de manière exponentielle avec $s$.
2. Sommabilité : En exploitant la sommabilité $L_V$ du potentiel d'interaction et la sommabilité $L_g$ (ou la décroissance exponentielle) de la fonction de Green non interagissante, ils bornent la sommation sur les termes d'interaction $P_1, \dots, P_s$. La structure d'arbre permet de borner cette sommation par un produit de facteurs locaux, garantissant que le terme d'ordre $s$ suit une échelle de $N \cdot \rho^s$ pour un certain $\rho < 1$.

2.3 Algorithme randomisé via échantillonnage préférentiel

Puisque la série converge exponentiellement, elle peut être tronquée à l'ordre $S = O(\log(1/\epsilon))$. Le défi consiste alors à évaluer efficacement la somme tronquée. Au lieu d'une sommation par force brute, les auteurs proposent un algorithme d'échantillonnage préférentiel randomisé (importance-sampling) :

1. Échantillonnage d'arbres : Un arbre étiqueté $T$ est échantillonné uniformément (en utilisant les codes de Prüfer).
2. Échantillonnage de variables : Conditionnellement à l'arbre et aux temps imaginaires, les termes d'interaction $P_1, \dots, P_s$ sont échantillonnés à partir d'une distribution proportionnelle à leur contribution absolue. En raison de la structure d'arbre, cette distribution forme un champ aléatoire de Markov (MRF) sur un arbre, qui peut être échantillonné efficacement en utilisant la propagation de croyance (Belief Propagation - BP).
3. Construction de l'estimateur : Pour chaque échantillon, un poids non biaisé $w_s$ est calculé. L'estimation finale est la moyenne de ces poids sur de nombreux échantillons.

La variance de l'estimateur est bornée indépendamment de $N$ (sous la condition d'interaction faible), garantissant que $O(1/\epsilon^2)$ échantillons suffisent pour atteindre la précision souhaitée.

3. Contributions clés et résultats

3.1 Principaux théorèmes

• Théorème 1.1 (Convergence) : Établit la convergence exponentielle de l'expansion des cumulants pour les hamiltoniens fermioniques géométriquement locaux lorsque l'intensité de l'interaction est inférieure à un seuil indépendant de la taille du système.
• Théorème 1.2 (Algorithme à température finie) : Fournit un algorithme classique randomisé qui estime $\log Z$ avec une erreur additive $\epsilon N$ avec une probabilité d'au moins $2/3$ en un temps $\tilde{O}(N \epsilon^{-2})$ pour les systèmes géométriquement locaux. Pour les systèmes invariants par translation, le temps d'exécution s'améliore à $\tilde{O}(\epsilon^{-2})$, indépendant de $N$.
• Corollaire 1.3 (Observables locaux) : Étend l'algorithme pour calculer les valeurs d'attente thermique d'observables locaux avec un temps d'exécution de $\tilde{O}(\epsilon^{-2})$, indépendant de la taille du système, en utilisant la fonction de partition comme fonction génératrice.
• Théorème 1.4 (Interactions générales) : Généralise les résultats aux interactions à longue portée pourvu qu'elles respectent des conditions de sommabilité ($L_V$ et $L_g$), produisant un algorithme en temps polynomial (bien qu'avec une dépendance de degré plus élevée vis-à-vis de $N$ que le cas strictement local).

3.2 Analyse de complexité

• Complexité de requête : L'algorithme nécessite O(|\mathcal{P}|^2 \epsilon^{-2} \text{polylog}(1/\epsilon}) requêtes dans le cas général et $O(N \epsilon^{-2} \text{polyllog}(N/\epsilon))$ pour les potentiels géométriquement locaux.
• Temps d'exécution : Combiné au coût de calcul de la fonction de Green non interagissante (qui est de $O(N^2 \text{polylog}(1/\epsilon))$ en général, mais de $O(\text{polylog}(N/\epsilon))$ pour les $H_0$ à portée finie), le temps d'exécution total est polynomial en $N$ et $1/\epsilon$.
• Optimalité : La dépendance linéaire en $N$ pour les systèmes locaux est notée comme essentiellement optimale, car la lecture de l'hamiltonien lui-même nécessite un temps linéaire.

4. Signification et Revendications

4.1 Signification

L'article prétend fournir le premier algorithme classique en temps polynomial pour calculer le logarithme de la fonction de partition des fermions faiblement interagissants. Sa signification réside dans plusieurs domaines :

1. Pont entre physique et complexité rigoureuse : Il jette un pont réussi entre les méthodes diagrammatiques inspirées de la physique (qui manquent de garanties de temps d'exécution rigoureuses) et les techniques algorithmiques rigoureuses (qui ont auparavant eu du mal avec la nature corrélée des états fondamentaux fermioniques).
2. Surmonter le "problème du signe" via les annulations : Contrairement aux systèmes bosoniques ou classiques où les expansions perturbatives peuvent diverger, les auteurs démontrent que les relations d'anti-commutation fermioniques induisent des annulations qui permettent un rayon de convergence positif, même à basse température (à condition que les interactions soient faibles).
3. Comparaison avec les algorithmes quantiques : Les résultats suggèrent que pour les fermions faiblement interagissants, il pourrait ne pas y avoir d'avantage quantique superpolynomial pour l'estimation des fonctions de partition, car les algorithmes classiques peuvent égaler la mise à l'échelle polynomiale des récentes approches d'échantillonnage de Gibbs quantique.
4. Innovation méthodologique : La combinaison des expansions par déterminant d'arbre avec l'échantillonnage préférentiel par propagation de croyance offre un nouveau paradigme pour l'évaluation de séries de perturbation d'ordre élevé dans les systèmes quantiques à plusieurs corps, évitant les problèmes de temps de mélange inhérents au QMC diagrammatique basé sur MCMC.

Les auteurs restent modestes concernant les applications à température nulle, notant que bien que leur approche repose sur la décroissance de la fonction de Green (ce qui est vrai pour les systèmes à gap), l'extension de leur algorithme au régime de l'état fondamental nécessite des investigations supplémentaires. Ils précisent également que leurs résultats s'appliquent au régime d'interaction faible, où l'intensité de l'interaction est petite par rapport à la température et au gap non perturbé, et ne prétendent pas résoudre le cas général des interactions fortes.