The Signal
Aaronson ritiene corretta la dimostrazione di una congettura quantistica ottenuta con l’IA
Scott Aaronson afferma di ritenere corretta una dimostrazione della congettura di Aaronson-Ambainis annunciata da Physical Superintelligence, sebbene non l’abbia ancora compresa personalmente. Secondo Aaronson, il risultato esclude una classe limitata di possibili accelerazioni quantistiche nella complessità di interrogazione, non la supremazia quantistica in generale né algoritmi come quello di Shor.

La dimostrazione di PSI e la valutazione di Aaronson
Scott Aaronson afferma di ritenere corretta una dimostrazione della congettura di Aaronson-Ambainis annunciata da Physical Superintelligence (PSI), pur precisando di non averla ancora compresa personalmente. In un post dell’8 novembre su Shtetl-Optimized, Aaronson ha riferito che PSI aveva annunciato il risultato verso la fine della settimana precedente. Ha detto che il lavoro è stato guidato da David Turturean e Jim Halverson presso la startup.
PSI ha dichiarato di aver ottenuto la dimostrazione usando un’infrastruttura di ricerca proprietaria su un modello Claude interno. Aaronson ha scritto di non sapere quale ruolo abbia avuto l’infrastruttura rispetto al modello. Ha fornito due ragioni per la sua attuale fiducia: un certificato Lean e il fatto che esperti umani avessero già esaminato e compreso la dimostrazione. «Non ho ancora compreso la dimostrazione, anche se spero di riuscirci», ha scritto.
Aaronson ha anche rimandato i lettori a un’esposizione di Guy Blanc del MIT e di Jordan Docter, Carmen Strassle e Li-Yang Tan di Stanford. L’ha descritta come un utile punto di partenza per chi vuole studiare l’argomentazione più a fondo. Ha affermato che il post sul blog di PSI era scritto con sufficiente chiarezza da non richiedere molte altre spiegazioni da parte sua sull’annuncio.
Che cosa afferma la congettura
La congettura riguarda polinomi di grado d in n variabili booleane che associano gli input a valori compresi tra zero e uno e hanno varianza costante. Prevede che almeno una variabile debba avere un’influenza non inferiore a 1/poly(d). Aaronson e Andris l’hanno formulata nel 2009. Secondo quanto riportato, la dimostrazione annunciata da PSI stabilisce uno specifico limite inferiore di circa 1/d6.
In questo contesto, l’influenza di una variabile misura quanto la modifica di quell’input possa incidere sul valore del polinomio. Aaronson afferma che lui e Andris erano interessati alla congettura anche perché avevano dimostrato che avrebbe implicato l’assenza di un vantaggio superpolinomiale della complessità di interrogazione quantistica rispetto a quella classica per problemi decisionali che funzionano sulla maggior parte degli input booleani. L’implicazione riguarda un particolare contesto in cui si confronta il numero di interrogazioni a un oracolo necessario ai due tipi di algoritmi.
L’argomentazione si basa su un risultato del 1998 di Beals e coautori: se un algoritmo quantistico effettua T interrogazioni a un oracolo, la sua probabilità di accettazione può essere espressa come un polinomio nei bit dell’oracolo, di grado non superiore a 2T. Se la congettura è valida, il ragionamento di Aaronson e Andris usa le variabili influenti di quel polinomio per costruire una simulazione classica. La simulazione interroga ripetutamente le variabili influenti finché il polinomio non diventa quasi costante, permettendole di apprendere la risposta dell’algoritmo con alta probabilità sulla maggior parte degli input, usando un numero di interrogazioni polinomiale in T.
Un’implicazione limitata per la computazione quantistica
Aaronson collega l’implicazione della congettura alla questione se P e BQP possano essere separati rispetto a un oracolo casuale, sollevata da Fortnow e Rogers nel 1998. Sottolinea che il risultato non esclude accelerazioni quantistiche in generale. Esclude invece una potenziale classe di accelerazioni per proprietà con risposta sì o no di un numero esponenziale di bit casuali, che consentirebbero un’esecuzione superpolinomialmente più veloce di qualsiasi algoritmo classico.
Questo limite non riguarda l’algoritmo di fattorizzazione di Shor, scrive Aaronson, perché il suo passaggio interno fondamentale usa un oracolo periodico, altamente non casuale. Aaronson non vede neppure effetti sulla simulazione quantistica in fisica e chimica, che generalmente non dipende da algoritmi basati su oracoli. Cita inoltre un lavoro di Yamakawa e Zhandry che mostra come possano verificarsi accelerazioni quantistiche esponenziali per problemi di ricerca NP rispetto a oracoli casuali. Il resoconto di Aaronson considera quindi la dimostrazione come un risultato relativo a una specifica congettura e a una specifica classe di problemi di interrogazione, non come un verdetto sulla computazione quantistica nel suo complesso.
Un problema aperto da tempo
Aaronson afferma che la congettura è diventata un problema aperto centrale nella complessità di interrogazione quantistica, attirando l’interesse di ricercatori concentrati tanto sulla questione dei polinomi in sé quanto sulle sue implicazioni per la computazione quantistica. I ricercatori avevano dimostrato casi particolari, scrive, ma una dimostrazione dell’intera congettura rimaneva un obiettivo importante. Ricorda anche un tentativo di soluzione fallito, di cui aveva parlato sul suo blog nel 2019.
Descrive la sua reazione all’annuncio come contrastante: soddisfazione per il fatto che la congettura sembri essere vera, stupore per la capacità dell’IA di affrontare problemi aperti, delusione perché gli esseri umani non l’hanno risolta per primi e stanchezza per il ritmo dei nuovi risultati. La sua valutazione resta cauta: ritiene che la dimostrazione sia corretta sulla base del certificato formale e della verifica degli esperti, ma afferma di sperare ancora di comprenderne personalmente l’argomentazione.
Fonte
Notizie correlate
- Una commissione statunitense sul quantistico propone un programma di produzione condivisa
- Quantum Microsystems di Lincoln Laboratory vince il premio R&D 100 Award 2026
- Yonsei installa il più recente processore IBM Quantum Nighthawk nel suo centro di computazione quantistica
- Ricercatori modellano gate quantistici in un elettrone libero soggetto a rinculo
- Fermilab, IBM e NVIDIA progettano una piattaforma quantistica modulare