Autore: Roberto Campagnola
Data Pubblicazione: 5/12/2021
La definizione di algoritmo è di per sé semplice: una serie di operazioni da compiere in un preciso ordine per eseguire un’azione o risolvere un problema. Tutti noi abbiamo familiarità con il concetto di algoritmo, anche se non matematicamente e formalmente precisa, a vari livelli: li abbiamo imparati alle elementari per calcolare le operazioni in colonna, li esaminiamo ogni volta che dobbiamo preparare una ricetta, o per trattare dati mediante machine learning.
A livello informatico, tutti gli algoritmi richiedono energia, tempo e potenza di calcolo per compiere le operazioni, ma non sono tutti equivalenti anche se il risultato può essere uguale.
Per creare una classificazione degli algoritmi, per identificare quale può essere più conveniente da usare per risolvere un problema si ricorre al concetto di complessità di un algoritmo, definita come la quantità di tempo o il numero di operazioni necessarie per elaborare dati di un registro di dimensione N.
Alcuni algoritmi, tra i più efficienti, hanno una complessità polinomiale, cioè il numero di operazioni necessarie per arrivare al risultato cresce come una qualunque potenza di N, numero di bit che stiamo elaborando. Altri algoritmi, molto meno efficienti, hanno una complessità che cresce esponenzialmente con il numero di bit, per esempio 2ⁿ eⁿ etc.
Gli algoritmi quantistici, implementati agendo sui qubit caratterizzati da differenti tecnologie di costruzione (superconducting qubit, ion trap, quantum dot etc), hanno alla base una matematica piuttosto complicata e, sfruttando la sovrapposizione coerente di stati, portano ad una riduzione di complessità davvero straordinaria e quindi a possibili prestazioni senza precedenti. Qui esporremo i due algoritmi più famosi: l’algoritmo di Grover e l’algoritmo di Shor. E’ interessante notare che entrambi questi algoritmi sono stati ideati rispettivamente nel 1996 e nel 1994, ben prima della realizzazione pratica del primo quantum computer.
L’algoritmo di Grover
Nel 1996 Lov Grover, ideò un algoritmo quantistico di ricerca che si proponeva di trovare una risposta al seguente problema: dato uno spazio di ricerca di dimensione N, di cui non conosciamo la struttura dell’informazione in esso contenuta, vogliamo trovare un elemento di tale spazio con precise proprietà.
Adoperando le tecniche della computazione e della teoria dell’informazione classica, il numero di operazioni necessarie per risolvere il problema è di ordine N, pari quindi alla dimensione del “database” che stiamo esaminando.
L’algoritmo di Grover consiste nella ripetizione di alcune subroutine quantistiche e grazie alle proprietà della meccanica quantistica e anche (ma questo non sorprende affatto) una trattazione matematica piuttosto complicata e solo apparentemente “magica” (una delle subroutine dell’algoritmo è chiamata “Oracolo”), riesce a risolvere il problema con un numero di operazioni che è ordine
Bisogna notare che nel caso di N molto grande, l’operazione di radice quadrata riduce la complessità in maniera notevole.
Rappresentazione schematica dell’algoritmo di ricerca, con la trasformata di Hadamard per la sovrapposizione di stati, e le subroutine G dell’algoritmo di Grover
L’Algoritmo di Shor
L’algoritmo ideato da Peter Shor, professore di matematica applicata al MIT, nel 1994 ha lo scopo di scomporre i numeri interi in numeri primi, un problema che ha applicazioni in molteplici campi ed è di straordinaria importanza in ambito matematico, e sappiamo che
“L’universo è scritto in lingua matematica, e i caratteri son triangoli, cerchi, ed altre figure geometriche, senza i quali mezzi è impossibile a intenderne umanamente parola“
L’algoritmo di Shor si basa sulla Trasformata di Fourier quantistica (QFT, Quantum Fourier Transform) una trasformazione lineare che è l’analogo quantistico della trasformata di Fourier classica. Quest’ultima è una legge che trasforma una funzione in una altra, permettendo di scrivere una funzione dipendente dal tempo come combinazione lineare di funzioni esponenziali. L’operatore classico da cui si parte è un tipo di trasformata di Fourier, la Trasformata Discreta di Fourier (DFT, Discrete Fourier Transform) usata in numerosissimi ambiti (elaborazione di immagini, elaborazioni di segnali, meccanica dei fluidi, risoluzione di complesse equazioni differenziali alle derivate parziali, etc); applicando la DFT ad uno spazio di Hilbert n-dimensionale proprio della meccanica quantistica ne troviamo l’analogo quantistico: la QFT.
Tale funzione può essere implementata mediante gate quantistici tra cui i gate di Hadamard, di cui abbiamo già parlato nel numero di scorso, e i gate di phase estimation.
L’algoritmo di Shor si compone di due fasi: una fase che può essere eseguita su un calcolatore classico, che ha lo scopo di trasformare la fattorizzazione in numeri primi nel processo di individuazione del periodo di una opportuna funzione, e una parte quantistica che, grazie alla sovrapposizione coerente di stati dei qubit, riesce a trovare il periodo della funzione.
La fase quantistica è quella che porta alla riduzione della complessità generale del processo e alla diminuzione del tempo necessario per raggiungere lo scopo: attualmente, infatti, l’algoritmo classico più efficiente per la fattorizzazione in numeri primi è il Crivello generale dei campi numerici e ha una complessità esponenziale nel numero di cifre del numero da fattorizzare, O(eⁿ) mentre l’algoritmo di Shor ha una complessità polinomiale nel logN., quindi notevolmente minore!
Rappresentazione della subroutine quantistica dell’algoritmo di Shor
Entrambi gli algoritmi descritti sono probabilistici e non deterministici, quindi forniscono il risultato corretto “con alta probabilità” ma comunque minore di 1, problema che in parte si risolve aumentando le iterazioni dell’algoritmo. Inoltre, connessa al problema e alla formulazione degli algoritmi, si apre la questione di quanto e come un computer quantistico possa simulare processi fisici.
Sappiamo che la natura è di per se’ quantistica, e ogni volta che tentiamo di risolvere problemi elementari con un computer classico (simulare urti tra particelle, descrivere il moto di atomo in un gas, le interazioni tra proteine in un organismo) stiamo solo fornendo alla macchina una nostra approssimazione della realtà, sicuramente più corretta possibile ma pur sempre una approssimazione.
Programmato nel modo corretto, un computer quantistico potrebbe descrivere e replicare esattamente il processo oggetto di studio, perché attraverso i qubit sta utilizzando fenomeni quantistici, e non una approssimazione della realtà. Questo tema lo affronteremo anche nella prossima “lezione” in cui cercheremo di capire quali sono i possibili ostacoli al processo di computazione quantistica.
Credit:
Quantum Computation and Quantum Information – Nielsen & Chuang
Image credit: https://en.wikipedia.org/wiki/Shor%27s_algorithm
Laureato in fisica delle particelle, attualmente assegnista di ricerca presso i Laboratori Nazionali di Frascati-INFN e il CERN, si occupa dell’upgrade dell’esperimento CMS – Compact Muon Solenoid per il Large Hadron Collider.
