Nel 1994, un matematico scoprì come far fare a un computer quantistico qualcosa che nessun normale computer classico poteva fare. Il lavoro ha rivelato che, in linea di principio, una macchina basata sulle regole della meccanica quantistica potrebbe scomporre efficacemente un gran numero nei suoi fattori primi, un compito così difficile per un computer classico che costituisce la base per gran parte della sicurezza di Internet di oggi.
Seguì un'ondata di ottimismo. Forse, hanno pensato i ricercatori, saremo in grado di inventare algoritmi quantistici in grado di risolvere una vasta gamma di problemi diversi.
Ma il progresso si è bloccato. "E 'stata un po' una traiettoria deludente", ha detto Ryan O'Donnell della Carnegie Mellon University. "Le persone dicevano, 'Questo è fantastico, sono sicuro che avremo tutti i tipi di altri incredibili algoritmi.' No." Gli scienziati hanno scoperto notevoli aumenti di velocità solo per una singola classe ristretta di problemi all'interno di un set standard chiamato NP, il che significa che avevano soluzioni verificabili in modo efficiente, come il factoring.
Questo è stato il caso per quasi tre decenni. Poi ad aprile, i ricercatori inventato un tipo di problema fondamentalmente nuovo che un computer quantistico dovrebbe essere in grado di risolvere esponenzialmente più velocemente di uno classico. Implica il calcolo degli input per un complicato processo matematico, basato esclusivamente sui suoi output confusi. Se il problema sta da solo o è il primo in una nuova frontiera di molti altri deve ancora essere determinato.
"C'è un senso di eccitazione", ha detto Vinod Vaikuntanathan, uno scienziato informatico presso il Massachusetts Institute of Technology. "Molte persone stanno pensando a cos'altro c'è là fuori."
Gli informatici cercano di capire cosa fanno meglio i computer quantistici studiando i modelli matematici che li rappresentano. Spesso immaginano un modello di computer quantistico o classico abbinato a una macchina calcolatrice idealizzata chiamata oracolo. Gli oracoli sono come semplici funzioni matematiche o programmi per computer, che assorbono un input e sputano un output predeterminato. Potrebbero avere un comportamento casuale, emettendo "sì" se l'input rientra in un determinato intervallo casuale (ad esempio, da 12 a 67) e "no" in caso contrario. Oppure potrebbero essere periodici, in modo che un input compreso tra 1 e 10 restituisca "sì", da 11 a 20 produca "no", da 21 a 30 produca di nuovo "sì" e così via.
Diciamo che hai uno di questi oracoli periodici e non conosci il periodo. Tutto quello che puoi fare è dargli numeri e vedere cosa produce. Con questi vincoli, quanto velocemente un computer potrebbe trovare il periodo? Nel 1993, Daniel Simon, allora all'Università di Montreal, scoprì che un algoritmo quantistico poteva calcolare la risposta a un problema strettamente correlato in modo esponenzialmente più veloce di qualsiasi algoritmo classico.
Il risultato ha permesso a Simon di determinare uno dei primi indizi di dove ci si potesse aspettare una drammatica superiorità per i computer quantistici. Ma quando ha presentato il suo articolo a una conferenza importante, è stato respinto. Il documento, tuttavia, ha interessato un giovane membro del comitato del programma della conferenza - Pietro Shore, che all'epoca era ai Bell Laboratories nel New Jersey. Shor ha continuato scoprendo che poteva adattare l'algoritmo di Simon per calcolare il periodo di un oracolo, se ne avesse uno. Poi si rese conto che poteva adattare ancora una volta l'algoritmo, per risolvere un'equazione che si comporta in modo simile a un oracolo periodico: l'equazione che descrive la fattorizzazione, che è periodica.
Il risultato di Shor è stato storico. L'algoritmo quantistico che ha scoperto potrebbe ridurre rapidamente numeri giganteschi nei loro fattori primi costituenti, cosa che nessun algoritmo classico noto può fare. Negli anni che seguirono, i ricercatori scoprirono altri algoritmi quantistici efficienti. Alcuni di essi, come l'algoritmo di Shor, fornivano persino un vantaggio esponenziale, ma nessuno poteva dimostrare un drammatico vantaggio quantistico su qualsiasi problema NP che non fosse periodico.
Questa scarsità di progresso ha portato due informatici, Scott Aaronson dell'Università del Texas, Austin, e Andris Ambainis dell'Università della Lettonia, per fare un'osservazione. Le prove del vantaggio quantistico sembravano sempre dipendere da oracoli che avevano una sorta di struttura non casuale, come la periodicità. Nel 2009 loro congetturato che non potevano esserci incrementi drammatici sui problemi NP che erano casuali o non strutturati. Nessuno è riuscito a trovare un'eccezione.
La loro congettura ha messo un limite ai poteri dei computer quantistici. Ma diceva solo che non c'erano incrementi drammatici per un tipo specifico di problema NP non strutturato, quelli con risposte sì o no. Se un problema consisteva nel trovare risposte quantitative più specifiche, che è noto come problema di ricerca, la congettura non si applicava.
Con questo in mente, ricercatori Takashi Yamakawa di NTT Laboratori di Informatica Sociale e Marco Zhandry di NTT Research e Princeton University ha deciso di sperimentare un problema di ricerca specifico, introdotto nel 2005 da Oded Regev.
Immagina una serie di banderuole che puntano tutte nella stessa direzione. Dai a ciascuno di loro una spinta misurata, quindi lascia che un vento rafficato influenzi la loro direzione. Regev voleva determinare, in base alle loro direzioni finali, dove tutti indicavano inizialmente. Problemi come questo sono stati chiamati "imparare con gli errori", perché la spinta e il vento agiscono come una fonte di errore casuale nella direzione originale. Ci sono prove che sia difficile da risolvere sia per gli algoritmi classici che per quelli quantistici.
Yamakawa e Zhandry hanno modificato la configurazione. Hanno modificato la forza di quelle spinte iniziali, rendendole più prevedibili. Hanno anche fatto sì che il vento fosse determinato da un oracolo casuale in modo che fosse ancora più casuale in alcuni casi ma completamente dormiente in altri.
Con queste modifiche, i ricercatori hanno scoperto che un algoritmo quantistico potrebbe trovare in modo efficiente la direzione iniziale. Hanno anche dimostrato che qualsiasi algoritmo classico deve essere più lento di un fattore esponenziale. Come Shor, hanno quindi adattato il loro algoritmo per risolvere una versione reale del problema, che sostituisce l'oracolo con una vera equazione matematica.
Gli informatici stanno ancora lavorando per capire e sviluppare il problema. Vaikuntanathan lo confronta con uno diverso che si verifica quando si esegue la compressione dei dati: quando le informazioni vengono compresse, due bit possono essere compressi accidentalmente nello stesso punto, sovrascrivendoli. Il problema di prevedere quelle collisioni in anticipo, in modo da poterle evitare, ha una certa somiglianza. "Questa è una classe di problemi che fondamentalmente assomigliano a questo", ha detto. "Forse questi problemi possono essere risolti quantisticamente."
C'erano speranze che un problema non strutturato come quello nuovo potesse essere risolvibile anche sulle nuove versioni odierne dei computer quantistici, fornendo così un mezzo per testarli. L'idea era che i problemi non strutturati potessero richiedere meno risorse per essere programmati o essere meno sensibili al rumore, poiché sono già casuali. Ma finora, il nuovo problema sembra ancora troppo avanzato per essere risolto dai computer quantistici esistenti. “È un problema strano. Non avevo pensato di definirlo", ha detto Aaronson. "Ma in retrospettiva, ha alcune caratteristiche molto interessanti."
Il risultato fornisce il primo esempio di vantaggio quantistico drammatico su un problema NP non strutturato. Potrebbero esserci molti altri problemi che il mondo quantistico cambia da praticamente irrisolvibile a risolvibile? Ora ci sono più ragioni per pensarlo.
"Ha in qualche modo ribaltato le nostre convinzioni sui tipi di problemi in cui i computer quantistici potrebbero essere bravi", ha affermato O'Donnell.
