INFORMATICA - QUANTUM COMPUTING - HYPER COMPUTING

Gennaio 2023

1. Complessità computazionale quantistica

Dalla tesi di Church-Turing è noto che qualsiasi modello di calcolo computazionale può essere emulato o realizzato da una Macchina di Turing, meglio ancora se da una Macchina di Turing probabilistica. Senza entrare nella questione della solidità o meno di questa tesi va considerato che essa è stata concepita in un ambito fisico reale e quindi non in quello quantistico. Attualmente, in letteratura, alla domanda: esiste un modello di Macchina di Turing Quantistica? la risposta è si e senza entrare troppo in tecnicismi si stabilisce che una Macchina di Turing Quantistica può essere emulata da una Macchina di Turing Probabilistica con un rallentamento esponenziale. In questo senso la Macchina di Turing Quantistica non introdurrebbe, a livello di complessità computazionale, nessuna particolare differenziazione rispetto al caso classico se non una notevole efficienza nei tempi di risoluzione peraltro solo di particolari classi di algoritmi (quindi non in tutti i casi).

In questa pagina vorrei introdurre, in proposito, una riflessione sul concetto di iper-computazione (altamente dibattuto e contestato in ambito accademico) per avanzare l'ipotesi che la Macchina di Turing Quantistica e quindi in generale i computer quantistici (a mano a mano che cresceranno) genereranno un tipo di calcolo computazionale che va oltre il concetto di Macchina di Turing deterministica o probabilistica. In definitiva il modello quantistico di computazione è possibile che sfugga alla tesi di Church-Turing classica (so che è un'affermazione forte ma dopotutto anche la tesi di Church-Turing non è perfettamente dimostrata in tutti gli ambiti, semplicemente ad oggi si può affermare con certezza che non è mai stata smentita).

2. Iper-computazione

La hypercomputation è uno strano settore a metà tra scienza e filosofia che studia la possibilità di un calcolo computazionale che vada oltre le possibilità della Macchina di Turing. Va considerato che ben lungi dall'essere un campo degli ultimi anni, le basi della iper-computazione sono state buttate proprio dallo stesso Turing nel 1938. Egli introdusse all'interno del meccanismo della Macchina di Turing degli oracoli, ossia delle particolari funzioni in grado di ottenere istantaneamente dei risultati impossibili per la Macchina di Turing stessa. Si trattava naturalmente di funzioni teorizzate e impiegate come tali, delle scatole nere senza nessuna pretesa di una loro realizzazione concettuale interna e tantomeno fisica reale. Di oracoli se ne possono teorizzare diversi, ad esempio il generatore di numeri random perfetto, che genera un numero perfettamente impredicibile in un singolo passo e quindi praticamente senza calcoli. Un altro esempio cui sono molto affezionato è l'oracolo che determina istantaneamente la costante di Chaitin (probabilità dell'halting problem). Una Macchina di Turing dotata di almeno un oracolo è un modello di iper-computer.

L'iper-computazione è stata studiata a più riprese dopo Turing e negli ultimi anni. Come dicevo prima è anche abbondantemente contestata quale irrealizzabile e non completamente attendibile, resta il fatto che, ad esempio, gli oracoli sono molto impiegati nello studio della complessità degli algoritmi e nella decrittazione in quanto, anche se non dovrebbero esistere :-))) permettono di svolgere studi ipotetici molto complicati. Sono quindi fiorite diverse ipotesi di ipercomputazione ulteriori agli oracoli: ad esempio le macchine computazionali nel continuo (qualcuno le chiama con il termine "reali") che dovrebbero operare nel campo dei numeri reali e non in quello dei numeri interi (ricordo a tutti che la maggioranza dei numeri reali non è computabile nel senso della Macchina di Turing - vedere la mia pagina sui numeri reali e quella sui numeri computabili); un altro esempio è quello delle macchine infinite, ossia modelli di macchine computazionali formate da un numero infinito di Macchine di Turing operanti insieme, ecc.; ultimo esempio che è importante riportare è quello delle macchine computazionali basate su reti neurali fisicamente realizzate (escludo quindi quelle emulate via software alla base del machine learning e del deep learning) sia in ambito elettronico che biologico, in tal caso, infatti i neuroni non separano elaborazione e memorizzazione come avviene nella Macchina di Turing classica realizzando, di fatto, una forma di iper-computer (in questo senso il nostro cervello esegue sicuramente hypercomputation e questo non dovrebbe sorprendere dato che siamo in grado di svolgere molte funzioni che una Macchina di Turing non può proprio eseguire). Inutile dire che c'è chi ha avanzato l'ipotesi che anche le macchine di elaborazione quantistiche siano in realtà iper-computer e qualora ciò sia vero e se tutto va come la tecnologia promette, saranno iper-computer realizzabili nella realtà e non "semplici" ipotesi matematiche.

