Learning quantum Hamiltonians at any temperature in polynomial time

Ce papier résout un problème ouvert majeur en présentant un algorithme de temps polynomial qui apprend des Hamiltoniens quantiques locaux avec une précision $\epsilon$ à partir d'un nombre polynomial de copies de leurs états de Gibbs à toute température inverse constante $\beta > 0$, en utilisant une nouvelle approximation polynomiale plate et une relaxation somme de carrés pour surmonter les barrières computationnelles précédentes.

L'essentiel

La vue d'ensemble : le rétro-ingénierie d'une machine quantique

Imaginez que vous possédez une machine mystérieuse et complexe, constituée de nombreuses pièces minuscules en interaction (comme une gigantesque horlogerie invisible faite de particules quantiques). Vous ne pouvez pas voir l'intérieur de la machine, et vous ne savez pas comment les engrenages sont connectés ni quelle est la force des ressorts.

Cependant, vous pouvez observer la machine lorsqu'elle est au « repos » ou « calme » (un état que les physiciens appellent l'état de Gibbs). Vous pouvez prendre de nombreuses instantanés de cet état de repos.

L'objectif : Votre travail consiste à déterminer le plan exact de la machine — spécifiquement, la force de chaque ressort et de chaque connexion d'engrenage (appelées forces d'interaction ou coefficients). En physique, ce plan est appelé le Hamiltonien.

Le problème : le piège du « froid »

Pendant longtemps, les scientifiques avaient une méthode pour déterminer ce plan, mais elle ne fonctionnait que lorsque la machine était chaude. Lorsque les choses sont chaudes, les particules bougent de manière chaotique, et les connexions sont faciles à repérer, un peu comme on peut voir les fils individuels dans une pelote de laine emmêlée si on la secoue vigoureusement.

Mais lorsque la machine est froide (ce qui est l'endroit où se produit la magie quantique la plus intéressante, comme la supraconductivité), les particules se calment et se verrouillent dans un motif très spécifique et rigide.

• L'ancien problème : Les méthodes précédentes pour rétro-ingénierier le plan dans cet état « froid » étaient théoriquement possibles mais pratiquement impossibles. Elles ressemblaient à essayer de résoudre un puzzle qui prendrait à un ordinateur plus de temps que l'âge de l'univers pour être terminé. Les mathématiques nécessaires pour décoder l'état froid étaient trop lourdes.

La percée : un nouveau type de « traducteur »

Cet article présente un nouvel algorithme capable de résoudre ce puzzle rapidement (en « temps polynomial »), même lorsque la machine est glaciale.

Voici comment ils ont procédé, en utilisant trois astuces principales :

1. L'approximation « plate » (Lissage de la courbe)

Pour comprendre la machine, vous devez comprendre une courbe mathématique spécifique appelée fonction exponentielle. Imaginez cette courbe comme une montagne raide et déchiquetée.

• L'ancienne méthode : Les méthodes précédentes tentaient d'approximer cette montagne en empilant de petits blocs plats (polynômes) les uns sur les autres. Mais pour obtenir le résultat correct dans le froid, il fallait tellement de blocs que la pile devenait d'une hauteur et d'une instabilité impossibles.
• La nouvelle méthode : Les auteurs ont inventé un nouveau type d'approximation « plate ». Imaginez qu'au lieu d'empiler des blocs, vous utilisiez une feuille flexible et extensible qui épouse parfaitement la montagne au milieu, mais qui est autorisée à s'éloigner doucement sur les bords lointains. Cette feuille « plate » est beaucoup plus facile à manipuler et ne s'effondre pas sous le poids du calcul.

2. Le traducteur « commutateur imbriqué »

Les mathématiques de la mécanique quantique impliquent quelque chose appelé les commutateurs, qui sont comme un jeu où « l'ordre compte ». Si vous poussez un engrenage vers la gauche puis vers la droite, ce n'est pas la même chose que de le pousser vers la droite puis vers la gauche.

• La traduction : Les auteurs ont créé un dictionnaire qui traduit ces règles quantiques complexes de « l'ordre compte » en de simples polynômes (des équations algébriques de base).
• Pourquoi cela aide : Une fois qu'ils ont traduit les règles quantiques en algèbre simple, ils ont pu traiter l'ensemble du problème comme un système d'équations que l'on pourrait résoudre au lycée, plutôt que comme un mystère quantique terrifiant.

3. Le détective « SOS » (Somme de carrés)

Maintenant qu'ils avaient un système d'équations algébriques, ils devaient le résoudre.

• La méthode : Ils ont utilisé un outil mathématique puissant appelé Somme de carrés (SoS). Imaginez cela comme un détective super-intelligent qui ne cherche pas seulement une solution, mais vérifie si n'importe quelle solution est possible en examinant les « carrés » des erreurs.
• Le résultat : Le détective a prouvé que si vous trouvez une solution qui correspond à l'approximation « plate » et aux règles algébriques, elle doit être le plan correct de la machine. Il n'existe aucun autre faux plan capable de tromper le système.

La « recette » de la solution

1. Prendre des instantanés : L'algorithme prend de nombreuses copies de l'état de repos de la machine quantique.
2. Mesurer les indices : Il mesure des interactions spécifiques (comme vérifier comment deux engrenages spécifiques bougent ensemble).
3. Construire le puzzle : Il met en place un gigantesque système d'équations algébriques basé sur ces mesures, en utilisant leur nouvelle approximation « plate » pour garder les mathématiques gérables.
4. Résoudre le puzzle : Il utilise le détective Somme de carrés pour résoudre les équations.
5. Obtenir le plan : La solution donne la force exacte de chaque interaction dans la machine.

Pourquoi cela compte (selon l'article)

L'article affirme qu'il s'agit d'une percée majeure car :

• Cela fonctionne à n'importe quelle température : Il résout le problème pour les états chauds et froids, déverrouillant enfin le code « basse température » qui a déconcerté les chercheurs pendant des années.
• C'est rapide : Il s'exécute en un temps raisonnable, alors que les tentatives précédentes auraient pris une éternité.
• C'est rigoureux : Ils n'ont pas seulement deviné ; ils ont prouvé mathématiquement que leur méthode fonctionne et que la solution est unique.

En bref, ils ont construit un anneau de décodage rapide et fiable capable de lire le plan secret d'une machine quantique, peu importe à quel point elle est froide et silencieuse.

Résumé technique

Résumé technique : Apprentissage de Hamiltoniens quantiques à toute température en temps polynomial

Énoncé du problème
L'article aborde le problème de l'apprentissage de Hamiltoniens pour des systèmes quantiques locaux. Étant donné un système de $n$ qubits décrit par un Hamiltonien local $H = \sum_{a=1}^m \lambda_a E_a$, où les termes d'interaction $E_a$ sont des opérateurs de Pauli connus, distincts et non-identité à localité bornée, et où les coefficients $\lambda_a$ sont des forces d'interaction inconnues dans $[-1, 1]$, l'objectif est d'estimer les $\lambda_a$. L'algorithme a accès à des copies de l'état de Gibbs $\rho = e^{-\beta H} / \text{tr}(e^{-\beta H})$ à une température inverse connue $\beta > 0$. L'objectif est de produire des estimations $\hat{\lambda}_a$ telles que $|\hat{\lambda}_a - \lambda_a| \leq \epsilon$ pour tout $a$, en utilisant un nombre d'échantillons et un temps d'exécution polynomiaux par rapport à la taille du système $n$ (et au nombre de termes $m$) et à $1/\epsilon$.

Auparavant, bien que des bornes de complexité d'échantillonnage polynomiales fussent connues [AAKS20], les algorithmes computations correspondants étaient inefficaces (temps exponentiel) pour les régimes généraux de basse température. Des algorithmes efficaces n'existaient que pour les hautes températures (petit $\beta$) [HKT22] ou pour des termes de Hamiltoniens commutatifs [AAKS21]. La question ouverte centrale était de savoir si l'apprentissage de Hamiltoniens à basse température (grand $\beta$) pouvait être résolu en un temps polynomial en $n$.

Méthodologie
Les auteurs proposent un algorithme computationnellement efficace basé sur la hiérarchie des Sommes de Carrés (SoS). La stratégie technique centrale implique trois composantes principales :

1. Formulation d'un système de contraintes polynomiales :
   Au lieu d'inverser directement l'application des paramètres vers les marginales locales (ce qui est computationnellement difficile), les auteurs définissent un système de contraintes que les vrais paramètres doivent satisfaire. Ce système inclut :

   • Des bornes sur les paramètres : $-1 \leq \lambda'_a \leq 1$.
   • Des contraintes de commutateur : Assurant que le Hamiltonien candidat $H'$ commute avec l'état de Gibbs $\rho$ (c'est-à-dire $[H', \rho] \approx 0$).
   • Des contraintes polynomiales « plates » : Remplaçant l'exponentielle matricielle $e^{-\beta H'}$ par une approximation polynomiale de bas degré $p(H' | P)$ agissant sur des observables locaux. Spécifiquement, ils imposent que pour des opérateurs de Pauli locaux $P, Q$, l'espérance $\text{tr}(Q e^{-\beta H'} P e^{\beta H'} \rho)$ soit proche de $\text{tr}(PQ\rho)$.

2. Approximation polynomiale plate de l'exponentielle :
   Un obstacle technique clé est que les approximations standards de série de Taylor de $e^{-\beta x}$ croissent trop rapidement en dehors de l'intervalle d'approximation, les rendant inadaptées aux régimes de basse température où les différences de valeurs propres peuvent être grandes. Les auteurs construisent une nouvelle approximation polynomiale « plate » $p(x)$ qui :

   • Approxime bien $e^{-\beta x}$ sur l'intervalle $[-1, 1]$.
   • Croît à un taux exponentiel contrôlé et lent ($e^{\eta \beta |x|}$) en dehors de cet intervalle.
     Cette construction s'inspire des techniques itératives de « pelage » utilisées dans les bornes de Lieb-Robinson. Cela permet de remplacer l'exponentielle matricielle dans les contraintes par un polynôme de bas degré en les inconnues $\lambda'_a$.

3. Traduction entre polynômes et commutateurs imbriqués :
   Les auteurs établissent une traduction formelle entre des polynômes scalaires multivariés et des commutateurs imbriqués d'opérateurs. En utilisant la formule de Hadamard, ils montrent que des termes comme $e^{-\beta H'} P e^{\beta H'}$ peuvent être exprimés comme des polynômes en les valeurs propres de $H'$, qui correspondent à des commutateurs imbriqués $[H', P]_\ell$. Ils prouvent que les identités polynomiales dans le domaine scalaire se traduisent par des identités impliquant des commutateurs imbriqués jusqu'à de petits termes d'erreur, à condition que les opérateurs soient locaux.

4. Relaxation Somme de Carrés et identifiabilité :
   Le système de contraintes résultant est un ensemble d'inégalités polynomiales de bas degré. Les auteurs résolvent ce système en utilisant une relaxation Somme de Carrés (SoS) de degré $d$, qui peut être formulée comme un Programme Semi-Défini (PSD).

   • Faisabilité : Ils prouvent que les vrais paramètres satisfont le système (jusqu'au bruit d'échantillonnage).
   • Identifiabilité : Ils fournissent une preuve SoS que toute solution du système doit être proche des vrais paramètres. Cela repose sur une philosophie de « preuve vers algorithmes ». Une étape cruciale consiste à montrer que la variance des opérateurs locaux sous l'état de Gibbs est bornée loin de zéro (un analogue quantique des propriétés des modèles graphiques classiques), assurant ainsi que les paramètres sont identifiables.
   • Efficacité : En analysant la structure spécifique des preuves SoS, ils montrent qu'un sous-ensemble épars de monômes est requis, permettant de résoudre le PSD en un temps polynomial en $m$ et $1/\epsilon$ (avec une dépendance exponentielle en $\beta$ dans le degré, mais polynomial en $n$).

Résultats clés
L'article présente le Théorème 1.1, qui stipule que pour toute température inverse constante $\beta > 0$ (spécifiquement $\beta \geq \beta_c$ pour une certaine constante universelle), il existe un algorithme qui apprend les coefficients du Hamiltonien avec une précision $\epsilon$ et une probabilité de $99/100$.

• Complexité d'échantillonnage : $n \geq \text{poly}(m, (1/\epsilon)^{2O(\beta)})$.
• Temps d'exécution : $n^{O(1)}$ (spécifiquement $\text{poly}(m, \log(1/\delta)) \cdot (1/\epsilon)^{2O(\beta)}$).

L'algorithme fonctionne pour des Hamiltoniens à « faible intersection », une classe qui inclut les Hamiltoniens localement géométriques sur des réseaux et ceux définis sur des graphes d'expansion.

Signification et revendications
Les auteurs revendiquent avoir entièrement résolu le problème ouvert de l'apprentissage efficace de Hamiltoniens à basse température.

• Résolution de questions ouvertes : Le résultat apporte une réponse positive à la question de savoir si l'apprentissage de Hamiltoniens à basse température est soluble en temps polynomial [AAKS20 ; HKT22 ; Alh23 ; AA23]. Il répond également négativement à l'hypothèse selon laquelle les états de Gibbs à basse température pourraient être pseudo-aléatoires (Question 3 dans [AA23]) et positivement à la question de savoir si l'apprentissage est possible sous indépendance conditionnelle approximative (Question 2 dans [AA23]).
• Outil algorithmique : Ce travail démontre que des outils sophistiqués de la théorie de l'optimisation, spécifiquement la hiérarchie des Sommes de Carrés, peuvent surmonter des barrières dans l'apprentissage des systèmes quantiques à plusieurs corps qui semblaient auparavant intraitables en raison de la difficulté de calculer les fonctions de partition.
• Indépendance par rapport aux limites classiques : Les auteurs notent que, bien que l'apprentissage de Hamiltoniens classiques (apprentissage de modèles graphiques non dirigés) nécessite un temps exponentiel en $\beta$, le cadre quantique n'hérite pas nécessairement de cette difficulté, malgré la non-commutativité et la non-localité des systèmes quantiques.
• Praticité : L'article reconnaît que, bien que l'algorithme soit théoriquement efficace (polynomial en $n$), la dépendance en $\beta$ dans l'exposant du temps d'exécution et de la complexité d'échantillonnage signifie qu'il n'est pas actuellement pratique pour des températures très basses ou de grands systèmes. Cependant, il établit une possibilité théorique là où aucune n'existait auparavant.

L'article ne propose pas de nouvelles configurations expérimentales ni d'applications pratiques immédiates, mais présente le résultat comme une avancée fondamentale dans la compréhension de la complexité computationnelle de la caractérisation des systèmes quantiques, particulièrement pertinente pour la validation des simulateurs quantiques analogiques qui fonctionnent souvent dans des régimes de basse température.