From Period Finding to Lattice Sampling: Experimental Insights into Shor's and Regev's Factoring Algorithms

Questo articolo presenta un confronto sperimentale tra gli algoritmi di fattorizzazione quantistica di Shor e di Regev su hardware NISQ reale per N=15, analizzando come i loro distinti approcci strutturali alla codifica aritmetica interagiscano con il rumore del dispositivo e le limitazioni di campionamento per informare il benchmarking pratico di strategie di fattorizzazione alternative.

L'essenziale

Il Grande Quadro: Due Modi Diversi per Decifrare un Codice

Immagina di cercare di decifrare un codice segreto (la fattorizzazione di un numero) usando un nuovo tipo di super-computer chiamato Computer Quantistico. Per molto tempo, tutti hanno usato un metodo specifico per farlo, inventato da un matematico di nome Shor. È come la ricetta "standard d'oro" per decifrare il codice.

Tuttavia, gli attuali computer quantistici sono come cucine "rumorose". Sono piccoli, commettono errori e si confondono facilmente. Per questo motivo, gli scienziati stanno cercando ricette alternative che potrebbero funzionare meglio in queste condizioni disordinate. Una di queste nuove ricette è stata inventata da un matematico di nome Regev.

Questo articolo è un esperimento in cui gli autori hanno cucinato entrambe le ricette (quella di Shor e quella di Regev) su veri computer quantistici rumorosi per vedere quale gestisce meglio il "rumore". Non hanno cercato di decifrare un codice enorme e reale (il che richiederebbe anni); hanno invece decifrato un numero minuscolo e facile (15) solo per vedere come si comportavano i due metodi.

Le Due Ricette: Una "Torcia" contro una "Mappa Nebbiosa"

Per capire la differenza, immagina di cercare di trovare un tesoro nascosto in una stanza buia.

1. L'Algoritmo di Shor: La Torcia

• Come funziona: Il metodo di Shor cerca di puntare una torcia molto luminosa e nitida sul tesoro. Concentra tutta la sua energia in uno o due punti specifici (picchi). Se la luce è abbastanza intensa, vedi immediatamente il tesoro.
• Il Problema: In una cucina rumorosa, la torcia sfarfalla. Se la luce diventa troppo debole o tremolante, non riesci più a capire dove sia il tesoro. Il "picco nitido" diventa sfocato e il segnale si perde.
• La Scoperta dell'Articolo: Sul computer IBM (che era leggermente meno rumoroso), la torcia funzionava ancora abbastanza bene. Ma sul computer QMIO (che era più rumoroso), la luce è diventata così sfocata che non riuscivano più a trovare il tesoro.

2. L'Algoritmo di Regev: La Mappa Nebbiosa

• Come funziona: Il metodo di Regev non usa una singola torcia. Invece, traccia un sacco di linee tratteggiate su una mappa. Nessun singolo punto indica direttamente il tesoro, ma se guardi il modello di tutti i punti insieme, essi formano una figura che rivela la posizione. Distribuisce l'informazione su molti punti.
• Il Problema: In una cucina rumorosa, la nebbia si fa più fitta. I punti sulla mappa vengono sparpagliati e mescolati. Poiché l'informazione è distribuita, è più difficile vedere il modello quando il rumore interferisce.
• La Scoperta dell'Articolo: Il metodo di Regev ha creato una distribuzione di punti più "piatta". Sul computer QMIO, che era rumoroso, i punti si sono così sparpagliati che il modello è scomparso completamente.

L'Esperimento: Cosa è Successo?

I ricercatori hanno eseguito entrambe le "ricette" su due diversi computer quantistici (IBM e QMIO) e le hanno confrontate con una simulazione perfetta e priva di rumore.

• Il Mondo "Ideale": In una simulazione perfetta, il metodo di Shor mostrava alcuni picchi molto alti e nitidi (la torcia). Il metodo di Regev mostrava alcuni punti leggermente più alti sparsi in un modello (la mappa). Entrambi funzionavano perfettamente.
• Il Mondo "Reale" (IBM):
  • Shor: I picchi sono diventati un po' più larghi e bassi, ma potevi ancora vederli. La "torcia" era tremolante ma visibile.
  • Regev: I punti sono diventati più sparpagliati, ma alcuni erano ancora leggermente più alti degli altri. La "mappa" era nebbiosa, ma il modello era ancora debolmente presente.
• Il Mondo "Reale" (QMIO - La Macchina più Rumorosa):
  • Shor: I picchi si sono appiattiti completamente. La torcia si è spenta. Il computer non riusciva più a distinguere il segnale dal rumore.
  • Regev: I punti sono diventati una nuvola uniforme. Il modello è svanito del tutto. La "mappa" era così nebbiosa da sembrare semplice rumore statico.

