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.
- Mid Semester exam (Oct 10, 2:00-3:30 pm): 30%
- Final Exam: 30%
- Assignments : 30%
- Class Participation: 10%
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
- This course by O'Donell at CMU.
- This course by Dakshita Khurana, UIUC.
- This course at Princeton.
- Previous offering of similar course at IITM (the first few weeks overlap).
- These lecture notes by Regev.
-
These lecture notes by Thomas Vidick, Caltech.
- These lecture notes by Ronald de Wolf, CWI.
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
- About CHSH experimental verification: Scott Aaronson's blog.
- Birthday Problem: See this paper for a description of the basic as well as general case.