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 theoryUnderstand what promise problems areUnderstand circuit models of computingUnderstand more quantum modelsUnderstand what complexity classes areUnderstand more behind complexity classesUnderstand NP
-
Understand BPP and BQPUnderstand a BQP complete problemUnderstand the difference between quantum vs classical complexityUnderstand that what have you learned leads to quantum supremacyUnderstand how to go beyond NPUnderstand approximate and exact counting for going beyond NPUnderstand 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