Quantum Algorithms e Laboratorio

Modulo Quantum Algorithms

Conoscenza e capacità di comprensione (knowledge and understanding)
Lo studente acquisirà conoscenze avanzate sui principali paradigmi algoritmici quantistici trattati nel corso, con particolare riferimento ai quantum walks e alle loro applicazioni a problemi di ricerca, connettività, distinctness e individuazione di sottostrutture in grafi. Comprenderà inoltre i principi fondamentali della simulazione Hamiltoniana, degli algoritmi quantistici per sistemi lineari e ottimizzazione, dei block-encodings e degli algoritmi ibridi. Saranno introdotti anche span programs, formula evaluation e ST-connectivity.

Capacità di applicare conoscenza e comprensione (applying knowledge and understanding)
Lo studente sarà in grado di analizzare problemi algoritmici individuando quando l'impiego di tecniche quantistiche possa fornire un vantaggio rispetto agli approcci classici. Saprà applicare i paradigmi studiati alla progettazione e all'analisi di algoritmi per problemi di ricerca su grafi, distinctness, triangle finding e problemi di ottimizzazione. Sarà inoltre in grado di comprendere e sviluppare semplici implementazioni o simulazioni dei principali algoritmi e sottoprocedure presentati nel modulo laboratoriale.

Autonomia di giudizio (making judgements)
Lo studente sarà in grado di valutare criticamente l'adeguatezza di differenti tecniche algoritmiche quantistiche rispetto al problema considerato, confrontandone requisiti, complessità e possibili vantaggi rispetto alle soluzioni classiche. Saprà interpretare le ipotesi alla base dei risultati teorici, riconoscere i principali limiti dei modelli e degli algoritmi studiati e valutare l'impatto di parametri quali dimensione dell'input, precisione richiesta, condizionamento e struttura del problema.

Abilità comunicative (communication skills)
Lo studente sarà in grado di descrivere con un linguaggio tecnico appropriato i principi di funzionamento degli algoritmi quantistici studiati, illustrandone correttamente struttura, ipotesi e complessità. Saprà presentare e discutere un procedimento algoritmico utilizzando formalismi matematici, circuitali e computazionali adeguati, mettendo in evidenza le differenze rispetto agli approcci classici e motivando le scelte metodologiche adottate nella soluzione di un problema.

Capacità di apprendimento (learning skills)
Lo studente svilupperà la capacità di approfondire autonomamente algoritmi e tecniche di quantum computing non trattati direttamente o trattati solo in forma introduttiva durante il corso. Le conoscenze acquisite consentiranno di affrontare articoli scientifici, documentazione tecnica e testi avanzati del settore, riconoscendo i paradigmi algoritmici utilizzati e ricostruendone i principali passaggi. Lo studente sarà inoltre preparato ad affrontare temi più avanzati di algoritmica quantistica, simulazione e ottimizzazione quantistica.

Le lezioni si svolgeranno in presenza, con modalità frontale. È prevista l'esposizione dei contenuti teorici da parte del docente, con il supporto di slide, lavagna ed esempi applicativi. Particolare attenzione sarà dedicata alla comprensione dei principali paradigmi algoritmici quantistici, alla loro analisi e al confronto con i corrispondenti approcci classici. La partecipazione attiva degli studenti sarà incoraggiata attraverso domande, discussioni e analisi guidata degli algoritmi presentati.

Qualora l'insegnamento venisse impartito in modalità mista o a distanza potranno essere introdotte le necessarie variazioni rispetto a quanto dichiarato in precedenza, al fine di rispettare il programma previsto e riportato nel syllabus.

Sono richieste conoscenze di base di algebra lineare, probabilità e analisi degli algoritmi. È inoltre utile avere familiarità con i concetti fondamentali del calcolo quantistico, quali qubit, misure e circuiti quantistici. Gli strumenti matematici e computazionali più specifici necessari alla comprensione degli argomenti saranno comunque richiamati durante il corso.

Per una comprensione approfondita degli argomenti trattati e delle metodologie presentate, si raccomanda vivamente la regolare partecipazione alle lezioni.

Il corso introduce alcuni dei principali paradigmi avanzati per la progettazione di algoritmi quantistici. La parte centrale è dedicata ai quantum walks e al loro impiego nella risoluzione di problemi di ricerca su grafi, hitting problems e problemi di connettività. Vengono quindi analizzate applicazioni rilevanti quali Element Distinctness e k-Distinctness, Triangle Finding, Triangle Listing e, più in generale, problemi di subgraph detection, insieme all’algoritmo di Montanaro. Una parte conclusiva introduce, a livello essenziale, gli Span Programs e il loro utilizzo nello studio di NAND Trees, formula evaluation su alberi AND/OR e ST-Connectivity. Il corso affronta inoltre tecniche quantistiche per la simulazione e l’ottimizzazione, includendo simulazione Hamiltoniana, formule di prodotto e combinazioni lineari di unitari, algoritmo HHL, block-encodings, preparazione di stati di Gibbs, Mirror Descent e Matrix Multiplicative Weights Update. Sono infine introdotti i solutori quantistici per problemi SDP, il teorema adiabatico e QAOA.

