CMSC 858L -- Fall 2026

• Lectures: Tuesday, Thursday 12:30-1:45 PM, CSI 2120
• Instructor: Daniel Gottesman (e-mail: dgottesm@umd.edu, office hours Tuesday 11 AM - noon, Atlantic 3251)
• Teaching Assistant: Chaitanya Karamchedu (e-mail: cdkaram@umd.edu, office hours Wednesday 12:00-1:00 PM, Atlantic 3257)
• Piazza: https://piazza.com/umd/fall2026/cmsc858l
• Gradescope: https://www.gradescope.com/courses/1375851

Homeworks

• Problem Set 1 (Due Sep. 24, 11:59 PM): pdf

Lecture Notes

1. Overview and Core Concepts

Topics Covered

1. Overview and core concepts (basic definitions and overview of complexity classes)
2. Universality and non-universal quantum circuits (universality, Solovay-Kitaev theorem, Clifford group, matchgates)
3. Quantum oracles and query complexity (quantum upper bounds, classical lower bounds, techniques for quantum lower bounds)
4. Quantum advantage (PostBQP = PP, quantum advantage results with one or more intermediate (between classical and quantum) complexity classes)
5. QMA (QMA-completeness of local Hamiltonians and other QMA-complete problems)
6. Quantum interactive proofs (QIP = PSPACE, introduction to MIP = RE)

Grades

Your grade will have 3 components:

• Problem sets (35%)
• Project (35%)
• Final exam (30%)

Problem Set Rules

• The problem sets will be available on this web page about once every two weeks.
• The problem sets will be turned in on Gradescope.
• No use of AI on problem sets.
• You may discuss problem sets with other students, but you must understand and write up your solution by yourself. If you do collaborate, indicate who you talked to on your assignment.
• Problem sets may be turned in up to 1 day late without penalty. If you need an extension beyond this, let me know.

Project Information

More information to follow later in the course.

Final Exam Information

• Take-home but timed.
• Open book for class materials only. No external references or AI use.
• More information to be announced closer to the exam.

UMD course-related policies

Web Accessibility