Ruizhe Zhang - Quantum Speedups of Continuous Sampling and Optimization Problems - IPAM at UCLA
October 6, 2023
Abstract
Recorded 06 October 2023. Ruizhe Zhang of the Simons Institute for the Theory of Computing presents "Quantum Speedups of Continuous Sampling and Optimization Problems" at IPAM's Quantum Algorithms for Scientific Computation Workshop.
Abstract: 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.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-i-quantum-algorithms-for-scientific-computation/?tab=schedule