Who can compete with quantum computers? Lecture notes on quantum inspired tensor networks computational techniques

Questa serie di appunti di lezione presenta gli algoritmi delle reti tensoriali, specificamente gli Stati e gli Operatori a Prodotto di Matrici, come strumenti di algebra lineare generale per gestire sistemi esponenzialmente grandi, fornendo dimostrazioni dettagliate e applicazioni che spaziano dalla simulazione quantistica alla risoluzione di equazioni differenziali alle derivate parziali tramite la rappresentazione "quantics".

L'essenziale

L'Idea Centrale: La Biblioteca "Impossibile"

Immaginate di avere una biblioteca con $2^{50}$ libri (ovvero più degli atomi che compongono il vostro corpo). Un computer quantistico è una macchina magica progettata per sfogliare questi libri in modo incredibilmente veloce. Tuttavia, c'è un trucco: non potete leggere l'intera biblioteca contemporaneamente. Potete solo dare un'occhiata a un libro alla volta (un "campione").

Il documento pone una domanda provocatoria: Un computer normale, di vecchia concezione (un supercomputer classico), può fare lo stesso lavoro di questa macchina quantistica magica?

Di solito, la risposta è "No", perché la biblioteca è troppo grande per essere contenuta nella memoria. Ma gli autori sostengono che molte di queste "biblioteche" nascondono un segreto: non sono in realtà un caos casuale. Hanno una struttura semplice e ripetitiva, come un frattale o un modello. Se conoscete il modello, non avete bisogno di memorizzare ogni singolo libro; vi basta memorizzare le istruzioni su come costruirli.

Questo documento vi insegna come trovare questi modelli utilizzando uno strumento chiamato Reti Tensoriali (Tensor Networks).

---

Lo Strumento Principale: L'Approccio "Lego" (Reti Tensoriali)

Gli autori introducono una tecnica matematica chiamata Reti Tensoriali. Pensate a un oggetto 3D gigante e complesso (come una massiccia scultura) che rappresenta uno stato quantistico.

• Il Problema: Descrivere l'intero oggetto in una volta sola richiede un miliardo di numeri.
• La Soluzione (Reti Tensoriali): Invece di descrivere tutto l'insieme, lo scomponete in piccoli e semplici mattoncini Lego.
  • MPS (Matrix Product States): Sono come una lunga catena di mattoncini Lego. Ogni mattoncino si collega al successivo. Se la scultura non è troppo "attorcigliata" (entangled), potete ricostruire l'intero oggetto usando solo pochi piccoli mattoncini.
  • MPO (Matrix Product Operators): Sono come le istruzioni o gli strumenti Lego che vi dicono come modificare la scultura (come una porta in un circuito quantistico).

Il documento dimostra che, per molti problemi, non avete bisogno dell'intera biblioteca da un miliardo di numeri. Vi basta la catena di mattoncini Lego. Questo permette a un computer normale di simulare ciò che fa un computer quantistico, ma molto più velocemente e con meno memoria.

L'Algoritmo di Apprendimento "Magico" (TCI)

Una delle parti più interessanti del documento è un algoritmo chiamato Interpolazione Incrociata Tensoriale (TCI).

