INFORMATICA - QUANTUM COMPUTING - ANNEAL 2

Maggio 2024

1. Le porte digitali base nel BQM

Facendo seguito a quanto spiegato nella pagina Quantum Annealing 1 andremo ora a vedere come rappresentare le porte logiche base (e non solo) nel BQM (Binary Quadratic Model), ossia nelle forme matriciale impiegabili da questi particolari sistemi quantistici (quali ad es. DWAVE). Partiremo da questo per vedere come queste rappresentazioni matriciali sono determinabili matematicamente ed empiricamente (in pratica vedremo come programmare nel quantum annealing) per poi capire come emulare, attraverso una matrice BQM qualsiasi circuito digitale classico asincrono.

Sempre nella pagina precedente Quantum Annealing 1 erano stati riportati quali esempi la matrice Q della porta NOT e quella della porta OR. Tale matrice, nella relativa forma quadratica H(X) = XT Q X genera dei minimi che devono corrispondere agli stati di funzionamento corretti (qui sotto evidenziati in giallo) delle relative porte logiche. Considerando ogni pin di ingresso ed uscita delle porte come uno stato quantistico binario (so che sembra strano ma è un assunto di natura puramente matematica molto utile) si avrebbero le seguenti combinazioni:

Porta NOT:

dove:

e la matrice Q (come già indicato nella pagina precedente) deve essere triangolare superiore per cui può essere scritta come:

A questo punto, delle 4 combinazioni di coppie di stati della porta NOT, i due di interesse (perchè descrivono correttamente il funzionamento della NOT) sono il secondo e il terzo (ripeto, evidenziati in giallo); inoltre considerando che H([0,0]) è sicuramente nullo (basta svolgere il prodotto righe per colonne della forma quadratica) ed è uno stato scorretto per la NOT, lo si imposterà come massimo della funzione (ricordiamo che lo scopo dei sistemi computazionali di quantum annealing è trovare dei minimi della forma quadratica). Quindi, impostando a = c = -1 si ha facilmente b = 2 e si determina la matrice (il "software") per emulare la NOT che abbiamo già incontrato nella pagina precedente Quantum Annealing 1.

Come si può vedere l'atto "creativo" della programmazione è "solo" lavorare sui parametri in maniera tale che le 4 condizioni elencate risultino soddisfatte tutte simultaneamente (per la gioia dei matematici la programmazione qui è intesa come lavorare con i numeri per soddisfare equazioni e disequazioni).

Nel caso della porta OR il sistema è un poco più complicato:

dove:

e la matrice triangolare questa volta è:

impostando a = d = f = 1 si ha, risolvendo il sistema di equazioni, b = 1, c = -2 ed e = -2, da cui:

Va osservato che questa matrice per la porta OR è diversa da quella presentata nella pagina precedente Quantum Annealing 1 (sebbene entrambi valide). La differenza importante è che per questa QOR i minimi della H() sono tutti uguali (ossia 0) per cui gli stati corretti saranno individuati dal quantum annealer con la stessa probabilità a parità di vincoli imposti al sistema. Al contrario per la Q3 della pagina precedente lo stato [1,1,1] è di certo più gettonato degli altri stati corretti perchè il suo minimo è assoluto (cioè -1) rispetto a tutte le combinazioni.

Infine, per completare le porte di base, studiamo la porta AND:

dove gli schemi della forma quadratica H() e della matrice triangolare sono gli stessi della OR per cui, dato che d ed a sono già definiti come nulli, impostando f = 3 e si ha b = 1 mentre c = e = -2.

Si noti che anche in questo caso i minimi della H() sono tutti uguali (ossia 0). Si lascia come esercizio per il lettore la determinazione della matrice Q per la porta NAND e la XOR che risultano le seguenti:

Si segnala che per la XOR non è possibile ottenere minimi tutti uguali (a zero) come fatto per tutte le altre porte (naturalmente se qualcuno dei lettori trova il modo mi faccia sapere perchè ci sono problemi matematici nel risolvere la questione). Ad ogni modo il problema sarà perfettamente aggirato nel prossimo paragrafo introducendo la possibilità di costruire sistemi digitali più complessi, nell'ottica di determinarne le matrici Q, partendo dalle porte già analizzate sopra.

2. Sistemi digitali asincroni nel BQM

Come noto, le combinazioni (NOT,AND) e (NOT,OR) sono dette basi per qualsiasi sistema digitale ossia con sole porte AND e NOT, così come con sole porte OR e NOT, è possibile realizzare qualsiasi funzione booleana e quindi qualsiasi circuito digitale classico asincrono. Al momento, grazie al paragrafo precedente, abbiamo le matrici Q delle basi ma ipotizzando di avere un qualsiasi circuito digitale come il seguente:

