Quantum Algorithms ( CS409.1 - Spring Semester 2024)

This is an elective course on Quantum Algorithms for computer science senior undergraduate and dual-degree students as well as MS and PhD students. The topics covered in this course: 

1) An introduction to qubits and quantum mechanics, 2) Preliminaries on quantum circuits and Solovay Kitaev Theorem, 3) Early Quantum Algorithms: Deutsch-Jozsa, Bernstein Vazirani and Simon's algorithm, 3) Quantum algorithmic primitives such as Quantum Fourier Transform and Quantum phase estimation, 4) Shor's factoring algorithm, 5) Grover's search algorithm, Quantum counting, quantum amplitude amplification and quantum amplitude estimation, 6) Advanced quantum algorithms such as Block-encoding, Linear Combination of Unitaries, Hamiltonian simulation, and 7) Quantum Singular Value Transformation and Quantum Linear Algebra. Time permitting, 8) different quantum computational models such as quantum walks (quantum walk search, element distinctness, Glued trees algorithm) and 9) adiabatic quantum computation will also be covered. 

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-person. 

Schedule: 

• Lectures twice a week - Tuesday and Friday, from 14:00 hrs - 15:25 hrs in H203.

• Tutorials - Mondays at 16hrs in H201.

Teaching Associate

• Zeeshan Ahmed ( zeeshan.ahmed@research.iiit.ac.in )

Evaluation:

There will be two assignments (20% weightage) and one in-class quiz (15% weightage). Students must submit a course project (details provided below) that will carry 30% 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

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 most of the topics to be covered.

The following lecture notes are also recommended reading material:

• Lecture notes on Quantum Computation by John Preskill (Caltech)

• Lecture notes on Quantum Algorithms by Andrew Childs (U. Maryland)

• Lectures notes on Quantum Computation by Ronald de Wolf (CWI)

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.