Uno studio dei ricercatori degli atenei di Catania e Palermo, pubblicato su Theoretical Computer Science, mostra come problemi chiave dell’informatica possano beneficiare di un vantaggio quantistico con ricadute in bioinformatica
Un risultato scientifico di grande rilievo internazionale, nato interamente in Sicilia, è stato recentemente pubblicato sulla prestigiosa rivista Theoretical Computer Science, uno dei principali punti di riferimento internazionali per la ricerca in informatica teorica.
Il lavoro – dal titolo Quantum algorithms for longest common and palindromic substrings in the circuit model - è frutto della collaborazione tra gli atenei di Catania e Palermo e vede coinvolto un gruppo di ricerca con competenze fortemente complementari.
Lo studio affronta due problemi classici dell’informatica teorica: la ricerca della sottostringa comune più lunga e della sottostringa palindroma più lunga.
Problemi noti da decenni, fondamentali sia dal punto di vista teorico sia per le applicazioni, che oggi vengono per la prima volta risolti tramite un algoritmo quantistico completo nel modello circuitale, il più vicino all’implementazione concreta su futuri computer quantistici.
L’impatto del lavoro va ben oltre l’informatica teorica e si estende a settori di forte rilevanza applicativa, in particolare la bioinformatica.
A comporre il team di ricerca i docenti dell’Università di Catania Domenico Cantone, ordinario e decano dell’ateneo, Simone Faro, associato e promotore negli ultimi anni di una forte crescita delle attività di ricerca e didattica in ambito quantistico, e Caterina Viola, ricercatrice rientrata nella città dell’Elefante dopo un dottorato in Germania e un periodo di post-dottorato all’Università di Oxford.
Per l’Università di Palermo la ricercatrice dal profilo interdisciplinare Arianna Pavone, attiva tra computazione quantistica, analisi delle sequenze e studi cognitivi.
Un risultato che nasce dall’informatica teorica
Il lavoro pubblicato rappresenta il punto di arrivo di un percorso di ricerca avviato negli anni precedenti. Una prima versione preliminare dei risultati era stata presentata nel 2024 dalla dottoressa Arianna Pavone alla conferenza ICTCS, svoltasi a Torino, uno degli appuntamenti più rilevanti in Italia per l’informatica teorica. Quel contributo ha permesso di avviare un confronto approfondito con la comunità scientifica, che ha portato alla versione estesa e definitiva oggi riconosciuta a livello internazionale.
Secondo Simone Faro questo percorso riflette un cambiamento più ampio nel panorama della ricerca: «Negli ultimi anni lo studio degli algoritmi quantistici si sta incardinando sempre più naturalmente nell’ambito dell’informatica, e in particolare dell’informatica teorica. Se in passato questi temi erano appannaggio quasi esclusivo della fisica, oggi sono sempre più centrali nelle conferenze e nelle riviste di computer science, come dimostra il fatto che risultati di questa portata vengano presentati e valutati in contesti come ICTCS».
Il lavoro si inserisce inoltre all’interno di un più ampio quadro di ricerca nazionale ed europea, essendo svolto con il supporto del National Centre for HPC, Big Data and Quantum Computing, nell’ambito del Progetto Pnrr CN00000013 – Spoke 10, co-finanziato dall’Unione Europea attraverso il programma NextGenerationEU. Un contesto che testimonia come la ricerca quantistica rappresenti oggi una delle direttrici strategiche per l’innovazione scientifica e tecnologica del Paese.
Il significato dello speed-up quantistico
Per comprendere la portata del risultato è essenziale capire cosa si intende per algoritmo quantistico.
«Un algoritmo quantistico», spiega Domenico Cantone, ordinario e decano dell’Università di Catania «sfrutta le leggi della meccanica quantistica per elaborare l’informazione in modo profondamente diverso rispetto ai computer classici. I qubit possono trovarsi in sovrapposizione di stati e possono essere entangled tra loro, consentendo di esplorare molte configurazioni simultaneamente».
Questo non significa che un computer quantistico sia “più veloce in assoluto”, ma che per alcune classi di problemi può ridurre drasticamente il numero di operazioni necessarie. «Il nostro lavoro», continua Cantone, «mostra come questi principi possano essere tradotti in circuiti quantistici concreti, non solo in modelli teorici astratti».
Uno degli aspetti centrali del risultato riguarda il cosiddetto speed-up quantistico, ovvero il vantaggio di efficienza rispetto agli algoritmi classici.
A chiarirne il significato è Simone Faro, associato all’Università di Catania: «Uno speed-up quantistico indica che un problema può essere risolto con un numero di passi molto inferiore rispetto a quanto possibile con un algoritmo classico. Nel nostro caso, il tempo di esecuzione cresce come la radice quadrata della dimensione dell’input, invece che in modo lineare o peggiore».
Si tratta di un miglioramento sostanziale, soprattutto per input di grandi dimensioni. «Questo tipo di vantaggio - aggiunge Faro - è cruciale perché rende realistico l’uso di algoritmi quantistici su problemi che, altrimenti, sarebbero computazionalmente proibitivi».
«Negli ultimi anni - sottolinea Faro - Catania ha investito fortemente in questo settore. Abbiamo lavorato molto per sviluppare ricerca e didattica in informatica quantistica. Il nuovo corso di laurea magistrale in Informatica, con sei curricula di cui uno interamente dedicato al Quantum Computing e all’HPC, va esattamente in questa direzione e si inserisce in un contesto di rilevanza nazionale e internazionale».
Perché questo problema è così importante
«I problemi che affrontiamo - spiega Arianna Pavone, ricercatrice all’Università di Palermo con un profilo interdisciplinare - sono centrali in bioinformatica, dove confrontare sequenze è una delle operazioni fondamentali per l’analisi del Dna, dell’Rna e delle proteine».
Un aspetto che Pavone conosce anche dal punto di vista applicativo: la ricercatrice ha lavorato per un anno come post-doc all’Università di Pisa, occupandosi di problemi di bioinformatica legati allo studio delle sequenze biologiche, con applicazioni dirette allo sviluppo e all’analisi dei vaccini. «In quel contesto», sottolinea, «la capacità di individuare rapidamente regioni comuni o strutture palindromiche all’interno di grandi quantità di dati biologici è cruciale per comprendere il comportamento di patogeni e la risposta immunitaria».
Individuare sottostringhe comuni o palindromiche significa infatti riconoscere strutture biologicamente significative, come regioni conservate o motivi funzionali. «Disporre di algoritmi più efficienti», continua Pavone, «ha ricadute dirette sulla possibilità di analizzare grandi moli di dati in tempi compatibili con le esigenze della ricerca biomedica, con effetti potenzialmente rilevanti in genetica, medicina e biotecnologie».
Secondo Pavone, il valore del risultato risiede proprio nella sua duplice natura: «Si tratta di una scoperta che ha un forte impatto teorico perché introduce nuove tecniche nell’informatica quantistica, ma anche un potenziale pratico di ampio respiro. Il fatto che un problema così centrale per la bioinformatica possa beneficiare di uno speed-up quantistico apre scenari molto interessanti per applicazioni future».
Un gruppo di ricerca con competenze complementari
Il lavoro è il risultato di una collaborazione tra studiosi con esperienze e competenze diverse, maturate in contesti internazionali e poi convogliate in un progetto comune.
Accanto a Domenico Cantone, Simone Faro e Arianna Pavone, figura Caterina Viola, ricercatrice rientrata a Catania dopo un dottorato in Germania e un periodo di post-dottorato all’Università di Oxford.
«Il mio contributo - spiega Caterina Viola - si è concentrato sugli aspetti di complessità computazionale, un ambito su cui avevo lavorato intensamente all’estero. Inserirmi nel gruppo del professor Faro mi ha permesso di applicare queste competenze al contesto della computazione quantistica».
Accanto all’attività di ricerca, Viola ha svolto anche un ruolo importante nella divulgazione scientifica: per due anni consecutivi ha organizzato presso l’Università di Catania l’evento IBM Qiskit Fall Fest, contribuendo a diffondere tra studenti e giovani ricercatori la conoscenza e l’importanza dell’informatica quantistica.
La collaborazione tra Catania e Palermo si riflette anche a livello nazionale: Pavone e Faro sono, infatti, responsabili delle rispettive sedi dei nodi locali del Working Group del CINI sulle Quantum Technologies, contribuendo allo sviluppo coordinato della ricerca quantistica in Italia.
A offrire una prospettiva realistica sulle ricadute tecnologiche del lavoro è Domenico Cantone, che invita a distinguere tra progresso teorico e applicazione immediata: «Questi risultati rappresentano un passo fondamentale dal punto di vista scientifico, ma per essere eseguiti su larga scala su macchine quantistiche reali sarà necessario attendere ancora qualche anno. Oggi tali algoritmi possono essere testati solo su sequenze molto brevi».
Una precisazione che non ridimensiona l’importanza del risultato, ma ne chiarisce il valore: «È proprio questo il ruolo della ricerca teorica - conclude Cantone - preparare il terreno affinché, quando l’hardware sarà maturo, gli algoritmi siano già pronti».
Con questo lavoro, la Sicilia si conferma protagonista in un settore di frontiera come l’informatica quantistica, dimostrando come ricerca di base, formazione avanzata e collaborazione tra atenei possano generare risultati di rilevanza internazionale, con ricadute che vanno ben oltre i confini dell’accademia.