• L'Analogia: Immaginate di cercare di indovinare la forma di una catena montuosa nascosta. Non potete vedere tutto l'insieme, ma potete chiedere a una guida: "Qual è l'altezza in questo punto specifico?".
• Come funziona: Inveve di chiedere l'altezza di ogni singolo punto (il che richiederebbe un tempo infinito), il TCI è un detective intelligente. Chiede informazioni su alcuni punti strategici, capisce il modello e poi completa il resto della mappa.
• Il Risultato: Può apprendere la forma di una funzione complessa (come un'onda o una distribuzione di calore) guardando solo una minuscola frazione dei dati. Trasforma un problema a "scatola nera" in un insieme di istruzioni Lego (un MPS) che un computer può gestire facilmente.

Il Trucco "Quantics": Zoom Avanti e Indietro

Il documento introduce un concetto chiamato Quantics per risolvere equazioni fisiche (come la diffusione del calore o il movimento delle onde).

• L'Analogia: Immaginate la mappa di un paese. Di solito, guardate l'intero paese in una volta sola. Ma cosa succederebbe se poteste zoomare su una città, poi su una strada, poi su una casa, tutto nello stesso momento?
• Il Trucco: Gli autori rappresentano i numeri in binario (0 e 1). Il primo bit vi dice se siete sul lato destro o sinisto del paese (scala grande). Il bit successivo vi dice se siete a nord o a sud di quel lato (scala media). L'ultimo bit vi dice se siete a sinistra o a destra della vostra specifica casa (scala minuscola).
• Perché aiuta: Organizzando i dati in questo modo, il computer vede che i cambiamenti su "grande scala" e quelli su "piccola scala" sono spesso indipendenti. Questo rende la "catena Lego" (MPS) molto corta e facile da calcolare.
• Il Risultato: Possono risolvere equazioni su una griglia con trilioni di punti su un normale laptop. Un computer normale andrebbe in crash cercando di contenere tutti quei punti in memoria, ma il trucco Lego dei "Quantics" li comprime in qualcosa di gestibile.

Il Controllo di Realtà sulla "Supremazia Quantistica"

Il documento discute i famosi esperimenti di "Supremazia Quantistica" (dove le aziende sostengono che i loro computer quantistici abbiano fatto qualcosa di impossibile per i computer classici).

• La Visione del Documento: Gli autori sono scettici riguardo all'entusiasmo eccessivo. Sostengono che quegli esperimenti siano stati progettati per creare "rumore casuale" (un caos senza schema). Naturalmente, un computer classico fatica a simulare il rumore casuale!
• Il Punto Chiave: Se il computer quantistico sta facendo qualcosa di utile (come simulare una reazione chimica o un materiale specifico), lo stato possiede solitamente molta struttura. Il documento mostra che i computer classici, usando queste tecniche Lego, possono in realtà simulare molto bene quegli stati quantistici utili.
• Il Verdetto: Un computer quantistico non è una bacchetta magica che risolve tutto. È uno strumento specifico. Se il problema ha una struttura a "basso rango" (modelli Lego semplici), un computer classico può spesso battere quello quantistico.

Riassunto di Ciò che Hanno Fatto

1. Hanno insegnato le basi: Come scomporre enormi problemi matematici in piccoli pezzi connessi (Reti Tensoriali).
2. Hanno mostrato come simulare i computer quantistici: Hanno costruito un computer quantistico "virtuale" su un normale laptop che può gestire centinaia di qubit, a patto che il circuito non sia troppo caotico.
3. Hanno introdotto uno strumento di apprendimento (TCI): Un modo per insegnare a un computer la forma di un problema semplicemente dando un'occhiata a pochi punti dati.
4. Hanno risolto problemi fisici reali: Hanno usato questi strumenti per risolvere equazioni complesse (come il flusso di calore e le equazioni delle onde) su griglie così vaste che normalmente sarebbero impossibili, il tutto su una normale workstation.

Conclusione

Il documento afferma che i computer classici non sono spacciati. Finché il problema ha una struttura sottostante (come la maggior parte dei problemi scientifici utili), possiamo usare le "Reti Tensoriali" per comprimere i dati e risolverli. Non abbiamo sempre bisogno di un computer quantistico per fare il lavoro pesante; a volte, un algoritmo classico intelligente può competere, e persino vincere.

Sommario tecnico

Sintesi Tecnica: "Chi può competere con i computer quantistici? Note di lezione su tecniche computazionali basate su reti tensoriali ispirate al quantum"

Definizione del Problema
Il documento affronta la sfida fondamentale della simulazione di sistemi quantistici e della risoluzione di problemi di algebra lineare ad alta dimensione che scalano esponenzialmente con la dimensione del sistema ($2^N$ per $N$ qubit). Sebbene i computer quantistici siano teoricamente capaci di manipolare questi spazi di stato esponenzialmente grandi, i supercomputer classici non possono memorizzare l'intera funzione d'onda per $N \gtrsim 50$. Tuttavia, gli autori osservano che molti stati fisicamente rilevanti possiedono strutture matematiche interne che permettono una rappresentazione classica efficiente. Il problema centrale è identificare e sfruttare queste strutture — specificamente le proprietà a basso rango (low-rank) — per eseguire moltiplicazioni matrice-vettore, risolvere problemi di autovalori e simulare la dinamica senza dover memorizzare esplicitamente l'intero oggetto esponenziale. Le lezioni mirano a separare gli algoritmi delle reti tensoriali dal loro tradizionale contesto di fisica della materia condensata per presentarli come strumenti generali per l'algebra lineare su matrici e vettori di grandi dimensioni.

Metodologia
Il documento presenta una suite completa di algoritmi basati su Stati a Prodotto di Matrici (MPS) e Operatori a Prodotto di Matrici (MPO). Queste sono rappresentazioni di reti tensoriali che fattorizzano vettori e matrici esponenzialmente grandi in una catena di piccoli tensori locali connessi da indici virtuali (dimensioni di legame o bond dimensions).

1. Emulazione Esatta: Gli autori stabiliscono innanzitutto che i circuiti quantistici sono reti tensoriali. Descrivono strategie di emulazione esatta:

   • Simulatore di Stato Completo: Alloca un vettore di dimensione $2^N$ e applica i gate sequenzialmente. La scala è esponenziale in termini di memoria ($O(2^N)$) ma lineare rispetto al numero di gate.
   • Emulatore MPS Esatto: Rappresenta lo stato come un MPS. Per circuiti con entanglement limitato (ad esempio, gate a vicinanza immediata su stati prodotto), la scala è lineare in $N$ e polinomiale rispetto alla profondità del circuito, a condizione che la dimensione di legame $\chi$ rimanga piccola.

2. Compressione e Approssimazione: Per gestire sistemi più grandi, le lezioni introducono la compressione a basso rango tramite Decomposizione ai Valori Singolari (SVD).

   • Forma Canonica: Una scelta di gauge in cui i tensori sono isometrie, permettendo di leggere direttamente l'entropia di entanglement dai valori singolari di un tensore centrale.
   • TEBD (Time-Evolving Block Decimation): Un algoritmo per circuiti quantistici in cui i gate vengono applicati e lo stato risultante viene troncato tramite SVD per mantenere una dimensione di legame $\chi$ fissa. Ciò introduce un errore controllato, limitato dai valori singolari scartati.
   • DMRG (Density Matrix Renormalization Group): Adattato qui per circuiti quantistici e diagonalizzazione di Hamiltoniane. Ottimizza uno o due tensori alla volta per minimizzare l'energia (per le Hamiltoniane) o massimizzare la fedeltà (per i circuiti), effettuando una scansione (sweep) attraverso il sistema fino alla convergenza.

3. Apprendimento e Costruzione (TCI): Una parte significativa della metodologia è dedicata all'Interpolazione Incrociata Tensoriale (TCI). A differenza dei metodi tradizionali che richiedono l'accesso al tensore completo, la TCI è un algoritmo di apprendimento attivo che costruisce una rappresentazione MPS/MPO interrogando una funzione $F(\sigma)$ in specifici indici.

   • Utilizza la Cross Interpolation (CI) e la decomposizione Rank-Revealing LU parziale (prrLU) per selezionare i "pivot" (righe e colonne) che massimizzano il determinante (principio maxvol), garantendo che le sezioni selezionate catturino l'informazione essenziale della matrice.
   • Ciò consente la conversione di funzioni arbitrarie (ad esempio, integrandi, potenziali) in formati MPS/MPO senza una conoscenza preventiva della loro struttura tensoriale.

4. La Rappresentazione "Quantics": Gli autori introducono uno schema di discretizzazione specifico in cui una variabile continua $x$ viene mappata su una stringa binaria di bit. Questa rappresentazione "quantics" permette di trattare le funzioni di variabili continue come MPS.

   • Forniscono costruzioni analitiche di MPO per operatori differenziali (derivazione, integrazione, Laplaciano), convoluzione e la Trasformata di Fourier Quantistica (QFT).
   • Crucialmente, la QFT è mostrata essere un MPO a basso rango (rango $\chi \approx 15$ per la precisione di macchina), consentendo trasformate di Fourier "superveloci" su griglie con $2^N$ punti.

Contributi Chiave

• Generalizzazione delle Reti Tensoriali: Le lezioni riformulano MPS e MPO non solo come strumenti per la fisica della materia condensata, ma come risolutori di algebra lineare generali per vettori e matrici esponenzialmente grandi.
• Strumentario Algoritmico: Il testo fornisce derivazioni dettagliate, passo dopo passo, per:
  • Campionamento da MPS (campionamento esatto tramite la regola di catena bayesiana).
  • Somma e moltiplicazione di MPS/MPO.
  • Risoluzione di sistemi lineari ($Ax=b$) utilizzando MPS.
  • Costruzione analitica di MPO per operatori differenziali e la QFT.
• TCI come Interfaccia: Il documento posiziona la TCI come il ponte critico che permette di mappare problemi non legati alle reti tensoriali (come le equazioni differenziali alle derivate parziali) nel framework delle reti tensoriali.
• Quantics per le PDE: Gli autori dimostrano come la rappresentazione quantics, combinata con TCI e MPO a basso rango, permetta di risolvere PDE (Poisson, Schrödinger, equazione del calore) su griglie con $2^{30}$ a $2^{40}$ punti utilizzando workstation standard, una scala irraggiungibile per i metodi brute-force.

Risultati
Il documento illustra questi metodi attraverso applicazioni concrete:

• Simulazione di Circuiti Quantistici: I confronti mostrano che per circuiti con basso entanglement (ad esempio, generazione dello stato GHZ), l'emulatore MPS esatto scala come $\sim N^2$, mentre il simulatore di stato completo scala come $\sim N 2^N$.
• Circuiti Casuali e Fedeltà: Le simulazioni di circuiti quantistici casuali (simili agli esperimenti di "supremazia quantistica") mostrano che la fedeltà decade esponenzialmente con la profondità del circuito, controllata dalla dimensione di legame. Ciò suggerisce che anche per $N$ grandi, se il tasso di errore (o la dimensione di legame effettiva) è sufficientemente basso, le reti tensoriali possono simulare il sistema.
• Soluzioni di PDE:
  • Integrazione: La TCI viene utilizzata per calcolare un integrale oscillatorio a 10 dimensioni, convergendo come $\sim 1/N_{eval}^4$, superando significativamente i metodi Monte Carlo che soffrono del problema del segno e scalano come $1/\sqrt{N_{eval}}$.
  • Equazione del Calore: Utilizzando l'MPO della QFT a basso rango, l'equazione del calore viene risolta su una griglia di $2^{30}$ punti (un trilione di punti) in pochi secondi su un laptop.
  • Equazione di Gross-Pitaevskii: Vengono eseguite simulazioni di questa equazione non lineare su un potenziale quasi-periodico con $2^{20}$ punti di griglia per dimensione, dimostrando la capacità di gestire scale di lunghezza vastamente differenti.

Significato e Rivendicazioni
Gli autori sostengono che queste tecniche "ispirate al quantum" competono direttamente con le capacità dei computer quantistici, sfruttando le stesse strutture matematiche sottostanti (basso entanglement/basso rango) che rendono trattabili gli stati quantistici.

• Riformulazione della Supremazia Quantistica: Il documento argomenta che gli esperimenti di "supremazia quantistica" spesso prendono di mira stati casuali e caotici che sono difficili da simulare ma che potrebbero mancare di rilevanza fisica. Al contrario, molti algoritmi quantistici utili e sistemi fisici possiedono una struttura che permette alle reti tensoriali classiche di simularli efficientemente.
• Collo di Bottiglia I/O: Gli autori evidenziano come i computer quantistici affrontino un "collo di bottiglia I/O" (output di soli $N$ bit di informazione probabilistica), mentre le reti tensoriali possono fornire l'intera funzione d'onda o integrali ad alta precisione.
• Prospettive Future: Il documento ipotizza che le reti tensoriali e la TCI giocheranno un ruolo cruciale nel futuro del computing quantistico, fungendo potenzialmente da interfaccia per mappare gli input dei problemi in formati di rete tensoriale che possano poi essere compilati in circuiti quantistici. Gli autori sottolineano che, sebbene le reti tensoriali siano potenti, non sono una panacea; esse dipendono dall'esistenza di una struttura a basso rango, che non è garantita per tutti i problemi.

In sintesi, il documento funge da guida pedagogica e tecnica dimostrando che gli algoritmi classici delle reti tensoriali, in particolare quando integrati con TCI e la rappresentazione quantics, offrono un'alternativa robusta, scalabile e spesso superiore alla simulazione brute-force per una vasta classe di problemi ad alta dimensione, sfidando efficacemente la necessità dell'hardware quantistico per compiti specifici.