Computational Complexity And Quantum Supremacy

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


  • 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


  • 5m 15s
    Get a basic understanding of complexity theory FREE ACCESS
  • 2m 50s
    Learn about promise problems FREE ACCESS
  • Locked
    3.  Models Of Computing: Circuits
    8m 45s
    Learn about circuit models of computing FREE ACCESS
  • Locked
    4.  Random, Quantum, and Non-Determinism
    4m 42s
    Learn about more quantum models FREE ACCESS
  • Locked
    5.  Complexity Classes: Deterministic Time
    1m 24s
    Learn how to put all topics from previous videos together FREE ACCESS
  • Locked
    6.  Complexity Classes: Polynomial Exponential & PSPACE
    3m 18s
    Learn more about complexity classes FREE ACCESS
  • Locked
    7.  Complexity Classes: Nondeterministic Polynomial Time
    3m 48s
    Learn what NP is and why its important FREE ACCESS
  • Locked
    8.  BPP and BQP
    2m 27s
    Learn about the BPP and BQP classes FREE ACCESS
  • Locked
    9.  BQP-Complete Problem: Quantum Circuit Evaluation
    5m 38s
    Learn about a BQP-Complete problem FREE ACCESS
  • Locked
    10.  BQP & BPP: Quantum vs Classical Complexity
    2m 33s
    Learn about the difference between quantum and classical complexity FREE ACCESS
  • Locked
    11.  How To Think About Quantum Supremacy
    Learn how the topics in this course lead to quantum supremacy FREE ACCESS
  • Locked
    12.  Beyond NP- Counting Solutions
    3m 33s
    Learn about going beyond NP FREE ACCESS
  • Locked
    13.  Beyond NP- Approximate and Exact Counting
    4m 56s
    Learn about approximate and exact counting FREE ACCESS
  • Locked
    14.  Modern Argument Of Quantum Supremacy
    3m 4s
    Learn about the modern argument of quantum supremacy FREE ACCESS