Speaker - Edwardson School of Industrial Engineering - Purdue University

Quantum speedups for sampling and optimization problems

Sampling and optimization in high-dimensional continuous spaces are fundamental computational problems with wide applications in statistics, machine learning, physics, and other fields. We develop quantum algorithms to sample from a d-dimensional log-concave distribution with polynomial quantum speedups. We also apply our quantum samplers to estimate normalizing constants of log-concave distributions, achieving an almost optimal precision dependence. Furthermore, we go beyond the convex regime and consider the approximately convex optimization problem, which is an important problem in robust optimization and paves the way for understanding nonconvex optimization in the general case. We show a quantum algorithm that runs faster than the best-known classical algorithm. As an application, we can use it to solve the quantum version of the zeroth-order stochastic convex bandit problem with exponentially reduced T (the number of rounds) dependence in the regret compared to the classical lower bound.