Quantum Boolean Summation with Repetitions in the Worst-Average Setting

Simple item page
dc.creatorHeinrich, Stefan
dc.creatorKwas, Marek
dc.creatorWozniakowski, Henryk
dc.date2003-11-06
dc.date.accessioned2026-07-07T06:08:15Z
dc.date.available2026-07-07T06:08:15Z
dc.descriptionWe study the quantum summation QS algorithm of Brassard, Hoyer, Mosca and Tapp, which approximates the arithmetic mean of a Boolean function defined on $N$ elements. We present sharp error bounds of the QS algorithm in the worst-average setting with the average performance measured in the $L_q$ norm, $q \in [1,\infty]$. We prove that the QS algorithm with $M$ quantum queries, $M<N$, has the worst-average error bounds of the form $Θ(\ln M/M)$ for $q=1$, $Θ(M^{-1/q})$ for $q\in (1,\infty)$, and is equal to 1 for $q=\infty$. We also discuss the asymptotic constants of these estimates. We improve the error bounds by using the QS algorithm with repetitions. Using the number of repetitions which is independent of $M$ and linearly dependent on $q$, we get the error bound of order $M^{-1}$ for any $q \in [1,\infty)$. Since $Ω(M^{-1})$ is a lower bound on the worst-average error of any quantum algorithm with $M$ queries, the QS algorithm with repetitions is optimal in the worst-average setting.
dc.description16 pages
dc.identifierhttps://arxiv.org/abs/quant-ph/0311036
dc.identifierhttp://arxiv.org/abs/quant-ph/0311036
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/91566
dc.subjectQuantum Physics
dc.titleQuantum Boolean Summation with Repetitions in the Worst-Average Setting
dc.typetext

Files

Collections

arXiv