Resource-Efficient Digitized Adiabatic Quantum Factorization

Sintesi Tecnica: Fattorizzazione Quantistica Adiabatica a Risorse Efficienti

Enunciato del Problema
Il documento affronta la sfida di implementare una fattorizzazione quantistica adiabatica efficiente su computer quantistici digitalizzati (gate-based). Gli approcci standard, come il metodo proposto da Peng et al. [1], formulano la fattorizzazione di interi come una ricerca dello stato fondamentale di un Hamiltoniano di problema derivato da una funzione di Ottimizzazione Binaria Non Vincolata Polinomiale (PUBO). Questa formulazione genera un Hamiltoniano contenente termini di interazione non locali a tre e quattro qubit ($Z^3$ e $Z^4$). Sui dispositivi digitalizzati, queste interazioni di ordine superiore richiedono la decomposizione in molteplici gate a due qubit nativi (ad esempio, CNOT), portando a circuiti profondi con un elevato numero di gate. Tale complessità limita severamente la fedeltà e la scalabilità dell'algoritmo, con probabilità di successo che diminuiscono drasticamente per numeri superiori a 91, anche impiegando tecniche di apprendimento automatico.

Metodologia
Gli autori propongono un nuovo algoritmo adiabatico digitalizzato che riformula il problema della fattorizzazione utilizzando un framework di Ottimizzazione Binaria Non Vincolata Quadratica (QUBO). Il nucleo del cambiamento metodologico risiede in due modifiche chiave:

1. Codifica del Sottospazio del Kernel: Invece di codificare la soluzione come lo stato fondamentale (minimo di energia zero) di una funzione al quadrato $F^2$, gli autori definiscono l'Hamiltoniano del problema $\hat{H}_{LP}$ come la funzione lineare $F(N, \hat{p}', \hat{q}')$ stessa. In questa formulazione, la soluzione corrisponde allo stato autovettore a energia zero (il sottospazio del kernel) dell'Hamiltoniano, che è uno stato eccitato rispetto allo spettro globale, piuttosto che lo stato fondamentale.
2. Formulazione QUBO: Utilizzando la funzione lineare, l'Hamiltoniano risultante contiene solo interazioni a due corpi, classificando il problema come un problema QUBO. Ciò elimina la necessità delle riduzioni polinomiali NP-hard e delle variabili ausiliarie tipicamente richieste per mappare i problemi PUBO in QUBO.

L'algoritmo è implementato utilizzando un Algoritmo Quantistico Variazionale (specificamente QAOA). Il protocollo inizializza il sistema in uno stato di sovrapposizione uniforme (specificamente $|+\rangle|-\rangle\dots$ per allinearsi al null-subspace di $\hat{H}_{LP}$) e lo evolve utilizzando unitari alternati derivati dall'Hamiltoniano di costo ($\hat{H}_{LP}$) e dall'Hamiltoniano di mixing ($\hat{H}_M$). La funzione di costo minimizzata dagli ottimizzatori classici è definita come il valore atteso del valore assoluto dell'Hamiltoniano, $C_{LP} = \langle |\hat{H}_{LP}| \rangle$, per garantire la convergenza alla soluzione a autovalore zero.

Contributi Chiave

• Semplificazione del Circuito: L'approccio QUBO proposto riduce l'Hamiltoniano del problema a interazioni a due corpi. Ciò elimina la necessità di decomporre complessi gate multi-qubit, riducendo significativamente la profondità del circuito.
• Nuova Strategia di Codifica: Il documento dimostra che la fattorizzazione adiabatica può essere eseguita con successo puntando al sottospazio del kernel (lo stato eccitato a energia zero) invece che allo stato fondamentale, superando i limiti delle formulazioni PUBO.
• Analisi di Robustezza: Gli autori analizzano la densità spettrale degli Hamiltoniani, mostrando che la formulazione QUBO offre una densità di stati più sparsa attorno al sottospazio della soluzione rispetto alla formulazione PUBO, il che aiuta a evitare minimi locali e barren plateaus durante l'ottimizzazione.

Risultati
Gli autori hanno testato il loro algoritmo basato su QUBO rispetto all'approccio PUBO standard per la fattorizzazione di interi fino a 8 bit (specificamente $N=25, 119, 143$).

• Complessità dei Gate: Per un singolo layer del circuito QAOA, l'approccio QUBO richiede significativamente meno gate CNOT. Ad esempio, la fattorizzazione di $N=25$ richiede 8 CNOT per layer per il metodo QUBO, rispetto ai 34 CNOT del metodo PUBO (dopo la decomposizione dei gate a 3 e 4 qubit).
• Fedeltà e Confidenza: L'algoritmo QUBO dimostra una fedeltà sensibilmente superiore nell'identificare i fattori corretti. Per numeri più grandi come $N=119$ e $N=143$, l'approccio PUBO fallisce nel concentrare l'ampiezza di probabilità sulla soluzione corretta, risultando in punteggi di confidenza bassi e alta entropia di Shannon. Al contrario, l'approccio QUBO popola con successo gli stati della soluzione corretta.
• Convergenza della Funzione di Costo: L'algoritmo QUBO raggiunge una riduzione della funzione di costo più profonda (fino a 3 ordini di grandezza per $N=143$) rispetto all'approccio PUBO (fino a 2 ordini di grandezza), indicando un'ottimizzazione più efficace.
• Analisi Spettrale: L'analisi degli spettri energetici rivela che l'Hamiltoniano PUBO ha un'alta densità di stati vicino alla soluzione, creando un paesaggio "piatto" che ostacola gli ottimizzatori classici. L'Hamiltoniano QUBO presenta uno spettro più ampiamente distribuito con gap energetici maggiori vicino al sottospazio del kernel, facilitando la preparazione dello stato.

Significatività e Rivendicazioni
Il documento afferma che questo lavoro fornisce un percorso a risorse efficienti per la fattorizzazione quantistica adiabatica digitalizzata. La principale significatività risiede nella sostanziale riduzione della complessità del circuito e nel corrispondente aumento della fedeltà algoritmica, rendendo la fattorizzazione di interi più grandi fattibile su dispositivi near-term.

Gli autori sottolineano che, sebbene puntare a uno stato eccitato (il kernel) sia una sfida per gli annealer quantistici a causa della mancanza di protezione dal decoerenza dello stato fondamentale, ciò è vantaggioso per gli annealer quantistici digitalizzati. Nei sistemi gate-based, dove il decoerenza è spesso governata dal decadimento locale del singolo qubit, il ridotto numero di gate del approccio QUBO minimizza il tempo di esecuzione totale e l'esposizione agli errori. I risultati suggeriscono che le formulazioni basate su QUBO possono superare quelle basate su PUBO nell'ottimizzazione QAOA, sfidando la letteratura precedente che assumeva che il PUBO fosse necessario o superiore per determinate strutture di problemi. Il lavoro stimola l'ulteriore esplorazione di protocolli adiabatici digitalizzati per problemi più ampi della teoria dei numeri e Hamiltoniani complessi.