venerdì 20 dicembre 2019

Supremazia quantistica di Google: Mito o realtà?

di Fausto Intilla
------------------------------
Quando pensiamo ai futuri computer quantistici, il primo luogo comune da sfatare, è che essi andranno a sostituire praticamente tutti i computer classici. Ebbene ciò non è affatto vero. In primis, occorre ricordare che non è sempre possibile trovare un algoritmo quantistico, più efficiente di un algoritmo classico per qualsiasi tipo di problema. Dunque i computer quantistici, il giorno in cui saranno alla portata di milioni di persone, verranno utilizzati solo per particolari classi di problemi.
Il primo modello di computazione quantistica risale al 1980, ad opera di Paul Benioff. Egli infatti elaborò uno schema, in versione quantistica, di macchina di Turing. In sostanza si trattava di una macchina di Turing, che poteva funzionare solo utilizzando le regole e i principi della meccanica quantistica (senza entrare in conflitto con gli assiomi di Church-Turing). Due anni dopo, nel 1982, R. Feynman intuisce qualcosa di fondamentale in seno alla computazione quantistica: siccome i sistemi quantistici prendono forma in uno spazio astratto, che è lo spazio di Hilbert (che accresce esponenzialmente la dimensione dello spazio con il numero di sottosistemi/componenti fisici del sistema considerato; 2^N, per N-sistemi a due livelli), è molto difficile fare una simulazione/computazione classica estesa di questi sistemi e ovviamente risulta impossibile, nel limite di N molto grande; dunque per esplorare questi sistemi in profondità, è assolutamente necessario disporre di un calcolatore quantistico (ovvero, per dirla con Feynman, di un “simulatore quantistico universale”). Tre anni dopo le intuizioni di Feynman, nel 1985, David Deutsch mostra come realizzare una computazione universale, utilizzando un modello a circuito con porte logiche reversibili (del tutto analogo al modello del circuito booleano classico, ma con la particolarità appunto della reversibilità di tutte le porte logiche; come richiesto dalle operazioni quantistiche).
I primi importanti algoritmi, vennero tuttavia ideati solo una decina di anni dopo. Risale infatti al 1994, un algoritmo fondamentale per la fattorizzazione di grandi numeri in fattori primi, ad opera di Peter Shor. L’enorme importanza di questo algoritmo (denominato semplicemente: algoritmo di Shor), sta nel fatto che rispetto ai più noti e migliori algoritmi classici attualmente conosciuti, si avvale di un vantaggio di speedup esponenziale; dunque un vantaggio enorme, in termini di velocità. Tale algoritmo, tuttavia, non dimostra affatto che non possano esistere algoritmi classici che siano polinomiali, nel tempo di calcolo in funzione della dimensione dell’input. Finora comunque, nessuno è mai riuscito a trovare un algoritmo classico che non sia esponenzialmente soppresso rispetto all’algoritmo di Shor.
Circa due anni dopo, nel 1996, Lov Grover formula un altro importante algoritmo, che prenderà il nome di: algoritmo di ricerca (quantistico) di Grover. Si tratta di un algoritmo che permette in sostanza di trovare il famoso “ago in un pagliaio”; poiché è in grado di cercare (…e trovare) delle informazioni in un database non strutturato. Il vantaggio di quest’ultimo algoritmo è di tipo quadratico. Evito a questo punto a tutti i miei lettori, tutta la noiosa teoria sulla differenza tra un bit classico e un qubit (idem per il discorso sui problemi indotti dalla decoerenza, dove il damping e il dephasing giocano un ruolo non indifferente); altrimenti il presente articolo diverrebbe troppo lungo e in pochi verrebbero stimolati a leggerlo fino in fondo. Si tenga solo presente un fatto estremamente importante, quasi sempre soggetto a fraintendimenti: nel momento in cui si compie l’atto di misurazione su un qubit, esso non è più definito da una sovrapposizione di stati, ma diventa semplicemente un bit classico! (infatti, in base al postulato della riduzione del pacchetto d’onda del vettore di stato, la misurazione dovrà terminare necessariamente in zero o in uno). È dunque assolutamente sbagliato credere che quando abbiamo N qubit in realtà abbiamo 2^N possibilità di bit classici! (è possibile tuttavia fare un encoding e grazie ai principi della meccanica quantistica, eseguire delle operazioni che classicamente non potrebbero essere eseguite, senza scalare con il numero dei bit).
Un’altra cosa importante in merito alle porte logiche quantistiche, consiste nel fatto che esse, oltre a dover essere reversibili, debbano anche essere unitarie; poiché è proprio l’unitarietà, a garantire la conservazione del prodotto scalare (nonché della probabilità e della reversibilità). La reversibilità, fortunatamente, è consentita e garantita grazie ad un importante risultato ottenuto da Charles Bennett nel lontano 1973. Egli infatti dimostrò che qualsiasi computazione deterministica può essere resa reversibile. Ad emergere è dunque un fatto molto importante: nonostante la computazione quantistica sia (di base) non deterministica e permette inoltre la reversibilità, essa è tuttavia utilizzabile come modello/struttura computazionale. In sostanza, una computazione deterministica, può essere eseguita con un computer quantistico, solo se essa è reversibile.
Riguardo al concetto di velocità di elaborazione dell’informazione, in generale non ha senso chiedersi quanto sia più veloce un computer quantistico rispetto a un computer classico; ciò che ha senso invece, è chiedersi quanto è asintoticamente più veloce un computer quantistico rispetto a un computer classico. In genere si dice che un computer quantistico ha un vantaggio asintotico, solo se il suo vantaggio su un computer classico, diventa sempre più grande man mano che i problemi che deve affrontare diventano anch’essi sempre più grandi (con il rapporto tra le due velocità, tendente ad infinito). Dunque è possibile che, anche nella risoluzione di un problema in cui, asintoticamente, il computer quantistico “batta” quello classico, per piccoli casi di tale problema, il computer classico sia più “efficiente” di quello quantistico. Si consideri inoltre il fatto che non esiste alcun teorema, che indichi che per particolari e determinate applicazioni, un computer quantistico sia più veloce rispetto a uno classico (si tratta in sostanza di una semplice credenza, tra fisici ed informatici, ancora tutta da dimostrare; se mai un giorno verrà dimostrata).
Ma veniamo a questo punto al concetto di supremazia quantistica, che ha dato in parte il titolo al presente articolo. Con supremazia quantistica, in genere si fa riferimento al fatto che si evidenzi una netta differenza tra il tempo di computazione utilizzato da un computer quantistico e quello invece utilizzato da un computer classico, nel momento in cui entrambi si trovino a risolvere uno stesso/identico problema. È però importante osservare che non si tratta di una caratteristica universale, ma dipende ogni volta dal tipo di problema che viene analizzato.
Stando all’annuncio di Google, l’azienda in questione dichiara (in un articolo uscito su Nature nel mese di ottobre di quest’anno, 2019) di aver costruito un processore a 53 qubit superconduttori, che realizzano una distribuzione di un circuito random quantistico e la ricostruiscono in meno di tre minuti; mentre secondo loro (ovvero secondo Google), i migliori algoritmi classici impiegherebbero migliaia di anni. Ebbene è proprio qui che entra in gioco la logica del vantaggio asintotico, menzionata poc’anzi. È vero che oggi Google può vantare un notevole traguardo raggiunto con “soli” 53 qubit, ma ben presto è quasi del tutto certo che quei 53 qubit diventeranno 60 e poi addirittura 70 (un obiettivo che hanno già pianificato di raggiungere entro il 2023); allora a tal punto, grazie alla natura della crescita esponenziale, a lungo termine, neppure il più potente computer classico che una mente umana possa mai concepire, su un medesimo problema di natura quantistica, riuscirà mai a “stare al passo” con un computer quantistico. Possiamo dunque dare a questo punto una risposta alla domanda che il titolo stesso di questo articolo porta con sé: Google ha realmente raggiunto la supremazia quantistica? Ebbene in questo momento l’unica dimostrazione reale di una supremazia quantistica, nel senso del vantaggio asintotico (ovvero che “andando a scalare”, la supremazia diventa sempre più grande), non vi è quasi più alcun dubbio, è di Google.

A tutti coloro che ritengono che tale supremazia spetti alla D-Wave Systems, posso solo dire: mettetevi il cuore in pace, non è così. La D-Wave non utilizza il modello a circuito per la realizzazione del suo computer quantistico; essa infatti utilizza un Annealer. In estrema sintesi: partendo da un ground state molto semplice, con una successiva evoluzione adiabatica che è lentissima e con un’hamiltoniana molto più complicata (di cui non è possibile prepararne il ground state) e in base al teorema adiabatico (che mi garantisce che se l’evoluzione è sufficientemente lenta, rimango sempre nel ground state), si arriva in sostanza a trasformare il ground state semplice iniziale, nel ground state complicato che in ultima istanza è ciò che si vuole realizzare. Questo è ciò che in pratica fa la D-wave (che recentemente è arrivata oltre i 5000 qubit entangled; cosa non da poco). Ciò che tuttavia la D-wave non è mai riuscita a dimostrare, purtroppo, è di aver raggiunto lo speedup asintotico; cosa che Google è invece riuscito a conquistare …ed anche a dimostrare. 

Nessun commento: