La posta di Schrödinger S1.E7
Perché lavorare allo smistamento dei pacchi di Amazon non è una buona idea, neanche se aveste un computer quantistico
C’è una prima volta per tutto.
E oggi “festeggio” il mio primo refuso in una newsletter. Forse lo sapete già se mi seguite su Instagram.
La formula dell’equazione di Schrödinger che ho scritto nello scorso episodio era sbagliata.
Quella corretta è questa:
Cosa cambia? In pratica, le costanti di cui vi parlavo nella scorsa newsletter si devono trovare dall’altra parte dell’uguale. Concettualmente è la stessa equazione, ma se volete tirar fuori numeri che coincidono con dati presi da esperimenti dovete usarla scritta in questo modo.
Perché l’ho sbagliata? Perché non ho fatto sufficiente attenzione ai dettagli.
Poi considerate che ho anche il brutto vizio di essere un fisico teorico. E spesso noi fisicə teoricə decidiamo semplicemente di ignorare le costanti e decidere che sono uguali a 1. Così che i calcoli sui fogli (o sui tablet, ormai), vengono più semplici.
Tanto a rimettere le costanti al posto loro c’è sempre tempo.
Mea culpa.
Ho corretto l’espressione dell’equazione anche sulla versione sito della scorsa newsletter. Così se volete rileggervi la scorsa email senza errori, vi consiglio di passare da lì.
Ora passiamo alle (buone) nuove.
Ovvero l’argomento di oggi.
Una storia in due parti
Finora vi ho parlato di meccanica quantistica, di principio di sovrapposizione, di equazione di Schrödinger. Di fotoni. Ad un certo punto, anche di cosa sono i qubit.
Ora vorrei iniziare a scomodare uno dei temi che la fanno da padrone nel campo dell’informazione quantistica. Sia in ambito di ricerca che, più recentemente, in ambito di investimenti e di copertura mediatica.
Esatto: il computer quantistico.
L’idea del computer quantistico nasce abbastanza di pari passo con quella di qubit. Se il concetto generale di informazione quantistica è quello di codificare informazione in particelle, il computer quantistico è una delle sue naturali applicazioni.
Così come un computer tradizionale elabora informazione in termini di bit, ora un computer quantistico prova a fare lo stesso, ma usando dei qubit. Lo so, ve l’ho già detto quando si parlava di uncini.
La domanda che mi piacerebbe iniziare ad affrontare oggi è: perché?
Perché, se abbiamo speso decenni a sviluppare la tecnologia per un computer tradizionale, dovremmo ricominciare da capo per sviluppare un computer quantistico? (sì, un computer quantistico richiede tutt’altra tecnologia, magari una delle prossime volte vi spiego meglio il motivo).
La risposta, che è arrivata già svariati decenni fa, è che un computer quantistico può risolvere alcuni problemi in maniera molto più efficiente di un computer tradizionale. Non tutti i problemi, ma alcuni sicuramente sì.
In alcuni casi, questa differenza di efficienza è molto grande. Concretamente, ci sono casi in cui un computer quantistico è esponenzialmente più veloce di un computer tradizionale. E se vi ricordate l’esempio di un paio di newsletter fa, una differenza esponenziale è molto grande. Al livello tale che, mentre un computer quantistico vi dà una risposta nel giro di minuti, un computer tradizionale ci metterebbe milioni di anni.
Capite bene che una cosa del genere può far sì che problemi che non ci sogneremmo mai di provare a risolvere con un computer di casa, diventerebbero improvvisamente accessibili con un computer quantistico.
Sono stato convincente fin qui?
(sì lo so, è una newsletter e non potete rispondere. Quindi la domanda era retorica. Ma mi piace immaginare che abbiate annuito mentalmente mentre leggevate.)
Una volta capito il perché, vorrei passare ad una questione ancora più spinosa: il come.
Ovvero, qual è il trucco magico dietro a questa accelerazione esponenziale? Cos’è che fanno di diverso i computer quantistici per essere così veloci nel risolvere alcuni problemi?
Siccome la questione è intricata, ho pensato di dividere la risposta in due parti.
Nella prima, cioè la newsletter di oggi, vi racconto cos’è che NON fanno i computer quantistici.
Nella seconda, cioè la prossima newsletter, vi racconto invece cos’è che fanno i computer quantistici per riuscire ad essere più veloci. Almeno in alcuni casi.
Cominciamo.
Il problema del furgone di Amazon
Immaginatevi di lavorare per un centro smistamento pacchi di Amazon.
Ogni giorno, vi arrivano centinaia di ordini da vari posti diversi nella regione in cui vi trovate. Tizi@ ha comprato un nuovo cellulare e dobbiamo spedirlo oggi. Cai@ sta aspettando di ricevere lo zaino che ha ordinato una settimana fa.
Mettendo tutto insieme, ogni mattina vi ritrovate qualche manciata di pacchi da consegnare in giornata, ognuno ad un indirizzo diverso. E magari anche in città diverse. Per le consegne, oggi avete a disposizione un certo numero di furgoni, con relativə autistə. Che vi tocca fare? Dovete mettervi a pensare come distribuire i pacchi. Il cellulare va al furgone uno, insieme allo zaino, perché dopotutto Tizi@ e Cai@ abitano abbastanza vicino. Cosa diamo al furgone due invece? E al tre?
Non solo vogliamo distribuire i pacchi, ma vogliamo anche dire ad ogni furgone qual è l’ordine migliore in cui consegnarli. Prima il cellulare a Tizi@ o lo zaino a Cai@? E dopo da chi andiamo?
Non è una questione da poco, perché, a seconda dell’ordine di consegna che scegliamo, potremmo metterci molto più tempo. Chiaramente è più intelligente consegnare tutti i pacchi nella stessa città, prima di spostarci a quelli nella successiva. E se non facciamo bene i conti, magari l’autistə non riesce a consegnare tutto in giornata. Mentre se siamo bravə riusciamo a far finire la sua giornata lavorativa prima del solito. E a far tornare a casa l’autistə senza mal di testa.
Ora, lo so che questa storia non è realistica. E che probabilmente Amazon ha un programma al computer che calcola tutte queste divisioni dei pacchi e dei percorsi. Mica una persona.
Ma quello che posso dirvi con certezza, programma o persona che sia, è che raramente ruiscirà a trovare il percorso migliore. E solitamente si dovrà accontentare di qualche soluzione più o meno buona.
Perché?
La questione è esattamente quella che vi dicevo poco fa, quando parlavo di problemi matematici che sono difficili da risolvere per un computer tradizionale.
Quello che vi ho descritto è proprio un esempio di uno di questi problemi. Si chiama il problema del commesso viaggiatore. Ed è stato formulato ben prima che esistesse Amazon, quindi non parla esattamente di pacchi e furgoni. Ma il succo è lo stesso. Abbiamo una serie di posti che dobbiamo visitare, ognuno ad una certa distanza dagli altri. E dobbiamo scegliere l’ordine migliore per visitarli, in modo da metterci il minor tempo possibile.
Pensate di formulare un algoritmo che riesca a risolvere questo problema. Per qualunque lista di posti e distanze gli diate in pasto, vi deve rispondere con il percorso migliore da fare.
Ebbene, è stato dimostrato che il miglior algoritmo che potremmo trovare con un computer tradizionale, per darvi la risposta corretta ci metterebbe un tempo che cresce esponenzialmente con il numero di posti da visitare. Almeno in certi casi.
Così che se Amazon volesse sempre trovare il percorso migliore, farlo per cento pacchi già richiederebbe migliaia di anni.
Forse lo so cosa state pensando: ma allora Amazon come fa?
Semplicemente si accontenta di una risposta buona, magari non così buona come il percorso migliore, ma neanche terribile. Ma sicuro vuole una risposta che può tirar fuori dai suoi computer in un tempo ragionevole. Magari in dieci minuti ogni mattina, quando arriva la lista dei pacchi da consegnare e degli indirizzi.
Esponenziale, di nuovo
Fatemi spiegare un pochino qual è l’intuizione dietro al fatto che questo problema dei pacchi è così difficile.
Immaginatevi di essere di nuovo la fantomatica persona che si occupa dello smistamento pacchi ogni mattina. Come approccereste la scelta del percorso per ogni furgone?
La prima cosa che potreste fare è scegliere a caso tra uno dei percorsi possibili. E calcolarvi quanta distanza deve percorrere il furgone in quel preciso caso. Considerate che calcolare la distanza totale non richiede molto tempo, basta sommare le varie distanze fra loro.
Ad esempio, considerate il caso descritto nell’immagine.
I posti da visitare sono 5. Supponiamo di scegliere il percorso 1-5-3-2-4, la distanza totale sarà
(distanza tra 1 e 5) + (distanza tra 5 e 3) + (distanza tra 3 e 2) + (distanza tra 2 e 4)
Sommare dei numeri è qualcosa che richiede uno tempo lineare nel numero di distanze da sommare. Quindi questa è decisamente la parte facile del problema. Se volessimo dirla in termini tecnici, esiste un algoritmo efficiente per calcolare la distanza di un singolo percorso.
Ora però siete solo all’inizio. Avete scelto un percorso specifico, e avete calcolato la distanza da percorrere. Non avete nessuna idea di se sia il percorso migliore. Se lo fosse, e lo avete scelto a caso, mandatemi i numeri del lotto, ché me li gioco subito. Ma comunque, non siete in grado di saperlo a priori. Per convincervi di questa cosa, o per trovare un percorso migliore, il prossimo passo che dovete fare è molto semplice.
Provare un altro percorso.
Quindi tornate alla vostra lista di cinque posti e scegliete un altro ordine, magari 3-4-2-5-1. Sommate di nuovo le distanze e ottenete un nuovo numero. È minore della distanza del percorso di prima? Allora vi conviene scegliere questo, anziché 1-5-3-2-4. È maggiore di quella di prima? Allora tenetevi 1-5-3-2-4.
La storia non finisce qui. Perché quello che vi interessa veramente è trovare il percorso più breve. E finora avete semplicemente comparato due diversi percorsi, e scelto quello che vi piaceva di più.
Forse avete capito dove voglio arrivare. Seguendo questo schema, se volete trovare il percorso migliore, non vi resta che elencare tutti i percorsi possibili. E per ognuno di questi, calcolare la distanza totale. A quel punto, il percorso migliore sarà semplicemente quello che vi ha dato la distanza totale più piccola.
Lo ripeto: dovete elencare tutti i percorsi possibili.
Se la memoria non mi inganna, abbiamo già parlato del legame tra possibilità ed esponenziale. Quindi forse non vi risulterà nuovo se vi dico che, se vi mettete a contare il numero di percorsi possibili, questo numero è esponenizale nel numero di posti da visitare. (E se vi suona nuovo, passate da qui, che è anche dove parlavo della differenza tra lineare ed esponenziale, quindi serve da ripasso molto utile).
È qui che nasce il problema. Fissato un percorso, calcolarne la distanza non richiede tanto tempo. Ma se volete trovare il percorso migliore, dovete provarli tutti, e semplicemente elencarli vi richiede già un tempo esponenziale.
Tutto in parallelo, ovvero viva il quantistico
Ora, nella storia di prima vi ho dato un esempio di procedura che, se voleste calcolarvi il percorso migliore, richiederebbe un tempo esponenziale.
Potrebbe ancora essere, però, che la procedura che vi ho descritto non sia la più intelligente. Magari si può fare di meglio che semplicemente passare da un percorso all’altro e calcolare la distanza. In gergo tecnico, potrebbe esserci un algoritmo più efficiente di quello che vi ho raccontato io.
Qui entra in gioco la ricerca nel campo della complessità computazionale. Grazie a tecniche matematiche molto sofisticate (e che non capisco a fondo), è possibile dimostrare che: no, qualunque altro algoritmo vi venga in mente per il problema del commesso viaggiatore, richiederà comunque un tempo esponenziale.
Bene, abbiamo identificato un problema difficile per un computer tradizionale. A questo punto, l’idea sorge spontanea: magari possiamo risolverlo più velocemente se avessimo a disposizione un computer quantistico.
Anche se così fosse, quale sarebbe una possibile strategia da adottare?
Proviamo a sfruttare una delle proprietà fondamentali della meccanica quantistica. Sì, avete indovinato, è il principio di sovrapposizione. Sfruttare il principio di sovrapposizione ci permette infatti di calcolare la distanza di tutti i percorsi possibili, in contemporanea.
Provo a spiegarvi come si può fare una cosa del genere. Immaginatevi di aver a disposizione l’algoritmo di prima, quello che, dato un percorso, vi calcola la distanza totale da percorrere. Solo che ora lo state usando in un computer quantistico a qubit. In pratica, potreste fare così: numerate i vari percorsi possibili, e associateli ad un numero binario. Ad esempio
1-2-3-4-5 corrisponde 00000
1-4-3-5-2 corrisponde a 00001
1-5-2-3-4 corrisponde a 00010
Eccetera, eccetera.
Quindi, se volete calcolarvi la distanza del terzo percorso, inizializzate i qubit del vostro computer quantistico a 00010 e fate girare l’algoritmo. In risposta, vi arriverà la distanza totale.
Questo è quello che potreste fare anche con dei bit normali, in un computer tradizionale. Con un computer quantistico, però, potete fare qualcosa di più. In particolare, potete inizializzare tutti i qubit in uno stato di sovrapposizione. Con 50% di probabilità valgono 0, con 50% di probabilità valgono 1. Ecco che, mettendo tutto insieme, vi trovate con una sovrapposizione di tutti i valori
00000
00001
00010
00011
E così via.
Visto che ora ogni valore dei qubit corrisponde ad un percorso possibile, è come chiedere al vostro algoritmo di calcolare la distanza totale di tutti i percorsi possibili. In sovrapposizione.
Fantastico, no?
Avete praticamente superato l’ostacolo più grande, quello di dover elencare tutti i percorsi e calcolarne la distanza, uno per uno. Non vi importa più che il numero di percorsi possibili sia esponenziale, tanto li state calcolando tutti in contemporanea.
Ecco spiegato il vantaggio quantistico. Visto che possiamo calcolare tutto in parallelo, siamo estremamente più veloci di un computer tradizionale.
Giusto.
Giusto?
Sì, ma no: il problema della misura
La questione, guardate un pò, non è così semplice.
Una cosa è vera: preparando i qubit in sovrapposizione, state chiedendo al vostro algoritmo di calcolare tutte le distanze in parallelo.
Su questo non ci piove.
La cosa complicata è cosa ottenete come risultato in uscita. Siete partitə in sovrapposizione, quindi finirete in sovrapposizione. I qubit del vostro computer quantistico si troveranno in una sovrapposizione di valori di distanze. Una per ogni percorso possibile.
Ora voi volete un’informazione precisa: quale tra queste distanze è la più corta?
Per ottenere una risposta, però, dovete interagire con i qubit nel vostro computer. Ad esempio, volete sapere, per ognuno di loro, che valore hanno. Zero o uno? In pratica, dovete effettuare una misura del valore dei vostri qubit.
Visto che i qubit sono in una sovrapposizione di valori di distanze, sapete che il risultato che ottenete vi darà una delle distanze possibile. In particolare, quella associata ad un certo percorso.
Quale sia il percorso, però, non lo sapete a priori. Questo è il problema della sovrapposizione quantistica. Non sapete quale risultato ottenete, solo le varie probabilità di ottenere ogni risultato. E siccome avete iniziato con una sovrapposizione cosiddetta uniforme (zero e uno avevano la stessa probabilità per ogni qubit), alla fine otterrete una sovrapposizione uniforme delle distanze. Quindi ogni distanza avrà la stessa probabilità di essere il risultato della vostra misura.
Ecco che, nonostante siate partiti con una sovrapposizione di tutte le risposte, se volete conoscere queste risposte dovete misurare. Ma se misurate otterrete una sola di queste risposte. E non sapete neanche quale sarà. Di certo non avete garanzia che sia quella associata alla risposta più corta.
Va bene, allora magari potreste misurare di nuovo.
Qui purtroppo entra in gioco l’altra caratteristica delle misure in meccanica quantistica. Quando misurate la proprietà di una particella in sovrapposizione, la sovrapposizione si perde.
Ad esempio, se avete un qubit in sovrapposizione di 0 e 1 e lo misurate, otterrete uno dei due valori possibili. Supponiamo sia 1. Da ora in poi, il qubit non è più in sovrapposizione, ma si troverà in uno stato in cui vale sempre 1. Quindi se ripetete la misura, non vi capiterà mai di ottenere 0. Otterrete sempre 1, non importa quante volte riproviate.
Questo è un bel problema per il nostro bel algoritmo quantistico. Perché significa che, una volta ottenuto un valore di distanza, non possiamo più estrarne altri dalla sovrapposizione che avevamo creato. Se ripetiamo la misura di nuovo, siamo condannati a ricevere di nuovo la stessa risposta di prima.
L’unica cosa che possiamo fare è ricominciare da capo. Ripetere tutto l’algoritmo di nuovo, calcolare di nuovo la sovrapposizione di distanze, e misurare. Se siamo fortunati, otterremo una distanza associata ad un percorso diverso.
E poi potremo ripetere di nuovo. Finché non le avremo ottenute tutte e potremo capire qual era la distanza minore.
Capite bene, però, che siamo praticamente tornati allo stesso caso del computer tradizionale. In cui dovevamo per forza elencare tutti i percorsi possibili per scoprire qual era il migliore.
Mi chiederete: ma perché ci hai raccontato tutta questa storia per poi scoprire che questo algoritmo non funziona?
Le ragioni sono due.
La prima è che il motto “I computer quantistici sono super veloci perché calcolano tutto in parallelo” è usato molto comunemente in ambito mediatico (e non solo). Volevo farvi capire che purtroppo le cose non sono così semplici. E che capire qual è l’ingrediente che fa funzionare bene un computer quantistico non è così facile. Anzi, in realtà è ancora una domanda molto aperta.
La seconda è per aumentare la suspence. Perché, se vi ricordate, all’inizio vi ho detto che sappiamo che i computer quantistici sono più veloci nel risolvere determinati problemi. Quindi in qualche modo dovranno pure riuscirci ad essere più rapidi, no?
Quello che posso dirvi è che non si conosce la ricetta generale, ma che per alcuni casi specifici si conosce una buona strategia per far funzionare questa storia del calcolo in parallelo. Solo che bisogna procedere in maniera più furba (e complessa) di quello che ho fatto io.
Ma per raccontarvelo meglio, vi do appuntamento alla prossima newsletter. Per ora passo e chiudo per questo settimo episodio della newsletter. Come sempre, spero che vi sia piaciuto e vi abbia stimolato una sana dose di curiosità. Commentate qui
o scrivetemi in privato se avete domande/commenti/qualunque cosa. Sono sempre felice di leggervi e rispondervi.
Nel frattempo, noi ci rileggiamo alla prossima. Che stavolta sarà nel 2022. Mi prendo un paio di settimane di pausa per godermi le vacanze di Natale e riflettere sui prossimi argomenti da raccontarvi. Quindi appuntamento a martedì 11 Gennaio.
A presto!
Un disclaimer finale
Hai ricevuto questa email perchè qualcun@ te l’ha inoltrata?
Ti svelo un segreto: fa parte di una newsletter. Si parla di meccanica quantistica e molte delle sue applicazioni più recenti, ma non solo. Ne mando una ogni due settimane, il martedì mattina.
Se ti interessa rimanere al passo con le prossime newsletter, ecco il bottone per iscriversi
Altrimenti, amic@ come prima.
Puoi sempre recuperare tutti gli episodi passati e futuri sulla pagina Substack de la posta di Schrödinger.