Abstract
Algorithms on convex bodies is a central topic in the theory of convex optimization. In this talk, I will introduce two quantum algorithms that we recently proposed with quantum speedups compared to their state-of-the-art classical counterparts. First, I will present a quantum algorithm that estimates the volume of an n-dimensional convex body within multiplicative error eps using tilde{O}(n^3+n^2.5/eps) queries to the membership oracle of the convex body and tilde{O}(n^5+n^4.5/eps) additional arithmetic operations. For comparison, the best-known classical algorithm uses tilde{O}(n^4+n^3/eps^2) queries and tilde{O}(n^6+n^5/eps^2) additional arithmetic operations. Furthermore, I will also briefly introduce a quantum algorithm that can optimize a convex function over an n-dimensional convex body using tilde{O}(n) queries to the membership oracle and the evaluation oracle of the convex function. This represents a quadratic improvement over the best-known classical algorithm.