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.

本研究提出一种基于 Chebyshev cooling 并利用量子随机游走技术的量子算法，用于估算多维凸包的体积，比已知的经典算法要更快，同时还证明了量子算法所需的查询次数。

用于估算凸体积的量子算法

Quantum algorithm for estimating volumes of convex bodies

We present an $O^*(n^3)$ randomized algorithm for estimating the volume of a
well-rounded convex body given by a membership oracle, improving on the
previous best complexity of $O^*(n^4)$. The new algorithmic ingredient is an
accelerated cooling schedule where the rate of cooling increases with the
temperature. Previously, the known approach for potentially achieving this
asymptotic complexity relied on a positive resolution of the KLS hyperplane
conjecture, a central open problem in convex geometry.
We also obtain an $O^*(n^3)$ randomized algorithm for integrating a standard
Gaussian distribution over an arbitrary convex set containing the unit ball.
Both the volume and Gaussian volume algorithms use an improved algorithm for
sampling a Gaussian distribution restricted to a convex body. In this latter
setting, as we show, the KLS conjecture holds and for a spherical Gaussian
distribution with variance $\sigma^2$, the sampling complexity is
$O^*(\max\{n^3, \sigma^2n^2\})$ for the first sample and $O^*(\max\{n^2,
\sigma^2n^2\})$ for every subsequent sample.

我们提出了一种基于随机化算法的方法，用于估计具有会员 Oracle 的圆满凸体的体积。我们还提供了一种有改进的高斯分布采样算法，并分析了采样复杂性。