Complexity of solving nonlinear equations in the deterministic, randomized and quantum settings

作     者：Gocwin, Maciej Kacewicz, Boleslaw 

作者机构：AGH Univ Sci & Technol Fac Appl Math PL-30059 Krakow Poland 

出 版 物：《APPLIED MATHEMATICS AND COMPUTATION》 (应用数学和计算)

年 卷 期：2013年第224卷

页      面：652-662页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：Ministry of Science and Higher Education [NN 201 547738  11.11.420.04] 

主　　题：Nonlinear equations Deterministic algorithms Randomized algorithms Quantum algorithms Optimality Complexity 

摘      要：We consider the root finding of a real-valued function f defined on the d-dimensional unit cube. We assume that f has r continuous partial derivatives, with all partial derivatives of order r being Holder functions with the exponent rho. We study the epsilon-complexity of this problem in three settings: deterministic, randomized and quantum. It is known that with the root error criterion the deterministic epsilon-complexity is infinite, i.e., the problem is unsolvable. We show that the same holds in the randomized and quantum settings. Under the residual error criterion, we show that the deterministic and randomized epsilon-complexity is of order epsilon(-d/(r+rho)). In the quantum setting, the epsilon-complexity is shown to be of order epsilon(-d/(2(r+rho))). This means that a quadratic speed-up is achieved on a quantum computer. (C) 2013 Elsevier Inc. All rights reserved.