1. Dispense del docente, fornite in formato PDF e rese disponibili agli studenti durante il corso. Le dispense costituiscono il principale materiale di riferimento per il modulo di Quantum Algorithms e coprono gli argomenti relativi a quantum walks, problemi di ricerca e connettività, Element Distinctness e k-Distinctness, Triangle Finding e Triangle Listing, algoritmo di Montanaro, Span Programs, formula evaluation e ST-Connectivity.

2. Giacomo Nannicini, Quantum Algorithms for Optimizers. Testo di riferimento per il modulo dedicato agli algoritmi quantistici per simulazione e ottimizzazione, con particolare riferimento a simulazione Hamiltoniana, sistemi lineari quantistici, block-encodings, stati di Gibbs, metodi per problemi SDP, ottimizzazione adiabatica e QAOA.

La verifica dell’apprendimento si articola in una prova orale, che costituisce la componente principale dell’esame, e in una prova progettuale da svolgere autonomamente. La prova progettuale riguarderà l’approfondimento, l’analisi o l’applicazione di uno degli argomenti trattati durante il corso e dovrà essere completata secondo le modalità indicate dal docente.

La prova orale rappresenta la componente principale della valutazione ed è finalizzata a verificare la conoscenza e la comprensione dei contenuti del corso, la capacità di analizzare gli algoritmi presentati, di discuterne il funzionamento e la complessità e di stabilire collegamenti tra i diversi paradigmi studiati. Durante la prova orale potrà inoltre essere richiesta la discussione delle scelte metodologiche e dei risultati relativi alla prova progettuale.

La prova progettuale e la prova orale concorrono congiuntamente alla determinazione del voto finale. Il progetto ha valore integrativo rispetto alla prova orale e consente di valutare la capacità dello studente di applicare in modo autonomo le conoscenze acquisite e di approfondire uno specifico problema algoritmico.

La prova d’esame è finalizzata a valutare in modo approfondito la preparazione dello studente, la capacità di analisi e di ragionamento sugli argomenti trattati durante il corso, nonché l’adeguatezza del linguaggio tecnico utilizzato.

Tali prove potranno avere luogo per via telematica, qualora le condizioni lo dovessero richiedere.

Per l’attribuzione del voto finale si seguiranno di norma i seguenti criteri:

• non approvato: lo studente dimostra una conoscenza insufficiente dei concetti fondamentali e non è in grado di descrivere correttamente gli algoritmi e le tecniche principali trattati nel corso;

• 18–23: lo studente dimostra una conoscenza essenziale dei contenuti, è in grado di descrivere i principali algoritmi ma presenta capacità limitate di analisi, collegamento e approfondimento;

• 24–27: lo studente dimostra una buona padronanza dei contenuti, espone gli argomenti in modo appropriato ed è in grado di analizzare gli algoritmi, discuterne la complessità e stabilire collegamenti tra i diversi argomenti;

• 28–30 e lode: lo studente dimostra una conoscenza completa e approfondita dei contenuti, capacità di analisi autonoma e critica, piena padronanza del linguaggio tecnico e capacità di collegare e rielaborare efficacemente i diversi paradigmi algoritmici trattati.

Gli studenti con disabilità e/o DSA dovranno contattare con sufficiente anticipo rispetto alla data dell'esame il docente, il referente CInAP del DMI (prof.ssa Daniele) e il CInAP per comunicare che intendono sostenere l'esame fruendo delle opportune misure compensative.

A titolo esemplificativo, durante la prova orale potranno essere proposte domande relative a:

• descrizione e analisi di uno degli algoritmi quantistici presentati durante il corso;

• confronto tra un approccio quantistico e il corrispondente approccio classico;

• analisi della complessità di un algoritmo o di una sua componente;

• applicazione di un paradigma algoritmico quantistico a uno specifico problema;

• discussione delle ipotesi, dei limiti e dei possibili vantaggi delle tecniche studiate;

• collegamenti tra differenti argomenti e paradigmi presentati nel corso;

• discussione di aspetti teorici o metodologici relativi alla prova progettuale.

Si precisa che tali domande hanno carattere puramente indicativo: le domande effettivamente proposte in sede d’esame potranno divergere, anche in modo significativo, da quelle riportate in questa lista.