An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance

(1) , (2) , (3, 4) , (1)
1
2
3
4

Abstract

We describe two quantum algorithms to approximate the mean value of a black-box function. The first algorithm is novel and asymptotically optimal while the second is a variation on an earlier algorithm due to Aharonov. Both algorithms have their own strengths and caveats and may be relevant in different contexts. We then propose a new algorithm for approximating the median of a set of points over an arbitrary distance function.

Dates and versions

hal-00660058 , version 1 (15-01-2012)

Identifiers

Cite

Gilles Brassard, Frederic Dupuis, Sebastien Gambs, Alain Tapp. An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance. 2011. ⟨hal-00660058⟩
228 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More