2004/05/31 by Stephen P. Jordan
Physics and Astronomy · #quant-ph
paper · pdf · doi:10.1103/physrevlett.95.050501
published as Phys. Rev. Lett. 95, 050501 (2005) · additional references and minor clarifications and corrections to version 1
arxiv created 2005/01/02 · arxiv updated 2013/05/29
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 one query regardless of d. The number of bits of precision to which f must be evaluated matches the classical requirement in the limit of large n.