2003/03/10 by Marek Kwas, Henryk Woźniakowski, Kwas, Marek +2 · 2 citations
Computer Science · Physics and Astronomy · #Coding theory and cryptography #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0303049
32 pages, 2 figures
arxiv created 2003/03/10 · openalex publication_date 2003/03/10 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the quantum summation (QS) algorithm of Brassard, Hoyer, Mosca and Tapp, that approximates the arithmetic mean of a Boolean function defined on N elements. We improve error bounds presented in [1] in the worst-probabilistic setting, and present new error bounds in the average-probabilistic setting. In particular, in the worst-probabilistic setting, we prove that the error of the QS algorithm using M - 1 queries is 3π/(4M) with probability 8/π2, which improves the error bound πM-1 + π2 M-2 of Brassard et al. We also present bounds with probabilities p∈ (1/2, 8/π2] and show they are sharp for large M and NM-1. In the average-probabilistic setting, we prove that the QS algorithm has error of order min\M-1, N-1/2\ if M is divisible by 4. This bound is optimal, as recently shown in [10]. For M not divisible by 4, the QS algorithm is far from being optimal if M ≪ N1/2 since its error is proportional to M-1^.