CMSC 858L -- Spring 2023
Project Presentations
The project presentations will be in class on May 9 and 11. Additional instructions are here. Sign up for your group to present at
this Google Sheets link.
(You should need your UMD account to access it.)
Homeworks
Lecture Notes
- Lecture 1 (Jan. 26, 2023): Introduction, complexity class overview, basic definitions, Turing machines
- Lecture 2 (Jan. 31, 2023): Circuits, uniformity, P, BPP
- Lecture 3 (Feb. 2, 2023): BQP, NP, NP-completeness
- Lecture 4 (Feb. 7, 2023): QMA, PSPACE
- Lecture 5 (Feb. 9, 2023): Solovay-Kitaev theorem, intro to non-universal quantum circuits
- Lecture 6 (Feb. 14, 2023): Clifford group
- Lecture 7 (Feb. 16, 2023): Matchgates
- Lecture 8 (Feb. 21, 2023): Computational universality
- Lecture 9 (Feb. 23, 2023): Introduction to oracles, Deutsch-Jozsa algorithm
- Lecture 10 (Feb. 28, 2023): Simon's algorithm, Grover's algorithm
- Lecture 11 (Mar. 2, 2023): Lower bounds on query complexity: hybrid method, polynomials
- Lecture 12 (Mar. 7, 2023): Polynomial and adversary bounds
- Lecture 13 (Mar. 9, 2023): Applications of adversary bounds, quantum communication complexity
- Lecture 14 (Mar. 14, 2023): Local Hamiltonian problems and QMA
- Lecture 15 (Mar. 16, 2023): QMA-completeness of local Hamiltonian problems
- Lecture 16 (Mar. 28, 2023): QMA-completeness of local Hamiltonian problems, continued
- Lecture 17 (Mar. 30, 2023): Additional QMA-complete problems
- Lecture 18 (Apr. 4, 2023): QMA witness amplification and quantum PCP
- Lecture 19 (Apr. 6, 2023): PP and PostBQP
- Lecture 20 (Apr. 11, 2023): PP and PostBQP, continued
- Lecture 21 (Apr. 13, 2023): PostBPP and exact quantum supremacy
- Lecture 22 (Apr. 18, 2023): IQP, approximate quantum supremacy
- Lecture 23 (Apr. 20, 2023): Experimental quantum supremacy, PSPACE, interactive proofs
- Lecture 24 (Apr. 25, 2023): Perfect completeness and 3-Round interactive proofs
- Lecture 25 (Apr. 27, 2023): Semidefinite programming, QIP = PSPACE
- Lecture 26 (May 2, 2023): Multiprover interactive proofs, Tsirelson's Problem, and the Connes Embedding Problem
- Lecture 27 (May 4, 2023): MIP* = RE
Topics Covered
Grades
Your grade will have 3 components:
- Problem sets (35%)
- Project (35%)
- Final exam (30%)
Problem Sets
- The problem sets will be available on this web page about once every two weeks.
- The problem sets will be turned in on Gradescope.
- For the problem sets, if you use any external material to solve it (other than the lectures and any referenced sources), cite the source and indicate what you took from it.
- 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 3 days late without penalty. If you need an extension beyond this, let me know; however, remember the reason needs to be good enough to justify a longer than 3 day extension.
Project
- Performed in groups of 1-5 people (larger groups will need more content covered).
- Should present original research or the main results from 1-5 research papers, depending on length of the papers, overlap between them, and group size.
- Each group will turn in a written report (length 10-30 pages, depending on group size and scope of the project) and give a brief presentation in the last week of class.
- The writeup should contain a brief summary of the contributions of each member of the group.
Final Exam
- Most likely take-home.
- More information to be announced closer to the exam.
UMD course-related policies
Web Accessibility