Reducing the Complexity of Matrix Multiplication to $O(N^2log_2N)$ by an Asymptotically Optimal Quantum Algorithm

Riassunto Tecnico: Riduzione della Complessità della Moltiplicazione di Matrici a $O(N^2 \log^2 N)$ tramite un Algoritmo Quantistico Asintoticamente Ottimale

1. Il Problema (Problem Statement)

La moltiplicazione di matrici è un'operazione fondamentale nel calcolo classico, cruciale per l'addestramento di modelli di deep learning. Nonostante decenni di ricerca, il limite superiore della complessità classica è ancora superiore al limite teorico inferiore di $O(N^2)$, attestandosi attualmente a circa $O(N^{2.371552})$.

Nel campo del calcolo quantistico, la mancanza di un framework standardizzato per misurare la complessità (query complexity vs gate complexity) ha reso difficile il confronto tra algoritmi. Molti approcci quantistici esistenti (come il Swap Test o l' Hadamard Test) soffrono di un'elevata scalabilità in termini di qubit e porte logiche, rendendoli poco pratici per l'era NISQ (Noisy Intermediate-Scale Quantum).

2. Metodologia (Methodology)

Gli autori propongono un nuovo algoritmo denominato Quantum Kernel-based Matrix Multiplication (QKMM). La metodologia si basa sull'utilizzo dei kernel quantistici per calcolare il modulo del prodotto scalare tra vettori, sfruttando la sovrapposizione e il parallelismo quantistico.

L'algoritmo viene sviluppato attraverso una gerarchia di quattro livelli di complessità crescente:

1. V2V (Vector-to-Vector): Calcola il modulo del prodotto scalare tra due vettori utilizzando l'encoding di ampiezza e misurando la probabilità dello stato fondamentale $|0\rangle^{\otimes n}$.
2. V2M (Vector-to-Matrix): Estensione del V2V che utilizza un registro di indici per moltiplicare una matrice per un vettore in un singolo circuito.
3. M2M (Matrix-to-Matrix): L'algoritmo principale che utilizza due registri di indici per calcolare il prodotto di due matrici $A \times B$ simultaneamente.
4. M-MM (Multi-Matrix Multiplication): Un'estensione che permette di moltiplicare una matrice per più matrici contemporaneamente.

L'approccio utilizza l'amplitude encoding per mappare i dati vettoriali in stati quantistici, riducendo drasticamente il numero di qubit necessari ($3 \log_2 N$).

3. Contributi Chiave (Key Contributions)

• Nuovo Framework di Complessità: Gli autori propongono di utilizzare il numero di porte quantistiche di base come metrica fondamentale per la complessità, fornendo un parametro di confronto diretto e coerente con il calcolo classico.
• Ottimalità Asintotica: Dimostrano matematicamente che la complessità dell'algoritmo è $O(N^2 \log^2 N)$. Attraverso l'analisi del limite per $N \to \infty$, provano che questa complessità si avvicina asintoticamente al limite teorico inferiore di $O(N^2)$, superando i limiti degli algoritmi classici e quantistici precedenti.
• Efficienza delle Risorse: Rispetto ai metodi basati su Swap Test o Hadamard Test, il QKMM riduce significativamente il numero di qubit ausiliari e la profondità del circuito grazie alla capacità di estrarre i termini di correlazione direttamente dallo stato fondamentale.

4. Risultati (Results)

Gli autori hanno condotto simulazioni sia in modelli ideali (noiseless) che in scenari con rumore (noisy) utilizzando la piattaforma Origin Quantum:

• Simulazioni Noiseless: I risultati confermano che il parallelismo quantistico riduce drasticamente il tempo di calcolo all'aumentare della dimensione della matrice $N$. L'efficienza del QKMM cresce in modo marcato rispetto ai benchmark classici e quantistici esistenti.
• Simulazioni Noisy (Modello NISQ):
  • L'algoritmo mostra una forte robustezza per dimensioni ridotte (matrici $2 \times 2$ e $4 \times 4$), mantenendo una fedeltà $> 0.95$.
  • È stato identificato che il rumore delle porte logiche (gate noise) è il fattore limitante principale rispetto alla decoerenza ambientale ($T_1, T_2$) quando si scalano le dimensioni.
  • In ambienti con rumore combinato, la fedeltà decade rapidamente per matrici grandi (es. $8 \times 8$), evidenziando la necessità di tecniche di encoding più efficienti per l'hardware attuale.

5. Significato e Implicazioni (Significance)

Il lavoro ha un impatto profondo su due fronti:

1. Teorico: Stabilisce un nuovo standard per la valutazione degli algoritmi di moltiplicazione di matrici quantistiche, dimostrando che l'ottimalità asintotica è raggiungibile tramite i kernel quantistici.
2. Pratico: Offre una via per accelerare il "Quantum-intensive computing". Poiché la moltiplicazione di matrici è il cuore dell'intelligenza artificiale e del calcolo scientifico, l'algoritmo QKMM rappresenta un passo fondamentale verso l'integrazione del calcolo quantistico nei carichi di lavoro dell'IA del futuro, promettendo un'accelerazione significativa nell'addestramento di modelli massivi.