Ho visto molto più entusiasmo riguardo ai computer quantistici su X recentemente, quindi ho pensato di fare un lungo post su di essi. Sintesi esecutiva: non credo che il calcolo quantistico arriverà a breve. Penso questo perché non è stato fatto alcun progresso negli ultimi anni sul problema più semplice per cui i computer quantistici possono essere utilizzati, che è la fattorizzazione. Il record di fattorizzazione quantistica è rimasto attorno al numero 15 (sì, 15, 3 x 5!) per un decennio ormai, e non ci sono stati progressi evidenti ultimamente. Le mie motivazioni sono di seguito. Cercherò di spiegare le cose per le persone che non conoscono molto di matematica o informatica, ma questo potrebbe comunque spaventare le persone con fobie matematiche. La fattorizzazione di numeri grandi è di interesse perché diversi algoritmi crittografici importanti dipendono dal fatto che ci vuole molto tempo per fattorizzare un numero sufficientemente grande nei suoi fattori primi utilizzando computer convenzionali. Puoi fattorizzare un numero piccolo (diciamo 21) a mano molto rapidamente, basta provare a dividerlo per i numeri partendo da 2, poi 3 e così via, e scoprirai rapidamente che 21 è 3 x 7. Tuttavia, questo non funziona per numeri davvero grandi perché lo spazio di tutti i numeri che dovresti provare diventa troppo grande. Se potessi fattorizzare numeri di oltre circa 1200 cifre decimali (non il numero 1200, che ha quattro cifre, ma numeri con 1200 cifre!) potresti rompere molti sistemi crittografici che interessano le persone, ma nessuno sa come farlo abbastanza rapidamente su un computer normale. (Abbastanza rapidamente significa "prima che tutte le stelle nel cielo si spengano.") Alcuni anni fa, Peter Shor ha dimostrato che si potrebbero (in teoria almeno) fattorizzare numeri molto rapidamente utilizzando computer quantistici. Fattorizzare utilizzando l'Algoritmo di Shor è, a mio avviso, il benchmark più ovvio difficile da falsificare per il calcolo quantistico. Nel 2016, il numero 15 (non un numero di 15 cifre, il numero 15!) è stato per la prima volta fattorizzato (ovviamente in 3 x 5) in una dimostrazione pulita e non truccata dell'Algoritmo di Shor. Questo è un numero piccolo, ma è stato un inizio. (C'è qualche discussione su se il numero 21 sia stato anche fattorizzato in una dimostrazione non truccata dell'algoritmo di Shor o meno.) Ma di nuovo, 15 è un numero a due cifre. Vogliamo fattorizzare numeri di migliaia di cifre per poter rompere i sistemi crittografici. Tuttavia, dal 2016, non sono stati fattorizzati numeri più grandi in dimostrazioni pulite dell'algoritmo di Shor. (Alcune persone hanno affermato di aver fattorizzato numeri più grandi utilizzando l'Algoritmo di Shor, ma hanno sempre usato trucchi che richiedevano di conoscere già i fattori per farlo e impostare il computer quantistico con quello che equivale a una pre-conoscenza della risposta, il che non è davvero il punto. Sto cercando dimostrazioni *non truccate*.) Stiamo aspettando da molto tempo che qualcuno dimostri la fattorizzazione anche di un numero leggermente più grande di 15. Avresti sperato che ci potesse essere un progresso costante su questo, con qualcuno che fattorizza (diciamo) un numero come 77 (7 x 11), e poi uno come 323 (17 x 19), poi qualcosa di migliaia, e così via. Tuttavia, nessuno ha dimostrato una macchina che possa fare qualcosa di meglio del numero 15 (che un bambino può fattorizzare nella sua testa in 3 e 5 in pochi istanti) e quel record è rimasto in piedi per molto tempo. Quindi, su questo problema almeno, un problema davvero basilare che è facile da spiegare, non c'è stato alcun progresso costante nel calcolo quantistico. Abbiamo avuto molto entusiasmo, molte persone che mostrano computer quantistici che presumibilmente eseguono algoritmi che non sono dimostrazioni così ovviamente pulite, ma non abbiamo visto nulla da molto tempo sulla fattorizzazione. Crederò che ci sia stato un vero progresso nel calcolo quantistico quando iniziamo a vedere numeri più grandi fattorizzati in dimostrazioni pulite e non truccate dell'Algoritmo di Shor. Crederò che abbiamo fatto un vero progresso quando potremo fare numeri a quattro cifre, cioè numeri di migliaia. Anche una dimostrazione di qualcosa che potrebbe fare un numero a due cifre molto più grande di 15 sarebbe gradita. Tuttavia, nessuna macchina che possa farlo è realmente all'orizzonte a breve termine. Ora, essere in grado di rompere codici richiede macchine che possano gestire numeri con *migliaia* di cifre, ma non abbiamo nemmeno numeri a tre cifre in vista (o nemmeno la maggior parte dei numeri a due cifre). Quindi, il mio benchmark personale è vedere anche un po' di progresso su questo. Richiamami quando avremo computer quantistici che possono fattorizzare (diciamo) 323 con successo, in una dimostrazione pulita e non truccata dell'Algoritmo di Shor che possa gestire qualsiasi numero composto di dimensioni simili. Fino ad allora, non penso che ci sia molto di interessante in corso, almeno non per me.

(A proposito, non voglio dare l'impressione di pensare che il calcolo quantistico sia impossibile o altro. Sto solo dicendo che, da dove mi trovo, i progressi recenti non sono stati evidenti e siamo ancora lontani dal risolvere problemi semplici come la fattorizzazione dei numeri con esso.)

A proposito, questo non significa nemmeno che aziende come Google siano sciocche per perseguire la ricerca pura nel campo del calcolo quantistico. Penso che valga la pena lavorarci. Semplicemente non ha alcuna applicazione pratica imminente. Potrebbe anche essere che la NSA o altre organizzazioni simili abbiano fatto progressi più significativi nel problema rispetto al mondo della ricerca aperta, ma ovviamente, queste non sono informazioni di cui sarei a conoscenza. Infine, questo non significa che la ricerca sugli algoritmi crittografici post-quantistici sia una cattiva idea.

Nel mio post originale in cima, ho evitato di menzionare quanto siano difficili i problemi di scalabilità. Principalmente mi sono concentrato sul fatto che nessuna scalabilità è effettivamente avvenuta. E per essere sicuri, a un certo punto, è molto possibile che le questioni di correzione degli errori inizieranno a comparire. Ma, scalare per fattorizzare numeri seri non accadrà il giorno dopo.

@defendtheworld Comunque, di nuovo: inizierò a credere quando vedrò la tecnologia andare oltre il fattorizzare 15. E sì, questo significa che un'enorme quantità di lavoro sarà già stata svolta, ma lascerà anche un'enorme quantità di lavoro ancora da fare.