Szczegóły publikacji
Opis bibliograficzny
Complexity of solving nonlinear equations in the deterministic, randomized and quantum settings / Maciej GOĆWIN, Bolesław KACEWICZ // Applied Mathematics and Computation ; ISSN 0096-3003. — 2013 — vol. 224, s. 652–662. — Bibliogr. s. 661–662, Abstr.
Autorzy (2)
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 77162 |
|---|---|
| Data dodania do BaDAP | 2013-10-30 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.amc.2013.09.008 |
| Rok publikacji | 2013 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Applied Mathematics and Computation |
Abstract
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.
