摘要
We obtain the optimal order of high-dimensional integration complexity in the quantumcomputation model in anisotropic Sobolev classes W∞^r ([0, 1]^d) and Hǒlder Nikolskii classes H∞^r([0, 1]^d). It is proved that for these classes of functions there is a speed-up of quantum algorithms over deterministic classical algorithms due to factor n^-1 and over randomized classical methods due to factor n^-1/2. Moreover, we give an estimation for optimal query complexity in the class H∞^∧ (D) whose smoothness index is the boundary of some complete set in Z+^d.
