English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We initiate the study of quantum algorithms for optimizing approximatelyconvex functions. Given a convex set ${\cal K}\subseteq\mathbb{R}^{n}$ and afunction $F\colon\mathbb{R}^{n}\to\mathbb{R}$ such that there exists a convexfunction $f\colon\mathcal{K}\to\mathbb{R}$ satisfying $\sup_{x\in{\calK}}|F(x)-f(x)|\leq \epsilon/n$, our quantum algorithm finds an $x^{*}\in{\calK}$ 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 apolynomial quantum speedup compared to the best-known classical algorithms. Asan application, we give a quantum algorithm for zeroth-order stochastic convexbandits with $\tilde{O}(n^{5}\log^{2} T)$ regret, an exponential speedup in $T$compared to the classical $\Omega(\sqrt{T})$ lower bound. Technically, weachieve quantum speedup in $n$ by exploiting a quantum framework of simulatedannealing and adopting a quantum version of the hit-and-run walk. Our speedupin $T$ for zeroth-order stochastic convex bandits is due to a quadratic quantumspeedup in multiplicative error of mean estimation.

Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits