Quantum Spectral Clustering Framework via Compact Circuit Structures

Sintesi Tecnica: Framework di Clustering Spettrale Quantistico tramite Strutture di Circuiti Compatti

Problema
I metodi di apprendimento automatico spettrale, basati sulla teoria dei grafi spettrali, sono strumenti potenti per il clustering e l'apprendimento di varietà (manifold learning). Tuttavia, la loro applicazione pratica è ostacolata dagli elevati costi computazionali. La costruzione di una matrice di kernel (adiacenza) per $M$ campioni richiede tipicamente un tempo di $O(M^2)$, e la risoluzione dell'associato problema degli autovettori costa esattamente $O(M^3)$. Sebbene esistano metodi di approssimazione classica (ad esempio, Nyström, Random Fourier Features, Lanczos), essi richiedono spesso l'accesso esplicito a matrici kernel parziali o complete. Nel contesto dell'apprendimento automatico quantistico, dove le voci del kernel vengono stimate tramite subroutine quantistiche (ad esempio, SWAP test) piuttosto che essere lette direttamente, l'accesso voce per voce diventa proibitivamente costoso, scalando come $O(\epsilon^{-2}M^4)$ per la stima della matrice completa. Gli autori identificano una lacuna nell'esecuzione efficiente del clustering spettrale utilizzando kernel quantistici senza costruire la matrice kernel o stimare le singole voci.

Metodologia
Il paper propone un framework variazionale per il clustering spettrale che evita completamente la costruzione della matrice kernel. Invece, stima le quantità necessarie direttamente attraverso circuiti quantistici compatti tramite forme quadratiche aggregate.

1. Funzione Obiettivo: Gli autori formulano un obiettivo di tipo rapporto di Rayleigh normalizzato derivato dal Laplaciano del grafo simmetrico ($L_{sym}$). L'obiettivo è massimizzare:
   $$J(\alpha) = \frac{\alpha^\dagger A \alpha - \xi \alpha^\dagger D \mathbf{1}\mathbf{1}^\dagger D \alpha}{\alpha^\dagger D \alpha}$$
   dove $A$ è la matrice di adiacenza, $D$ è la matrice di grado, $\mathbf{1}$ è il vettore unitario e $\xi > 0$ è un parametro di penalità. Il numeratore include un termine di penalità progettato per sopprimere l'autovettore banale (il vettore costante), garantendo soluzioni di clustering non banali.

2. Design del Circuito Quantistico: Il framework utilizza tre stimatori quantistici specifici per valutare i termini della funzione obiettivo senza costruire la matrice:

   • $q_a(\alpha)$: Stima la forma quadratica di adiacenza ($\alpha^\dagger A \alpha$).
   • $q_d(\alpha)$: Stima la forma quadratica pesata dal grado ($\alpha^\dagger D \alpha$).
   • $q_p(\alpha)$: Stima il termine di penalità del proiettore ($\alpha^\dagger D \mathbf{1}\mathbf{1}^\dagger D \alpha$).

   Questi stimatori si basano su un'unitaria di embedding dei dati $U_{\phi, D}$ che prepara una sovrapposizione indicizzata di punti dati e uno stato di pesatura addestinabile $|\alpha_\theta\rangle$ su un registro di indici. I circuiti utilizzano subroutine stile SWAP-test per calcolare le fedeltà (similarità) tra stati quantistici.

3. Inferenza (Testing): Per punti dati non visti $\hat{x}$, viene definita una funzione di punteggio basata sulla fase della sovrapposizione tra lo stato di test e lo stato di pesatura addestrato. La fase $\hat{\phi}(\hat{x}, \hat{\alpha})$ viene estratta tramite circuiti di interferenza (misurando i qubit ancilla nelle basi $\sigma_x$ e $\sigma_y$) e utilizzata per assegnare etichette di cluster tramite sogliatura o clustering circolare.

4. Workflow di Addestramento: I parametri dello stato di pesatura $|\alpha_\theta\rangle$ sono ottimizzati utilizzando un ottimizzatore classico (discesa del gradiente) guidato dagli stimatori quantistici. Il gradiente viene calcolato utilizzando la regola del parametro-shift (parameter-shift rule).

