Apprentissage optimal des hamiltoniens quantiques à partir d'états de Gibbs à haute température

Informations fondamentales

• ID de l'article : 2108.04842
• Titre : Optimal learning of quantum Hamiltonians from high-temperature Gibbs states
• Auteurs : Jeongwan Haah (Microsoft Quantum), Robin Kothari (Microsoft Quantum), Ewin Tang (University of Washington)
• Classification : quant-ph cs.DS cs.LG
• Date de publication : 17 mars 2023 (version arXiv)
• Lien de l'article : https://arxiv.org/abs/2108.04842

Résumé

Cet article étudie le problème d'apprentissage de l'hamiltonien H à partir de copies de l'état de Gibbs ρ=exp(-βH)/Tr(exp(-βH)) avec une température inverse β connue, jusqu'à une précision ε. Dans le régime haute température (β faible), les auteurs proposent un algorithme d'apprentissage pour la classe des hamiltoniens à faible intersection, réalisant une complexité d'échantillonnage S=O(logN/(βε)²) et une complexité temporelle O(SN), et prouvent des bornes inférieures correspondantes, démontrant que l'algorithme est optimal en complexité d'échantillonnage et temporelle.

Contexte et motivation de la recherche

Définition du problème

Le problème d'apprentissage de l'hamiltonien est une question importante à l'intersection de la physique quantique multi-corps et de l'apprentissage automatique. Étant donné plusieurs copies de l'état d'équilibre thermique (état de Gibbs) d'un hamiltonien inconnu H, l'objectif est d'apprendre les coefficients de l'hamiltonien. Ce problème possède une motivation directe en physique : l'hamiltonien décrit les interactions et l'évolution temporelle d'un système quantique, tandis que l'état de Gibbs est l'état du système en équilibre thermique avec son environnement à une température donnée.

Signification de la recherche

1. Signification physique : Comprendre les propriétés fondamentales des systèmes quantiques et prédire leur comportement
2. Signification computationnelle : Il s'agit d'une généralisation quantique du problème classique d'apprentissage des champs aléatoires de Markov
3. Signification théorique : Établit des connexions entre la théorie de l'information quantique et la théorie de l'apprentissage statistique

Limitations des approches existantes

• Le travail d'Anshu et al. (AAKS21) sur les hamiltoniens géométriquement locaux présente une complexité d'échantillonnage O(2^{poly(β)}N²logN/(β^c ε²)), qui n'est pas optimale dans sa dépendance en β et N
• L'analyse et l'optimisation de la complexité temporelle manquent de clarté
• S'applique uniquement à la classe des hamiltoniens géométriquement locaux

Contributions principales

1. Algorithme optimal : Propose un algorithme optimal pour l'apprentissage des hamiltoniens à faible intersection dans le régime haute température, avec complexité d'échantillonnage O(logN/(βε)²) et complexité temporelle O(N logN/(βε)²)
2. Borne inférieure correspondante : Prouve une borne inférieure correspondante pour la complexité d'échantillonnage Ω(exp(β)logN/(β²ε²)), atteignant l'optimalité dans le régime haute température
3. Classe d'hamiltoniens plus générale : Étend à des hamiltoniens à faible intersection, qui sont plus généraux que les hamiltoniens géométriquement locaux
4. Analyse théorique : Améliore l'analyse de la forte convexité de la fonction de partition logarithmique, raffinant le paramètre de forte convexité à β²/2
5. Extension à l'évolution en temps réel : Démontre que le même algorithme peut être utilisé pour apprendre l'hamiltonien à partir d'opérateurs unitaires d'évolution en temps réel e^{-itH}

Détails de la méthode

Définition de la tâche

Considérons l'hamiltonien d'un système de N qubits H = Σ_^M λ_a E_a, où :

• E_a sont des opérateurs de Pauli non-identité distincts et connus
• λ_a ∈ -1,1 sont les coefficients à apprendre
• L'hamiltonien est à faible intersection : chaque opérateur agit sur un nombre constant de qubits, et chaque opérateur n'a que des intersections non-triviales avec un nombre constant d'autres opérateurs

