INFORMATICA - QUANTUM COMPUTING - ANNEAL 1

Ottobre 2023

1. Un altro modo di programmare i sistemi quantistici

Facendo riferimento alle risorse DWAVE (https://www.dwavesys.com/ disponibili in cloud anche su Amazon AWS) proviamo a capire quest'altro modo di programmare i sistemi di elaborazioni quantistici (profondamente diverso da quanto visto nella precedente pagina sulla programmazione gate-based) che peraltro sta avendo notevole successo anche in ambito commerciale e quindi non è solo aspetto di ricerca scientifica. Il quantum annealing è una procedura basata su principi quantistici che riesce ad inviduare stati a minima energia di sistemi descritti mediante particolari funzioni dette Hamiltoniane (non è qui la sede di approndire questi aspetti matematici e fisici). I sistemi DWAVE sono formati da reticoli di QPU (Quantum Processor Unit) che realizzano via hardware la procedura di annealing. Tali QPU sono in grado di determinare minimi assoluti e ottimi minimi con grande efficienza, garantendo sia la determinazione di soluzioni perfette che di soluzioni approssimate probabilistiche o intermedie.

2. Programmare definendo matrici...

La citata funzione Hamiltoniana che considereremo per i sistemi DWAVE è detta QBM (Binary Quadratic Model), in particolare l'ottimizzazione delle QPU DWAVE fa riferimento al QUBO (Quadratic Unconstrained Binary Optimization) che, in maniera semplificata è definita attraverso:
(a) X=[x1,x2,...xn] n variabili di stato del sistema considerato che possono assumere solo valori 0 e 1 (binarie);
(b) una matrice triangolare superiore Q (per la quale gli elementi della matrice sotto la diagonale principale sono tutti nulli).

La funzione è una classica funzione quadratica che, in notazione matriciale, si può scrivere: H(X) = XT Q X (dove X è un vettore colonna e XT il suo trasposto ossia un vettore riga, il prodotto è quello matriciale riga per colonna).

Le QPU dei sistemi DWAVE trovano efficacemente minimi di H(X) determinando il vettore di stato X in corrispondenza di tale minimo, il quale, è proprio l'output dell'elaborazione. L'input dell'elaborazione è la matrice Q che descrive il sistema in studio. Programmare in DWAVE significa soprattutto essere molto bravi nel determinare la matrice Q (non necessariamente unica) per il sistema che si vuole emulare quantisticamente. La parola "emulare" non è stata introdotta a caso, infatti una delle migliori applicazioni pratiche del quantum annealing è elaborare nuove molecole emulando gli stati energetici (nuovi farmaci, nuovi vaccini, ecc.), oppure sistemi che sono troppo complessi per avere una descrizione classica in termini analitici (sistemi finanziari, logistici, ecc.).

3. Un esempio di programmazione

Ipotizziamo di voler emulare il comportamento di una classica porta NOT digitale, quindi la tabella di verità:
1 = NOT(0) e 0 = NOT(1).

Iniziamo considerando la porta NOT come un sistema unico con due variabili di stato x1 e x2 corrispondenti rispettivamente a input e output. In senso quantistico ci sono 4 combinazioni possibili delle due variabili binarie x1 e x2 ognuna delle quali determina uno stato energetico. Attenzione che la NOT sembra ammettere solo due combinazioni possibili ma questo è vero solo in senso matematico, nella realtà i circuiti elettronici che determinano le NOT non sono sempre completamente deterministici e talvolta, soprattutto ad alta velocità e ad alte temperature sbagliano (la correzione errori è un capitolo estremamente importante nella realizzazione di un calcolatore elettronico). L'approccio quantistico quindi non deve sorprendere, la funzione Hamiltoniana si può pensare come questa tabella:
x1 - x2 - H(X) dove X=[x1,x2]
0 - 0 - H([0,0])
0 - 1 - H([0,1])
1 - 0 - H([1,0])
1 - 1 - H([1,1])
dato il funzionamento della NOT i minimi della H(.) dovranno essere in corrispondenza di H([0,1]) e H([1,0]) che (se la NOT funziona bene) dovrebbero essere gli stati altamente più probabili (la natura segue sempre percorsi a minima energia per cui al minimo dell'energia corrisponde il massimo della probabilità di persistenza dello stato del sistema).

A questo punto, stabilita la descrizione di massima del sistema da emulare con le QPU è necessario determinare la matrice Q, la quale dovrà determinare una funzione quadratica H(.) che abbia le caratteristiche appena evidenziate per la NOT. Non esiste un metodo unico per ottenere tale matrice, ciò richiede parecchia esperienza e programmatori diversi possono trovare Q diverse ugualmente rispondenti, magari con livelli di ottimizzazione raggiungibili differenti in fase di elaborazione.

Per la NOT, data la semplicità del sistema, bisogna fare in modo che H(.) dia valori bassi nei casi in cui x1 e x2 assumano valori differenti. Ad esempio:
H1(x1,x2) = -x1 + -x2 + 2x1,x2
determina -1 per H1([0,1]) e H1([1,0] e 0 per le altre 2 combinazioni per cui potrebbe andare. In termini matriciali, ricordando che per variabili binarie x2 = x, la matrice corrispondente Q1 si può scrivere facilmente come:

che è anche una matrice diagonale superiore.


Quindi una funzione H1(.) BQM di una NOT è:

traducendo in python e invocando le librerie e i servizi DWAVE (esecuzione del programma quantistico):

from dwave.system
import DWaveSampler, EmbeddingComposite
sampler = EmbeddingComposite(DWaveSampler())
Q1 = {('x1', 'x1'): -1, ('x1', 'x2'): 2, ('x2', 'x1'): 0, ('x2', 'x2'): -1}
sampleset = sampler.sample_qubo(Q1, num_reads=5000, label='NOT Gate')
print(sampleset)
n. x1 x2 energy num_oc. chain_.
0 0 1 -1.0 2226 0.0
1 1 0 -1.0 2732 0.0
2 0 0 0.0 1 0.0
3 1 1 0.0 1 0.0
['BINARY', 4 rows, 5000 samples, 2 variables]

come si può vedere dal codice, su 5000 campionamenti del sistema di annealing:
(a) solo 2 ricadono in ipotesi di malfunzionamento della NOT (valori di ingresso e uscita x1 e x2 uguali);
(b) il funzionamento della NOT non appare esattamente simmetrico come ci si dovrebbe aspettare in teoria ma plausibilmente tale.
Il punto (b) dipende da fluttuazioni casuali ma anche dalla struttura della stessa H(.) e del reticolo di QPU.

Programmare il sistema di quantum annealing quindi, significa determinare la matrice Q e uno stesso sistema può essere descritto energeticamente da diverse matrici Q (che è equivalente a dire che si possono scrivere più programmi quantistici per descrivere uno stesso sistema). Se si considera, ad esempio, la matrice:

essa rappresenta ancora una NOT ma i minimi in corrispondenza delle due situazioni in cui la porta dovrebbe operare correttamente sono stavolta diversi per cui si introduce un'ulteriore perturbazione all'emulazione del sistema considerato.

4. Un altro esempio: emulare una porta OR

Dato che una porta OR ha 3 connettori (due di ingresso e una di uscita) la considereremo come un sistema quantistico con uno vettore di stato X=[x1,x2,x3], dove x1 e x2 sono gli ingressi e x3 l'uscita (x3=OR(x1,x2)). Analogamente a quanto fatto prima per la NOT, si possono considerare tutte le combinazioni binarie delle variabili di stato individuate e quindi:
x1 - x2 - x3 - H(X)
0 - 0 - 0 - H([0,0,0])
0 - 0 - 1 - H([0,0,1])
0 - 1 - 0 - H([0,1,0])
0 - 1 - 1 - H([0,1,1])
1 - 0 - 0 - H([1,0,0])
1 - 0 - 1 - H([1,0,1])
1 - 1 - 0 - H([1,1,0])
1 - 1 - 1 - H([1,1,1])
considerato il funzionamento della OR i minimi della H(.) dovranno essere in corrispondenza di H([0,0,0]), H([0,1,0]), H([1,0,1]) e H([1,1,1]), mentre tutte le altre combinazioni dovrebbero risultare a probabilità molto bassa e quindi a energia più alta di questi.

Non è difficile verificare che la matrice Q3 che segue soddisfa quanto evidenziato e quindi è il nostro quantum-software per emulare su DWAVE la OR.


La funzione quadratica H3(.) che ne consegue, infatti, ha minimi in:

0 - 0 - 0 - H3([0,0,0]) = 0
0 - 1 - 1 - H3([0,1,1]) = 0
1 - 0 - 1 - H3([1,0,1]) = 0
1 - 1 - 1 - H3([1,1,1]) = -1
mentre nelle rimanenti combinazioni (improbabili) assume valori superiori:
0 - 0 - 1 - H3([0,0,1]) = 1
0 - 1 - 0 - H3([0,1,0]) = 1
1 - 0 - 0 - H3([1,0,0]) = 1
1 - 1 - 0 - H3([1,1,0]) = 2

Quale esercizio per il lettore si lascia determinare la matrice Q per una AND, in una prossima pagina sull'argomento programmazione quantum annealing vedremo come programmare un generico sistema digitale composto da n porte logiche interconnesse e altro per cui descriverò anche la soluzione.

5. Conclusioni

La programmazione in questo ambito risente molto dell'area di applicazione, assomiglia alla programmazione dei sistemi fortemente embedded dei primi tempi dell'informatica e sicuramente non si può considerare un metodo generalizzato di programmazione come quello gate-based. Resta il fatto che questa tipologia di elaboratori quantistici viene già impiegata con successo in diversi settori industriali proprio per la sua capacità di risolvere ad velocemente problemi di ottimizzazione ad elevatissima complessità (dell'ordine di milioni di variabili di stato: una strabiliante applicazione è la rilocazione dinamica delle risorse - tempo reale - tra gli ospedali dell'area di Los Angeles, un'altra la gestione delle movimentazione logistica di grandi porti marittimi, ancora, la gestione tempo reale della logistica dei mezzi di trasporto per corrieri con migliaia di vettori, ecc.).

marcomattiucci.it

Informatica:

Quantum Computing: