Computational Complexity And Quantum Supremacy

  • 14 Videos | 52m 54s
  • Includes Assessment
Likes 1 Likes 1
Learn about computational complexity and consider what it means to demonstrate quantum computational advantage over classical computers.

WHAT YOU WILL LEARN

  • Understand the basics of complexity theory
    Understand what promise problems are
    Understand circuit models of computing
    Understand more quantum models
    Understand what complexity classes are
    Understand more behind complexity classes
    Understand NP
  • Understand BPP and BQP
    Understand a BQP complete problem
    Understand the difference between quantum vs classical complexity
    Understand that what have you learned leads to quantum supremacy
    Understand how to go beyond NP
    Understand approximate and exact counting for going beyond NP
    Understand the modern argument of quantum supremacy

IN THIS COURSE

  • Playable
    1. 
    Introduction To Complexity Theory
    5m 15s
    UP NEXT
  • Playable
    2. 
    Promise Problems
    2m 50s
  • Locked
    3. 
    Models Of Computing: Circuits
    8m 45s
  • Locked
    4. 
    Random, Quantum, and Non-Determinism
    4m 42s
  • Locked
    5. 
    Complexity Classes: Deterministic Time
    1m 24s
  • Locked
    6. 
    Complexity Classes: Polynomial Exponential & PSPACE
    3m 18s
  • Locked
    7. 
    Complexity Classes: Nondeterministic Polynomial Time
    3m 48s
  • Locked
    8. 
    BPP and BQP
    2m 27s
  • Locked
    9. 
    BQP-Complete Problem: Quantum Circuit Evaluation
    5m 38s
  • Locked
    10. 
    BQP & BPP: Quantum vs Classical Complexity
    2m 33s
  • Locked
    11. 
    How To Think About Quantum Supremacy
    41s
  • Locked
    12. 
    Beyond NP- Counting Solutions
    3m 33s
  • Locked
    13. 
    Beyond NP- Approximate and Exact Counting
    4m 56s
  • Locked
    14. 
    Modern Argument Of Quantum Supremacy
    3m 4s