Quantum algorithm for estimating volumes of convex bodies
share
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 Õ(n^3.5+n^2.5/ϵ) queries to a membership oracle and Õ(n^5.5+n^4.5/ϵ) additional arithmetic operations. For comparison, the best known classical algorithm uses Õ(n^4+n^3/ϵ^2) queries and Õ(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.
READ FULL TEXT