Prime Number Identification Demonstrated with Quantum Processors Using a New Rescaling-Based Noise Mitigation Technique

Sintesi Tecnica: Identificazione dei Numeri Primi Dimostrata con Processori Quantistici Utilizzando una Nuova Tecnica di Mitigazione del Rumore Basata sul Ricalcolo

Enunciato del Problema
L'identificazione e la classificazione dei numeri primi rimangono sfide fondamentali nella teoria dei numeri, con implicazioni significative per la crittografia e la complessità computazionale. Sebbene gli algoritmi classici abbiano fatto progressi, gli approcci quantistici offrono metodi alternativi codificando le proprietà della teoria dei numeri in osservabili quantistici. Nello specifico, l'algoritmo "Identificazione dei Primi tramite Dinamica di Entanglement" (PIED), precedentemente proposto in lavori teorici, associa la primalità di un intero a firme specifiche nello spettro di Fourier della purezza ridotta (entanglement) di un sistema quantistico bipartito. Tuttavia, il passaggio di questo algoritmo dalla simulazione classica all'hardware reale su dispositivi NISQ (Quantistici a Scala Intermedia Rumorosi) presenta sfide significative a causa del rumore sperimentale, che può oscurare le sottili distinzioni tra numeri primi e composti nei modi di Fourier misurati.

Metodologia
Gli autori hanno implementato l'algoritmo PIED su processori quantistici IBM (in particolare il dispositivo Heron r2 "Aachen") per dimensioni di sistema $d = 4, 8,$ e $16$. Il protocollo prevede:

1. Configurazione del Sistema: Un sistema bipartito $AB$ con sottosistemi identici di dimensione $d$, evoluti sotto un Hamiltoniano diagonale con livelli energetici equidistanti.
2. Preparazione dello Stato: Il sistema viene inizializzato in uno stato di sovrapposizione uniforme (preparato tramite porte Hadamard) ed evolto sotto un operatore unitario derivato dall'Hamiltoniano.
3. Misurazione: La purezza ridotta $\gamma_A(t)$ del sottosistema $A$ viene misurata nel tempo utilizzando il protocollo SWAP test, che richiede due copie identiche del sistema e un qubit ancilla.
4. Estrazione del Segnale: La purezza dipendente dal tempo viene trasformata in Fourier per estrarre i modi $\alpha_n$. Teoricamente, i numeri primi corrispondono a valori minimi di questi modi, mentre i numeri composti producono valori più elevati.

Per affrontare il rumore hardware, gli autori hanno sviluppato e applicato una tecnica di Estrapolazione del Fattore di Correzione (CFE). Questo metodo prevede:

• Calibrazione: Esecuzione di circuiti per un sottoinsieme di dimensioni di sistema ($d=4, 8, 16$) dove i valori analitici ideali dei modi di Fourier sono noti.
• Ottimizzazione: Calcolo di un fattore di ricalcolo globale ottimale $\Lambda_{opt}(d)$ per ciascuna dimensione minimizzando la deviazione tra i dati sperimentali rumorosi e il riferimento analitico.
• Estrapolazione: Adattamento di una forma funzionale ai valori calcolati di $\Lambda_{opt}(d)$ (specificamente $\Lambda_{opt}(d) = \Lambda_0 + \kappa d^\eta$) per prevedere fattori di correzione per altre configurazioni o per validare la tendenza. Ciò consente il ricalcolo dei modi di Fourier rumorosi per mitigare il bias sistematico senza richiedere misurazioni multiple a diversi livelli di rumore per ogni istanza di circuito (come nell'Estrapolazione a Rumore Zero).

Contributi Chiave

1. Implementazione Hardware: La prima dimostrazione dell'algoritmo PIED su hardware quantistico reale, con successo nel passaggio dalla simulazione ai dispositivi NISQ.
2. Strategia di Mitigazione del Rumore (CFE): L'introduzione di una tecnica di mitigazione degli errori basata sul ricalcolo, a basso costo computazionale. A differenza dei metodi tradizionali che richiedono esecuzioni ripetute del circuito a diversi livelli di rumore, la CFE sfrutta il comportamento analitico noto dell'algoritmo su diverse dimensioni di sistema per costruire un fattore di correzione.
3. Limiti Teorici Raffinati: La derivazione di un nuovo limite inferiore analitico, $P_n$, per i modi di Fourier dei numeri composti (specificamente per interi della forma $n=k^2$ dove $k$ è primo). Questo limite fornisce una separazione più stretta tra le firme dei numeri primi e composti rispetto al limite banale precedentemente noto $B_n$. Gli autori hanno identificato rigorosamente che le eccezioni a questo limite si verificano solo per specifici semiprimi che coinvolgono i fattori 2 e 3 entro certi sottointervalli, consentendo un quadro di classificazione più robusto.
4. Stati Iniziali Alternativi: Simulazioni numeriche che esplorano l'uso di stati coerenti di spin come condizioni iniziali. Sebbene la preparazione sia più complessa, questi stati hanno mostrato il potenziale per ridurre il numero di partizioni temporali necessarie per un'integrazione di Fourier accurata rispetto agli stati di sovrapposizione uniforme.

Risultati

• Separazione Primi/Composti: Le implementazioni hardware hanno riprodotto con successo la tendenza teorica in cui i numeri primi corrispondono a valori minimi dei modi di Fourier. L'applicazione del metodo CFE ha migliorato significativamente l'accordo tra i dati sperimentali e le previsioni analitiche, ripristinando efficacemente la separazione tra le firme dei numeri primi e composti che era stata oscurata dal rumore nei dati grezzi.
• Prestazioni della CFE: È stato riscontrato che il fattore di correzione $\Lambda_{opt}(d)$ aumenta monotonicamente con la dimensione $d$, saturando asintoticamente. I dati ricalcolati hanno mostrato un eccellente accordo con il modello funzionale proposto.
• Validazione Teorica: È stato dimostrato che il nuovo limite $P_n$ vale per la maggior parte dei numeri composti. L'analisi ha confermato che solo specifici semiprimi (della forma $2k$ o $3k$) possono produrre valori inferiori a questo limite, rendendo necessarie verifiche di divisibilità specifiche in quelle regioni.
• Stati Coerenti di Spin: Le simulazioni hanno indicato che, sebbene gli stati coerenti di spin siano più difficili da preparare, potrebbero offrire una scalabilità più favorevole per il numero di campioni temporali necessari per l'integrazione di Fourier, riducendo potenzialmente il sovraccarico computazionale.

Significato
Il documento afferma che questi risultati rappresentano un passo verso applicazioni pratiche della teoria dei numeri su dispositivi NISQ. Validando l'algoritmo PIED in condizioni hardware realistiche e dimostrando una strategia di mitigazione del rumore specializzata e a basso sovraccarico (CFE), il lavoro evidenzia il potenziale della combinazione di intuizioni analitiche con implementazioni basate sull'hardware. Gli autori sottolineano che il loro approccio offre una via praticabile per estrarre informazioni strutturate dalla dinamica quantistica rumorosa, suggerendo una maggiore applicabilità ad altri algoritmi quantistici che si basano su firme spettrali di osservabili fisici. Il lavoro non afferma di risolvere la fattorizzazione di interi su larga scala, ma dimostra piuttosto la fattibilità dell'identificazione di firme di numeri primi in sistemi quantistici su piccola scala utilizzando la dinamica di entanglement.