come si può individuare la matrice Q che gli equivale?

Trattasi naturalmente di un problema di programmazione nel senso dei sistemi di quantum annealing. Di seguito vedremo un metodo semplice ed automatizzabile per conseguire il citato obiettivo. Potrebbe non essere unico, io stesso ne ho individuati altri, ma per semplicità, comprensibilità ed efficienza il seguente è in assoluto il mio preferito (oltretutto è facilmente implementabile in un qualsiasi linguaggio di programmazione, es. python). Vedremo infatti come costruire la matrice Q di tutto il sistema partendo dalle matrici Q delle varie porte base. Di fatto ci stiamo comportando esattamente come quando, programmando classicamente, costruiamo delle subroutine o delle function e le riutilizziamo per costruire software più complessi.

Le uniche porte presenti nel circuito in esame sono la AND e la NOT, per cui consideriamo le matrici QAND e QNOT ed accorpiamole secondo il semplice schema che segue:

questa nuova matrice 5x5 descrive in senso generico gli stati combinati e indipendenti della AND e della NOT (se avete curiosità ricercate i minimi della corrispondente funzione quadratica H() e vedrete che tutto corrisponde come se le due porte lavorassero isolate - ciò ricorda molto il prodotto tensoriale visto nelle altre pagine sul quantum computing). Ora è necessario correlare gli stati della AND e della NOT nel modo corretto. Precisamente gli stati x2 (uscita della AND) e x3 (ingresso della NOT) devono corrispondere perfettamente (che equivale a considerare il fatto che siano collegati). Si tratta in definitiva di un vincolo strutturale (dovuto al circuito) da applicare alla ricerca del minimo, esso non può essere ricercato in tutto lo spazio delle possibili soluzioni ma solo in quello in cui x2 e x3 corrispondono. L'ottimizzazione con vincoli è trattata senza problemi dai sistemi di quantum annealing (lo stesso DWAVE provvede funzioni in tal senso), in ogni caso, di seguito vedremo un modo matematico per gestire il vincolo specifico in trattazione molto semplice ed efficace.

Infatti, nell'ipotesi che x2 e x3 debbano essere prossimi tra loro il fattore (x2 - x3)2 (sicuramente positivo) deve risultare minimo. In pratica possiamo convertire il vincolo sullo spazio delle soluzioni in funzione di penalizzazione alterando la H() (quindi la matrice Q 5x5) in maniera tale che includa (x2 - x3)2. In questo modo il sistema di quantum annealing, andando alla ricerca del minimo globale, terrà implicitamente conto del fatto che x2 e x3 devono convergere tra loro.
Alterare la matrice Q non è difficile dato che:

ed è anch'essa una forma quadratica i cui coefficienti cerchiati in rosso possono essere sommati alla matrice direttamente come segue, in corrispondenza delle variabili di stato x2 e x3:

Come era intuibile la nuova matrice 5x5 che si ottiene, rispetto alle variabili x0 e x1 come input e x4 come output rappresenta anch'essa una matrice Q della porta NAND che poi equivale al circuito che abbiamo analizzato. I minimi di H() degli stati corretti sono tutti uguali a -1 (potete fare il calcolo per verificare).

Vediamo ora un circuito leggermente più impegnativo e calcoliamo anche per esso la matrice Q:

