Efficient quantum algorithm for numerical gradient estimation
Stephen P. Jordan · arXiv (Cornell University) · 2004
Given a blackbox for f, a smooth real scalar function of d real variables, one wants to estimate the gradient of f at a given point with n bits of precision. On a classical computer this requires a minimum of d+1 blackbox queries, whereas on a quantum computer it requires only two queries regardless of d. The number of bits of precision to which f must be evaluated differs between the quantum and classical cases. In the limit of large n the quantum algorithm requires twice as many bits.