Computational Complexity And Quantum Supremacy
Everyone
- 14 videos | 52m 54s
- Includes Assessment
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
-
1.Introduction To Complexity Theory5m 15sUP NEXT
-
2.Promise Problems2m 50s
-
3.Models Of Computing: Circuits8m 45s
-
4.Random, Quantum, and Non-Determinism4m 42s
-
5.Complexity Classes: Deterministic Time1m 24s
-
6.Complexity Classes: Polynomial Exponential & PSPACE3m 18s
-
7.Complexity Classes: Nondeterministic Polynomial Time3m 48s
-
8.BPP and BQP2m 27s
-
9.BQP-Complete Problem: Quantum Circuit Evaluation5m 38s
-
10.BQP & BPP: Quantum vs Classical Complexity2m 33s
-
11.How To Think About Quantum Supremacy41s
-
12.Beyond NP- Counting Solutions3m 33s
-
13.Beyond NP- Approximate and Exact Counting4m 56s
-
14.Modern Argument Of Quantum Supremacy3m 4s
