A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz

Sintesi Tecnica: Un'Eurisitica di Impostazione dei Parametri per il Quantum Alternating Operator Ansatz

Definizione del Problema
Il Quantum Alternating Operator Ansatz (QAOA) è un prominente algoritmo quantistico parametrizzato per la risoluzione di problemi di ottimizzazione combinatoria. Tuttavia, trovare parametri ($\vec{\gamma}, \vec{\beta}$) di alta qualità in modo efficiente rimane una sfida pratica significativa. Il processo di impostazione dei parametri implica tipicamente un ciclo variazionale quantistico-classico in cui un ottimizzatore classico aggiorna i parametri sulla base del valore di aspettazione di una funzione di costo valutata su hardware quantistico o tramite una costosa simulazione classica. Questo processo affronta difficoltà quali i barren plateaus, l'esistenza di numerosi ottimi locali e la scalabilità esponenziale delle risorse richieste per la valutazione esatta dei valori di aspettazione classici all'aumentare del numero di qubit ($n$) o della profondità del circuito ($p$). Inoltre, gli attuali dispositivi NISQ (Noisy Intermediate-Scale Quantum) esacerbano tali sfide attraverso il rumore e gli errori di campionamento finiti.

Metodologia
Gli autori propongono una "Eurisitica Omogenea per l'Impostazione dei Parametri", una strategia classica progettata per sostituire la costosa valutazione classica o quantistica del valore di aspettazione della funzione di costo con un efficiente modello classico. Il nucleo di questo approccio si basa sul concetto di Omogeneità Perfetta.

1. Omogeneità Perfetta: Questa è definita come una proprietà dello stato in cui tutti i bitstring $x$ che condividono lo stesso valore di costo $c(x)$ possiedono ampiezze quantistiche identiche. Sebbene questa proprietà valga esattamente solo per problemi specifici simmetrici o nel limite di parametri piccoli, osservazioni empiriche suggeriscono elevati overlap tra gli stati QAOA e stati perfettamente omogenei in varie configurazioni.
2. Proxy Omogeneo Classico: Gli autori costruiscono un modello classico, denominato "Classical Homogeneous Proxy", che impone l'Omogeneità Perfetta per assunzione. In questo proxy, lo stato non è descritto da $2^n$ ampiezze, ma da un insieme di ampiezze $Q(c)$ corrispondenti a ciascun valore di costo unico $c$.
   • L'evoluzione è modellata utilizzando una prospettiva "sum-of-paths" (somma di cammini). Gli autori sostituiscono il conteggio esatto dei bitstring a una specifica distanza di Hamming con una distribuzione $N(c'; d, c)$ derivata analiticamente che dipende solo dalle classi di costo.
   • Ciò consente il calcolo ricorsivo delle ampiezze $Q_\ell(c)$ per ogni layer $\ell$ utilizzando l'Eq. (5), la cui scalabilità è polinomiale rispetto alla dimensione del problema $n$ e al numero di valori di costo distinti $|C|$, a condizione che $|C|$ cresca polinomialmente con $n$.
3. Il Ciclo Euristico: La procedura di impostazione dei parametri (Algoritmo 3) utilizza questo proxy come sottoprocedura interna. Un ottimizzatore classico cerca i parametri $(\vec{\gamma}, \vec{\beta})$ che minimizzano la "funzione obiettivo dei parametri omogenei" (una stima del valore di aspettazione del costo derivata dal proxy). Una volta trovati i parametri ottimali per il proxy, questi vengono applicati direttamente al circuito QAOA effettivo.

Il documento dimostra come sia possibile calcolare le distribuzioni necessarie ($N(c'; d, c)$ e probabilità di costo $P(c')$) per specifiche classi di problemi di soddisfacimento di vincoli (CSP) con clausole estratte casualmente, inclusi k-SAT casuali, MaxCut su grafi di Erdős-Rényi e Max-k-XOR.

Contributi Chiave

• Definizione di Omogeneità Perfetta e del Proxy: Gli autori formalizzano la condizione di Omogeneità Perfetta e definiscono un Proxy Omogeneo Classico che fornisce sia le descrizioni dello stato che i valori di aspettazione in modo efficiente.
• Scalabilità Polinomiale: Il metodo proposto consente il calcolo classico dei parametri del proxy in un tempo che scala polinomialmente rispetto sia al numero di variabili $n$ che alla profondità $p$, evitando la crescita esponenziale delle risorse associata alla simulazione esatta dello stato vettoriale.
• Generalizzazione alle Classi di CSP: Il documento fornisce derivazioni esplicite per le distribuzioni del proxy per quattro classi di CSP casuali, mostrando che il proxy può descrivere un'intera classe di problemi piuttosto che un singolo caso.
• Framework Euristico: Gli autori introducono un workflow completo (Algoritmo 3) che integra questo proxy nei loop standard di ottimizzazione dei parametri, mantenendo la flessibilità nella scelta degli schemi di aggiornamento dei parametri.

Risultati
Gli autori hanno valutato numericamente l'euristica su problemi MaxCut su grafi casuali non pesati di Erdős-Rényi ($G(n, p_e)$):

• Bassa Profondità ($p \leq 3$): Per grafi con $n=20$, l'euristica ha trovato parametri che hanno prodotto rapporti di approssimazione comparabili a quelli ottenuti con la strategia di "parameter transfer" (trasferimento dei parametri ottimizzati globalmente da istanze più piccole). La differenza nelle prestazioni non era statisticamente significativa, sebbene l'euristica abbia mostrato prestazioni medie leggermente superiori in alcuni casi.
• Alta Profondità ($p \leq 20$): Per profondità fino a $p=20$, l'euristica è riuscita a identificare parametri che producono rapporti di approssimazione che aumentano monotonicamente all'aumentare della profondità. Al contrario, una strategia che utilizza il trasferimento dei parametri con identiche risorse classiche non è riuscita a convergere.
• Accuratezza del Proxy: L'analisi numerica ha mostrato che il proxy mantiene grandi overlap con le simulazioni complete dello stato vettoriale, in particolare per schemi di parametri a rampa lineare e in regimi in cui il parametro $\gamma$ è piccolo. Le distribuzioni analitiche utilizzate nel proxy sono risultate altamente correlate con le medie empiriche su istanze di grafi casuali.

Significatività e Rivendicazioni
Il documento sostiene che l'Eurisitica Omogenea offre una via pratica per l'impostazione dei parametri in regimi che sono attualmente intrattabili per i dispositivi NISQ a causa del rumore e per i metodi classici a causa della scalabilità esponenziale. Sostituendo la costosa valutazione del valore di aspettazione con un proxy classico a tempo polinomiale, il metodo consente l'esplorazione di circuiti QAOA più profondi (ad esempio, $p=20$) dove le strategie precedenti falliscono la convergenza.

Gli autori sottolineano che, sebbene l'euristica non garantisca parametri ottimali per ogni specifico caso, essa fornisce una strategia robusta e di classe che compete con i metodi stabiliti a basse profondità e li supera ad alte profondità. Il lavoro suggerisce che l'assunzione di Omogeneità Perfetta, pur non essendo universalmente esatta, funge da approssimazione sufficientemente accurata per guidare l'ottimizzazione dei parametri in molti contesti di ottimizzazione combinatoria, particolarmente quelli che coinvolgono vincoli casuali. Gli autori concludono delineando direzioni future, come l'incorporazione di informazioni specifiche dell'istanza nel proxy e l'estensione dell'approccio ad altri algoritmi quantistici variazionali come il Variational Quantum Eigensolver (VQE).