Course Syllabus
Obiettivi
Comprensione dei principi di funzionamento di alcuni modelli di calcolo non convenzionali, bio-ispirati e quantistici. Capacità di capire il funzionamento di tali sistemi quando risolvono problemi computazionalmente difficili. Capacità di scegliere il modello di calcolo più adatto per risolvere un problema assegnato.
Contenuti sintetici
Nozioni e concetti alla base della Teoria della Computazione, e della Teoria della Complessità Computazionale, applicate a modelli di calcolo non convenzionali e quantistici. Il corso fornisce inoltre gli strumenti concettuali e teorici che consentono di comprendere le basi matematiche su cui si basa la definizione dei modelli di calcolo esaminati.
Programma esteso
Per la parte di Unconventional Computing:
• Introduzione: architetture di calcolo classiche, sequenziali e parallele
• Problemi di calcolo non-convenzionali
• DNA Computing: esperimento di Adleman, algoritmo di Lipton
• Computazione Cellulare
• Membrane systems: modello standard, membrane systems per problemi computazionalmente complessi
• Spiking neural P systems
• Algoritmi genetici e reti neurali
• Social algorithms
Per la parte di Quantum Computing:
• Fenomeni fisici quantistici, parallelismo quantistico, entanglement, misurazioni
• Notazione matematica: qubit, bra, ket, operatori unitari
• Gate quantistici, loro rappresentazione, e operatori corrispondenti
• Circuiti quantistici
• Algoritmi quantistici fondamentali: trasformata di Fourier quantistica, algoritmi di Shor (fattorizzazione e logaritmi discreti), algoritmo di Grover
• Cenni ad altri modelli: Macchine di Turing quantistiche, adiabatiche, …
• Linguaggi di programmazione, librerie, simulatori, piattaforme (in particolare: QCEngine , Qiskit)
• Reti neurali ibride, e quantum machine learning
Prerequisiti
Argomenti trattati nei corsi di matematica della laurea triennale in Informatica. È utile - ma non indispensabile - la conoscenza di alcune nozioni di base di informatica teorica (in particolare, macchine di Turing).
Modalità didattica
Lezioni ed esercitazioni in aula.
La lingua di erogazione prevista è l'Inglese. Tuttavia, lezioni ed esercitazioni potranno essere erogate in Italiano se tutti gli studenti presenti in aula parlano Italiano, e nessuno studente fa richiesta di seguire le lezioni e le esercitazioni in lingua Inglese.
Materiale didattico
Libri:
• Andrew Adamatzky: Unconventional Computing - A Volume in the Encyclopedia of Complexity and Systems Science, Second Edition. Springer, 2018
• Wolfgang Polak, Eleanor Rieffel: Quantum Computing : A Gentle Introduction. MIT Press, 2011
• Eric R. Johnston, Nic Harrigan, Mercedes Gimeno-Segovia: Programming Quantum Computers: Essential Algorithms and Code Samples. O'Reilly Media, 2019
Appunti forniti dai docenti.
Periodo di erogazione dell'insegnamento
Secondo semestre
Modalità di verifica del profitto e valutazione
La verifica dell'apprendimento è basata su un colloquio orale avente per oggetto gli argomenti svolti a lezione. Durante il colloquio verrà valutata la capacità dello studente di esporre gli argomenti del corso, e di effettuare brevi ragionamenti su di essi.
Non sono presenti prove in itinere.
Orario di ricevimento
Su appuntamento
Sustainable Development Goals
Aims
Understanding of the operating principles of some unconventional, bio-inspired and quantum computational models. Ability to understand how such systems work when solving computationally difficult problems. Ability to choose the most suitable computational model to solve an assigned problem.
Contents
Notions and concepts at the base of the Theory of Computation, and of the Theory of Computational Complexity, applied to unconventional and quantum computational models. The course also provides the conceptual and theoretical tools that allow to understand the mathematical bases on which the definition of the computational models examined is based.
Detailed program
For the Unconventional Computing part:
• Introduction: classical, sequential and parallel computing architectures
• Unconventional Computing Problems
• DNA Computing: Adleman experiment, Lipton algorithm
• Cellular Computing
• Membrane systems: standard model, membrane systems for computationally complex problems
• Spiking neural P systems
• Genetic Algorithms, Neural Networks
• Social Algorithms
For the Quantum Computing part:
• Quantum physical phenomena, quantum parallelism, entanglement, measurements
• Mathematical notation: qubit, bra, ket, unit operators
• Quantum gates, their representation, and corresponding operators
• Quantum circuits
• Fundamental quantum algorithms: quantum Fourier transform, Shor's algorithms (factorization and discrete logarithms), Grover's algorithm
• Notes on other models: Quantum Turing machines, adiabatic Turing machines, ...
• Programming languages, libraries, simulators, platforms (in particular: QCEngine, Qiskit)
• Hybrid neural networks, and quantum machine learning
Prerequisites
Topics explained in mathematics courses held in the laurea degree in Informatics. It is useful - but not necessary - to have basic notions of theoretical computer science (in particular, Turing machines).
Teaching form
Lessons and exercises in the classroom.
The expected teaching language is English. However, lessons and exercises can be delivered in Italian if all students present in the classroom speak Italian, and no student requests to follow the lessons and exercises in English.
Textbook and teaching resource
Textbooks:
• Andrew Adamatzky: Unconventional Computing - A Volume in the Encyclopedia of Complexity and Systems Science, Second Edition. Springer, 2018
• Wolfgang Polak, Eleanor Rieffel: Quantum Computing : A Gentle Introduction. MIT Press, 2011
• Eric R. Johnston, Nic Harrigan, Mercedes Gimeno-Segovia: Programming Quantum Computers: Essential Algorithms and Code Samples. O'Reilly Media, 2019
Lecture notes provided by the teachers.
Semester
Second semester
Assessment method
The learning assessment is based on an oral interview, on the subjects exposed in class during the course. During the interview, the student's ability to explain the topics of the course, and to make brief thoughts on them, will be assessed.
Office hours
On appointment
