INFORMATICA - QUANTUM COMPUTING - ANNEAL 3

Maggio 2025

1. Software per convertire generici circuiti digitali in BQM

Facendo seguito a quanto spiegato nella pagina Quantum Annealing 2 ho realizzato un software in python che converte qualsiasi circuito digitale asincrono in una matrice Q alla base di una forma quadratica binaria (BQM) il cui minimo descrive perfettamente il comportamento elettronico del circuito stesso.

Il citato software è liberamente accessibile su github: github.com/mmattiucci2024/circuit_encoder_for_dwave e vi sono anche riportati tre esempi applicativi a grado di complessità crescenti: (1) la costruzione e conversione di una NAND; (2) la costruzione e conversione in di un simple adder (sommatore a due bit con riporto); (3) la costruzione e conversione in BQM di un full adder (sommatore a tre bit con riporto in ingresso e uscita). Tali esempi determinano delle matrici Hamiltoniane Q che possono essere usate sia su Quantum Annealer DWAVE che su emulatori di quantum annealing o QUBO solver di varia tipologia.

Per un utile confronto, nello stesso software sono riportati due QUBO Solver: un bruteforce solver che esplora tutte le combinazioni binarie del BQM fino a trovare il minimo della funzione quadratica, e un simulatore di quantum annealing che opera su base probabilistica con dei numeri random. I primi due circuiti generano una piccola matrice Q e la risoluzione bruteforce è possibile. Il terzo circuito non consente l'impiego del bruteforce (almeno senza usare computer ad alte prestazioni o paralleli).

2. Funzionamento del software

Il software parte dalle matrici Q delle porte logiche di base già individuate nella pagina Quantum Annealing 2:

quando si crea il nuovo oggetto (dalla classe) "myDigitalCirtuit" si devono obbligatoriamente elencare tutte le porte logiche che formano il circuito, nell'ordine che si ritene utile dal punto di vista mnemonico, in conseguenza di ciò il software pone sulla diagonale principale di una matrice piena di zeri tutte le relative matrici Q di ognuna della porte elencate. Un esempio chiarirà in maniera semplice il fatto, faremo riferimento al circuito di esempio 0 (quello più elementare) nel software:

Il costruttore circuit_0 = myDigitalCirtuit(["and","not"]) determina una matrice Q che non considera i collegamenti tra le porte logiche:

0 1 -2 0 0
0 0 -2 0 0
0 0 3 0 0
0 0 0 -1 2
0 0 0 0 -1

in cui è semplice verificare la presenza delle due Qand e Qnot. A questo punto, per collegare la NOT (indice 3 partendo da 0 della matrice) all'uscita della AND (indice 2 della matrice) basta applicare quanto visto in Quantum Annealing 2 per integrare nella BQM il polinomio (x2-x3)2 la cui minimizzazione porta a far coincidere i due valori x2 e x3. Quindi si aggiunge 1 alle posizioni (2,2) e (3,3) e si aggiunge -2 a (2,3) (il tutto dallo sviluppo del quadrato del binomio visto). Il software imposta il collegamento tramite il metodo della classe che segue:

circuit_0.set_link(gate_idx_1 = 0, connection_idx_1 = 2,
gate_idx_2 = 1, connection_idx_2 = 0)

0 1 -2 0 0
0 0 -2 0 0
0 0 4 -2 0
0 0 0 0 2
0 0 0 0 -1

Questa è la matrice Q di una NAND e infatti il software, impiegando i due QUBO solver determina i minimi in corrispondenza delle seguenti combinazioni binarie (che vanno a formare la tabella di verità del circuito):

######################################
Bruteforce QUBO solver is working...
everything done.
Truth table solutions:
0 1 - 4 (input and output indexes of the matrix Q)
0 0 - 1 min= -1
0 1 - 1 min= -1
1 0 - 1 min= -1
1 1 - 0 min= -1
######################################
Simulated annealing QUBO solver:
Max number of attempts to use the simulated annealing process: 100
Max number of annealing iterations: 1000
Starting temperature: 100
Cooling rate: 0.99
Processing...
everything done.
Truth table solutions:
0 1 - 4 (input and output indexes of the matrix Q)
0 0 - 1 freq = 100 / 100
0 1 - 1 freq = 100 / 100
1 0 - 1 freq = 100 / 100
1 1 - 0 freq = 100 / 100

in entrambi i casi i solver individuano in maniera praticamente certa la tabella di verità di una NAND.

Gli altri due esempi nel software sono circuiti via via più complessi e naturalmente determinano matrici Q sempre più grandi. Per il circuito 1 (simple adder) si ha:

1 2 0 0 0 0 0 0 -2 0 0 0 0 -2 0 0
0 0 -2 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 -2 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 -2 -2 0 0 0 0 0 0 0 0 0 0
0 0 0 0 4 0 0 0 0 0 -2 0 0 0 0 0
0 0 0 0 0 1 2 0 0 0 0 0 0 0 -2 0
0 0 0 0 0 0 0 -2 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 -2 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 -2 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 4 0 -2 0 0 0 0
0 0 0 0 0 0 0 0 0 0 2 1 -2 0 0 0
0 0 0 0 0 0 0 0 0 0 0 2 -2 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 -2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 -2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3

e il software determina come tabelle di verità:

