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

摘要

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 Hölder functions with the exponent ρ. We study the ε-complexity of this problem in three settings: deterministic, randomized and quantum. It is known that with the root error criterion the deterministic ε-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 ε-complexity is of order ε-d/(r+ρ). In the quantum setting, the ε-complexity is shown to be of order ε-d/(2(r+ρ)). This means that a quadratic speed-up is achieved on a quantum computer.