Quantum Boolean Summation with Repetitions in the Worst-Average Setting
Stefan Heinrich, Marek Kwas, Henryk Woźniakowski · arXiv (Cornell University) · 2003
We 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