Volume Estimation is a natural and important question in geometry. It is also a canonical example of #P-hard problem for which there exists a fully polynomial randomized approximation scheme. The state-of-the-art algorithms for volume estimation are based on Markov Chain Monte Carlo methods, and are a good example of the utility of simulated annealing for convex problems. In my talk, I will present the main ideas behind these algorithms, and discuss a recent quantum algorithm (https://arxiv.org/abs/1908.03903 ) that obtains a speedup over the classical state-of-the-art (https://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/LovaszVempala.pdf, https://arxiv.org/abs/1409.6011), both in terms of the dimension $n$ and precision $\epsilon$.  These speedups are based on quantum random walks over continuous spaces and involve primitives such as fixed-point Grover search and non-destructive mean estimation.

This talk covers joint work with Andrew Childs, Tongyang Li, Chunhao Wang, Shih -Han Hung and Xiaodi Wu.