Per ulteriori informazioni visitate il thread ufficiale presente nel nostro forum.
D-Wave sta sviluppando una nuova classe di sistema di calcolo ad alte prestazioni progettato per risolvere problemi di ottimizzazione complessi con l'iniziale accento sulle applicazioni di apprendimento automatico (machine learning).
I sistemi D-Wave sono stati archittetati attorno ad un innovativo processore che utilizza un modello computazionale conosciuto come adiabatic quantum computing (AQC). Questi processori sfruttano gli effetti quantistici per risolvere problemi di ottimizzazione in un nuovo modo. Sono fabbricati utilizzando metalli superconduttori invece di semiconduttori e operano a bassissime temperature in un vuoto magnetico.
Introduzione
Un algortimo è una ricetta per risolvere un problema.1 Un esempio è fornito alla voce algortimo su Wikipedia dove il problema da risolvere è sempre una lampada da lavoro rotta. In questo caso, una sequenza di passi è seguita con le possibili soluzioni del problema ad ogni passo raffigurate in un diagramma di flusso.
Di solito è semplice valutare quanto bene operi un algortimo proposto. Una maniera per capirlo è quello di contare quanti passi impiega per risolvere un problema di una data dimensione.
Alcuni algortimi sono meglio di altri. Nell'esempio della lampadina di figura 1, un perfetto algortimo valido potrebbe richiedere un viaggio in Siberia tra il controllo che la lampada sia stata collegata ed il controllo se la lampadina sia bruciata. L'aggiunta del viaggio in Siberia non influenza l'esito dell'algoritmo. Questo modificato algoritmo che fissa la lampadina potrebbe essere ancora visualizzato come inferiore all'originale.
A volte una ricetta di recente scoperta per risolvere il problema è chiaramente superiore di tutte le altre che l'hanno preceduta. Quando questo accade, gli approcci storici sono spesso abbandonati ed ognuno che condivide il problema in questione gli prende immediatamente e a volte hanno degli spettacolari incrementi di prestazioni.2 Nello scenario della lampada, immaginate che tutti abbiano usato la versione "visita in Siberia" fino a che qualche brillante informatico ha sottolineato che si poteva omettere questo passaggio e ottenere ancora la sistemazione della lampada. La maggior parte sarebbe passata immediatamente all'approccio migliore.
A volte è molto difficile dire se un particolare algoritmo potrebbe essere fatto meglio. Nelle ultime due decadi molti progressi sono stati compiuti nella comprensione di un tipo di limitazione e a quanto possono essere buoni gli algoritmi. Si scopre che le leggi della fisica impongono dei limiti su quanto efficcaciemente i problemi possano essere risolti. Proprio come i limiti fisici posti dalla velocità con cui qualcosa può viaggiare (la velocità della luce) sono necessari per risolvere un dato problema. Questi limiti sono indipendenti da quanto è astuto un programmatore oppure da quali tipi di hardware sono disponibili.
Concettualmente, la ragione per cui le leggi della fisica sono importanti per il calcolo è che i computer sono costruiti da materiale che è ovviamente soggetto alle leggi della fisica. Le informazione che sono salvate e processati in un computer sono soggette a queste regole e quindi ereditano tutti i vincoli che tali regole comportano.
Informazioni quantistiche e algortimi
I progressi nella comprensione delle relazioni tra fisica e informatica ha portato allo sviluppo di una nuova categoria di ricerca scientifica, dove i limiti estremi di calcolo sono studiati. Questa categoria è chiamata informatica quantistica (quantum information science). La premessa base è che le leggi fondamentali della fisica (che non sono necessariamente di primaria rilevanza negli odierni processori e sistemi di calcolo) fissano i limiti finali di come gli algoritmi funzionino bene. Trenta anni fa questa categoria della scienza non esisteva. Oggi si sarebbe in difficoltà a trovare una singola università senza una facoltà che studi gli affascinanti problemi aperti in questo campo.
Una della più affascinanti scoperte fatte nel corso di queste indagini è che ci sono degli algoritmi consentiti dalla natura ma che non possono funzionare sui moderni sistemi di calcolo.3 Questi algoritmi quantistici richiedono operazioni che sono consentite dalla meccanica quantistica ma non dalla fisica classica.4 Per eserguirli, sono richiesti sistemi hardware speciali (chiamati solitamente computer quantistici) progettati per essere in grado di eseguire le "operazioni quantistiche" richieste dagli algoritmi quantistici. Alcuni di loro sarebbero dei cambiatori di gioco per il problema per il quale sono stati progettati.
Un noto esempio è l'algoritmo di Shor che è un algortimo quantistico di fattorizzazione.5 La fattorizzazione è un problema difficile utilizzato come base per alcuni sistemi crittografici; è in grado di fattorizzare grandi prodotti di numeri primi e permette di rompere rapidamente alcuni codici comunemente utilizzati. L'algoritmo di Shor riduce il numero di passi richiesti per fattorizzare una quantità enorme. Se in un moderno PC potesse girare l'algoritmo di Shor, potrebbe violare il codice di protezione della tua carta di credito basata su acquisti online in circa un secondo mentre, utilizzando il migliore algoritmo di fattorizzazione conosciuto, questa stessa impresa avrebbe utilizzato il più grande supercomputer al mondo per più di un giorno.6
Algoritmo adiabatico quantistico
Una classe importante di algoritmi quantistici sono gli algoritmi adiabatici quantistici (adiabatic quantum algorithms).7 Inizialmente scoperto nel 2000 da un gruppo del MIT, questi algoritmi risolvono una importante classe di difficili problemi computazionali in modo nuovo.8 Questi algoritmi hanno generato una grande quantità di controversie nell'informatica e nella fisica perché non c'è un modo facile per analizzare quanto tempo impiegano per risolvere i problemi per cui sono stati realizzati.
Alcuni scienzati di informatica teorica credono che non forniscano alcun vantaggio mentre molti studi su questi approcci di risoluzione dei problemi credono che ci possano essere esponenziali riduzioni nei tempi, che portano alla risoluzione di questi problemi, sui migliori algoritmi classici conosciuti.9
Risolvere la questione di quanto tempo ci vuole per un algoritmo adiabatico quantistico per calcolare la risposta ad un problema è un'importantissima questione scientifica relativo ad uno dei più grandi problemi in informatica. Oltre ad essere un importante problema accademico, la questione è di estrema importanza pratica allo sforzo di D-Wave, che si concentra intorno alla costruzione hardware che permetta questi algoritmi.
L'utilizzo di Quantum Monte Carlo per il calcolo dei runtime
Recentemente una tecnica è stata introdotta per il calcolo del tempo impiegato da un algortimo adiabatico quantistico per risolvere problemi relativamente piccoli, simulando l'algoritmo in azione su un computer quantistico.10
Mentre questo approccio, purtroppo, non può dirci come questi algoritmi operino su grandi problemi, questo è sufficiente per prevedere le prestazioni attese di un computer adiabatico quantistico di circa 128 qubit.
Questo approccio simulativo è basato su una tecnica chiamata Monte Carlo Quantistico (Quantum Monte Carlo - QMC). L'approccio è un imbarazzante parallelismo e può, in modo efficiente, utilizzare un gran numero di processori indipendenti.
D-Wave e il Dr. Peter Young11 (un co-autore sul paper di QMC precedentemente menzionato e un professore dell'Università della California - Santa Clara) ha costruito una piattaforma QMC distribuita per calcolare il runtime di un algortimo adiabatico quantistico che sarà eseguito in un hardware sperimentale alla D-Wave. Il progetto si chiama AQUA (Adiabatic QUantum Algorithms - Algoritmi Adiabatici Distribuiti) con la versione distribuita chiama AQUA@home.
La tecnologia di calcolo distribuita è basa su BOINC, la stessa tecnologia che utilizzano SETI@home ed una miriade di altri calcoli distribuiti su larga scala scientifica.12
AQUA@home gira sul server all'indirizzo http://aqua.dwavesys.com/ che è impostato per accettare cicli volontari da individui che desiderano contribuire risorse di calcolo per il progetto.
L'hardware che viene simulato
I processori che vengono simulati nel progetto AQUA@home sono attualmente fabbricati da D-Wave ed il loro nome in codice è Rainier. Sono costituiti da definiti circuiti metallici litografici. Il metallo utilizzato è il niobio, che diventa un superconduttore a temperature molto basse. I superconduttori hanno proprietà esotiche che li rendono particorlamente adatti per certi tipi di progetti di processori ad alte prestazioni. Un'ampia panoramica della tecnologia di un processore superconduttore la trovate in questa consultazione.13
Il processore simulato contiene 128 qubits. Questo rende lo studio abbastanza piccolo utilizzando la tecnica QMC usata in AQUA@home. Ampie descrizioni dell'hardware del sistema e del processore le trovate in http://dwave.wordpress.com.
Figura 2: Il processore a 28 qubit utilizzati nella dimostrazione di supercalcolo di D-Wave/Google nel 2007.
Il problema che l'algoritmo adiabatico quantistico risolve
Il processore Rainier è progettato specificatamente per risolvere un particolare difficile problema chiamato ottimizzazione binaria quadratica vincolata (QUBO - quadratic unconstrained binary optimization).14 Risolvere un problema QUBOrichiede di trovare un set di N variabili binarie {xi} che minimizza una funzione obiettivo nella forma
E(x1,...,xN) = Σi≤jN Qijxixj
dove Q è un valore reale di una matrice triangolare superiore. Ogni particolare matrice Q è chiamata istanza del problema. Generalmente, la matrice Q nasce da una domanda che richiede la soluzione di un QUBO. Un esempio di questa domanda è l'apprendimento automatico (machine learning), l'area di interesse del team di sviluppo degli algoritmi di D-Wave.15
Cosa calcola AQUA@home?
AQUA@home è il calcolo del tempo di esecuzione di una serie di istanze del problema del tipo sopra indicato per i problemi di formato da 8 a 128 variabili. Generiamo 50 istanze per ogni problema delle seguente dimensioni: 8, 16, 32, 48, 72, 96 e 128 variabili, per un totale di 350 istanze del problema. Usiamo AQUA@home per calcolare il tempo di esecuzione di ogni istanza. Questa è l'uscita desiderata dal calcolo.
Questa informazione può essere utilizzata per due scopi importanti. Il primo è che ci dice quanto velocemente il nostro hardware simulato può operare e quanto dobbiamo aspettare per risolvere il problema in questione. Il secondo è che ci dice come scala il tempo di esecuzione con l'aumento della dimensione del problema. Sapere come un problema scala ci fornisce informazioni vitali sul fatto che il problema sia adatto all'approccio adiabatico. Per esempio se il tempo di esecuzione ha un incremento esponenziale rispetto alla dimensione del problema, questo ci dice che le istanze del problema che abbiamo studiato non sono adatte per l'hardware.
Cosa succede ai dati generati da AQUA@home?
I dati generati da AQUA@home sono resi pubblici in forma di grafici di media di esecuzione vs. dimensione del problema per tutti i tipi di hardware, algoritmi quantici e classi di istanza del problema su AQUA@home in quanto i dati saranno disponibili. In aggiunta saranno pubblicate descrizioni complete della scienza che sta dietro alla computazione in paper scientifici sul server di prestampa arxiv.org e alcuni di questi risultati tra pari da importanti riviste scientifiche, Physical Review Letters.
e allo "Stato del server" 
.
.
o alla "Classifica utenti" 
(solo per iscritti al team).
o alla "Classifica dei team italiani" 
.