Szczegóły publikacji
Opis bibliograficzny
On the quantum complexity of computing the median of continuous distributions / Maciej GOĆWIN // Quantum Information & Computation ; ISSN 1533-7146. — 2019 — vol. 19 no. 11–12, s. 952–966. — Bibliogr. s. 965, Abstr. — DOI dla numeru czasopisma: 10.26421/QIC19.11-12
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 125648 |
|---|---|
| Data dodania do BaDAP | 2020-01-08 |
| Rok publikacji | 2019 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Quantum Information & Computation |
Abstract
We study the approximation of the median of an absolutely continuous distribution with respect to the Lebesgue measure given by a probability density function f. We assume that f has r continuous derivatives, with derivative of order r being Holder continuous with the exponent rho. We study the quantum query complexity of this problem. We show that the epsilon-complexity up to a logarithmic factor is of order epsilon(-1/ (r+rho+1)).
