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

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.
Type de document :
Pré-publication, Document de travail
Ten pages, no figures, three algorithms. 2011
Liste complète des métadonnées

https://hal.inria.fr/hal-00660058
Contributeur : Sébastien Gambs <>
Soumis le : dimanche 15 janvier 2012 - 15:27:11
Dernière modification le : mardi 16 janvier 2018 - 15:54:19

Identifiants

  • HAL Id : hal-00660058, version 1
  • ARXIV : 1106.4267

Citation

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. Ten pages, no figures, three algorithms. 2011. 〈hal-00660058〉

Partager

Métriques

Consultations de la notice

558