An efficient Pauli decomposition algorithm for structured matrices

Sintesi Tecnica: Un Algoritmo Efficiente per la Decomposizione di Pauli per Matrici Strutturate

Definizione del Problema
La decomposizione di matrici classiche $2^n \times 2^n$ in combinazioni lineari di stringhe di Pauli è un collo di bottiglia critico per le implementazioni end-to-end di algoritmi quantistici nel breve termine, in particolare nella chimica, nell'apprendimento automatico e nella finanza. Molti algoritmi, come l'Algoritmo Quantistico Variazionale (VQE) e i risolutori di algebra lineare, assumono che i dati di input siano forniti come una Combinazione Lineare di Unitari (LCU) di stringhe di Pauli. Tuttavia, per matrici generiche classiche, tale decomposizione non è nota a priori.

Gli algoritmi esistenti per matrici dense e generiche scalano esponenzialmente con il numero di qubit $n$. L'approccio più diretto richiede un tempo di $O(32^n)$, mentre il miglior metodo noto attualmente (ad esempio in PennyLane) scala come $O(n4^n)$. Questo costo esponenziale deriva dal fatto che, nel caso peggiore, una matrice ha supporto su tutte le $4^n$ componenti della base di Pauli, richiedendo il recupero di tutti i coefficienti.

