No Quantum Speedup Over Gradient Descent for Non-Smooth Convex Optimization

Channel:

Subscribers:

68,700

Published on July 15, 2021 4:21:26 PM ● Video Link: https://www.youtube.com/watch?v=m--GP8znQEQ

Duration: 44:20

389 views

Other Videos By Simons Institute for the Theory of Computing

2021-07-16	Provably Efficient Machine Learning for Quantum Many-Body Problems
2021-07-16	Quantum Pseudorandomness and Classical Complexity
2021-07-15	Quantum Generative Training Using Rényi Divergences
2021-07-15	Quantum Algorithms for Escaping from Saddle Points
2021-07-15	Quantum Pseudo-Randomness From Domain Walls and Spectral Gaps
2021-07-15	Noise vs Imprecision in the Hardness of Random Quantum Circuits
2021-07-15	Quantum Learning Algorithms Imply Circuit Lower Bounds
2021-07-15	One-Way Functions Imply Secure Computation in a Quantum World
2021-07-15	Interactive Proofs for Synthesizing Quantum States and Unitaries
2021-07-15	Optimization Based Approach for Quantum Signal Processing and Its Energy Landscape
2021-07-15	No Quantum Speedup Over Gradient Descent for Non-Smooth Convex Optimization
2021-07-15	Symmetries, Graph Properties, and Quantum Speedups
2021-07-15	Optimal Learning of Quantum Hamiltonians From High-Temperature Gibbs States
2021-07-15	Hamiltonian Complexity in the Thermodynamic Limit
2021-07-15	(Sub)Exponential Advantage of Adiabatic Quantum Computation With No Sign Problem
2021-07-15	Quantum Garbled Circuits
2021-07-15	Strongly Universal Hamiltonian Simulators
2021-07-15	On the NLTS Conjecture
2021-07-15	Device-Independent Protocols From Computational Assumptions
2021-07-15	Classical Verification of Quantum Computational Advantage
2021-06-17	Breakthroughs — A Refined Laser Method and Faster Matrix Multiplication

Tags:

Simons Institute

theoretical computer science

UC Berkeley

Computer Science

Theory of Computation

Theory of Computing

Robin Kothari

Quantum Wave in Computing Reunion