3. Macchina di Turing Quantistica

Come noto le operazioni svolte da una Macchina di Turing classica sono davvero poche ed elementari, si tratta naturalmente di una macchina a stati che ha un controllore in grado di leggere, scrivere e spostarsi su un nastro (che fa da memoria) suddiviso in celle, seguendo una logica di controllo (algoritmo). Per questa trattazione considereremo un compito davvero semplicissimo: partiremo da un nastro con tutti 0 nelle celle tranne che in una ove c'è un 1, la Macchina dovrà cercare la cella con l'unico 1 e lì fermarsi. La logica di controllo è quindi ridotta al minimo e molto semplice da stabilire, ad esempio una ricerca del 1 cieca e unidirezionale a scorrimento sul nastro. Il tempo (numero di step) che la macchina impiega (tempo di halting) per risolvere il compito è naturalmente dipendente dalla posizione del 1 rispetto alla cella di partenza della ricerca (spesso si considera il nastro di lunghezza infinita e quindi il tempo di halting potrebbe essere grande a piacere se non teoricamente infinito).

Da questa base di partenza introduciamo un comportamento quantistico nella citata Macchina semplificata, anche tale comportamento lo selezioneremo in maniera molto elementare, consideriamo il valore contenuto da ogni cella in chiave quantistica, come potrebbe essere un quantum-bit. Il controllore della macchina avrà quindi una parte quantistica che va a trattare il qbit su cui è posizionato il lettore C[0] il quale, per la proprietà di superposition andrà ad assumere una tra infinite combinazioni possibili di 0 ed 1, in tal senso, qualora osservassimo il comportamento della Macchina quantistica lo vedremmo collassare (termine tecnico in ambito quantistico) in maniera per noi random verso un riconoscimento o meno della presenza di un 1. Se invece l'osservazione non avvenisse, la Macchina quantistica si comporterebbe in una maniera molto difficile da comprendere per noi esseri umani: simultaneamente si fermerebbe per aver trovato un 1 e continuerebbe la ricerca come se 1 non fosse stato trovato(!!!).

So che queste considerazioni sono difficili da contestualizzare nel mondo reale e dopotutto la fisica quantistica non brilla per comportamenti facilmente comprensibili alla mente umana, ma si tratta solo di un'astrazione matematica particolarmente complessa e in letteratura c'è uno schema che permette di trattarla abbastanza razionalmente. Ad ogni cella C[i] per i = 0,1,2,3,... la Macchina di Turing Quantistica si comporta come se ci fossero più Macchine di Turing classiche a operare simultaneamente sulla stessa cella ma in ambienti totalmente diversi (teoria matematica del "multiverso"). Ne conseguono alcuni punti che sottolineo: (1) in almeno uno degli "universi" il valore 1 è trovato istantaneamente per cui la Macchina di Turing Quantistica, nel suo complesso risolve SEMPRE istantaneamente il compito della ricerca; (2) la Macchina di Turing Quantistica così come vista sarebbe costituita da infinite Macchine di Turing classiche per cui potrebbe definirsi un iper-computer.

NOTA: il ricorso alla teoria matematica del "multiverso" non implica che esso esista veramente... è solo un modo schematico per capire un modello matematico che non ha corrispondenti nella nostra realtà oggettiva. E' un'astrazione utile spesso anche nell'ambito della programmazione delle macchine quantistiche.

Nelle macchine computazionali quantistiche attualmente realizzate il numero di qbit disponibili è fortemente limitato per cui l'approssimazione del nastro a lunghezza infinita non regge e tantomeno il fatto che siano iper-computer o che possano avere comportamenti da iper-computer (quali ad esempio l'ottenimento del risultato di una ricerca sempre in un solo passo). In ogni caso la disponibilità di un certo numero di qbit implica di fatto un comportamento fortemente parallelo del sistema. Un software per macchine quantistiche è molto spesso uno schema circuitale in cui delle porte quantistiche interagiscono tra loro e il parallelismo a livello di qbit è fortemente sentito, inoltre molto spesso il risultato dell'elaborazione quantistica in sè è praticamente istantaneo o quanto meno ad un singolo step.

