Verso computer quantistici: un passo avanti dalla Sicilia

Due problemi classici dell’informatica teorica — la ricerca della sottostringa comune più lunga e della sottostringa palindroma più lunga — sono stati affrontati con algoritmi quantistici formalizzati nel modello circuitale. 

È il risultato di una ricerca condotta dalle Università di Catania e Palermo, pubblicata sulla rivista internazionale Theoretical Computer Science con il titolo “Algoritmi quantistici per le sottostringhe più lunghe comuni e palindromiche nel modello del circuito”.

Gli algoritmi sono definiti nel modello circuitale, il linguaggio che permette di descrivere passo passo come funzionerebbe un calcolatore quantistico. Finora, per questi problemi erano disponibili solo formulazioni astratte. Siamo ancora lontani dall'esecuzione, su larga scala, di questi algoritmi ma il lavoro svolto rappresenta un passo fondamentale dal punto di vista scientifico. 

Nel modello considerato si nota uno speed-up quantistico rispetto alle soluzioni classiche. La complessità temporale cresce come la radice quadrata della dimensione dell’input, inceve che in modo lineare o peggiore. Un miglioramento che si dimostra particolarmente significativo quando si ha una grande mole di dati da analizzare.

Ecco perché la scoperta dei ricercatori siciliani non è importate solo per il calcolo quantistico applicato. Diventa particolarmente importante per la bioinformatica. I problemi affrontati sono centrali nel confronto di sequenze biologiche, come DNA, RNA e proteine, dove l’individuazione di regioni comuni o di strutture palindromiche è fondamentale per l’analisi funzionale ed evolutiva. 

Potenziali ricadute positive si ipotizzano in genetica, medicina e biotecnologie, inclusi contesti applicativi come lo studio dei patogeni e lo sviluppo di vaccini.

Il gruppo di ricerca è composto da Dario Cantone, Giuseppe Faro ed Emanuele Viola per l’Università di Catania e Andrea Pavone per l’Università di Palermo. Una prima presentazione dei risultati era stata fatta alla conferenza ICTCS 2024. La ricerca rientra nelle attività del National Centre for HPC, Big Data and Quantum Computing, finanziato dal PNRR (CN00000013 – Spoke 10) con fondi NextGenerationEU.