A 0.651-approximation to quantum Max Cut via Rydberg atoms

Sintesi Tecnica: Un'approssimazione di 0,651 per il Max Cut Quantistico tramite Atomi di Rydberg

Definizione del Problema
Il documento affronta il problema del Max Cut Quantistico (QMC), che è equivalente a trovare l'energia dello stato fondamentale dell'Hamiltoniana di Heisenberg antiferromagnetica. Questo problema è QMA-completo, il che significa che non può essere risolto efficientemente nemmeno con un computer quantistico universale. L'obiettivo è trovare un algoritmo di approssimazione che garantisca una soluzione entro un rapporto specifico ($\alpha$) rispetto all'energia dello stato fondamentale ottimale. Lo stato dell'arte classico attuale, basato esclusivamente su rilassamenti di programmazione semidefinita (SDP), raggiunge un rapporto di approssimazione $\alpha = 0,614$.

Metodologia: Un Approccio Ibrido Quantistico-Classico
Gli autori propongono un algoritmo ibrido che integra la dinamica quantistica naturale dei sistemi di atomi di Rydberg con tecniche di ottimizzazione classica (SDP e rounding randomizzato). La metodologia procede in quattro fasi distinte:

1. Codifica e Annealing:
   Un'istanza di QMC definita su un grafo $G=(V, E, \omega)$ viene codificata in un array di atomi di Rydberg. La parte statica dell'Hamiltoniana di Rydberg, $H_r$, è costruita per contenere i termini di interazione $XX + YY$ corrispondenti agli archi del grafo:
   $$H_r = \sum_{(ij) \in E} \omega_{ij} (X_i X_j + Y_i Y_j)$$
   Il sistema subisce una procedura di annealing per preparare uno stato fondamentale approssimativo, denotato come $\varrho_r$.

2. Misurazione e Formulazione dei Vincoli:
   I valori di aspettazione $\langle X_i X_j + Y_i Y_j \rangle$ vengono misurati per tutti gli archi nello stato di annealing $\varrho_r$. Questi valori fungono da vincoli empirici per una successiva fase di ottimizzazione classica.

3. Programmazione Semidefinita e Rounding:
   Una matrice pseudo-momento $\Delta$ viene ottimizzata tramite SDP, soggetta ai vincoli derivati dalle misurazioni di Rydberg e dalle relazioni algebriche degli operatori di Pauli. Questa matrice viene poi trasformata in uno stato prodotto $\varrho_p$ utilizzando una tecnica di proiezione randomizzata (decomposizione di Cholesky seguita da proiezione casuale da $\mathbb{R}^{4n}$ a $\mathbb{R}^3$).

4. Selezione dello Stato Finale:
   L'algoritmo restituisce lo stato con l'energia inferiore: ovvero lo stato fondamentale di Rydberg $\varrho_r$ o lo stato prodotto $\varrho_p$ ottenuto tramite il rounding classico.

Contributi Teorici Chiave
Il documento stabilisce un rapporto di approssimazione condizionale di 0,651, superando il precedente miglior rapporto noto di 0,614. La derivazione si basa su due principali intuizioni teoriche:

• Limite Inferiore tramite lo Stato Fondamentale di Rydberg: Gli autori dimostrano che l'energia dell'Hamiltoniana QMC completa ($H_{qmc}$) può essere limitata inferiormente utilizzando l'energia dell'Hamiltoniana di Rydberg ($H_r$). Sfruttando l'invarianza $SU(2)$ del modello di Heisenberg, mostrano che i valori di aspettazione di $XX$, $YY$e$ZZ$ sono uguali nello stato fondamentale ottimale. Ciò consente la ricostruzione dell'energia QMC completa dalle misurazioni parziali $XX+YY$ ottenute dal sistema di Rydberg.
• Limite Superiore tramite Rounding: Il documento analizza l'energia dello stato prodotto $\varrho_p$ generato dal rounding SDP. Viene derivata un'espressione analitica per l'energia attesa di questo stato basata sulle correlazioni misurate.
• Ottimizzazione del Rapporto: Combinando il limite inferiore (derivato dallo stato di Rydberg) e i limiti superiori (sia dallo stato di Rydberg che dallo stato prodotto), gli autori formulano un problema di minimizzazione sul parametro di correlazione $t_{ij}$. Risolvendo questo problema, si ottiene il rapporto di 0,651.

Risultati e Robustezza

• Rapporto di Approssimazione: L'algoritmo raggiunge un rapporto di approssimazione condizionale di $\kappa = 0,651$.
• Robustezza al Rumore: Un risultato significativo è la resilienza dell'algoritmo alla preparazione imperfetta dello stato fondamentale. Gli autori dimostrano che il vantaggio di 0,651 persiste anche se la procedura di annealing di Rydberg produce uno stato con un'energia pari solo all'89% dell'energia dello vero stato fondamentale di Rydberg ($\eta = 0,89$). Al di sotto di questa soglia, il vantaggio rispetto ai metodi SDP puramente classici diminuisce.
• Complessità Computazionale: L'approccio ibrido riduce la dimensionalità del problema di ottimizzazione classica. Mentre gli schemi classici che mirano a stati entangled richiedono $O(n^4)$ variabili reali, questo metodo ibrido opera su $O(n^2)$ variabili, sfruttando il sistema quantistico per gestire la complessità della struttura dell'entanglement.

Significatività
Il documento sostiene di aprire una nuova strada per gli algoritmi ibridi quantistico-classici. Dimostra che combinare l'hardware quantistico (specificamente array di atomi di Rydberg) con l'ottimizzazione classica può fornire garanzie di approssimazione più forti rispetto ai metodi classici da soli, anche quando l'hardware quantistico non risolve perfettamente il problema dell'Hamiltoniana sottostante. Il lavoro suggerisce che le piattaforme quantistiche possono fungere da "proxy" efficaci per fornire limiti inferiori di alta qualità e punti di partenza per le procedure di rounding classiche, aggirando efficacemente alcune delle limitazioni di scalabilità computazionale dei puri approcci classici.