Riepilogo Tecnico: AQKA: Acquisizione Attiva del Kernel Quantistico sotto un Budget di Shot

1. Enunciato del Problema

I metodi di kernel quantistico, che mappano input classici in uno spazio delle caratteristiche quantistico per calcolare le fedeltà $K(x_i, x_j) = |\langle \phi(x_j)|\phi(x_i)\rangle|^2$, sono tra i carichi di lavoro più accessibili per l'hardware NISQ (Noisy Intermediate-Scale Quantum). Tuttavia, il loro dispiegamento pratico è ostacolato dai costi di misurazione. La stima di una matrice di kernel $N \times N$ richiede $\Theta(N^2 S)$ esecuzioni del circuito (shot), dove $S$ è il numero di shot per voce necessario per raggiungere una precisione desiderata. Sull'hardware attuale, dove le latenze del circuito variano da millisecondi a secondi, questa scalabilità limita le dimensioni dei problemi dispiegabili alle basse centinaia.

Le strategie esistenti per risparmiare budget (ad esempio, Nyström-QKE, ShoFaR, allineamento kernel-obiettivo) affrontano questo problema sottocampionando quali voci misurare (ad esempio, selezionando colonne o punti di training di riferimento). Tuttavia, questi metodi allocano tipicamente il budget di shot in modo uniforme all'interno dei loro sottoinsiemi scelti. Non tengono conto dell'eterogeneità di quanto ogni specifica voce del kernel contribuisca alle prestazioni del classificatore a valle. La domanda fondamentale irrisolta è: dato un budget di shot fisso $B$, come dovrebbero essere allocati gli shot a livello di coppia per minimizzare la perdita della task a valle?

2. Metodologia: AQKA

Gli autori formulano l'apprendimento del kernel quantistico con budget di shot come un problema di ottimizzazione che minimizza la perdita attesa $\mathbb{E}[L(\hat{K})]$ soggetta a un vincolo di budget totale di shot $\sum s_{ij} \leq B$.

Derivazione Teorica

Utilizzando un'analisi del primo ordine (metodo Delta) combinata con le condizioni Karush-Kuhn-Tucker (KKT), gli autori derivano una regola di allocazione ottimale in forma chiusa. Per una voce del kernel $K_{ij}$ stimata con $s_{ij}$ shot, la varianza è $K_{ij}(1-K_{ij})/s_{ij}$. L'allocazione ottimale $s^*_{ij}$ che minimizza la varianza dello stimatore della perdita è proporzionale alla sensibilità della perdita rispetto a quella voce:
$$s^*_{ij} \propto |g_{ij}| \sqrt{K_{ij}(1-K_{ij})}$$
dove $g_{ij} = \partial L / \partial K_{ij}$ è il gradiente della perdita rispetto alla voce del kernel.

• Per la Regressione Ridge a Kernel (KRR): Il gradiente è derivato esplicitamente come $g_{ij} = -2\lambda^2(\beta_i \alpha_j + \beta_j \alpha_i)$, dove $\alpha = (K+\lambda I)^{-1}y$ e $\beta = (K+\lambda I)^{-1}\alpha$.
• Per le Macchine a Vettori di Supporto (SVM): Utilizzando il teorema dell'involucro (teorema di Danskin), il gradiente è derivato come $g_{ij} = -y_i y_j \eta^*_i \eta^*_j$, dove $\eta^*$ sono le variabili duali ottimali.

Implementazione Algoritmica

Gli autori propongono AQKA (Acquisizione Attiva del Kernel Quantistico), un algoritmo dispiegabile che opera a round:

1. Riscaldamento (Warm-up): Una piccola frazione del budget ($\eta_w B$) viene spesa in modo uniforme per generare una stima iniziale del kernel $\hat{K}$.
2. Stima della Sensibilità: L'algoritmo risolve il problema KRR (o SVM) su $\hat{K}$ per calcolare i punteggi di sensibilità basati sul gradiente $g_{ij}$.
3. Allocazione Target-Fill: Invece di campionare gli shot da una distribuzione multinomiale (che può lasciare senza risorse le coppie a bassa sensibilità a causa di picchi stocastici), AQKA utilizza un approccio deterministico "target-fill". Calcola il conteggio target degli shot $s^*_{ij}$ e aggiunge la differenza $\max(0, s^*_{ij} - s_{ij})$ a ciascuna coppia.
4. Esplorazione: Una piccola frazione di esplorazione ($\eta_e B$) viene aggiunta in modo uniforme per impedire all'algoritmo di ignorare completamente le coppie che potrebbero diventare importanti a causa di effetti di ordine superiore o rumore di stima.

3. Contributi Chiave

1. Decomposizione Completa dei Regimi

Il paper fornisce una caratterizzazione rigorosa di quando diverse strategie di allocazione sono ottimali:

• AQKA domina nel regime limitato dal budget ($B \lesssim 16 n_{pairs}$) su task KRR a sensibilità sparsa.
• Nyström-QKE (ricostruzione a rango basso) vince ai budget saturi su dati piantati sparsi, dove la struttura a rango basso può essere completamente recuperata.
• I metodi di tipo ShoFaR sono competitivi solo nei regimi di budget estremamente bassi.

