Basic quantum subroutines: finding multiple marked elements and summing numbers
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Forlagets udgivne version, 802 KB, PDF-dokument
We show how to find all k marked elements in a list of size N using the optimal number O(√Nk) of quantum queries and only a polylogarithmic overhead in the gate complexity, in the setting where one has a small quantum memory. Previous algorithms either incurred a factor k overhead in the gate complexity, or had an extra factor log(k) in the query complexity. We then consider the problem of finding a multiplicative d-approximation of s =ΣNi=1viwhere v = (vi) ∈ [0, 1]N, given quantum query access to a binary description of v. We give an algorithm that does so, with probability at least 1 - ρ, using O(√N log(1/ρ)/δ) quantum queries (under mild assumptions on ρ). This quadratically improves the dependence on 1/δ and log(1/ρ) compared to a straightforward application of amplitude estimation. To obtain the improved log(1/ρ) dependence we use the first result.
Originalsprog | Engelsk |
---|---|
Artikelnummer | 1284 |
Tidsskrift | Quantum |
Vol/bind | 8 |
Antal sider | 29 |
ISSN | 2521-327X |
DOI | |
Status | Udgivet - 2024 |
Bibliografisk note
Publisher Copyright:
© 2024 Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften. All rights reserved.
Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk
ID: 388875723