9 units (3-0-6), P/F. Spring term 2020.
This course will teach the fundamentals of quantum algorithms through a combination of theory and programming. The goal will be to understand how quantum algorithms work, what advantages they offer over non-quantum (classical) algorithms, as well as the limitations of efficient quantum computation. On the theory side, this will be done using tools from algorithms analysis and computational complexity theory. On the programming side, we will be implementing a number of algorithms in Microsoft's quantum programming language Q#. The course will cover standard quantum algorithms, such as those of Deutsch-Jozsa, Simon, Shor and quantum simulation, as well as some of the more modern ones, such as algorithms for near-term devices and quantum machine learning.
Image courtesy of Vivian Uhlir.
Requirements: Students taking this course should be familiar with the basics of linear algebra, programming, algorithms and data structures. While the course will also serve as an introduction to quantum computation, students that have completed a quantum computing course (such as Ph 219), and wish to deepen their understanding of quantum algorithms are encouraged to take this course.
The main resources for the course will be the lectures themselves and the lecture notes. In addition, these other resources will be useful:
Students will be evaluated based on 4 homework assignments and one group project. The homeworks will consist of 3 programming assignments and one written assignment. The programming assignments will involve solving various problems in either Python or Q# (2 assignments in Q# and one in Python). These problems will be very similar in style to the Quantum Katas from the Q# website . The written assignment will be a problem set and will involve proofs pertaining to complexity theory and algorithms analysis. Finally, the group project will be a team-based assignment in which students will be asked to do a quantum algorithms project in their programming language of choice and write a short report (around 10 pages) on the project and the obtained results. Suggested ideas for projects will be posted in the second half of the course. The exact breakdown as well as the time period for each assignment are as follows:
As the course is P/F, students are required to complete at least 50% in order to pass.
The collaboration policy is the same as for CS/Ph-120, see collaboration table and ask the instructor in case of confusion.