2. Teoria di Acquisizione a Livello di Coppia in Forma Chiusa

• Allocazione Ottimale KKT: Derivazione del gradiente in forma chiusa $g_{ij}$ per KRR e SVM sotto rumore di shot.
• Limiti Corretti Consapevoli della Sparsità: Gli autori derivano un limite di Cauchy-Schwarz per il rapporto di riduzione della varianza raggiungibile $\rho$. Correggono la scalatura ingenua $\Theta(m^2/N^2)$ (assumendo che $g$ sia supportata su $S \times S$) in una scalatura più accurata $\Theta(m/N)$ ($\rho \leq 2m/N$ per KRR). Questo riflette il fatto strutturale che anche se il vettore soluzione $\alpha$ è sparso, il vettore di sensibilità $\beta = (K+\lambda I)^{-1}\alpha$ è genericamente denso, il che significa che qualsiasi coppia che tocca l'insieme di supporto ha sensibilità non nulla.
• Limiti di Rimpianto (Regret Bounds): Viene fornito un limite di rimpianto con costante esplicita, che mostra come l'errore converga all'ottimo dell'oracolo all'aumentare del budget di riscaldamento.

3. Algoritmo Target-Fill Dispiegabile

Il paper dimostra che uno schema deterministico target-fill supera il campionamento multinomiale naturale, in particolare nel regime limitato dal budget. Il campionamento multinomiale tende a concentrarsi aggressivamente su poche coppie ad alto punteggio, lasciando senza risorse le altre e amplificando il rumore nell'inversione della matrice; target-fill mantiene un livello minimo di copertura.

4. Prima Adattazione Online Live Multi-Seed su Hardware Quantistico

Gli autori riportano la prima dimostrazione pubblicata di allocazione adattiva degli shot online su dispositivi attuali di classe IBM Heron da 156 qubit.

• IBM Aachen (N=20): +17,0 ± 4,8 punti percentuali rispetto all'allocazione uniforme (significatività 3,5$\sigma$).
• IBM Berlino (N=30): +14,0 ± 8,5 punti percentuali a budget più elevati.

4. Risultati Sperimentali

Ambienti Sintetici e Simulati

• KRR Piantato Sparso: Su dati sintetici con vettori soluzione sparsi, AQKA (target-fill con sensibilità stimata) ottiene +8 fino a +25 punti percentuali rispetto all'allocazione uniforme mentre $N$ scala da 225 a 1000.
• Kernel Quantistici Senza Rumore: I guadagni si trasferiscono alle simulazioni noiseless di mappatura ZZFeatureMap a 4 qubit, mostrando +13 fino a +18 punti rispetto all'uniforme.
• Ablazione di Ricampionamento Hardware: Utilizzando un kernel misurato su IBM Pittsburgh (156 qubit) e ricampionato con rumore di shot, AQKA ottiene +26,3 ± 6,1 punti a $B = n_{pairs}$ e +31,9 ± 7,2 punti a $B = 4n_{pairs}$ rispetto all'uniforme.

Benchmark su Dati Reali

• Cancro al Seno ($\alpha$ Denso): Su un dataset reale dove il vettore soluzione è denso (non sparso), AQKA non domina uniformemente. È competitivo ma mostra prestazioni dipendenti dal regime, evidenziando che il vantaggio del metodo si basa sull'alta eterogeneità della sensibilità a livello di coppia.
• SVM vs KRR: Il paper nota che, sebbene il quadro teorico si estenda alle SVM, la versione plug-in è più fragile a causa dell'instabilità dell'insieme di supporto sotto riscaldamenti rumorosi. In regimi a N piccolo con riscaldamenti rumorosi, AQKA per SVM può performare peggio dell'allocazione uniforme, mentre la versione KRR rimane robusta.

5. Significato e Affermazioni

Il paper afferma di colmare il divario tra l'ottimizzazione teorica del budget di shot e il dispiegamento pratico su hardware NISQ. Il suo significato principale risiede in:

1. Superare l'allocazione uniforme: Dimostrare che un'allocazione degli shot non uniforme e consapevole della sensibilità è critica per l'apprendimento del kernel quantistico a breve termine, specialmente quando i budget sono ristretti.
2. Validazione Hardware: Fornire la prima validazione multi-seed, live-online di una strategia di allocazione adattiva degli shot su hardware quantistico reale, dimostrando che i guadagni teorici sopravvivono al rumore del dispositivo e alla deriva di calibrazione.
3. Consapevolezza del Regime: Stabilire che nessun metodo è universalmente superiore; AQKA è specificamente progettato per il regime limitato dal budget e a sensibilità sparsa, che è la zona operativamente rilevante per l'hardware attuale.

Gli autori sono modesti nelle loro affermazioni, riconoscendo che per problemi a sensibilità densa o budget saturi, altri metodi (come Nyström) o l'allocazione uniforme possono essere preferibili. Identificano inoltre il rumore del plug-in SVM come una limitazione attuale che richiede lavori futuri (ad esempio, acquisizione stabilizzata dal margine).