Contributi Chiave

• Strutture di Circuiti Compatti: Gli autori presentano una famiglia di circuiti quantistici che stimano direttamente le componenti del rapporto di Rayleigh. Questo approccio evita la costruzione della matrice kernel completa o parziale e la stima delle singole voci del kernel, che rappresentano colli di bottiglia in altri metodi quantistici spettrali.
• Analisi Rigorosa della Complessità di Shot: Un'analisi teorica dimostra che la complessità di campionamento per il termine di penalità ($q_p$) è trattabile. Contrariamente all'intuizione secondo cui la magnitudo minore del termine di penalità richiederebbe un numero di shot esponenzialmente maggiore, gli autori dimostrano, utilizzando disuguaglianze di concentrazione, che il numero di shot richiesto cresce al massimo in modo quasi-polinomiale rispetto alla probabilità di errore. Ciò valida il fatto che lo stimatore della penalità non domina il budget di campionamento complessivo.
• Workflow Unificato di Addestramento-Testing: Il framework fornisce una pipeline completa, dalla ottimizzazione variazionale all'inferenza su dati non visti utilizzando un meccanismo di punteggio basato sulla fase.

Risultati
Gli autori hanno validato il framework utilizzando simulazioni quantistiche senza rumore su dataset canonici:

• Dataset: Il dataset Iris (clustering binario tra Setosa vs. Versicolor/Virginica) e il dataset MNIST (clustering binario delle cifre '0' e '1', ridotto a 4 dimensioni tramite PCA).
• Performance:
  • Iris: Con un circuito relativamente poco profondo (4 strati, 24 parametri), il modello ha raggiunto un'accuratezza media di test del 98,7%. Aumentando gli strati a 6 o più, l'accuratezza si è stabilizzata a $\ge 99,8\%$.
  • MNIST: Una performance affidabile è iniziata a 6 strati, stabilizzandosi a un'accuratezza media del 97,2% per 8+ strati.
• Comportamento a Shot Finiti: Le simulazioni hanno confermato che il termine di penalità si comporta come previsto. La media campionaria del termine di penalità è confluita rapidamente verso lo zero e la varianza si è contratta di conseguenza. Fondamentalmente, il termine di penalità poteva essere stimato in modo affidabile con un numero relativamente piccolo di shot (ad esempio, 256–1024), in linea con l'analisi teorica secondo cui non richiede un budget di shot significativamente maggiore rispetto agli altri termini.

Significatività e Claim
Il paper posiziona questo lavoro come una "prova di concetto" per un framework di clustering spettrale compatibile con circuiti quantistici efficienti per l'hardware e a basso numero di strati. La significatività primaria risiede nel:

1. Evitare i Colli di Bottiglia della Matrice Kernel: Operando su forme quadratiche aggregate, il metodo elude i costi di $O(M^2)$ o $O(M^4)$ associati alla stima voce per voce del kernel in contesti quantistici.
2. Mitigare il Disallineamento di Scala: L'analisi rigorosa mostra che il termine di penalità, spesso fonte di instabilità numerica o di elevati costi di campionamento, può essere stimato efficientemente, rendendo pratico l'obiettivo variazionale.
3. Contesto di Apprendimento Non Supervisionato: Gli autori osservano che, sebbene i metodi kernel quantistici siano studiati ampiamente nell'apprendimento supervisionato, la loro applicazione al clustering spettrale non supervisionato è meno esplorata. Questo lavoro unisce la teoria dei grafi spettrali agli algoritmi quantistici variazionali in questo dominio specifico.

Gli autori rimangono modesti riguardo a claim più ampi, dichiarando esplicitamente di non affrontare se il kernel di fedeltà quantistica fornisca un vantaggio quantistico rispetto ai kernel classici per task generali. L'attenzione è invece focalizzata sul fornire un'implementazione efficiente assumendo che il kernel quantistico sia la misura di similarità scelta. Suggeriscono che lavori futuri potrebbero estendere questo approccio di analisi della penalità ad altri algoritmi variazionali con termini di penalità (ad esempio, problemi QUBO) e investigare ulteriormente le proprietà teoriche delle codifiche quantistiche in contesti non supervisionati.