Basic quantum subroutines: finding multiple marked elements and summing numbers
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Basic quantum subroutines : finding multiple marked elements and summing numbers. / Van Apeldoorn, Joran; Gribling, Sander; Nieuwboer, Harold.
In: Quantum, Vol. 8, 1284, 2024.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Basic quantum subroutines
T2 - finding multiple marked elements and summing numbers
AU - Van Apeldoorn, Joran
AU - Gribling, Sander
AU - Nieuwboer, Harold
N1 - Publisher Copyright: © 2024 Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften. All rights reserved.
PY - 2024
Y1 - 2024
N2 - 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.
AB - 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.
U2 - 10.22331/q-2024-03-14-1284
DO - 10.22331/q-2024-03-14-1284
M3 - Journal article
AN - SCOPUS:85189683580
VL - 8
JO - Quantum
JF - Quantum
SN - 2521-327X
M1 - 1284
ER -
ID: 388875723