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

We consider the root finding of a real-valued function ff defined on the dd-dimensional unit cube. We assume that ff has rr continuous partial derivatives, with all partial derivatives of order rr 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+ρ)ε-d/(r+ρ). In the quantum setting, the εε-complexity is shown to be of order ε-d/(2(r+ρ))ε-d/(2(r+ρ)). This means that a quadratic speed-up is achieved on a quantum computer.