← Ultimi articoli
⚛️ fisica quantistica

Formally verified harness for Shor's order finding algorithm with O(n2+ϵ)O(n^{2+\epsilon}) gate cost

Questo articolo presenta un harness formalmente verificato che ingerisce policy di progettazione di circuiti ricorsivi da fonti esterne, come agenti AI, per generare automaticamente prove controllate da macchina della correttezza matematica e della scalabilità del costo di porte O(n2+ϵ)O(n^{2+\epsilon}) per l'algoritmo di ricerca dell'ordine di Shor, abilitando così una sfida aperta per la scoperta di circuiti di fattorizzazione quantistica più efficienti con correttezza garantita.

Autore originale: Anirudh Suresh, Joshua M. Courtney, Runzhou Tao, Yudong Cao

Pubblicato 2026-11-17
📖 8 min di lettura🧠 Approfondimento

Autore originale: Anirudh Suresh, Joshua M. Courtney, Runzhou Tao, Yudong Cao

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dall'autore. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Nel panorama dell'informatica moderna, esiste una tensione fondamentale tra la velocità di calcolo e la sicurezza dei segreti. Per decenni, la sicurezza della comunicazione digitale si è basata su un lucchetto matematico: la difficoltà di scomporre un grande numero nei suoi due blocchi costruttivi primi. Mentre i computer classici faticano in questo compito, impiegando migliaia di anni per violare un singolo codice, una macchina teorica costruita sulle leggi della fisica quantistica potrebbe risolverlo in una frazione di secondo. Questa minaccia potenziale ha spinto gli scienziati a perfezionare il progetto di tale macchina, specificamente un algoritmo noto come l'algoritmo di Shor. La sfida non è mai stata se l'algoritmo funzioni in teoria, ma come costruire la macchina fisica per eseguirlo in modo efficiente. Il collo di bottiglia risiede nell'aritmetica: i passaggi specifici richiesti per moltiplicare e dividere i numeri all'interno del sistema quantistico. Per anni, i metodi più efficienti noti per questi passaggi richiedevano un numero di operazioni che cresceva così rapidamente con la dimensione del numero che anche i più potenti computer futuri potrebbero non avere risorse sufficienti per eseguire il compito.

Un team di ricercatori ha introdotto un nuovo framework progettato per navigare in questo complesso spazio di progettazione, offrendo un modo per trovare circuiti più veloci ed efficienti garantendo al contempo che la matematica rimanga corretta. Chiamano la loro creazione ForShor, un imbracatura formalmente verificata che agisce sia come arbitro che come costruttore. Invece di chiedere agli scienziati di costruire manualmente ogni possibile variazione del circuito quantistico — un compito incline all'errore umano e impossibile da controllare accuratamente — hanno costruito un sistema in cui i ricercatori possono sottomettere un insieme di regole, o una "policy", che descrive come la moltiplicazione debba essere scomposta. Il sistema controlla poi automaticamente queste regole rispetto a uno standard matematico rigoroso. Se le regole passano, il sistema genera un programma quantistico completo e verificato e calcola esattamente quanti componenti fisici, noti come gate, sarebbero necessari per eseguirlo. Questo approccio permette una ricerca aperta di design migliori, dove esperti umani e agenti di intelligenza artificiale possono competere per trovare la via più efficiente, il tutto mentre il sistema assicura che il circuito risultante sia matematicamente solido e pronto per la stima delle risorse nel mondo reale.

Il cuore del problema risiede in come l'algoritmo gestisce la moltiplicazione. Per fattorizzare un numero grande, il computer quantistico deve eseguire una massiccia serie di moltiplicazioni. I ricercatori si sono concentrati su una tecnica specifica chiamata moltiplicazione ricorsiva Toom-Cook, che funziona come una forma sofisticata di divisione lunga. Invece di moltiplicare direttamente due grandi numeri, il metodo li divide in pezzi più piccoli, moltiplica quei pezzi e poi ricombina i risultati. L'efficienza di questo processo dipende interamente da come i pezzi vengono divisi e da come i risultati vengono riassemblati. Esistono innumerevoli modi per organizzare questi passaggi, creando un vasto spazio di progettazione. I ricercatori hanno scoperto che, sebbene esista un metodo matematico esatto per trovare la migliore disposizione possibile, esso è computazionalmente impossibile da eseguire per le dimensioni dei numeri utilizzati nella crittografia moderna. Il numero di possibilità è così grande che anche con i supercomputer più veloci, controllare ogni singola opzione richiederebbe più tempo dell'età dell'universo.

Per risolvere questo problema, il team ha creato un sistema che separa il lavoro creativo di progettazione del circuito dal lavoro tedioso di verifica del medesimo. Un partecipante alla loro sfida sottomette una "policy", che è essenzialmente un insieme di istruzioni che dice al computer come dividere i numeri e quali operazioni eseguire in ogni passaggio. Il sistema controlla poi se queste istruzioni seguono un rigoroso insieme di regole logiche. Queste regole assicurano che i passaggi siano reversibili, che nessuna informazione vada perduta e che il risultato finale sia matematicamente equivalente alla moltiplicazione prevista. Se la policy passa questo controllo, il sistema costruisce automaticamente il circuito quantistico completo e calcola il costo delle risorse. Questo processo è formalizzato in modo da non lasciare spazio a dubbi; il sistema dimostra che qualsiasi policy valida produrrà un risultato corretto, indipendentemente da chi ha progettato il design o da quanto sia complesso il design stesso.

