|
Abstract: |
High-dimensional sampling problems are ubiquitous in statistics, operations research, machine learning, etc. In this talk, I will introduce quantum algorithms for two important problems in high-dimensional sampling: logconcave sampling and volume estimation. Technically, we show how to give quantum speedups of Monte Carlo methods by using a quantum version of simulated annealing, applying quantum mean estimation, and replacing classical random walks by quantum walks. This talk is based on two papers: 1. Andrew M. Childs, Tongyang Li, Jin-Peng Liu, Chunhao Wang, Ruizhe Zhang, “Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants”, QIP 2023, NeurIPS 2022, arXiv:2210.06539. 2. Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, Xiaodi Wu, “Quantum algorithm for estimating volumes of convex bodies”, QIP 2020, ACM Transaction on Quantum Computing 2023, arXiv:1908.03903. |
