The Pulse

Un sistema di ricerca di PSI dimostra la congettura di Aaronson-Ambainis

Un sistema di ricerca sviluppato internamente ha trovato una dimostrazione della congettura di Aaronson-Ambainis, che riguarda l’accelerazione quantistica su input casuali, afferma PSI. La dimostrazione mostra che un computer quantistico no

AI.info Team · Scritto con l’IA · verificato · 2026-11-07

Il 6 novembre 2026, PSI ha dichiarato che il suo sistema di ricerca sviluppato internamente aveva trovato una dimostrazione della congettura di Aaronson-Ambainis, irrisolta dal 2008, che riguarda la possibilità che i computer quantistici siano esponenzialmente più veloci su input casuali.

Scott Aaronson e Andris Ambainis hanno formulato la congettura e hanno dimostrato che, se è vera, i computer quantistici sono al massimo polinomialmente più veloci su input casuali. Nel 1994, Peter Shor ha trovato un algoritmo quantistico che fattorizza grandi numeri molto più velocemente di qualsiasi metodo noto per i computer tradizionali.

Il sistema aveva una dimostrazione completa durante il terzo giorno di esecuzione

Il sistema di ricerca sviluppato internamente ha trovato la dimostrazione nel corso di un’esecuzione sulla propria infrastruttura, usando istanze di un modello non pubblico di Anthropic, afferma PSI. Il sistema aveva una dimostrazione completa durante il terzo giorno di esecuzione. Lean, un assistente di dimostrazione in cui un computer verifica ogni passaggio, l’ha accettata.

PSI ha poi messo il sistema al lavoro su problemi aperti correlati. Secondo l’azienda, il sistema ha migliorato il risultato due volte e Lean ha accettato la versione finale. David Turturean, membro dello staff tecnico, ha guidato il lavoro: ha sviluppato il sistema di ricerca, ha definito l’ambito del problema e ha eseguito il sistema, poi ha chiesto al modello tramite prompt di raccogliere i risultati in una prima bozza dell’articolo. Turturean ha revisionato la bozza ed è responsabile della correttezza dell’articolo, afferma PSI. Jim Halverson, consulente, ha verificato la dimostrazione e Phiala Shanahan, consulente, ha commentato la formalizzazione in Lean.

La dimostrazione pone limiti all’accelerazione quantistica su input casuali, afferma PSI

La probabilità che un computer quantistico risponda «sì» dopo T accessi al suo input può essere rappresentata da un polinomio nei bit dell’input di grado al massimo 2T, secondo precedenti lavori di Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca e Ronald de Wolf. La congettura di Aaronson-Ambainis riguarda quanto cambia il polinomio quando un singolo bit cambia valore. La dimostrazione consente a un computer tradizionale di stimare la probabilità di risposta del computer quantistico per tutte le stringhe tranne una piccola frazione, usando un numero di accessi che cresce al massimo come una potenza fissa di T per qualsiasi errore e frazione fissati, afferma PSI.

La dimostrazione mostra che un computer quantistico non può risparmiare un numero esponenziale di accessi nelle domande a risposta sì o no su stringhe casuali, a meno che la stringa non presenti uno schema raro, afferma PSI. La dimostrazione segue un piano di Shachar Lovett e Jiapeng Zhang, sostituendo una disuguaglianza che avevano lasciato come congettura con una nuova disuguaglianza dimostrata nel manoscritto. La dimostrazione abbina le configurazioni degli interruttori usando un determinante. Il Butterfly Lemma di David Reimer fornisce già un abbinamento più debole, afferma PSI; l’abbinamento della dimostrazione limita anche la frequenza con cui le configurazioni abbinate coincidono su ciascun interruttore. La dimostrazione usa anche risultati di altri ricercatori.

I ricercatori di Stanford stanno preparando un’esposizione della dimostrazione di PSI, afferma l’azienda

Nell’agosto 2026, Guy Blanc, Jordan Docter, Carmen Strassle e Li-Yang Tan della Stanford University hanno risolto la previsione della congettura in un caso particolare, dimostrando che non esiste un’accelerazione esponenziale su input casuali per gli algoritmi quantistici che accedono al proprio input in un numero fisso di turni paralleli. Da allora i ricercatori di Stanford hanno letto la dimostrazione di PSI, inviato commenti e stanno scrivendo un’esposizione più breve per esperti, afferma PSI.

«È un risultato enorme. Risolve una congettura vecchia di decenni, con importanti implicazioni per la natura dei problemi che ammettono accelerazioni quantistiche. La dimostrazione attinge a diversi filoni di ricerca nell’analisi delle funzioni booleane e nella combinatoria probabilistica e li estende. Tutto viene riunito in un modo piuttosto magico».

Guy Blanc, Jordan Docter, Carmen Strassle e Li-Yang Tan della Stanford University

Se un polinomio f i cui valori rimangono tra 0 e 1 non è costante, qualche bit i ha influenza Infᵢ(f) ≥ cv⁵ᐟ²/d⁶ ≥ (v/d)⁷, dove v è la varianza, d è il grado e c = 8√15/(125π⁴), circa 0,0025, afferma PSI. Secondo PSI, i limiti precedenti per i polinomi generali decrescono esponenzialmente al crescere del grado, mentre la congettura era già dimostrata per i polinomi con valori soltanto 0 e 1.