In Semester 1, 2024-2025, I will be teaching CS 6846: Quantum Computing.

Course Description


Quantum computers, which harness the power of quantum mechanics, have demonstrated surprising power over classical computers. In this course, we will study the foundations of quantum computing. We will study the basics of quantum information, speedups offered by quantum algorithms, attacks on cryptography using quantum computers and (if time allows) quantum complexity and quantum cryptography.

No prior information about quantum mechanics will be assumed. The course requires mathematical maturity. A good working knowledge of linear algebra, probability, algorithms and complexity theory are required.

Administrative Information


Lectures are Thursday 2:00- 3:30 pm and Friday, 3:30-5:00 pm in CS 36.

Pre-requisites.

There are no formal prerequisites for the course. In particular, I will not assume any background in quantum information/physics/mechanics. But the course will ask for strong mathematical maturity, particularly familiarity with theory of computation and algorithms. A good working knowledge of linear algebra and probability is also required. If you have not had prior exposure, please read Sections 1, 2.1 and 6.1 (all required), and section 10 (optional) from this textbook.

Requirements.


Policies and Grades.

Collaboration is encouraged but you must write up solutions on your own. You must also write the names of all the people you discussed the problem with. In case you find material that will help you in solving some problems, you should mention the source in your writeup.
I expect all students to behave according to the highest ethical standards. Any cheating or dishonesty of any nature will result in failing the class.

Teaching Assistants.

Simran Kumari (cs19d401@smail.iitm.ac.in) and Anuja Modi (cs21d405@cse.iitm.ac.in)

Resources


There are no required text books though the book quantum computation and quantum information by Nielson and Chuang is useful.

Topicwise Class Summaries


Topic References
Basics of Quantum Information. Lec 1, 2 in UIUC notes, Lecture 1 in CMU notes . Also see Lec 2 in Princeton notes,
and Lec 0 in Caltech notes.
Quantum Computation and No Cloning. Lec 3 in UIUC notes, Lec 2 in Princeton notes.
Deutsch and Deutsch-Jozsa algorithms. Lec 4 and 5 in UIUC notes.
Simons and Bernstein-Vazirani algorithms. Lec 5 and 6 in UIUC notes.
CHSH game and quantum teleportation. Lec 3 in CMU notes.
Grover's Algorithm Lec 4 in CMU notes.
What we will break: The RSA Cryptosystem Wikipedia (for beginners). This and this are useful books.
Quantum Fourier Transform Lec 6 and Lec 7 of CMU notes.
Period Finding: Simon's Algorithm over ZN Lec 8 of CMU notes.
Shor's Algorithm Lec 9 of UCB notes and Lec 9 of CMU notes.
Mixed States and Quantum Key Distribution Lec 9-12 of UIUC notes and Lec 18 of CWI notes.
One time pad and encryption: classical and quantum. Lec 15-18 of UIUC notes.
Quantum Money Lec 26 of UIUC notes.
Quantum Fully Homomorphic Encryption (if time permits) Lec 20-22 of UIUC notes.
Proofs of Quantumness (if time permits) Lec 23-25 of UIUC notes.


Homeworks





Other Reading