(articolo redatto da Domenico Di Mieri)
Siamo giunti al nostro settimo e ultimo approfondimento sul quantum computing.
Nei precedenti articoli, dopo un’introduzione generale, abbiamo visto:
- come installare l’ambiente di sviluppo (Anaconda e Jupyter Notebook);
- come creare un semplice circuito quantico che prende in ingresso due qubit e genera due qubit entangled (tramite l’operatore H di Hadamard);
- come simulare il circuito sul nostro computer (classico).
- come eseguire il circuito su un computer quantico reale
- come sfruttare l’entanglement per trasferire l’informazione contenuta in QBit
Finora abbiamo parlato di uno strumento che ci consente di creare in maniera intuitiva dei circuiti quantici che eseguono delle elaborazioni di diverso tipo.
Ti consigliamo di consultare la guida in linea di Qiskit per un elenco completo delle gate messe a disposizione dal framework.
Ma in cosa si differenzia veramente la programmazione di un computer quantico da quella di un computer classico derivante dal modello di Von Neumann?
In effetti si dimostra che un circuito classico è un caso degenere di un circuito quantico per cui, a patto di disporre di un numero di qubit sufficiente, tutto quello che può essere elaborato tramite un computer classico può essere trattato anche tramite un computer quantico.
Tuttavia è evidente che utilizzare un computer quantico come se fosse un computer normale porterebbe a risultati non molto diversi da quelli ottenuti dai processori oggi in commercio.
Ciò che veramente fa la differenza è l’introduzione di algoritmi che sono in grado di sfruttare le caratteristiche della meccanica quantistica, ovvero la sovrapposizione degli stati e l’entanglement.
Complessità computazionale
Per dimostrare che esistono algoritmi diversi e più performanti da quelli possibili usando l’informatica classica è necessario, innanzitutto, ricordare cos’è la complessità computazionale:
L’Enciclopedia Treccani scrive:
“Si definisce complessità computazionale l’operatore che fornisce il numero di operazioni necessarie a risolvere un determinato problema in funzione del numero di dati da trattare, usando l’algoritmo più efficiente possibile.”
Se, ad esempio, abbiamo un array non ordinato di n elementi e vogliamo trovare la prima occorrenza di uno specifico valore, non possiamo fare altro che effettuare una ricerca lineare del valore all’interno dell’array, confrontando uno per uno ogni elemento dell’array con quello che stiamo cercando.
Nel caso fortuito in cui il valore cercato è al primo posto nell’array, il numero di operazioni eseguite è 1, ma nel caso meno fortunato in cui l’elemento cercato è in ultima posizione, il numero di operazioni da effettuare è n.
In media, quindi, supponendo che la probabilità P(i) di trovare l’elemento cercato nella posizione i (con i tra 1 e n) abbia distribuzione uniforme, il numero di operazioni da effettuare nel generico caso è n/2.
Poiché si dimostra che l’algoritmo di ricerca sopra utilizzato è anche il migliore possibile, il problema di cercare un elemento in un array non ordinato ha complessità computazionale n/2 e si scrive O(n) per indicare che il numero di operazioni richieste in media è proporzionale (linearmente) alla cardinalità dei dati di input.
Tutti i problemi risolvibili con un numero di operazioni proporzionale ad n o al più ad una potenza intera di n sono detti di tipo polinomiale e si indicano con P (es. l’ordinamento di un array ha complessità O(n2), il calcolo del determinante di una matrice ha complessità O(n3)).
Questo tipo di problemi è risolvibile abbastanza facilmente tramite un computer classico e anche se al crescere di n i tempi di elaborazione possono essere molto lunghi questi restano sempre “accettabili” e probabilmente riducibili nel breve periodo grazie ai continui progressi dell’elettronica.
Esistono tuttavia molti problemi che non sono di tipo polinomiale e che richiedono tempi di elaborazione che crescono in maniera esponenziale all’aumentare della cardinalità dei dati di input.
Pensiamo, ad esempio, alla ricerca dei fattori primi di un numero intero.
L’algoritmo più veloce, ad oggi conosciuto, è chiamato “General Number Field Sieve” ed ha complessità esponenziale (cresce col numero di bit della parola). Questo tipo di problemi si avvantaggia molto poco dei miglioramenti tecnologici dei computer classici, mentre diventano “facilmente” risolvibili se li si guarda dal punto di vista dell’informatica quantistica.
Prima di continuare facciamo un esempio “semplice” in cui mostriamo come costruire un circuito quantico che sia più efficiente rispetto allo stesso circuito in informatica classica.
Algoritmo di Deutsch
David Deutsch è tra i fondatori del quantum computing. Nel 1985 ha pubblicato un documento intitolato “Quantum theory, the Church-Turing principle and the universal quantum computer” in cui per la prima volta descrive un algoritmo basato sul quantum computing che effettivamente è più veloce di un algoritmo classico.
Consideriamo tutte le possibili funzioni binarie di una variabile binaria x:
Le funzioni f1 e f4 sono dette “costanti” poiché il loro output è lo stesso a prescindere dal valore in input. Le funzioni f2 e f3, invece, sono dette “bilanciate” perché il loro output contiene tanti 0 quanti 1.
Supponiamo di avere un circuito che implementa una delle 4 funzioni di sopra, ma di non sapere quale.
Supponiamo di non essere interessati a sapere esattamente quale delle 4 funzioni è implementata dal circuito, ma semplicemente se si tratta di una funzione costante o di una funzione bilanciata.
Utilizzando un algoritmo classico dobbiamo necessariamente procedere come segue:
Fissiamo x = 0 ed effettuiamo la prima valutazione f(x).
Se f(x)=0 allora f(x) potrebbe essere sia f1(x) che f2(x) mentre se f(x)=1 potremmo trovarci nei casi f3(x) e f4(x).
Per saperlo, quindi, siamo costretti ad effettuare un’altra valutazione in x=1.
Usando un algoritmo classico, quindi, questo tipo di problema si risolve con due attivazioni del circuito.
Consideriamo ora il problema dal punto di vista quantistico.
Per prima cosa introduciamo il circuito in figura sotto:
Questo circuito trasforma:
Il circuito di sopra è una generalizzazione del problema precedente infatti il qubit di sopra viene trasformato nello stesso modo dell’esempio precedente, mentre il qubit di sotto viene trasformato nella maniera opposta.
Se utilizzassimo i qubit |0> e |1> per determinare se la funzione fi è costante o bilanciata dovremmo effettuare esattamente le stesse operazioni fatte con il circuito classico di sopra poiché il circuito quantico utilizzato non fornisce informazioni diverse da quello classico.
David Deutsch, però, intuì che se utilizziamo come input una superposizione degli stati |0> e |1> allora è sufficiente una sola attivazione del circuito per classificare la funzione.
Il circuito usato da Deutsch è il seguente:
La coppia di qubit (|0>, |1>) attraversa le due Gate di Hadamard e in ingresso alla gate arrivano i qubit nello stato
Ora se facciamo passare questo qubit nella gate
ovvero
Osserviamo ora che ||fi(0)>-|fi(0)⊕1> corrisponde ad uno dei valori |0>-|1> o |1> – |0> (a seconda che fi(0) sia 0 o 1) per cui possiamo scrivere:
|fi(0)>-|fi(0)⊕1> = (-1)fi(0)(|0> – |1>)
Allo stesso modo
|fi(1)>-|fi(1)⊕1> = (-1)fi(1)(|0> – |1>)
Lo stato dei qubit all’uscita della gate può, quindi, essere riscritto come segue:
ovvero
Il qubit in uscita sulla linea in alto (quella con il simbolo di misura a destra) prima della gate di Hadamard in uscita è, quindi:
mentre il qubit in basso è:
Si osservi che i due qubit non sono in stato entangled.
Consideriamo ora il valore del qubit in alto per le 4 funzioni possibili:
Ora la gate di Hadamard in uscita trasforma:
Quindi il qubit in alto alla nostra gate fi, una volta attraversata la porta di Hadamard sarà:
Misurando il qubit usando la base standard otteniamo, nei 4 casi di sopra:
Se, quindi, il nostro circuito misura 0 in uscita, allora la gate non può che implementare una delle funzioni costanti f1(x) o f4(x).
Se, invece, il circuito misura 1 in uscita, allora la gate è una delle funzioni bilanciate f2(x) o f3(x).
Con questo abbiamo dimostrato che tramite le proprietà della meccanica quantistica (entanglement e sovrapposizione degli stati) riusciamo a costruire un circuito quantico più efficiente di uno classico e capace di risolvere in molto meno tempo lo stesso problema in maniera esatta.
Naturalmente l’algoritmo di sopra ha scarso utilizzo pratico ed è stato appositamente studiato per dimostrare che esistono problemi che in informatica classica sono di complessità NP e che possono, invece, essere risolti con algoritmi di complessità P sui computer quantistici.
Algoritmo di Deutsch-Jozsa
Una generalizzazione dell’algoritmo di Deutsch detta algoritmo di Deutsch-Jozsa consente di estendere il discorso ad una funzione binaria di n variabili binarie.
Non ne daremo una dimostrazione, ma chi fosse interessato può trovare informazioni sul sito IBM in cui sono specificati anche i passaggi pratici da seguire per testare i risultati.
L’algoritmo di Shor per la fattorizzazione in numeri primi
L’algoritmo di Shor richiede la conoscenza di concetti di matematica avanzata e per questo ne daremo solo una descrizione sommaria.
L’algoritmo si basa su una gate fondamentale chiamata quantum Fourier Transform gate.
La gate di Fourier può essere vista come una generalizzazione della gate di Hadamard e nel caso di un qubit le due gate coincidono.
La differenza fondamentale tra la gate di Fourier e quella di Hadamard è che la porta di Fourier viene descritta tramite una matrice di ordine n i cui coefficienti sono numeri complessi (radici complesse dell’unità). La matrice della trasformata quantica di Fourier su n bit contiene tutte le 2n radici complesse dell’unità.
L’algoritmo di Shor è, per certi versi, simile all’algoritmo di Simon (di cui non abbiamo parlato, ma che serve per calcolare il periodo di una funzione periodica) dove, però, il ragionamento è fatto sulla matrice della trasformata quantica di Fourier.
Conoscendo un numero intero N, vogliamo calcolare i fattori primi p e q.
L’algoritmo sceglie un numero a tale che: 1 < a < N e verifica se a ha qualche fattore in comune con N, se la condizione è vera possiamo dedurre che a è un multiplo di p o q ed è facile concludere l’algoritmo di fattorizzazione. Se a, invece, non ha fattori in comune con N allora l’algoritmo calcola a mod(N), a2 mod(N), a3 mod(N) e così via. Dato che i valori della sequenza sono tutti modulo N essi saranno sempre minori di N stesso e, di conseguenza, ci sarà un periodo r per cui ai mod(N)=a(i+r) mod(N). L’algoritmo di Shor è in grado di calcolare proprio il periodo r. Una volta noto il periodo si possono utilizzare degli algoritmi di tipo classico per calcolare i fattori p e q di N.
Questo è, per grandi linee, come funziona l’algoritmo di Shor per la fattorizzazione dei numeri nel prodotto di due primi.
Se si vuole approfondire l’argomento si può dare un’occhiata al link:
https://qiskit.org/textbook/ch-algorithms/shor.html
Si osservi che l’algoritmo di Shor è stato implementato e testato per fattorizzare numeri “piccoli”, ma man mano che i computer quantici si dotano di un numero sempre maggiore di qubit, sarà presto possibile fattorizzare anche numeri di 1024 o 2048 bit nel giro di pochi secondi.
Questo metterà in serio pericolo tutti i sistemi basati sulla codifica RSA ed è per questo che assumono sempre maggiore interesse gli algoritmi Quantum Proof.
Si veda, ad esempio: https://en.wikipedia.org/wiki/Post-quantum_cryptography
Conclusioni
Con questo articolo, si conclude la serie di approfondimenti sul quantum computing pubblicati nel nostro blog. Continua a seguirci per rimanere sempre al passo con le ultime frontiere dello sviluppo software.
Se anche tu vuoi occuparti di progetti di sviluppo software di ultima generazione
dai un’occhiata alle nostre opportunità di lavoro e conosciamoci subito!
