Quantum Computing Seminar: Quantum Speedups of Continuous Sampling and Optimization Problems

Speaker: Ruizhe Zhang, University of Texas at Austin

Title: Quantum Speedups of Continuous Sampling and Optimization Problems

Abstract:  Sampling and optimization in high dimensional continuous space are fundamental computational problems and have wide applications in statistics, machine learning, physics, etc. First, we develop quantum algorithms to sample from a d-dimensional log-concave distribution (with density proportional to e^{-f(x)} for some convex function f). We achieve polynomial quantum speedups in query complexity over the best-known classical algorithms. We also apply our quantum sampling algorithms to estimate normalizing constants of log-concave distributions, achieving an almost optimal precision dependence. Second, we go beyond convexity and consider the approximate convex optimization problem, where the objective function only promises to be close to an unknown convex function. It is an important problem in robust optimization and paves the way for understanding nonconvex optimization in the general case. Using an efficient quantum sampling procedure, we also achieve polynomial quantum speedup in optimizing approximate convex functions. As an application, we give a quantum algorithm for zeroth-order stochastic convex bandits, exponentially reducing the T (the number of rounds) dependence in the regret compared to the classical lower bound. Based on joint works with Andrew Childs, Tongyang Li, Jin-Peng Liu, and Chunhao Wang (arXiv:2210.06539 and arXiv:2209.12897.

Time:  Monday, April 24, 2023, 12:30pm – 1:30pm

Place:  Exploratory Hall, room 3301

Zoom and In-person

Flyer