ABCDEFGHIJKLMNOPQRSTUVWXYZ
1
LecturesTopic
2
Lecture 1Basics of Quantum Computing
3
Lecture 2Quantum complexity classes: BQP and QMA
4
Lecture 3Bell's inequality and non-local games
5
Lecture 4Mixed states, observables, and super-operators
6
Lecture 5The Fourier Sampling algorithm
7
Lecture 6Hidden Subgroup Problem
8
9
SeminarsPresenter 1Presenter 2References
10
Lecture 7The Quantum Cook-Levin theoremYiyi-
https://groups.uni-paderborn.de/fg-qi/courses/UPB_QCOMPLEXITY/2019/notes/Lecture%206%20-%20The%20Quantum%20Cook-Levin%20Theorem.pdf
11
Lecture 8The Quantum PCP conjectureLeoOrlando
https://arxiv.org/abs/1309.7495
12
Lecture 9Quantum Interactive ProofsAnantKevin
https://arxiv.org/abs/1610.01664
13
Lecture 10MIP* = RESam S-
https://www.henryyuen.net/classes/fall2020/ ()
14
Lecture 11Quantum Zero-Knowledge ProofsZhongqi (zz479)Kenan W
https://www.cs.umd.edu/~jkatz/complexity/f05/QZK.pdf
15
Lecture 12Quantum Supremacy: Yamakawa-ZhandryShreyHayden
https://arxiv.org/abs/2204.02063
16
Lecture 13Quantum TomographyDeniz (da626)Harold
https://arxiv.org/abs/2305.20069
17
Lecture 14The Bell sampling algorithmMaja KokotChenxi L
https://people.maths.bris.ac.uk/~csxam/papers/bsampling.pdf
18
Lecture 15Limitations of quantum algorithmsIsaac (iag38)Mate (mm2771)
https://arxiv.org/pdf/quant-ph/9802049
19
Lecture 16Shallow quantum circuitsAlisonVaibhav
https://arxiv.org/abs/2311.09631
20
21
Topics for projects (feel free to suggest other papers)
22
Unentanglement and Post-Measurement Branching in Quantum Interactive Proofs
https://eccc.weizmann.ac.il/report/2025/145/
23
How hard is it to verify a classical shadow?
https://arxiv.org/abs/2510.08515
24
Conjugate queries can help
https://arxiv.org/abs/2510.07622
25
No exponential quantum speedup for SIS∞ anymore
https://arxiv.org/abs/2510.07515v1
26
Reconquering Bell sampling on qudits
https://arxiv.org/abs/2510.06848
27
Clifford testing: algorithms and lower bounds
https://arxiv.org/pdf/2510.07164
28
Fourier Spectrum of Noisy Quantum Algorithms
https://arxiv.org/abs/2510.06385
29
Randomized and quantum approximate matrix multiplication
https://arxiv.org/abs/2510.08509
30
Efficient Quantum Hermite Transform
https://arxiv.org/pdf/2510.04929
31
Magic and communication complexity
https://arxiv.org/abs/2510.07246
32
On the Pure Quantum Polynomial Hierarchy
https://arxiv.org/abs/2510.06522
33
On the complexity of estimating ground state entanglement
https://arxiv.org/abs/2510.06796
34
The power of quantum circuits in sampling
https://arxiv.org/abs/2510.03645
35
Discrete Bulk Reconstruction
https://arxiv.org/abs/2210.15601
36
Two bases suffice for QMA1-completeness
https://arxiv.org/abs/2509.24390v1
37
Gap amplification for for quantum Hamiltonians
https://arxiv.org/abs/2510.01333v1
38
Instance-Optimal Quantum State Certification
https://arxiv.org/abs/2507.06010v1
39
Few Single-Qubit Measurements Suffice to Certify Any Quantum State
https://arxiv.org/abs/2506.11355v1
40
Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument
https://arxiv.org/abs/quant-ph/0208062
41
Maximum Separation of Quantum Communication Complexity
http://arxiv.org/abs/2505.16457v1
42
QMA vs. QCMA and Pseudorandomness
http://arxiv.org/abs/2411.14416v4
43
Polynomial-time tolerant testing stabilizer states
https://arxiv.org/abs/2408.06289
44
Learning stabilizer structure of quantum states
https://arxiv.org/abs/2510.05890
45
Testing and learning structured quantum Hamiltonians
https://arxiv.org/pdf/2411.00082
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100