Quantum algorithm for estimating volumes of convex bodies

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 $\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.

arXiv comment61 pages, 8 figures. v2: Quantum query complexity improved to $\tilde{O}(n^3+n^{2.5}/\epsilon )$ and number of additional arithmetic operations improved to $\tilde{O}(n^5+n^{4.5}/\epsilon )$. v3: Improved Section 4.3.3 on nondestructive mean estimation and Section 6 on quantum lower bounds; various minor changes

References in corpus (20)

• Quantum Mechanics helps in searching for a needle in a haystack
• Strengths and Weaknesses of Quantum Computing
• Quantum Amplitude Amplification and Estimation
• Quantum Computation and Decision Trees
• Exponential algorithmic speedup by quantum walk
• Quantum speedup of Monte Carlo methods
• Quantum Metropolis Sampling
• Search via Quantum Walk
• Fixed-point quantum search with an optimal number of queries
• Quantum Simulations of Classical Annealing Processes
• A Quantum-Quantum Metropolis Algorithm
• Speed-up via Quantum Sampling
• Quantum speedup of classical mixing processes
• Decoherence in Quantum Walks on the Hypercube
• Almost uniform sampling via quantum walks
• Quantum Speed-up for Approximating Partition Functions
• Quantum algorithms and lower bounds for convex optimization
• Convex optimization using quantum oracles
• Faster quantum mixing for slowly evolving sequences of Markov chains
• Analog quantum algorithms for the mixing of Markov chains

Cited by in corpus (5)

• A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
• A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation
• Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians
• Quantized Markov Chain Couplings that Prepare Qsamples
• On Quantum Perceptron Learning via Quantum Search