Quantum algorithm for estimating volumes of convex bodies

Understand

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.