Can PCE solve the factorisation problem via optimisation?

Sintesi Tecnica: Il PCE può risolvere il problema della fattorizzazione tramite ottimizzazione?

Enunciato del Problema
La fattorizzazione degli interi, in particolare di numeri semiprimi ($N = p \cdot q$), è un problema fondamentale nella teoria computazionale dei numeri e la base della sicurezza per la crittografia RSA. Sebbene l'algoritmo di Shor offra una soluzione quantistica in tempo polinomiale, l'attuale hardware NISQ (Noisy Intermediate-Scale Quantum) manca del numero di qubit e della coerenza necessari per un'implementazione pratica. Approcci alternativi, come gli algoritoli quantistici variazionali (VQA) che convertono la fattorizzazione in problemi di ottimizzazione binaria, affrontano problemi di scalabilità, richiedendo tipicamente un numero di qubit che scala linearmente con il numero di variabili binarie. Tale scalabilità lineare li rende impraticabili per istanze su larga scala su hardware attuale. Il documento investiga se la Pauli Correlation Encoding (PCE), un framework capace di codificare $m$ variabili binarie utilizzando un numero polinomiale di qubit ($n \ll m$), possa essere adattata per risolvere il problema della fattorizzazione tramite ottimizzazione con risorse limitate.

Metodologia
Lo studio riformula il problema della fattorizzazione come un compito di ottimizzazione binaria e applica la PCE per ridurre i requisiti dei qubit. La metodologia prevede:

1. Strategie di Codifica: Sono stati sviluppati due approcci distinti per mappare i vincoli di fattorizzazione in una funzione di costo:
   • Approccio Base: Codifica direttamente le rappresentazioni binarie dei fattori ignoti $p$ e $q$. La funzione di costo minimizza la distanza di Hamming al quadrato tra l'intero target $N$ e il prodotto candidato $x_p \cdot x_q$, con penalità per evitare soluzioni banali (es. $N \cdot 1$).
   • Approccio Difference of Two Squares (DoTS): Riformula il problema come la ricerca di interi $a$ e $b$ tali che $a^2 \equiv b^2 \pmod N$ (con $a \not\equiv \pm b$). I fattori vengono recuperati tramite $\gcd(a-b, N)$ e $\gcd(a+b, N)$. La funzione di costo combina un termine che impone la congruenza modulare con un termine che verifica la risultante fattorizzazione.
2. Circuito Quantistico: È stato impiegato un ansatz "brickwork" hardware-efficient, composto da strati alternati di rotazioni a singolo qubit ($R_X, R_Y, R_Z$) e porte di entanglement ($R_{XX}, R_{YY}, R_{ZZ}$). L'ordine di compressione PCE $k$ determina la profondità del circuito e il numero di qubit richiesti ($n \approx m/k$).
3. Ottimizzazione: I circuiti quantistici parametrizzati sono stati simulati classicamente utilizzando Qiskit Aer. L'ottimizzazione è stata eseguita utilizzando tre algoritmi privi di gradiente: Differential Evolution (DE), Particle Swarm Optimisation (PSO) e Quantum Delta Particle Swarm Optimisation (QDPSO). È stata utilizzata la funzione segno per approssimare le variabili binarie, evitando la rilassazione iperbolica della tangente per prevenire soluzioni reali infinite.

Contributi Chiave e Risultati

• Riduzione delle Risorse: Lo studio dimostra che la PCE può ridurre drasticamente il numero di qubit necessari per la fattorizzazione. Per le tipiche lunghezze di chiave RSA, i qubit richiesti rimangono in un intervallo "accessibile" per l'hardware attuale o vicino-futuro, e per ordini di compressione $k > 2$, il problema può essere risolto interamente su computer classici tramite emulazione di circuiti quantistici.
• Confronto delle Prestazioni:
  • DoTS vs. Basic: L'approccio DoTS ha superato costantemente l'approccio Basic. La funzione di costo DoTS, catturando la struttura aritmetica della relazione della differenza di due quadrati, ha prodotto tassi di successo più elevati e un panorama di ottimizzazione più favorevole.
  • Sensibilità dell'Ottimizzatore: Differential Evolution (DE) si è rivelato l'ottimizzatore più robusto, raggiungendo fattorizzazioni di successo attraverso varie lunghezze di bit. I metodi basati su swarm (PSO, QDPSO) hanno mostrato tassi di successo significativamente inferiori, suggerendo che il panorama di ottimizzazione sia impegnativo per questi specifici algoritmi.
  • Limiti di Scalabilità: Il metodo ha fattorizzato con successo semiprimi fino a 36 bit utilizzando l'approccio DoTS con $k=4$ e DE. I tassi di successo sono diminuiti per interi superiori a 25–36 bit, indicando limiti intrinseci nelle attuali formulazioni delle funzioni di costo per istanze più grandi.
• Efficienza di Ricerca: L'analisi del numero di valutazioni della funzione obiettivo ha mostrato che l'algoritmo non si affida all'esplorazione brute-force. Il numero di valutazioni è rimasto diversi ordini di grandezza al di sotto della dimensione dello spazio di ricerca combinatorio ($2^n$), indicando un processo di ricerca guidato.

Significatività e Rivendicazioni
Il documento posiziona questo lavoro come un contributo preliminare ed esplorativo piuttosto che una soluzione definitiva o una rivendicazione di vantaggio computazionale rispetto agli algoritmi esistenti.

• Fattibilità: Il risultato principale è che gli algoritmi basati su PCE sono un framework plausibile per studiare la fattorizzazione come problema di ottimizzazione con risorse quantistiche limitate. Offre una prospettiva alternativa ai metodi stabiliti come VQF e QAOA, disaccoppiando il numero di variabili dal numero di qubit.
• Limitazioni: Gli autori dichiarano esplicitamente che le attuali formulazioni non scalano con successo verso dimensioni di interi crittograficamente rilevanti (es. RSA a 2048 bit). Il successo del metodo dipende fortemente dal design della funzione di costo classica e dalla scelta dell'ottimizzatore.
• Direzioni Future: Lo studio suggerisce che la ricerca futura dovrebbe concentrarsi su:
  • Progettare funzioni di costo più informative che catturino meglio la struttura aritmetica della fattorizzazione (potenzialmente incorporando variabili di riporto/carry).
  • Esplorare assunzioni di fattori bilanciati (comuni in RSA) per ridurre il conteggio delle variabili.
  • Investigare strategie di "warm-start" e architetture ansatz alternative.
  • Valutare le prestazioni sotto modelli di rumore realistici.

In conclusione, sebbene il metodo non minacci attualmente la sicurezza RSA, esso stabilisce un framework viabile e a risorse efficienti per investigare la fattorizzazione tramite ottimizzazione ispirata al quantum, giustificando ulteriore ricerca nel design delle funzioni di costo e nei raffinamenti algoritmici.