QUANTUM COMPLEXITY OF THE INTEGRATION PROBLEM FOR ANISOTROPIC CLASSES

(整期优先)网络出版时间:2005-03-13
/ 1
Weobtaintheoptimalorderofhigh-dimensionalintegrationcomplexityinthequantumcomputationmodelinanisotropicSobolevclassesW∞^r([0,1]^d)andHǒlderNikolskiiclassesH∞^r([0,1]^d).Itisprovedthatfortheseclassesoffunctionsthereisaspeed-upofquantumalgorithmsoverdeterministicclassicalalgorithmsduetofactorn^-1andoverrandomizedclassicalmethodsduetofactorn^-1/2.Moreover,wegiveanestimationforoptimalquerycomplexityintheclassH∞^∧(D)whosesmoothnessindexistheboundaryofsomecompletesetinZ+^d.