  Gradient-based numerical methods are ubiquitous in optimization techniques
frequently applied in industry to solve practical problems. Often times,
evaluating the objective function is a complicated process, so estimating the
gradient of a function with as few function evaluations as possible is a
natural problem.
  We investigate whether quantum computers can perform
$\ell^{\infty}$-approximate gradient estimation of multivariate functions $f :
\mathbb{R}^d \to \mathbb{R}$ with fewer function evaluations than classically.
Following previous work by Jordan [Jor05] and Gily\'en et al. [GAW18], we prove
that one can calculate an $\ell^{\infty}$-approximation of the gradient of $f$
with a query complexity that scales sublinearly with $d$ under weaker
smoothness conditions than previously considered.
  Furthermore, for a particular subset of smoothness conditions, we prove a new
lower bound on the query complexity of the gradient estimation problem, proving
essential optimality of Gily\'en et al.'s gradient estimation algorithm in a
broader range of parameter values, and affirming the validity of their
conjecture [GAW18]. Moreover, we improve their lower bound qualitatively by
showing that their algorithm is also optimal for functions that satisfy the
imposed smoothness conditions globally instead of locally. Finally, we
introduce new ideas to prove lower bounds on the query complexity of the
$\ell^p$-approximate gradient estimation problem where $p \in [1,\infty)$, and
prove that lifting Gily\'en et al.'s algorithm to this domain in the canonical
manner is essentially optimal.
