Separating Quantum from Classical with K-Fold Forrelation and Friends
Offered By: Simons Institute via YouTube
Course Description
Overview
Explore a comprehensive lecture on quantum-classical separations through the lens of k-fold Forrelation problem. Delve into the challenges of differentiating quantum and classical complexity classes, and discover how concrete models like query and communication complexity provide valuable insights. Examine recent quantum-classical separations, including oracle separation of BQP and PH, optimal separations between quantum and classical algorithms, and oracle separation of one-way functions from quantum cryptographic primitives. Gain understanding of key analytical tools such as l1-Fourier growth and pathwise analysis, and their broader applications in pseudorandomness and statistical physics. Learn about the work of Makrand Sinha and Nikhil Bansal, as well as contributions from other researchers in this field.
Syllabus
Separating Quantum from Classical with k-fold Forrelation and Friends
Taught by
Simons Institute
Related Courses
مقدمة في علم الحاسوب والبرمجةMassachusetts Institute of Technology via Edraak Algorithmic Information Dynamics: From Networks to Cells
Santa Fe Institute via Complexity Explorer Computational Thinking using Python
Massachusetts Institute of Technology via edX Java: Algorithms
Codecademy Technical Interview Practice with Java
Codecademy