La Conclusione Chiave

L'articolo conclude che nessuno dei due metodi è chiaramente "migliore" in questo momento per queste piccole macchine rumorose.

• Il metodo di Shor è come uno strumento di alta precision: funziona benissimo se l'ambiente è pulito, ma si rompe facilmente se c'è anche solo un po' di sporco (rumore).
• Il metodo di Regev è come una rete distribuita: utilizza circuiti meno profondi (meno passaggi complessi), il che sembra un bene, ma poiché distribuisce la sua informazione, il rumore rimescola il modello con la stessa efficacia con cui rimescola la torcia.

In sintamente:
Gli autori hanno scoperto che il modo in cui questi algoritmi memorizzano l'informazione è fondamentalmente diverso. Shor "concentra" l'informazione (come un laser), mentre Regev la "distribuisce" (come uno spray). Sui computer rumorosi di oggi, entrambe le strategie faticano, ma falliscono in modi diversi. Shor perde la sua messa a fuoco nitida, mentre Regev perde il suo modello geometrico.

Questo studio non dice che possiamo rompere i codici bancari reali oggi stesso. Invece, ci dice che mentre costruiamoamo computer quantistici migliori, dobbiamo capire come questi diversi algoritmi reagiscono al rumore, in modo da poter scegliere quello giusto per la macchina giusta.

Sommario tecnico

Sintesi Tecnica: Dalla Ricerca del Periodo al Campionamento di Reticoli

Enunciato del Problema
Sebbene l'algoritmo di Shor risolva teoricamente la fattorizzazione degli interi in tempo polinomiale, la sua implementazione pratica sull'attuale hardware Noisy Intermediate-Scale Quantum (NISQ) è severamente limitata dalla profondità del circuito, dagli errori delle porte e dalla decoerenza. Queste limitazioni hanno stimolato l'interesse per algoritmi di fattorizzazione alternativi, come l'algoritmo di Regev, che riformula il problema come un compito di campionamento di reticoli ad alta dimensionalità piuttosto che come un problema di ricerca del periodo monodimensionale. Tuttavia, le analisi sperimentali esistenti spesso mancano di confronti sistematici tra più backend sotto condizioni strettamente controllate per comprendere come queste distinte strutture algoritmiche interagiscano con il rumore reale dell'hardware. Questo studio affronta tale lacuna confrontando sperimentalmente gli algoritmi di Shor e di Regev su hardware quantistico reale per caratterizzare la loro relativa robustezza e i loro modi di fallimento.

Metodologia
Gli autori hanno condotto uno studio sperimentale controllato utilizzando l'istanza di benchmark $N = 15$. Entrambi gli algoritmi sono stati implementati utilizzando Qiskit ed eseguiti su due backend quantistici distinti: il computer quantistico QMIO presso il Centro de Supercomputación de Galicia (CESGA) e un processore quantistico aperto di IBM (ibm_torino). Le simulazioni ideali (senza rumore) sono servite come linea di base di riferimento.

• Configurazione dell'Algoritmo:
  • Algoritmo di Shor: Utilizzato la base $a=2$ con un registro di controllo di $k=3$ qubit per trovare l'ordine $r=4$. Il circuito ha utilizzato costruzioni di esponenziazione modulare specializzate e poco profonde basate su permutazioni anziché su aritmetica generica per minimizzare la profondità.
  • Algoritmo di Regev: Configurato come un'istanza bidimensionale ($d=2$) con basi $a_1=4, a_2=49$. Ha impiegato una sovrapposizione gaussiana su $\mathbb{Z}^d$ seguita da un campionamento di Fourier per approssimare i vettori nel reticolo duale.
• Compilazione ed Esecuzione: I circuiti sono stati trasposti utilizzando Qiskit con parametri regolati per i set di porte native e la connettività di ciascun backend. Tutte le esecuzioni sull'hardware hanno utilizzato 4.096 shot.
• Metriche di Valutazione: Per quantificare l'impatto del rumore senza fare affidamento sulla completa ricostruzione classica per ogni esecuzione, gli autori hanno introdotto metriche basate sulla distribuzione:
  • Entropia di Shannon ($H(p)$): Misura la dispersione della distribuzione di probabilità.
  • Dimensione del Supporto Effettivo ($N_{eff}$): Stima il numero di esiti che contribuiscono significativamente alla distribuzione.
  • Massa Top-K ($M_4$): La frazione della probabilità totale contenuta nei quattro esiti più frequenti.

Contributi Chiave

