A quantum algorithm estimates the volume of an n-dimensional convex body within error epsilon using O-tilde(n^3 + n^2.5/epsilon) membership queries, the first quantum speedup for this task.
Efficient Convex Optimization with Membership Oracles
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We consider the problem of minimizing a convex function over a convex set given access only to an evaluation oracle for the function and a membership oracle for the set. We give a simple algorithm which solves this problem with $\tilde{O}(n^2)$ oracle calls and $\tilde{O}(n^3)$ additional arithmetic operations. Using this result, we obtain more efficient reductions among the five basic oracles for convex sets and functions defined by Gr\"otschel, Lovasz and Schrijver.
fields
quant-ph 1years
2019 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
Quantum algorithm for estimating volumes of convex bodies
A quantum algorithm estimates the volume of an n-dimensional convex body within error epsilon using O-tilde(n^3 + n^2.5/epsilon) membership queries, the first quantum speedup for this task.