  Estimating the volume of a convex body is a central problem in convex
geometry and can be viewed as a continuous version of counting. We present a
quantum algorithm that estimates the volume of an $n$-dimensional convex body
within multiplicative error $\epsilon$ using
$\tilde{O}(n^{3}+n^{2.5}/\epsilon)$ queries to a membership oracle and
$\tilde{O}(n^{5}+n^{4.5}/\epsilon)$ additional arithmetic operations. For
comparison, the best known classical algorithm uses
$\tilde{O}(n^{4}+n^{3}/\epsilon^{2})$ queries and
$\tilde{O}(n^{6}+n^{5}/\epsilon^{2})$ additional arithmetic operations. To the
best of our knowledge, this is the first quantum speedup for volume estimation.
Our algorithm is based on a refined framework for speeding up simulated
annealing algorithms that might be of independent interest. This framework
applies in the setting of "Chebyshev cooling", where the solution is expressed
as a telescoping product of ratios, each having bounded variance. We develop
several novel techniques when implementing our framework, including a theory of
continuous-space quantum walks with rigorous bounds on discretization error. To
complement our quantum algorithms, we also prove that volume estimation
requires $\Omega(\sqrt n+1/\epsilon)$ quantum membership queries, which rules
out the possibility of exponential quantum speedup in $n$ and shows optimality
of our algorithm in $1/\epsilon$ up to poly-logarithmic factors.
