Quantum algorithms (CMSC 858Q, Spring 2021)

This is an advanced graduate course on quantum algorithms for students with prior experience in quantum information. The course will cover algorithms that allow quantum computers to solve problems faster than classical computers. Topics will include quantum circuits, quantum algorithms for algebraic problems (computing discrete logarithms, the hidden subgroup problem, quantum algorithms for number fields), quantum walk algorithms, quantum algorithms for simulating quantum mechanics, limitations on the power of quantum computers, and selected recent developments in quantum algorithms.

This course assumes a good working knowledge of linear and abstract algebra, as well as concepts in quantum information at the level of CMSC 657: Introduction to Quantum Information Processing. In particular, you should already be familiar with the material reviewed in Chapter 1 of the lecture notes. You are encouraged to consult with the instructor if you are unsure whether you are prepared to take the course.

This class will be held virtually, with no in-person meetings. We will have synchronous lectures on Zoom, which will be recorded and made available through Canvas (also referred to as ELMS). We will reevaluate this format as the semester progresses and may make adjustments.

We will use Piazza for class announcements and discussion. You should sign yourself up for the course Piazza page. Instead of emailing questions to the teaching staff, please post questions on Piazza. You are encouraged to post questions publicly when possible so the whole class can benefit from the discussion, though you can also post private questions for any personal issues.

There is no required textbook. Good sources of background material include

• Kaye, Laflamme, and Mosca, An Introduction to Quantum Computing (errata)
• Kitaev, Shen, and Vyalyi, Classical and Quantum Computation
• Nielsen and Chuang, Quantum Information and Quantum Computation

Lecture notes will be available for all topics covered in the class. The relevant chapters will be indicated on the lecture schedule below.

Grades for the course will be based on three assignments (each worth 13% of the course grade), a course project to be presented in the last few weeks of the semester (31% of the course grade), and a final exam (30% of the course grade).

There will be three assignments, which will be made available on Canvas. You are encouraged to discuss the problems with your colleagues and the instructor and to consult the research literature. However, your solutions should be written independently, based on your own understanding, and you should acknowledge whatever resources you consulted. The assignments will be due on Gradescope as follows:

• Assignment 1: February 18
• Assignment 2: March 11
• Assignment 3: April 8

For the course project, you will study a topic related to quantum algorithms. In addition to reviewing previous work on your topic, you should aim to identify new research directions. Outstanding projects will also include some original research contributions. A list of suggested topics is available, but you are free to choose a topic not on that list. You may choose to work alone or with a group of two or three students. Each group should have a unique topic.

Your project will include the following deliverables:

• a project proposal, due March 4 (10% of your project grade);
• a presentation to the class, to be scheduled during lecture times in the last few weeks of the semester (45%); and
• a paper (45%), due May 11.

Further details will be provided in class and on Piazza as the course progresses.

Final exam

Course policies and academic accommodations

Course evaluations

Schedule

Web Accessibility