1. Benchmark Sperimentale Controllato: Il documento fornisce un confronto diretto e a basso livello degli algoritmi di Shor e di Regev sullo stesso problema di istanza ($N=15$) attraverso molteplici piattaforme hardware e simulazioni ideali.
2. Valutazione Multi-Backend: I risultati sono riportati sia per i dispositivi IBM che per i dispositivi QMIO, offrendo intuizioni su come diverse architetture hardware influenzino le prestazioni algoritmiche.
3. Interpretazione della Codifica dell'Informazione: Lo studio interpreta i risultati sperimentali attraverso la lente della "concentrazione dell'informazione" (Shor) rispetto alla "distribuzione dell'informazione" (Regev). Dimostra come queste differenze strutturali portino a degradazioni indotte dal rumore qualitativamente distinte negli istogrammi di misura.
4. Riproducibilità: Gli autori riportano i parametri algoritmici specifici e le pipeline di compilazione utilizzati per generare le distribuzioni sperimentali.

Risultati
I dati sperimentali rivelano distinti modi di fallimento per i due algoritmi sotto i vincoli NISQ:

• Algoritmo di Shor (Concentrazione dell'Informazione):

  • Nelle simulazioni ideali, la massa di probabilità è altamente concentrata su un piccolo numero di picchi spettrali (bassa entropia, $N_{eff} \approx 4$, $M_4 = 1.0$).
  • Su hardware IBM, la distribuzione si allarga ma mantiene picchi dominanti ($M_4 = 0.921$), permettendo un recupero parziale dell'ordine.
  • Sul dispositivo QMIO, più rumoroso, i picchi spettrali sono significativamente appiattiti e oscurati ($M_4 = 0.564$, $N_{eff} \approx 7.8$), portando a una perdita della struttura periodica necessaria per la ricostruzione classica.
  • Osservazione: L'algoritmo di Shor è altamente sensibile agli errori di fase; una volta che i picchi netti vengono allargati dal rumore, l'algoritmo non fornisce più informazioni utili.

• Algoritmo di Regev (Distribuzione dell'Informazione):

  • Nelle simulazioni ideali, la distribuzione è intrinsecamente più dispersa rispetto a quella di Shor, ma mostra comunque un sottoinsieme di vettori dominanti coerenti con il reticolo duale ($N_{eff} \approx 2.34$, $M_4 = 0.944$).
  • Su hardware IBM, la distribuzione diventa più diffusa ($M_4 = 0.645$), tuttavia un sottoinsieme di esiti rimane abbastanza dominante da poter potenzialmente supportare la riduzione del reticolo.
  • Su QMIO, il segnale geometrico è fortemente diluito ($M_4 = 0.29$, $N_{eff} \approx 15.8$), con la massa di probabilità che si diffonde uniformemente su molti vettori, oscurando efficacementamente la struttura del reticolo.
  • Osservazione: L'algoritmo di Regev si basa su un bias statistico attraverso molteplici campioni correlati. Sebbene utilizzi circuiti più superficiali (la Tabella 2 mostra che la profondità compilata di Regev è inferiore a quella di Shor su entrambe le piattaforme), la fase di campionamento multidimensionale introduce una sensibilità al rumore che causa una rapida dispersione del segnale geometrico.

• Profondità del Circuito vs. Robustezza: Nonostante l'algoritmo di Regev abbia una profondità di circuito compilato più superficiale (ad esempio, 147 contro 210 su IBM), questa riduzione non si è tradotta in una maggiore robustezza sull'attuale hardware. Le distribuzioni di misura per Regev si sono disperse più rapidamente sotto l'effetto del rumore rispetto a quelle di Shor.

Significatività e Rivendicazioni
Il documento sostiene con modestia che nessuno dei due algoritmi dimostra un vantaggio pratico rispetto all'altro nel regime di piccolo $N$ ($N=15$) sugli attuali dispositivi NISQ. Inveve, lo studio evidenzia un compromesso fondamentale:

• L'algoritmo di Shor beneficia di output altamente strutturati e concentrati quando il rumore è basso, ma fallisce catastroficamente quando la coerenza di fase viene persa.
• L'algoritmo di Regev distribuisce l'informazione in uno spazio a dimensionalità superiore, il che potrebbe offrire proprietà di scalabilità diverse per problemi più grandi, ma attualmente soffre di una maggiore sensibilità al rumore nel campionamento multidimensionale.

Gli autori concludono che questi risultati sottolineano il valore del benchmarking sperimentale per comprendere le implicazioni pratiche delle scelte di progettazione algoritmica. Essi enfatizzano che le relazioni asintotiche nell'ambito fault-tolerant non garantiscono comportamenti simili sull'hardware NISQ, dove la specifica codifica dell'informazione aritmetica (concentrazione vs. distribuzione) determina come il rumore si manifesti e come gli algoritmi falliscano. Si propone come lavoro futuro estendere questi benchmark a un $N$ più grande ed esplorare strategie di mitigazione dell'errore mirate a questi specifici compromessi.