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

Gilles Brassard (1) , Frederic Dupuis (2) , Sebastien Gambs (3, 4) , Alain Tapp (1)

1 DIRO - Département d'Informatique et de Recherche Opérationnelle [Montreal]
2 D-INFK - Department of Computer Science [ETH Zürich]
3 CIDRE - Confidentialité, Intégrité, Disponibilité et Répartition
4 CIDER

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.

Domaines: Algorithme et structure de données [cs.DS]; Physique Quantique [quant-ph]

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⟩