Quantum Algorithm for Estimating Volumes of Convex Bodies

Shouvanik Chakrabarti, Andrew M. Childs, Shih Han Hung, Tongyang Li, Chunhao Wang, Xiaodi Wu

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

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.

Original languageEnglish (US)
Article number20
JournalACM Transactions on Quantum Computing
Volume4
Issue number3
DOIs
StatePublished - May 8 2023

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Computer Science (miscellaneous)
  • Theoretical Computer Science
  • Statistical and Nonlinear Physics

Cite this