Quantum Algorithms e Laboratorio

Module Quantum Algorithms

Knowledge and understanding
Students will acquire advanced knowledge of the main quantum algorithmic paradigms covered in the course, with particular emphasis on quantum walks and their applications to search, connectivity, distinctness, and graph substructure detection problems. They will also understand the fundamental principles of Hamiltonian simulation, quantum algorithms for linear systems and optimization, block-encodings, and hybrid algorithms. Introductory notions of span programs, formula evaluation, and ST-connectivity will also be presented.

Applying knowledge and understanding
Students will be able to analyze algorithmic problems and identify situations in which quantum techniques may provide an advantage over classical approaches. They will be able to apply the paradigms studied in the course to the design and analysis of algorithms for graph search, distinctness, triangle finding, and optimization problems. They will also be able to understand and develop simple implementations or simulations of the main algorithms and subroutines introduced in the laboratory module.

Making judgements
Students will be able to critically assess the suitability of different quantum algorithmic techniques for a given problem by comparing their requirements, complexity, and potential advantages over classical solutions. They will be able to interpret the assumptions underlying theoretical results, recognize the main limitations of the models and algorithms studied, and evaluate the impact of parameters such as input size, required precision, condition number, and problem structure.

Communication skills
Students will be able to describe the principles underlying the quantum algorithms studied using appropriate technical terminology, clearly explaining their structure, assumptions, and complexity. They will be able to present and discuss an algorithmic procedure using suitable mathematical, circuit-based, and computational formalisms, highlighting differences with classical approaches and providing well-founded motivations for the methodological choices adopted in solving a problem.

Learning skills
Students will develop the ability to independently study quantum algorithms and techniques that are not covered directly, or are only introduced briefly, during the course. The knowledge acquired will enable them to approach scientific papers, technical documentation, and advanced textbooks in the field, identify the algorithmic paradigms employed, and reconstruct their main steps. Students will also be prepared to undertake further study of advanced topics in quantum algorithms, quantum simulation, and quantum optimization.

Classes will be held in person and delivered through lectures. Theoretical topics will be presented by the instructor with the support of slides, board work, and application-oriented examples. Particular attention will be devoted to understanding the main quantum algorithmic paradigms, their analysis, and their comparison with corresponding classical approaches. Active student participation will be encouraged through questions, discussions, and guided analysis of the algorithms presented.

Should the course be delivered in blended or online mode, the necessary adjustments may be introduced with respect to the arrangements described above in order to ensure completion of the syllabus.

Basic knowledge of linear algebra, probability, and algorithm analysis is required. Familiarity with the fundamental concepts of quantum computing, such as qubits, measurements, and quantum circuits, is also useful. More specific mathematical and computational tools required for the topics covered will be reviewed during the course when needed.

Regular attendance is strongly recommended in order to achieve a thorough understanding of the topics and methodologies presented in the course.

The course introduces some of the main advanced paradigms for the design of quantum algorithms. The core part focuses on quantum walks and their use in graph search problems, hitting problems, and connectivity problems. Relevant applications are then studied, including Element Distinctness and k-Distinctness, Triangle Finding, Triangle Listing and, more generally, subgraph detection problems, together with Montanaro’s algorithm. A final part provides an essential introduction to Span Programs and their application to NAND Trees, formula evaluation on AND/OR trees, and ST-Connectivity. The course also covers quantum techniques for simulation and optimization, including Hamiltonian simulation, product formulas and linear combinations of unitaries, the HHL algorithm, block-encodings, Gibbs state preparation, Mirror Descent, and Matrix Multiplicative Weights Update. Quantum SDP solvers, the adiabatic theorem, and QAOA are also introduced.

1. Lecture notes provided by the instructor, distributed in PDF format and made available to students during the course. The notes constitute the main reference material for the Quantum Algorithms module and cover quantum walks, search and connectivity problems, Element Distinctness and k-Distinctness, Triangle Finding and Triangle Listing, Montanaro’s algorithm, Span Programs, formula evaluation, and ST-Connectivity.

2. Giacomo Nannicini, Quantum Algorithms for Optimizers. Reference textbook for the module devoted to quantum algorithms for simulation and optimization, with particular emphasis on Hamiltonian simulation, quantum linear systems, block-encodings, Gibbs states, methods for SDP problems, adiabatic optimization, and QAOA.

The assessment consists of an oral examination, which represents the main component of the final evaluation, and an individual project to be completed independently. The project will focus on the study, analysis, or application of one of the topics covered in the course and must be completed according to the instructions provided by the instructor.

The oral examination represents the main component of the assessment and is intended to evaluate the student’s knowledge and understanding of the course contents, the ability to analyze the algorithms presented, discuss their operation and complexity, and establish connections among the different paradigms studied. During the oral examination, students may also be asked to discuss the methodological choices and results related to their project.

The project and the oral examination jointly contribute to the final grade. The project complements the oral examination and is intended to assess the student’s ability to independently apply the knowledge acquired and investigate a specific algorithmic problem in greater depth.

The examination is designed to assess the student’s overall preparation, analytical and reasoning skills concerning the topics covered in the course, and appropriate use of technical terminology.

The assessment may be conducted online should circumstances require it.

The final grade will normally be assigned according to the following criteria:

• fail: the student demonstrates insufficient knowledge of the fundamental concepts and is unable to correctly describe the main algorithms and techniques covered in the course;

• 18–23: the student demonstrates essential knowledge of the course contents and can describe the main algorithms, but shows limited ability to analyze, connect, and further develop the topics;

• 24–27: the student demonstrates good command of the course contents, presents the topics appropriately, and is able to analyze algorithms, discuss their complexity, and establish connections among different topics;

• 28–30 with honours: the student demonstrates complete and in-depth knowledge of the course contents, autonomous and critical analytical skills, full command of technical terminology, and the ability to effectively connect and elaborate on the different algorithmic paradigms covered.

Students with disabilities and/or specific learning disorders (SLD) should contact the instructor, the DMI CInAP representative (Prof. Daniele), and CInAP sufficiently in advance of the examination date in order to communicate their intention to take the examination using the appropriate compensatory measures.

By way of example, the oral examination may include questions concerning:

• description and analysis of one of the quantum algorithms presented during the course;

• comparison between a quantum approach and the corresponding classical approach;

• analysis of the complexity of an algorithm or one of its components;

• application of a quantum algorithmic paradigm to a specific problem;

• discussion of the assumptions, limitations, and potential advantages of the techniques studied;

• connections among different topics and paradigms presented during the course;

• discussion of theoretical or methodological aspects related to the project work.

These examples are provided for guidance only. The actual questions proposed during the examination may differ, even substantially, from those listed above.