######################################
Bruteforce QUBO solver is working...
Evaluated 65536 solutions
everything done.
Truth table solutions:
0 5 - 15 12 (input and output indexes of the matrix Q)
0 0 - 0 0 min= -2
0 1 - 0 1 min= -2
1 0 - 0 1 min= -2
1 1 - 1 0 min= -2
######################################
Simulated annealing QUBO solver:
Max number of attempts to use the simulated annealing process: 100
Max number of annealing iterations: 1000
Starting temperature: 100
Cooling rate: 0.99
Processing...
everything done.
Truth table solutions:
0 5 - 15 12 (input and output indexes of the matrix Q)
0 0 - 0 0 freq = 97 / 100
0 1 - 0 1 freq = 89 / 100
1 0 - 0 1 freq = 90 / 100
1 1 - 1 0 freq = 89 / 100

si può ora notare che il brute force solver ha svolto oltre 65000 valutazioni per soli 2 bit in ingresso e che il minimo trovato per ogni combinazione binaria è proprio la somma dei primi due bit. Lo stesso accade per il simulatore di quantum annealing ma è interessante osservare che mentre per la NAND le frequenze di successo erano tutte 100/100 qui iniziano a scendere, ossia l'algoritmo trova la soluzione ma inizia a sbagliare di tanto in tanto (come accade per i computer quantistici dopotutto :-) ).

Infine per il circuito 2 la matrice non sarà qui riportata per ragioni di praticità ma vedremo la soluzione trovata solo dai solver basati su quantum annealing (vero o simulato che sia):

######################################
Simulated annealing QUBO solver:
Max number of attempts to use the simulated annealing process: 100
Max number of annealing iterations: 1000
Starting temperature: 100
Cooling rate: 0.99
Processing...
everything done.
Truth table solutions:
0 5 18 - 34 25 (input and output indexes of the matrix Q)
0 0 0 - 0 0 freq = 29 / 100
0 0 1 - 0 1 freq = 22 / 100
0 1 0 - 0 1 freq = 24 / 100
0 1 1 - 1 0 freq = 25 / 100
1 0 0 - 0 1 freq = 25 / 100
1 0 1 - 1 0 freq = 32 / 100
1 1 0 - 1 0 freq = 34 / 100
1 1 1 - 1 1 freq = 18 / 100

invito a verificare che le frequenze di successo sono molto più basse di prima. Determinano ancora un risultato corretto, la somma delle prime tre colonne di bit, ma la quantità di errori è aumentata. In ogni caso il simulatore probabilistico almeno trova i risultati, quello bruteforce non vi riesce affatto su PC comuni.

3. Uso del computer quantistico di DWAVE

Come detto, il software realizzato determina la matrice Q per qualsiasi circuito digitale asincrono. Tale matrice registrata su file e poi trattata come da altro software che ho realizzato e inserito nel medesimo repository, permette di programmare e impiegare i computer quantistici di DWAVE direttamente (bisogna avere un abbonamento temporaneo o permanente per eseguire tale codice python). In pratica il sistema DWAVE in cloud assorbe la matrice Q che il software prepara, tramite rete Internet e trova i minimi e quindi le citate tabelle di verità che anche il simulatore trovava. Ciò naturalmente con errori di molto inferiori e con tempi di pochi secondi. Invito quindi a visionare il software Qdecode_dwave.py su:
github.com/mmattiucci2024/circuit_encoder_for_dwave
e usarlo in combinazione con Qencode.py al fine di provare a programmare il DWAVE creando delle "semplici" simulazioni di circuiti digitali comunque complessi.

Di fatto il software precedente Qencode.py incorpora l'algoritmo per dimostrare in maniera costruttiva quanto indicato nella pagina precedente Quantum Annealing 2 che qualsiasi circuito digitale asincrono può essere emulato, nelle sue funzioni logiche, da un computer quantistico basato sul quantum annealing, risultato principale di questo lavoro.

4. Conclusioni

Programmare un computer quantistico di DWAVE significa determinare delle matrici Q triangolari alte, con particolari caratteristiche matematiche, la cui associata forma quadratica BQM ha dei minimi che descrivono il risultato dell'algoritmo che si intende implementare. Mentre quindi nei computer classici si scrivono degli algoritmi in un qualche linguaggio di programmazione, in DWAVE si trasformano i problemi cui gli algoritmi dovrebbero dare una risposta in problemi di ottimizzazione (trovare il minimo di una funzione quadratica descritta dalla matrice Q).

I metodi per trovare Q non sono sempre gli stessi, non sono completamente sistematizzabili (al momento), richiedono inventiva e possono essere diversi (ossia per uno stesso problema si possono trovare differenti Q che lo descrivono con - più o meno - i medesimi risultati). Il software di questa pagina individua una classe di problemi (emulare circuiti digitali) e determina un metodo sistematico per generare Q che descrive il circuito digitale. In pratica, con questo software si può programmare DWAVE a risolvere questo problema senza saper programmare il computer quantistico di DWAVE. Ciò è determinante come approccio, al momento i computer quantistici, siano essi gate-based o quantum annealer hanno una programmazione senza astrazione, troppo legata al loro funzionamento hardware. E' anche difficile dire che esista un vero linguaggio di programmazione dei computer quantistici, di fatto quelli esistenti sono adattamenti dei linguaggi esistenti (ad esempio il python) atti a comandare specifiche funzioni hardware estremamente peculiari del singolo sistema da programmare (questa cosa ricorda allo scrivente, non più giovane, la programmazione dei vecchi sistemi embedded, ad esempio a 16 anni mi cimentavo nel programmare un plotter comandato da un sistema dedicato HP ad esso integrato per fargli risolvere e graficare una banale equazione differenziale lineare con soluzione 1-exp(-t/tau)... peccato che avessi a disposizione solo 128 BYTE per farlo, dati e assembler inclusi :-))) con i computer quantistici non siamo distanti da questo modo arcaico di lavorare).

marcomattiucci.it

Informatica:

Quantum Computing: