Modern quantum complexity theory
CSE 599c | Spring 2026
This course introduces quantum computational complexity theory, the study of the fundamental power and limitations of quantum computers. Topics include quantum complexity classes, Hamiltonian complexity, quantum games, low-depth quantum circuits, query complexity and open problem in the quantum setting. The goal of the course is to assist with or prepare for research in quantum complexity theory.
The emphasis will be to setup students to make progress on open questions broadly related to (1) quantum hardness-of-approximation, (2) entanglement complexity and area laws, (3) interactive protocols for quantum computation, (4) complexity theoretic foundations of quantum cryptography and more.
The course will be lecture-based, but flexible. Time permitting, student and guest speaker presentations will be incorporated. Course grades are based 50% on attendance/participation and 50% on ~ 6-10 homework problems.
This course builds on both quantum computation (CSE 534) and complexity theory (CSE 531). Knowledge of both is encouraged but not explicitly required. As in any other CS theory courses, appreciation and willingness to delve into topics with mathematical rigor is ideal.
The University takes academic integrity very seriously. Behaving with integrity is part of our responsibility to our shared learning community. If you’re uncertain about if something is academic misconduct, ask me. I am willing to discuss questions you might have.
Acts of academic misconduct may include but are not limited to:
Concerns about these or other behaviors prohibited by the Student Conduct Code will be referred for investigation and adjudication by (include information for specific campus office).
Students found to have engaged in academic misconduct may receive a zero on the assignment (or other possible outcome).
Your experience in this class is important to me. It is the policy and practice of the University of Washington to create inclusive and accessible learning environments consistent with federal and state law. If you have already established accommodations with Disability Resources for Students (DRS), please activate your accommodations via myDRS so we can discuss how they will be implemented in this course.
If you have not yet established services through DRS, but have a temporary health condition or permanent disability that requires accommodations (conditions include but not limited to; mental health, attention-related, learning, vision, hearing, physical or health impacts), contact DRS directly to set up an Access Plan. DRS facilitates the interactive process that establishes reasonable accommodations. Contact DRS at disability.uw.edu.
Washington state law requires that UW develop a policy for accommodation of student absences or significant hardship due to reasons of faith or conscience, or for organized religious activities. The UW’s policy, including more information about how to request an accommodation, is available at Religious Accommodations Policy (https://registrar.washington.edu/staffandfaculty/religious-accommodations-policy/). Accommodations must be requested within the first two weeks of this course using the Religious Accommodations Request form (https://registrar.washington.edu/students/religious-accommodations-request/).
Call SafeCampus at 206-685-7233 anytime – no matter where you work or study – to anonymously discuss safety and well-being concerns for yourself or others. SafeCampus’s team of caring professionals will provide individualized support, while discussing short- and long-term solutions and connecting you with additional resources when requested.
The University of Washington prohibits sex discrimination and sex-based harassment and expects all UW community members to respect one another in our shared academic and work environments. Sex discrimination and sex-based harassment can include sexual assault, relationship violence, stalking, unwanted sexual contact, sexual exploitation, sexual harassment, and discrimination based on sex.
Students who believe they have experienced sex discrimination or sex-based harassment are encouraged to contact a Title IX case manager by making a Title IX report. The case manager can provide guidance on available support resources and resolution options.