Questo articolo affronta una versione del problema della decomposizione di Pauli basata su una promessa (promise version). Si assume che la matrice di input $M$ sia garantita avere supporto solo su $k = \text{poly}(n)$ stringhe di Pauli. Inoltre, la matrice viene accessata tramite un modello di query sparsa classica, in cui un algoritmo può recuperare le voci non nulle di una specifica riga o colonna senza costruire l'intera matrice $2^n \times 2^n$ in memoria. L'obiettivo è recuperare la decomposizione di Pauli esatta (l'insieme delle stringhe di Pauli e i relativi coefficienti) con alta probabilità utilizzando risorse polinomiali in $n$, $k$ e $\log(1/\delta)$.

Metodologia
Gli autori propongono un algoritmo classico randomizzato che sfrutta la sparsità promessa ($k$) e la struttura delle stringhe di Pauli in forma simpatica binaria. L'algoritmo decompone il problema in tre fasi principali:

1. Scoperta delle Parti Attive di Pauli-X ($x$):
   Utilizzando il Lemma 1, che mette in relazione l'indice di riga $v$, l'indice di colonna $u$ e la parte Pauli-X $x$ tramite $x = u \oplus v$, l'algoritmo interroga righe casuali della matrice. Raccogliendo gli indici di colonna delle voci non nulle e calcolando l'XOR con gli indici di riga, l'algoritmo identifica l'insieme $X$ delle diverse stringhe di bit $x$ presenti nella decomposizione. Questo passaggio si basa sul principio di incertezza booleano (Fatto 1) per garantire che le query casuali rivelino le stringhe $x$ attive con alta probabilità.

2. Decodifica delle Stringhe $x$ Univoche:
   Per ogni $x$ scoperto, l'algoritmo verifica se è "univoco" (ovvero associato a esattamente una stringa di Pauli, tale che $p_x = 1$). Se univoco, la funzione di query $b_x(u) = M_{x \oplus u, u}$ si riduce a un singolo carattere di Walsh $\beta_x(z)(-1)^{z \cdot u}$. L'algoritmo recupera la parte Pauli-Z $z$ associata e il coefficiente $\beta$ valutando $b_x$ al vettore zero e ai vettori della base standard. Un passaggio di certificazione utilizzando input casuali verifica che la soluzione candidata non sia un caso degenero che coincida semplicemente con i punti interrogati.

3. Decodifica delle Stringhe $x$ Degeneri:
   Se un $x$ è "degenero" (associato a $p_x \geq 2$ stringhe di Pauli), il problema si riduce al recupero di uno spettro di Walsh-Hadamard sparso. L'algoritmo impiega una tecnica di folding randomizzato:

   • Mappa gli indici spettrali di $n$ bit ($z$) in contenitori (bins) di $m$ bit utilizzando una matrice binaria casuale $R$, dove $m \ll n$.
   • Questo "folding" isola le singole stringhe $z$ in "contenitori singleton" con alta probabilità.
   • Per un contenitore singleton, l'algoritmo utilizza query traslate per determinare i bit della stringa $z$ e il suo coefficiente.
   • I termini recuperati vengono sottratti dalla funzione residua e il processo si ripete fino a quando non vengono trovati tutti i termini per quell' $x$.
   • Una verifica randomizzata finale assicura che non siano stati tralasciati termini.

Contributi Chiave

• Design dell'Algoritmo: Il documento presenta un algoritmo classico randomizzato (Algoritmo 1) che risolve il problema della decomposizione di Pauli sotto la promessa di $k$-sparsità e accesso tramite query sparsa.
• Miglioramento della Complessità: A differenza dei metodi esistenti che scalano esponenzialmente in $n$, l'algoritmo proposto raggiunge una complessità di query e di runtime che è polinomiale in $n$, $k$ e $\log(1/\delta)$.
• Garanzie Teoriche: L'algoritmo ha successo con una probabilità almeno di $1-\delta$ per qualsiasi $\delta \in (0, 1)$ scelto dall'utente. Gli autori forniscono limiti rigorosi sulla probabilità di fallimento per ogni fase (scoperta, decodifica univoca e decodifica degenera).
• Tecniche di Walsh-Hadamard Sparse: Il lavoro adatta le tecniche di recupero sparso dal cubo booleano (specificamente la decodifica Walsh-Hadamard sparsa) al contesto della decomposizione di Pauli, utilizzando il folding randomizzato e il recupero dei bit tramite traslazione (shift-based bit recovery).

Risultati

• Benchmark Numerici: Gli autori hanno testato l'algoritmo su istanze casuali per $n = 2$ a $30$ con $k = 2^n$.
  • Per $n$ piccoli ($n < 10$), l'overhead dell'algoritmo randomizzato lo rende più lento della routine PauliDecompose di PennyLane.
  • Si osserva un punto di incrocio intorno a $n=10$. Per $n > 10$, il proposto algoritmo supera significativamente il baseline a tempo esponenziale.
  • Il tempo di esecuzione e il numero di query osservati scalano polinomialmente con $n$, in linea con i limiti teorici.
  • In tutte le prove eseguite, l'algoritmo ha recuperato con successo l'intera decomposizione senza fallimenti.
• Scalabilità: L'algoritmo ha gestito con successo istanze fino a $n=30$, un regime in cui la costruzione dell'intera matrice o l'esecuzione di algoritmi di decomposizione densi diventa computazionalmente intrattabile.

Significato e Rivendicazioni
L'articolo sostiene che, sebbene trovare la decomposizione di Pauli sia esponenzialmente difficile per matrici generiche, essa diventa efficientemente risolvibile per matrici note per essere sparse nella base di Pauli. Questo regime è altamente rilevante per gli algoritmi quantistici nel breve termine che operano su dati classici strutturati.

Gli autori sottolineano che il loro algoritmo è progettato specificamente per il problema della promessa dove $k = \text{poly}(n)$. Non pretendono di risolvere il caso denso generale. Il significato risiede nel rendere efficiente il pre-processing classico per algoritmi quantistici che richiedono decomposizioni di Pauli, potenzialmente rimuovendo un importante collo di bottiglia nei flussi di lavoro quantistici end-to-end. Il lavoro evidenzia inoltre contesti applicativi specifici, come matrici definite da regole classiche succinte o dati detenuti da server non fidati dove è disponibile solo l'accesso tramite query.

Il documento si conclude con modestia, osservando che i limiti superiori derivati potrebbero essere lassi e che lavori futuri potrebbero esplorare limiti più stretti, limiti inferiori ed estensioni ad matrici approssimativamente sparse.