Approximate simulation of complex quantum circuits using sparse tensors

Sintesi Tecnica: Simulazione Approssimata di Circuiti Quantistici Complessi mediante Tensori Sparsi

Problematica
La simulazione di circuiti quantistici su computer classici è essenziale per definire il confine del vantaggio quantistico verificabile, risolvere problemi di molti corpi quantistici e guidare lo sviluppo dell'hardware. Sebbene i metodi basati su reti tensoriali (ad esempio, Matrix Product States, Density Matrix Renormalization Group) siano diventati lo stato dell'arte per la simulazione di circuiti complessi, essi spesso si affidano a simmetrie sottostanti o a una bassa dimensionalità per raggiungere l'efficienza. Inoltre, la simulazione classica generale è limitata dalla teoria della complessità ($P \neq NP$), che impedisce l'esistenza di simulatori universali in tempo polinomiale. Gli autori identificano la necessità di strumenti di simulazione in grado di approssimare stati quantistici senza richiedere la decomposizione ai valori singolari (SVD), simmetrie sottostanti o bassa dimensionalità, mirando specificamente a circuiti dove le tradizionali reti tensoriali potrebbero incontrare difficoltà.

Metodologia: Truncated Sparse Tensor Simulation (TruSTS)
Il documento introduce TruSTS, un metodo per simulare approssimativamente circuiti quantistici utilizzando tensori a popolamento sparso. L'approccio centrale consiste nel rappresentare uno stato quantistico a $N$ qubit $|\psi\rangle$ come uno stato sparso $|\phi\rangle$, che è una combinazione lineare di $k$ stati base ($k \le 2^N$).

• Struttura Dati: Lo stato sparso è memorizzato utilizzando due array a lunghezza fissa di dimensione $k$:
  1. $x[x_i]$: Un array di coordinate intere che rappresentano le stringhe binarie degli stati base.
  2. $\alpha[\alpha_i]$: Un array di ampiezze di probabilità complesse corrispondenti a tali stati base.
  3. Un puntatore intero nnz traccia il numero di elementi attualmente riempiti.
• Algoritmo di Contrazione Bitwise: Per applicare un gate quantistico (rappresentato da un tensore $\hat{U}$), l'algoritmo impiega una strategia di ordinamento bitwise ispirata alla moltiplicazione di matrici Sparse Compressed Row (CSR):
  1. Viene definito un bitmask per selezionare i qubit accoppiati dal gate.
  2. L'array dello stato viene ordinato in base ai bit "non accoppiati" (il complemento della maschera). Ciò raggruppa gli stati base in sotto-array computazionalmente indipendenti dove il gate agisce in modo identico.
  3. Il gate viene applicato tramite contrazioni di matrici $4\times4$ indipendenti a ciascun sotto-array.
  4. Questo processo può aumentare il numero di termini non nulli (nnz) fino a un fattore di quattro per ogni applicazione del gate.
• Troncamento: Per prevenire la crescita esponenziale di nnz, l'algoritmo tronca lo stato nuovamente alla dimensione $k$ dopo ogni gate. Il documento confronta due strategie di troncamento:
  • Top-k: Mantiene i $k$ termini con le ampiezze di probabilità più grandi.
  • Random-k: Mantiene $k$ termini scelti casualmente.
  • Un fattore di rinormalizzazione $\gamma$ viene applicato a $|\phi\rangle$ per tenere conto della massa di probabilità persa durante il troncamento.

Contributi Chiave e Derivazioni Teoriche
Gli autori derivano le relazioni tra il parametto di rinormalizzazione $\gamma$ e la fedeltà di simulazione $f = |\langle \psi | \phi \rangle|^2$.

• Limiti di Fedeltà: Stabiliscono che per circuiti quantistici casuali, la fedeltà attesa $\bar{f}$ è approssimativamente $\gamma^2$ (la massa di probabilità mantenuta), con una leggera deviazione positiva dovuta ai termini di interferenza.
• Limiti Superiori e Inferiori:
  • Viene derivato un limite inferiore $\bar{f}_{min} \approx 1/2^N$ per il caso in cui lo stato venga troncato a un singolo stato base casuale.
  • Un limite superiore $f_{max}$ viene derivato assumendo che la distribuzione in uscita segua una distribuzione di Porter-Thomas. Questo limite rappresenta la migliore fedeltà possibile se si potesse identificare e mantenere i $k$ bitstring più probabili dopo l'esecuzione del circuito, anziché troncare a metà circuito. Il documento nota che $f_{max} \approx d(1 - \ln d)$, dove $d = k/2^N$ è la frazione di troncamento.

Risultati
Gli autori hanno testato TruSTS su circuiti quantistici casuali composti da unitari a due qubit di tipo Haar-random disposti in layer.

• Fedeltà vs Troncamento: Le simulazioni su $N=24$ qubit mostrano che la fedeltà dello stato approssimato scala approssimativamente con il quadrato del fattore di rinormalizzazione $\gamma^2$. Il troncamento Top-k supera costantemente il troncamento Random-k, concentrando la probabilità nei termini mantenuti.
• Scalabilità del Tempo di Esecuzione:
  • Verso $k$: Il tempo di esecuzione per gate scala linearmente con il numero di termini mantenuti $k$.
  • Verso $N$: Per $k \ll 2^N$, il tempo di esecuzione per gate è approssimativamente costante rispetto al numero di qubit $N$ (testato fino a $N=64$). Ciò indica che l'algoritmo non introduce un overhead dipendente dalle dimensioni dello spazio di Hilbert completo, a condizione che lo stato rimanga sparso.
  • Memoria: Il metodo evita l'allocazione della memoria completa $2^N$, memorizzando solo $k$ termini.
• Confronto con MPS: Un confronto preliminare con gli stati Matrix Product States (MPS) utilizzando la libreria quimb su $N=24$ qubit (5 layer) mostra che, per i parametri testati, l'MPS offre un rapporto tempo di esecuzione-fedeltà più favorevole su la maggior parte dell'intervallo dei dati, mantenendo una fedeltà più elevata a parità di tempi di esecuzione. Tuttavia, TruSTS dimostra un decadimento della fedeltà costante e prevedibile all'aumentare del tempo di esecuzione, raggiungendo un limite inferiore vicino a $f \sim 10^{-8}$.

Significatività e Rivendicazioni
Il documento posiziona TruSTS come uno strumento per estendere le capacità dei simulatori basati su reti tensoriali, in particolare per scenari in cui:

1. La simmetria è assente: Il metodo non dipende da simmetrie sottostanti.
2. Si evita la SVD: Ottiene il troncamento senza il costo computazionale della decomposizione ai valori singolari.
3. Esiste una sparsità intrinseca: È attraente per stati quantistici intrinsecamente sparsi.

Gli autori affermano che TruSTS fornisce un utile compromesso tra fedeltà e tempo di esecuzione, potenzialmente trovando un'applicazione immediata in circuiti dove non è strettamente richiesta un'alta fedeltà. Essi sottolineano che questo lavoro serve come fondamento per la ricerca futura nell'ottimizzazione delle reti tensoriali sparse e nel combinare TruSTS con strategie di ottimizzazione dell'ordine di contrazione delle reti tensoriali per spingere ulteriormente il confine della simulazione classica per sistemi quantistici complessi. Gli autori rimangono modesti, notando che il confronto rigoroso con metodi alternativi e l'investigazione di quantità misurabili (come la fedeltà dell'entropia incrociata) sono aree importanti per il lavoro futuro.