Lunedì, 29 marzo 2021

Risolvere problemi intrattabili con un Computer Quantistico

Articolo pubblicato su Information & Computation, Elsevier

Versione stampabile

Cosa sono i problemi intrattabili per un computer tradizionale?

Sono tipi di problemi la cui soluzione richiede tempi di elaborazione che crescono esponenzialmente con la loro dimensione, cosicché anche istanze relativamente piccole non possono essere risolte in un tempo ragionevole nemmeno dai computer più potenti. SAT (soddisfacibilità Booleana) è il tipo di problema intrattabile per antonomasia, con numerosissime applicazioni industriali (verifica di circuiti, pianificazione, logistica, intelligenza artificiale, ...).
Nonostante la ricerca abbia fatto enormi progressi negli ultimi 20 anni in questo campo, istanze di problemi SAT relativamente piccole sono ancora fuori dalla portata dei computer tradizionali. 

È convinzione di molti scienziati che i computer quantistici possano rappresentare una soluzione per problemi intrattabili. “Con i miei collaboratori" - spiega Roberto Sebastiani, professore al Dipartimento di Ingegneria e Scienza dell’Informazione - “stiamo provando a risolvere i problemi SAT utilizzando un Quantum Annealer, un particolare computer quantistico  sviluppato da D-Wave Systems Inc. I primi risultati che abbiamo ottenuto sono  molto incoraggianti”. 
Un Quantum Annealer è un dispositivo quantistico specializzato capace di risolvere un solo tipo di problema, detto QUBO, ma molto efficientemente; il lavoro di ricerca del prof. Sebastiani, usando un approccio innovativo, riesce a “tradurre” il problema intrattabile SAT in un problema QUBO per poi farlo risolvere quantisticamente al quantum annealer, con tempi molto più rapidi dei computer tradizionali.
I primi risultati della ricerca sono stati pubblicati sulla rivista  "Information and Computation" in un articolo intitolato “Solving SAT (and MaxSAT) with a quantum annealer: Foundations, encodings, and preliminary results” a firma del prof. Sebastiani, dell’ex-dottorando del DISI Stefano Varotti e di collaboratori di D-Wave Systems inc.

L'obiettivo finale di questa ricerca, a cui il prof. Sebastiani sta lavorando con un team di nuovi collaboratori, è quello di utilizzare quantum annealer di seconda generazione per risolvere problemi SAT attualmente fuori dalla portata dei computer tradizionali, ed ottenere la cosiddetta "supremazia quantistica" nel campo di problemi intrattabili.

Keywords:
Quantum Annealing, SAT, QUBO, problemi intrattabili