Sharp error bounds on quantum Boolean summation in various settings

DOI10.1016/J.JCO.2003.08.004MaRDI QIDQ1888376zbMATH OpenOpenAlexFDO

Publication date 23 November 2004

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0303049

Abstract: 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 p i / (4 M)

with probability

8 / p i^{2}

, which improves the error bound

p i M^{- 1} + p i^{2} M^{- 2}

of Brassard et al. We also present bounds with probabilities

p i n (1 / 2, 8 / p i^{2}]

and show they are sharp for large

M

and

N M^{- 1}

. In the average-probabilistic setting, we prove that the QS algorithm has error of order

m i n 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 l l N^{1 / 2}

since its error is proportional to

.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Sharp error bounds on quantum Boolean summation in various settings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1888376)