Impiliamo tutte le porte presenti in maniera indipendente lungo la diagonale come fatto prima definendo la matrice iniziale (il formalismo, per comodità è l'output del python):
[[-1 2 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 -1 2 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 1 -2 0 0 0 0 0 0]
[ 0 0 0 0 0 0 -2 0 0 0 0 0 0]
[ 0 0 0 0 0 0 3 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 -2 0 0 0]
[ 0 0 0 0 0 0 0 0 0 3 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 1 -2]
[ 0 0 0 0 0 0 0 0 0 0 0 0 1]]
non è difficile individuare le singole matrici 3x3 e 2x2 delle porte base: dalla OR in fondo a destra, poi a salire le due AND e infine a sinistra le due NOT. Sono ora da considerare ben 5 fattori di penalizzazione corrispondenti a 5 collegamenti presenti nel circuito: (9,10), (6,11), (1,8), (3,5), (2,7) e (0,4). Alterando di conseguenza la matrice precedente di volta in volta con i coefficienti dei binomi al quadrato come eseguito per il circuito precedente si ha la nuova matrice QXOR:
[[ 0 2 0 0 -2 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0 -2 0 0 0 0]
[ 0 0 0 2 0 0 0 -2 0 0 0 0 0]
[ 0 0 0 0 0 -2 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 1 -2 0 0 0 0 0 0]
[ 0 0 0 0 0 0 4 0 0 0 0 -2 0]
[ 0 0 0 0 0 0 0 1 1 -2 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 4 -2 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 2 -2]
[ 0 0 0 0 0 0 0 0 0 0 0 0 1]]
per la quale, analizzando i minimi della corrispondente funzione quadratica rispetto agli ingressi 4 e 7 e all'uscita 12, fornisce (direi senza sorprese dato che il circuito in studio è un sistema canonico) la tabella di verità di una XOR. Aspetto rilevante è che tutti i minimi per gli stati corretti della XOR questa volta sono uguali a -2, superando il problema indicato per questa porta al paragrafo precedente con una Q di dimensione 3x3.

3. Valori 0 e 1 nel BQM - gli oracoli

Oltre le porte logiche, nei sistemi digitali, esiste anche la necessità di impostare delle linee a 0 o a 1 logico. L'emulazione di 0 ed 1 nell'ambito del quantum annealing può essere fatta come prima attraverso dei vincoli sullo spazio di ricerca del minimo. Se ad esempio una linea xi deve essere settata a 1 o resettata a 0 si possono impostare gli elementari vincoli xi = 1 o xi = 0.

In alternativa, anche in questo caso si può agire matematicamente sulla matrice del sistema impostando una penalizzazione. Infatti:

quindi per impostare xi ad 1 basta modificare il valore della diagonale della matrice nella posizione (i.i) sottraendo 1, al contrario, per resettare xi a 0 è sufficiente sommare al valore nella stessa posizione (i,i) la quantità 1. Di fatto stiamo trattando 0 ed 1 non come porte logiche ma come "oracoli" nel classico senso computazionale (generatori di risultati di elaborazione generalmente istantanei senza tenere conto di come generino i loro risultati). Sottolineo che i concetti di oracolo computazionale, oracolo di Turing e oracolo quantistico sono piuttosto comuni nel quantum computing (avevo introdotto qualcosa in questa pagina sull'ipercomputazione).

Passando ad un'applicazione pratica, consideriamo la matrice QXOR di prima ed impostiamo la linea 4 a 0 e la linea 7 a 1 (i due ingressi). La matrice che si ottiene è banalmente (in grassetto i valori sulla diagonale modificati):
[[ 0 2 0 0 -2 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0 -2 0 0 0 0]
[ 0 0 0 2 0 0 0 -2 0 0 0 0 0]
[ 0 0 0 0 0 -2 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 1 -2 0 0 0 0 0 0]
[ 0 0 0 0 0 0 4 0 0 0 0 -2 0]
[ 0 0 0 0 0 0 0 0 1 -2 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 4 -2 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 2 -2]
[ 0 0 0 0 0 0 0 0 0 0 0 0 1]]
che ha una H() con un unico punto di minimo assoluto di valore -3 per il quale x12 = 1 (corretto output dello XOR tra 0 ed 1). Se invece proviamo ad impostare la linea 4 a 1 e la linea 7 a 1 si ha la matrice (in grassetto i valori sulla diagonale modificati):
[[ 0 2 0 0 -2 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0 -2 0 0 0 0]
[ 0 0 0 2 0 0 0 -2 0 0 0 0 0]
[ 0 0 0 0 0 -2 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 1 -2 0 0 0 0 0 0]
[ 0 0 0 0 0 0 4 0 0 0 0 -2 0]
[ 0 0 0 0 0 0 0 0 1 -2 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 4 -2 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 2 -2]
[ 0 0 0 0 0 0 0 0 0 0 0 0 1]]
la cui forma quadratica H() ha un unico punto di minimo assoluto di valore -4 per il quale x12 = 0 (corretto output dello XOR tra 1 ed 1).

4. Conclusioni

La fondamentale risultanza tecnica del lavoro in questa pagina è che qualsiasi circuito digitale asincrono può essere emulato da una matrice Q impiegabile per programmare una macchina computazionale basata sul quantum annealing. Ciò implica, con le dovute approssimazioni, che un sistema basato sul quantum annealing può "fare" tutto quello che può "fare" qualsiasi sistema digitale asincrono. Dato che i sistemi digitali asincroni sono il punto di partenza per il funzionamento di qualsiasi computer classico, il passaggio segnalato è molto importante in quanto in successivi lavori andremo ad esaminare la possibile equivalenza tra sistema computazionale basato sul quantum annealing e macchina di Turing. Ciò sempre nell'ottica di comprendere se una macchina computazionale quantistica può essere in grado potenzialmente di svolgere tutte le operazioni eseguibili da un computer classico (o da una macchina di Turing universale) e magari qualcosina in più :-)

marcomattiucci.it

Informatica:

Quantum Computing: