Q8 · Complexity
A 23-module path through q8 · complexity, in study order from foundations to the frontier.
Modules
- The Complexity Class BQP
- BQP versus P, NP, and PSPACE
- BQP is Contained in PP and PSPACE
- Quantum Merlin-Arthur (QMA)
- The Local Hamiltonian Problem
- The Quantum Cook-Levin Theorem
- QMA Variants and Related Classes
- Quantum Interactive Proofs (QIP)
- QIP = PSPACE
- MIP* = RE
- Quantum Query Complexity
- The Polynomial Method for Quantum Lower Bounds
- The Quantum Adversary Method
- Quantum Communication Complexity
- Oracle Separations in Quantum Complexity
- Oracle Separation of BQP and the Polynomial Hierarchy
- Quantum Supremacy and Quantum Advantage
- Random Circuit Sampling
- Boson Sampling
- Instantaneous Quantum Polynomial-Time (IQP)
- Hardness Arguments for Sampling Problems
- Cross-Entropy Benchmarking and Verification of Sampling
- PostBQP and Quantum Postselection