Objectif : Apprendre les coefficients {λ_a} à partir de copies de l'état de Gibbs ρ = exp(-βH)/Tr(exp(-βH)) jusqu'à une erreur additive ε.

Cadre technique fondamental

1. Développement en amas (Cluster Expansion)

Utilise la technique du développement en amas de la mécanique statistique pour développer la valeur d'espérance ⟨E_a⟩ en série de Taylor en β :

⟨E_a⟩(x) = β p₁^{(a)}(x) + β² p₂^{(a)}(x) + β³ p₃^{(a)}(x) + ...

où p_m^{(a)} est un polynôme homogène de degré m, et p₁^{(a)}(x) = -x_a.

2. Flux de l'algorithme

Étape 1 : Estimation des valeurs d'espérance

• Pour chaque opérateur de Pauli E_a, estimer ⟨E_a⟩ à la précision βε
• Utiliser la coloration du graphe d'interaction dual et mesurer en parallèle les opérateurs non-chevauchants
• Complexité d'échantillonnage : O(d/(β²ε²)log(M/δ))

Étape 2 : Méthode de Newton-Raphson Définir la fonction F_a(x) = Σ_^m β^k p_k^{(a)}(x) - Ê_a, l'objectif étant de trouver x tel que F(x) soit suffisamment petit.

Utiliser l'itération de Newton-Raphson modifiée :

x^{(t+1)} = Proj_{[-1,1]^M}[x^{(t)} + β^{-1} Σ_{k=0}^{K-1} (I + β^{-1}J(x^{(t)}))^k F(x^{(t)})]

3. Innovations techniques clés

Calcul des dérivées d'amas :

• Conception d'un algorithme pour calculer précisément les dérivées d'amas D_W L
• Complexité temporelle : (8m + L)poly(m)
• Utilise les propriétés entières des matrices de Pauli pour l'arithmétique exacte

Analyse de la matrice jacobienne :

• Prouve que la matrice jacobienne J possède une structure « bande-diagonale »
• Si b et a sont à distance k, alors J_ est d'ordre β^{k+1}
• Cela rend J proche de -βI, facilitant l'approximation de J^{-1}

Analyse de convergence

Condition de température critique

L'algorithme fonctionne pour β < β_c, où β_c = (25e^6(d+1)^{10})^{-1} dépend uniquement du degré d du graphe d'interaction dual.

Propagation d'erreur

Analyse la propagation d'erreur via le théorème de la valeur moyenne multivariée :

|x_a - λ_a| ≤ ||J^{-1}||_{∞→∞}(||F(x)||_∞ + ||F(λ)||_∞) ≤ 4ε

Configuration expérimentale

Vérification théorique

L'article est principalement un travail théorique, vérifiant la correction et l'optimalité de l'algorithme par des preuves mathématiques plutôt que par des expériences empiriques.

Analyse de complexité

• Complexité d'échantillonnage : O(logN/(βε)²) (erreur ℓ_∞), O(N/(βε)²) (erreur ℓ_2)
• Complexité temporelle : O(N logN/(βε)²) (ℓ_∞), O(N²/(βε)²) (ℓ_2)
• Temps de prétraitement : O(LMd log d) pour construire le graphe d'interaction dual

Résultats expérimentaux

Résultats théoriques principaux

Théorème de borne supérieure (Théorème 1.1)

Pour les hamiltoniens à faible intersection, sous la condition β < β_c :

• Erreur ℓ_∞ ε : complexité d'échantillonnage O(1/(β²ε²) log(N/δ))
• Erreur ℓ_2 ε : complexité d'échantillonnage O(N/(β²ε²) log(N/δ))
• Les complexités temporelles sont la complexité d'échantillonnage multipliée par N

Théorème de borne inférieure (Théorème 1.2)

Il existe des hamiltoniens 2-locaux tels que :

• Erreur ℓ_∞ : complexité d'échantillonnage Ω(exp(β)/(β²ε²) log(N/δ))
• Erreur ℓ_2 : complexité d'échantillonnage Ω(exp(β)N/(β²ε²))

Comparaison avec les travaux antérieurs

Amélioration de la forte convexité

Améliore le paramètre de forte convexité de la fonction de partition logarithmique de Ω(β^c/N) à Ω(β²), ce qui correspond à une amélioration de la borne inférieure de la variance des observables macroscopiques.

