Learning quantum Hamiltonians at any temperature in polynomial time

Riassunto Tecnico: Apprendimento di Hamiltoniane Quantistiche a Qualsiasi Temperatura in Tempo Polinomiale

Enunciato del Problema
Il lavoro affronta il problema dell'apprendimento di Hamiltoniane per sistemi quantistici locali. Dato un sistema di $n$ qubit descritto da un'Hamiltoniana locale $H = \sum_{a=1}^m \lambda_a E_a$, dove i termini di interazione $E_a$ sono operatori di Pauli noti, distinti, non-identità con località limitata, e i coefficienti $\lambda_a$ sono intensità di interazione sconosciute in $[-1, 1]$, l'obiettivo è stimare i $\lambda_a$. L'algoritmo ha accesso a copie dello stato di Gibbs $\rho = e^{-\beta H} / \text{tr}(e^{-\beta H})$ a una temperatura inversa nota $\beta > 0$. L'obiettivo è produrre stime $\hat{\lambda}_a$ tali che $|\hat{\lambda}_a - \lambda_a| \leq \epsilon$ per ogni $a$, utilizzando un numero di campioni e un tempo di esecuzione polinomiali nella dimensione del sistema $n$ (e nel numero di termini $m$) e in $1/\epsilon$.

Prima di questo lavoro, sebbene fossero noti limiti di complessità dei campioni polinomiale [AAKS20], i corrispondenti algoritmi computazionali erano inefficienti (tempo esponenziale) per regimi generali a bassa temperatura. Algoritmi efficienti esistevano solo per alte temperature (piccolo $\beta$) [HKT22] o per termini Hamiltoniani che commutano [AAKS21]. La questione aperta centrale era se l'apprendimento di Hamiltoniane a basse temperature (grande $\beta$) potesse essere risolto in tempo polinomiale in $n$.

Metodologia
Gli autori propongono un algoritmo computazionalmente efficiente basato sulla gerarchia Sum-of-Squares (SoS). La strategia tecnica fondamentale coinvolge tre componenti principali:

1. Formulazione di un Sistema di Vincoli Polinomiali:
   Invece di invertire direttamente la mappa dai parametri ai marginali locali (che è computazionalmente difficile), gli autori definiscono un sistema di vincoli che i parametri veri devono soddisfare. Questo sistema include:

   • Limiti sui parametri: $-1 \leq \lambda'_a \leq 1$.
   • Vincoli di commutatore: Garantendo che l'Hamiltoniana candidata $H'$ commuti con lo stato di Gibbs $\rho$ (cioè $[H', \rho] \approx 0$).
   • Vincoli polinomiali "piatti": Sostituendo l'esponenziale di matrice $e^{-\beta H'}$ con un'approssimazione polinomiale di basso grado $p(H' | P)$ che agisce su osservabili locali. Nello specifico, impongono che per operatori di Pauli locali $P, Q$, il valore di aspettazione $\text{tr}(Q e^{-\beta H'} P e^{\beta H'} \rho)$ sia vicino a $\text{tr}(PQ\rho)$.

2. Approssimazione Polinomiale Piatto dell'Esponenziale:
   Un ostacolo tecnico chiave è che le approssimazioni standard in serie di Taylor di $e^{-\beta x}$ crescono troppo rapidamente al di fuori dell'intervallo di approssimazione, rendendole inadatte ai regimi a bassa temperatura dove le differenze di autovalori possono essere grandi. Gli autori costruiscono una nuova approssimazione polinomiale "piatta" $p(x)$ che:

   • Approssima bene $e^{-\beta x}$ sull'intervallo $[-1, 1]$.
   • Cresce a un tasso esponenziale controllato e lento ($e^{\eta \beta |x|}$) al di fuori di questo intervallo.
     Questa costruzione è ispirata a tecniche iterative di "sfogliatura" (peeling) utilizzate nei limiti di Lieb-Robinson. Ciò permette di sostituire l'esponenziale di matrice nei vincoli con un polinomio di basso grado nelle incognite $\lambda'_a$.

3. Traduzione tra Polinomi e Commutatori Annidati:
   Gli autori stabiliscono una traduzione formale tra polinomi scalari multivariati e commutatori annidati di operatori. Utilizzando la formula di Hadamard, mostrano che termini come $e^{-\beta H'} P e^{\beta H'}$ possono essere espressi come polinomi negli autovalori di $H'$, che corrispondono a commutatori annidati $[H', P]_\ell$. Dimostrano che le identità polinomiali nel dominio scalare si traducono in identità che coinvolgono commutatori annidati fino a termini di errore piccoli, a condizione che gli operatori siano locali.

