01581nas a2200181 4500008004100000245006200041210006200103260001100165490000600176520106100182100002701243700002301270700001901293700001701312700001801329700001501347856003701362 2023 eng d00aQuantum algorithm for estimating volumes of convex bodies0 aQuantum algorithm for estimating volumes of convex bodies c4/20230 v43 a
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 O~(n3.5+n2.5/ε) queries to a membership oracle and O~(n5.5+n4.5/ε) additional arithmetic operations. For comparison, the best known classical algorithm uses O~(n4+n3/ε2) queries and O~(n6+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.
1 aChakrabarti, Shouvanik1 aChilds, Andrew, M.1 aHung, Shih-Han1 aLi, Tongyang1 aWang, Chunhao1 aWu, Xiaodi uhttps://arxiv.org/abs/1908.03903