Quantum algorithm for estimating volumes of convex bodies

Abstract

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 $ϵ$ using $\tilde{O}(n^3+n^{2.5}/ϵ)$ queries to a membership oracle and $\tilde{O}(n^5+n^{4.5}/ϵ)$ additional arithmetic operations. For comparison, the best known classical algorithm uses $\tilde{O}(n^4+n^3/{ϵ}^2)$ queries and $\tilde{O}(n^6+n^5/{ϵ}^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/ϵ)$ quantum membership queries, which rules out the possibility of exponential quantum speedup in $n$ and shows optimality of our algorithm in $1/ϵ$ up to poly-logarithmic factors.