I risultati di questo approccio sono significativi. Consentendo la ricerca di design migliori senza il timore di introdurre errori, i ricercatori hanno dimostrato che è possibile ridurre il numero di operazioni richieste per l'algoritmo di Shor. La loro analisi mostra che, con le giuste scelte di design, il numero di operazioni può scalare molto più lentamente di quanto precedentemente ipotizzato, passando da un tasso di crescita cubico a qualcosa di più vicino a uno quadratico. Ciò significa che, per numeri molto grandi, il nuovo metodo potrebbe richiedere molte meno risorse rispetto agli approcci standard. Tuttavia, i ricercatori avvertono con cautela che, sebbene i miglioramenti teorici siano sostanziali, i migliori design attuali richiedono ancora un numero di componenti fisici che è ben oltre ciò che la tecnologia odierna può fornire. Per un numero grande quanto quelli utilizzati nell'attuale crittografia, il sistema stima che il design più efficiente noto richiederebbe comunque oltre un trilione di operazioni specifiche, note come T-gate.

Il progetto evidenzia anche un nuovo modo di fare scienza nell'era dell'intelligenza artificiale. Il framework è progettato come una sfida aperta, invitando ricercatori umani e agenti di IA a sottomettere i propri design. Il sistema funge da giudice neutrale, accettando qualsiasi sottomissione che soddisfi i criteri matematici e rifiutando quelle che non li soddisfano. Questo crea un ambiente sicuro per l'innovazione, dove il rischio di un design difettoso è eliminato dalla verifica controllata dalla macchina. I ricercatori hanno scoperto che, anche all'interno di un set ristretto di scelte di progettazione, trovare la soluzione ottimale è incredibilmente difficile. Hanno testato il loro sistema con un esempio specifico riguardante un numero di 2048 bit, una dimensione comunemente usata nella crittografia. Il sistema ha confermato che, sebbene esista una soluzione ottimale esatta in teoria, trovarla tramite la forza bruta è impossibile. Invece, il sistema permette ricerche euristiche, dove agenti intelligenti possono esplorare lo spazio di progettazione e proporre soluzioni migliori che vengono poi istantaneamente verificate.

Una delle scoperte chiave è che l'efficienza dell'algoritmo dipende fortemente dalla dimensione del numero da fattorizzare. I ricercatori hanno scoperto che il modo migliore per dividere i numeri cambia man mano che i numeri diventano più grandi. Un design che funziona bene per un numero piccolo potrebbe essere inefficiente per uno più grande. Il loro sistema può gestire questo aspetto permettendo diverse strategie di divisione in diverse fasi del calcolo. Questa flessibilità è cruciale per spingere i limiti di ciò che è possibile. Il team ha confrontato i propri risultati con i metodi precedenti e ha scoperto che il loro approccio offre un chiaro vantaggio in termini di numero di operazioni richieste, ma solo per numeri significativamente più grandi di quelli attualmente in uso. Per i numeri standard a 2048 bit, il miglioramento è presente ma non ancora sufficiente a rendere il compito fattibile con la tecnologia a breve termine.

Il lavoro mette anche in ponte il divario tra le dimostrazioni matematiche astratte e l'ingegneria pratica. Il sistema prende la descrizione matematica verificata del circuito e la traduce in un formato che può essere utilizzato dagli strumenti software progettati per stimare le risorse fisiche necessarie. Questa traduzione è un passaggio critico, poiché consente ai ricercatori di vedere esattamente quanti qubit, o bit quantistici, e quanti componenti di correzione dell'errore sarebbero necessari per eseguire l'algoritmo su una macchina reale. I ricercatori hanno utilizzato questa pipeline per generare stime dettagliate per vari scenari, confermando che i miglioramenti teorici reggono quando tradotti in conteggi concreti delle risorse. Hanno scoperto che il numero di operazioni cresce in modo prevedibile, seguendo i modelli matematici che hanno dimostrato.

Nonostante i progressi, i ricercatori riconoscono che c'è ancora molto lavoro da fare. Le stime attuali si basano su modelli idealizzati del computer quantistico, e l'hardware del mondo reale introdurrà ulteriori sfide, come il rumore e la necessità di correzione degli errori. Il sistema non tiene ancora conto della disposizione fisica della macchina o del tempo necessario per spostare le informazioni tra le diverse parti del processore. Queste sono le prossime frontiere del settore. Tuttavia, la capacità di verificare formalmente la correttezza dell'algoritmo e contemporaneamente cercare il design più efficiente è un passo avanti importante. Fornisce una solida base su cui costruire futuri miglioramenti, assicurando che ogni nuova idea sia testata contro i più alti standard di rigore matematico.

Il progetto serve come prova di concetto per una nuova era dell'ingegneria del software quantistico. Combinando la verifica formale con la ricerca aperta e automatizzata, i ricercatori hanno creato uno strumento in grado di gestire la complessità degli algoritmi quantistici in un modo che prima era impossibile. Questo approccio non solo accelera la ricerca di algoritmi migliori, ma costruisce anche fiducia nei risultati, poiché ogni affermazione è supportata da una prova controllata dalla macchina. Mentre il campo dell'informatica quantistica continua a evolversi, strumenti come questo saranno essenziali per navigare nel vasto spazio di progettazione e trasformare le possibilità teoriche in realtà pratiche. I ricercatori hanno reso il loro framework disponibile al pubblico, invitando la comunità globale a contribuire alla ricerca del modo più efficiente per fattorizzare grandi numeri, un compito che rimane una delle sfide più importanti del settore.

Sommerso dagli articoli nel tuo campo?

Ricevi digest giornalieri degli articoli più recenti corrispondenti alle tue parole chiave di ricerca — con riassunti tecnici, nella tua lingua.

Prova Digest →