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 ℓ∞-approximate gradient estimation of multivariate functions f:Rd→R with fewer function evaluations than classically. Following previous work by Jordan [Jor05] and Gilyén et al. [GAW18], we prove that one can calculate an ℓ∞-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én 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 ℓp-approximate gradient estimation problem where p∈[1,∞), and prove that lifting Gilyén et al.'s algorithm to this domain in the canonical manner is essentially optimal.
We investigate whether quantum computers can perform ℓ∞-approximate gradient estimation of multivariate functions f:Rd→R with fewer function evaluations than classically. Following previous work by Jordan [Jor05] and Gilyén et al. [GAW18], we prove that one can calculate an ℓ∞-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én 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 ℓp-approximate gradient estimation problem where p∈[1,∞), and prove that lifting Gilyén et al.'s algorithm to this domain in the canonical manner is essentially optimal.