Quantum Supremacy I

Explore the concept of quantum supremacy in this 57-minute lecture from the Quantum Wave in Computing Boot Camp. Delve into the high complexity regime, challenges, and starting points of quantum computing. Examine the sharp differences between classical and quantum algorithms, focusing on sampling problems and their basic ideas. Analyze the Stockmeyer Reduction and its implications for average case hardness. Investigate hardness results and approximate hardness in the context of quantum supremacy, gaining valuable insights into this cutting-edge field of computer science.

Intro
Welcome
High Complexity Regime
Challenges
Starting Point
The Difference
Sharp P
Difference between classical and quantum
Quantum algorithm
Sampling problems
The basic idea
Drawbacks
Stockmeyer Reduction
Average Case Hardness
Hardness Results
Approximate Hardness