Travaux connexes

Apprentissage des hamiltoniens quantiques

• Bairey et al. (2019) : Première proposition d'apprentissage à partir d'états stationnaires, mais sans analyse du pire cas
• AAKS21 : Établit des bornes supérieures strictes de complexité d'échantillonnage, mais non optimales sur plusieurs paramètres
• Cas classique : Des algorithmes quasi-optimaux existent pour l'apprentissage des paramètres des champs aléatoires de Markov

Connexions techniques

• Développement en amas : Emprunte la technique du développement haute température de la mécanique statistique
• Méthode de Newton : Application de la méthode d'optimisation classique au cadre quantique
• Bornes informationnelles inférieures : Utilise le lemme de Fano pour établir les bornes informationnelles inférieures

Conclusion et discussion

Conclusions principales

1. Dans le régime haute température, l'apprentissage des hamiltoniens quantiques peut atteindre la même complexité optimale que le cas classique
2. L'algorithme proposé est optimal en complexité d'échantillonnage et temporelle
3. La classe des hamiltoniens à faible intersection est plus générale que celle des hamiltoniens géométriquement locaux, mais reste efficacement apprenable

Limitations

1. Restriction de température : L'algorithme ne fonctionne que dans le régime haute température, la température critique dépendant du degré du graphe dual
2. Dépendance au degré : Bien qu'optimal pour un degré fixe, la température critique décroît rapidement avec le degré
3. Région basse température : Le problème d'apprentissage en région basse température reste ouvert

Directions futures

1. Élargir la plage de température : Chercher des algorithmes fonctionnant sur une plage de température plus large
2. Hamiltoniens locaux généraux : Étendre aux cas où le degré n'est pas constant
3. Algorithmes basse température : Développer des algorithmes d'apprentissage efficaces pour la région basse température
4. Vérification expérimentale : Valider les performances de l'algorithme sur des systèmes quantiques réels

Évaluation approfondie

Avantages

1. Complétude théorique : Fournit une analyse complète des bornes supérieures et inférieures correspondantes
2. Innovation technique : Combine astucieusement le développement en amas et la méthode de Newton
3. Optimalité : Atteint l'optimalité simultanément sur plusieurs paramètres
4. Généralité : Étend à une classe d'hamiltoniens plus générale que les travaux antérieurs
5. Praticabilité de l'algorithme : Fournit un algorithme concrètement réalisable et une analyse de complexité

Insuffisances

1. Limitation du domaine d'application : S'applique uniquement au régime haute température
2. Sensibilité au degré : La dépendance de la température critique au degré est assez forte
3. Absence d'expériences : Travail purement théorique, manquant de vérification numérique
4. Avantage quantique peu évident : Dans le cadre étudié, la complexité quantique est identique au cas classique

Impact

1. Contribution théorique : Établit un repère pour l'apprentissage des hamiltoniens quantiques
2. Valeur méthodologique : Démontre l'application efficace des techniques classiques au cadre quantique
3. Recherches ultérieures : Pose les fondations pour les recherches en région basse température et cadres plus généraux
4. Potentiel pratique : Fournit des orientations théoriques pour la caractérisation expérimentale des systèmes quantiques

Scénarios d'application

1. Simulation quantique : Vérifier la précision des simulateurs quantiques
2. Science des matériaux : Apprendre l'hamiltonien effectif des systèmes de matière condensée
3. Informatique quantique : Étalonnage et vérification des processeurs quantiques
4. Recherche fondamentale : Comprendre les propriétés des systèmes quantiques multi-corps

Références

1. Anshu, A., Arunachalam, S., Kuwahara, T., & Soleimanifar, M. (2021). Sample-efficient learning of interacting quantum systems. Nature Physics.
2. Kuwahara, T., Kato, K., & Brandão, F. G. (2020). Clustering of conditional mutual information for quantum Gibbs states above a threshold temperature. Physical Review Letters.
3. Bresler, G. (2015). Efficiently learning Ising models on arbitrary graphs. STOC.
4. Klivans, A., & Meka, R. (2017). Learning graphical models using multiplicative weights. FOCS.