Quantum Algorithms on Convex Bodies

          @misc{ scivideos_15441,
            doi = {},
            url = {https://simons.berkeley.edu/talks/quantum-algorithms-convex-bodies},
            author = {},
            keywords = {},
            language = {en},
            title = {Quantum Algorithms on Convex Bodies},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {feb},
            note = {15441 see, \url{https://scivideos.org/Simons-Institute/15441}}
          }
          

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.