4. Rilassamento Sum-of-Squares e Identificabilità:
   Il sistema risultante di vincoli è un insieme di disuguaglianze polinomiali di basso grado. Gli autori risolvono questo sistema utilizzando un rilassamento Sum-of-Squares (SoS) di grado-$d$, che può essere formulato come un Programma Semidefinito (SDP).

   • Fattibilità: Dimostrano che i parametri veri soddisfano il sistema (fino al rumore di campionamento).
   • Identificabilità: Forniscono una dimostrazione SoS che qualsiasi soluzione del sistema deve essere vicina ai parametri veri. Questo si basa su una filosofia "dalla dimostrazione agli algoritmi". Un passaggio cruciale consiste nel mostrare che la varianza degli operatori locali sotto lo stato di Gibbs è limitata inferiormente da zero (un analogo quantistico delle proprietà nei modelli grafici classici), garantendo che i parametri siano identificabili.
   • Efficienza: Analizzando la struttura specifica delle dimostrazioni SoS, mostrano che è necessaria solo una sottoinsieme sparso di monomi, permettendo di risolvere l'SDP in tempo polinomiale in $m$ e $1/\epsilon$ (con una dipendenza esponenziale da $\beta$ nel grado, ma polinomiale in $n$).

Risultati Chiave
Il lavoro presenta il Teorema 1.1, che afferma che per qualsiasi temperatura inversa costante $\beta > 0$ (specificamente $\beta \geq \beta_c$ per una certa costante universale), esiste un algoritmo che apprende i coefficienti dell'Hamiltoniana con precisione $\epsilon$ con probabilità $99/100$.

• Complessità dei Campioni: $n \geq \text{poly}(m, (1/\epsilon)^{2O(\beta)})$.
• Tempo di Esecuzione: $n^{O(1)}$ (specificamente $\text{poly}(m, \log(1/\delta)) \cdot (1/\epsilon)^{2O(\beta)}$).

L'algoritmo funziona per Hamiltoniane a "bassa intersezione", una classe che include Hamiltoniane geometricamente locali su reticoli e quelle definite su grafi espansori.

Significato e Affermazioni
Gli autori affermano di risolvere completamente il problema aperto dell'apprendimento efficiente di Hamiltoniane a basse temperature.

• Risoluzione di Domande Aperte: Il risultato fornisce una risposta affermativa alla domanda se l'apprendimento di Hamiltoniane a basse temperature sia risolvibile in tempo polinomiale [AAKS20; HKT22; Alh23; AA23]. Risponde anche negativamente all'ipotesi che gli stati di Gibbs a basse temperature possano essere pseudocasuali (Domanda 3 in [AA23]) e positivamente alla domanda se l'apprendimento sia possibile sotto indipendenza condizionata approssimata (Domanda 2 in [AA23]).
• Strumento Algoritmico: Il lavoro dimostra che strumenti sofisticati della teoria dell'ottimizzazione, in particolare la gerarchia Sum-of-Squares, possono superare le barriere nell'apprendimento di molti corpi quantistici che in precedenza sembravano intrattabili a causa della difficoltà di calcolare le funzioni di partizione.
• Indipendenza dai Limiti Classici: Gli autori notano che, mentre l'apprendimento di Hamiltoniane classiche (apprendimento di modelli grafici non diretti) richiede tempo esponenziale in $\beta$, il contesto quantistico non eredita necessariamente questa durezza, nonostante la non commutatività e la non località dei sistemi quantistici.
• Praticità: Il lavoro riconosce che, sebbene l'algoritmo sia teoricamente efficiente (polinomiale in $n$), la dipendenza da $\beta$ nell'esponente del tempo di esecuzione e della complessità dei campioni significa che non è attualmente pratico per temperature molto basse o sistemi grandi. Tuttavia, stabilisce una possibilità teorica dove prima non ne esisteva alcuna.

Il lavoro non propone nuovi setup sperimentali o applicazioni pratiche immediate, ma inquadra il risultato come un avanzamento fondamentale nella comprensione della complessità computazionale della caratterizzazione dei sistemi quantistici, particolarmente rilevante per la validazione di simulatori quantistici analogici che operano spesso in regimi a bassa temperatura.