Quantum Speedups for Computing Expectation Values and Partition Functions

Monte Carlo methods are used extensively in various fields of science and engineering, such as statistical physics, finance, or machine learning. At the core of these methods, one can often find Monte Carlo processes whose expected outcomes are to be estimated with the highest possible accuracy. Quantum computing has opened the path to new algorithmic primitives (for instance, Quantum Phase Estimation) that can provide noticeable advantages for estimating certain parameters. In this talk, we present new advanced quantum algorithms for estimating fundamental statistics such as the mean of multivariate distributions or the partition function of Gibbs distributions. We highlight the core techniques behind these results, and we describe directions for future work.