Session: Quantum algorithms and optimization
Chair: Sander Gribling
Cluster: Optimization for Emerging Technologies (LLMs, Quantum Computing, ...)
Talk 1: Quantum interior point methods
Speaker: Sander Gribling
Abstract: The spectral gap of a Schrodinger operator is a central quantity in the analysis of quantum algorithms such as phase estimation and adiabatic quantum computation. While spectral gaps are typically difficult to characterize, semiclassical analysis can be used to study their asymptotic behavior, often with domain-dependent constants. Motivated by connections to interior point methods, we study Schrodinger operators associated to self-concordant barriers over convex domains. We prove a non-asymptotic, constant lower bound on the spectral gap for this class of operators. As an application, we incorporate this result into a quantum annealing framework to construct a quantum path-following method.
Talk 2: Quantum algorithms for volume estimation
Speaker: Arjan Cornelissen
Abstract: Estimating the volume of a convex body is a canonical problem in theoretical computer science. Its study has led to major advances in randomized algorithms, Markov chain theory, and computational geometry. In particular, determining the query complexity of volume estimation to a membership oracle has been a longstanding open question. Most of the previous work focuses on the high-dimensional limit. In this work, we tightly characterize the deterministic, randomized and quantum query complexity of this problem in the high-precision limit, i.e., when the dimension is constant.
Talk 3: Quantum speedups for stochastic optimization
Speaker: Chenyi Zhang
Abstract: We consider the problem of minimizing a continuous function given access to a natural quantum generalization of a stochastic gradient oracle. We provide two new methods for the special case of minimizing a Lipschitz convex function. Each method obtains a dimension versus accuracy trade-off which is provably unachievable classically and we prove that one method is asymptotically optimal in low-dimensional settings. Additionally, we provide quantum algorithms for computing a critical point of a smooth non-convex function at rates not known to be achievable classically. To obtain these results we build upon the quantum multivariate mean estimation result of Cornelissen et al. and provide a general quantum variance reduction technique of independent interest.
