  We initiate the study of quantum algorithms for optimizing approximately
convex functions. Given a convex set ${\cal K}\subseteq\mathbb{R}^{n}$ and a
function $F\colon\mathbb{R}^{n}\to\mathbb{R}$ such that there exists a convex
function $f\colon\mathcal{K}\to\mathbb{R}$ satisfying $\sup_{x\in{\cal
K}}|F(x)-f(x)|\leq \epsilon/n$, our quantum algorithm finds an $x^{*}\in{\cal
K}$ such that $F(x^{*})-\min_{x\in{\cal K}} F(x)\leq\epsilon$ using
$\tilde{O}(n^{3})$ quantum evaluation queries to $F$. This achieves a
polynomial quantum speedup compared to the best-known classical algorithms. As
an application, we give a quantum algorithm for zeroth-order stochastic convex
bandits with $\tilde{O}(n^{5}\log^{2} T)$ regret, an exponential speedup in $T$
compared to the classical $\Omega(\sqrt{T})$ lower bound. Technically, we
achieve quantum speedup in $n$ by exploiting a quantum framework of simulated
annealing and adopting a quantum version of the hit-and-run walk. Our speedup
in $T$ for zeroth-order stochastic convex bandits is due to a quadratic quantum
speedup in multiplicative error of mean estimation.
