Sharp Error Bounds on Quantum Boolean Summation in Various Settings

Details Sharp Error Bounds on Quantum Boolean Summation in Various Settings Sharp Error Bounds on Quantum Boolean Summation in Various Settings

2003-03-10

arxiv.org/abs/quant-ph/0303049v1

Physics

Quantum Physics

32 pages, 2 figures

Scientific paper

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\pi /(4M)$ with probability $8/\pi^2$, which improves the error bound $\pi M^{-1} + \pi^2 M^{-2}$ of Brassard et al. We also present bounds with probabilities $p\in (1/2, 8/\pi^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 \ll N^{1/2}$ since its error is proportional to $M^{-1}^$.

Affiliated with

Also associated with

No associations

Rating

Sharp Error Bounds on Quantum Boolean Summation in Various Settings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sharp Error Bounds on Quantum Boolean Summation in Various Settings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sharp Error Bounds on Quantum Boolean Summation in Various Settings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-284177