4. "Oracoli" quantistici

Come detto in precedenza gli "oracoli" nel senso di Turing sono considerati astrazioni matematiche assolutamente non realizzabili da un punto di vista fisico. Eppure anche in questo caso il quantum computing ha molto da dire. Una delle applicazioni commerciali attualmente più sviluppate del QC è proprio quella degli QRNG (Quantum Random Number Generator), ossia di generatori di numeri random basati su fenomeni quantistici. Tali generatori sono basati sul "collasso" verso valori casuali dei fenomeni quantistici quando un osservatore li osserva (tecnicamente quando li "misura"). Si tratta di una casualità assoluta (ad oggi), non si può spiegare con il determinismo classico e nemmeno è frutto di un calcolo o di una elaborazione come avviene per i classici PRNG (Pseudo Random Number Generator che ricordo a tutti essere algoritmi matematici basati su formule non lineari di matematica discreta e quindi, in definitiva, calcoli...) che siamo abituati ad utilizzare tutti i giorni sui comuni PC o online. I QRNG trovano impiego pratico ottimale in ambito di metodi montecarlo, crittazione e generazione delle chiavi in quanto assolutamente non predicibili e non attaccabili computazionalmente, per cui sono commercialmente sempre più diffusi e sono disponibili anche online (basta fare una ricerca per QRNG su google). Mi preme osservare che un QRNG è di fatto un "oracolo" nel senso di Turing, genera infatti un risultato in un solo step e con una caratteristica computazionale che nessuna Macchina di Turing (nessun calcolo) può implementare nello stesso modo. Si tratta ancora una volta, quindi, di hypercomputation.

5. E se l'approccio fosse sbagliato?

Proprio partendo dal più comune oracolo quantistico, ossia il QRNG di cui sopra, vorrei esporre una considerazione al limite (di cui mi prendo naturalmente paternità e responsabilità). Nelle attuali macchine computazionali quantistiche si è pensato di realizzare il quantum-bit e nella maggioranza dei casi le porte logiche quantistiche e quindi i circuiti quantistici quali implementazione del concetto di software in tale particolare ambito. La mia umile osservazione è che un QRNG non necessita del concetto di quantum-bit per funzionare. Il modo più semplice per realizzare un QRNG programmando una macchina quantistica gate-based è prendere un qbit e osservarlo (misurarlo), si tratta di un circuito quantistico semplicissimo e a livello di codice python fatto di poche chiamate a funzioni. Questo però non toglie che si può costruire un QRNG con un sistema fisico (es. ottico basato sui fotoni) che funziona perfettamente senza ricorrere ai concetti di qbit e programmazione quantistica (PicoQuant GmbH & Nano-Optics groups Department of Physics della Humboldt University). E se avessimo sbagliato direzione di studio? Se il nostro sforzo di imbrigliare le macchine quantistiche entro gli angusti limiti dei qbit e delle porte logiche fosse un limite che di principio stiamo ponendo noi?

Come avviene nelle macchine computazionali basate sul Quantum Annealing (https://www.dwavesys.com) penso che i computer quantistici siano di principio iper-computer e quindi dovrebbero essere sfruttati secondo framework e principi completamente diversi da quelli della Macchina di Turing e quindi dei computer classici che conosciamo, programmazione inclusa. I Quantum Annealer sono ad esempio degli ottimizzatori di funzioni quadratiche e anch'essi si comportano, al pari dei QRNG, quali oracoli (si tratta di sistemi commerciali straordinariamente efficienti ed efficaci e spesso i loro risultati sono addirittura impossibili da verificare... si pensi alla risoluzione di un problema di ottimizzazione con 10 milioni di variabili...). Ebbene, la programmazione dei Quantum Annealer non impiega i concetti di quantum bit, di porta logica e di circuito e in buona sostanza non sono assolutamente considerabili come delle Macchine di Turing.

marcomattiucci.it

Informatica:

Quantum Computing: