Szczegóły publikacji
Opis bibliograficzny
On the complexity of searching for a maximum of a function on a quantum computer / Maciej GOĆWIN // Quantum Information Processing ; ISSN 1570-0755 . — 2006 — vol. 5 no. 1, s. 31–41. — Bibliogr. s. 40–41
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 32137 |
|---|---|
| Data dodania do BaDAP | 2007-03-07 |
| Tekst źródłowy | URL |
| DOI | 10.1007/s11128-006-0011-8 |
| Rok publikacji | 2006 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Quantum Information Processing |
Abstract
We deal with the problem of finding a maximum of a function from the Holder class on a quantum computer We show matching lower and upper bounds oil the complexity of this problem. We prove upper bounds by constructing an alogorithm that uses a pre-exisiting quantum algorithm for finding maximum of a discrete sequence. To prove lower bounds we use results for finding the logical OR of sequence of bits. We show that quantum computation yields a quadratic speed-up over deterministic and randomized algorithms.
