Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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.
Complete list of metadatas

https://hal.inria.fr/hal-00660058
Contributor : Sébastien Gambs <>
Submitted on : Sunday, January 15, 2012 - 3:27:11 PM
Last modification on : Monday, July 20, 2020 - 12:34:51 PM

Links full text

Identifiers

  • 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. 2011. ⟨hal-00660058⟩

Share

Metrics

Record views

1126