Quantum Algorithms ( CS409.1 - Spring Semester 2022)

This is an elective course on Quantum Algorithms for computer science undergraduate and dual degree students as well as master and PhD students. The topics covered in this course include an introduction to qubits and quantum mechanics, quantum circuits, various quantum algorithmic primitives such as Quantum Fourier Transform and Quantum phase estimation, quantum algorithms such as Shor's factoring algorithm, Simon's algorithm, Grover's search algorithm and quantum amplitude amplification. Some advanced quantum algorithms in the different quantum computational models such as quantum walks (quantum walk search, element distinctness, Glued trees algorithm) and adiabatic quantum computation will also be discussed. The course will cover some recently developed quantum algorithms for Hamiltonian simulation and for solving linear systems, in particular using the techniques of block-encoding and quantum signal processing.


Prerequisites:

Familiarity with basic Linear Algebra, probability theory, discrete math, algorithms and elementary quantum mechanics (desirable but not mandatory).


Course Format:

The lectures and the tutorial sessions will be in hybrid mode like all other courses this semester.


Schedule:

  • Lectures twice a week - Tuesday and Friday, 11:30 hrs - 13:00 hrs.

  • Tutorials - Wednesdays 16:00 hrs - 17:00 hrs.


Teaching Associate

  • Aditya Morolia (aditya.morolia@research.iiit.ac.in)


Evaluation:


There will be two assignments (10% weightage) and one in-class quiz (20% weightage). Students will have to submit a course project (details provided below) that will carry 35% weightage overall. There will be a proctored final exam at the end of the semester (35% weightage).


Course project details:

Students have to submit a course project where they have to work on a topic related to quantum algorithms. While a list of suggested topics will be made available, students are free to choose their own topic. Along with surveying prior art, the students are strongly encouraged to identify or propose new research directions in that area.

The students can work on their own or form small groups of 2-3 students. The course project evaluation will have the following components:


      • Project proposal (5% of project grade) – to be submitted by the end of Lecture 12

      • Project presentation (40% of project grade) – to be made to the class (mandatory 10 mins allocated for questions)

      • Paper (55% of project grade) – to be submitted by the end of the course


Lecture slides:

Lecture 1 | Lecture 2 | Lecture 3 | Lecture 4 | Lecture 5 | Lecture 6 | Lecture 7 | Lecture 8 | Lecture 9 | Lecture 10 | Lecture 11 | Lecture 12 | Lecture 13 | Lecture 14 | Lecture 15 | Lecture 16 | Lecture 17 | Lecture 18 | Lecture 19 | Lecture 20 | Lecture 21 | Lecture 22 | Lecture 23 | Lecture 24

References


There is no required textbook for this course. Good introductory material:


    • MA Nielsen and IL Chuang, Introduction to Quantum Information and Computation, Cambridge University Press (2010)

    • P. Kaye, R. Laflamme and M. Mosca, An Introduction to Quantum Computing, Oxford University Press (2007)


These two books contain almost most of the topics to be covered.


The following lecture notes are also recommended reading material:



These lecture notes are updated periodically and cover some of the more recent topics on the subject.

A great self-learning material for beginners is “Why now is the right time to study quantum computing”, by Aram Harrow.

Additionally, we will be using various research articles throughout the course.