Quantum Algorithm for Estimating Volumes of Convex Bodies
Quantum Algorithm for Estimating Volumes of Convex Bodies
复制标题
DOI：
10.1145/3588579
复制
发表时间：
2019-08
期刊：
影响因子：
--
通讯作者：
Shouvanik Chakrabarti;Andrew M. Childs;S. Hung;Tongyang Li;C. Wang;Xiaodi Wu
中科院分区：
文献类型：
--
作者：
Shouvanik Chakrabarti;Andrew M. Childs;S. Hung;Tongyang Li;C. Wang;Xiaodi Wu
估计凸体的体积是凸几何学中的一个中心问题，可以看作是计数的一个连续版本。我们给出了一个量子算法，它在乘法误差ε下使用Õ(n3+n2.5/ε)查询成员神谕和Õ(n5+n4.5/ε)额外的算术运算来估计n维凸体的体积。作为比较，最著名的经典算法使用Õ(n3.5+n3/ε2)个查询和Õ(n5.5+n5/ε2)个额外算术运算。据我们所知，这是体积估计的第一次量子加速。我们的算法基于一个改进的框架，用于加速可能独立感兴趣的模拟退火法。这一框架适用于“切比雪夫冷却”的情况，其中解被表示为比率的伸缩乘积，每个比率都具有有界方差。在实现我们的框架时，我们开发了几种新的技术，包括具有严格离散化误差界的连续空间量子行走理论。为了补充我们的量子算法，我们还证明了体积估计需要Ω(√n+1/ε)量子成员查询，这排除了n的指数量子加速的可能性，并证明了我们的算法在1/ε直到多对数因子的最优性。
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 Õ(n3 + n2.5/ε) queries to a membership oracle and Õ(n5+n4.5/ε) additional arithmetic operations. For comparison, the best known classical algorithm uses Õ(n3.5+n3/ε2) queries and Õ(n5.5+n5/ε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 Ω (√ 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.