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; Frederic Dupuis; Sebastien Gambs; Alain Tapp

hal-00660058, version 1

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 ¹, Frederic Dupuis ², Sebastien Gambs ^3, 4, Alain Tapp ¹

(2011-06-21)

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.

1: Département d'Informatique et de Recherche Opérationnelle [Montreal] (DIRO)
Université de Montréal
2: Department of Computer Science (ETH Zurich)
ETH Zurich
3: CIDRE (INRIA - SUPELEC)
INRIA – SUPELEC
4: CIDER (IRISA)
Université de Rennes 1 – Institut National des Sciences Appliquées (INSA) - Rennes – CNRS : UMR6074

hal-00660058, version 1
http://hal.inria.fr/hal-00660058
oai:hal.inria.fr:hal-00660058
From: Sébastien Gambs <>
Submitted on: Sunday, 15 January 2012 15:27:11
Updated on: Saturday, 12 May 2012 10:12:27

See detailed view

Associated documents

arXiv: 1106.4267

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Documents without publication reference (Preprint)</head>
<biblStruct type="article" xml:id="hal-00660058"><analytic>
<author><persName><forename>Gilles</forename><surname>Brassard</surname></persName>
<affiliation>
<orgName type="laboratory">DIRO</orgName>
<orgName type="team">Département d'Informatique et de Recherche Opérationnelle [Montreal]</orgName>
<country>CA</country>
<orgName type="institution">Université de Montréal</orgName>
</affiliation>
</author>
<author><persName><forename>Frederic</forename><surname>Dupuis</surname></persName>
<affiliation>
<orgName type="laboratory">ETH Zurich</orgName>
<orgName type="team">Department of Computer Science</orgName>
<country>CH</country>
<orgName type="institution">ETH Zurich</orgName>
</affiliation>
</author>
<author><persName><forename>Sebastien</forename><surname>Gambs</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA - SUPELEC</orgName>
<orgName type="team">CIDRE</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">SUPELEC</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">IRISA</orgName>
<orgName type="team">CIDER</orgName>
<country>FR</country>
<orgName type="institution">Université de Rennes 1</orgName>
<orgName type="institution">Institut National des Sciences Appliquées (INSA) - Rennes</orgName>
<orgName type="institution">CNRS : UMR6074</orgName>
</affiliation>
</author>
<author><persName><forename>Alain</forename><surname>Tapp</surname></persName>
<affiliation>
<orgName type="laboratory">DIRO</orgName>
<orgName type="team">Département d'Informatique et de Recherche Opérationnelle [Montreal]</orgName>
<country>CA</country>
<orgName type="institution">Université de Montréal</orgName>
</affiliation>
</author>
<title type="main" level="a">An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance</title></analytic><monogr><imprint/></monogr><idno type="HALid">http://hal.inria.fr/hal-00660058</idno></biblStruct>
</listBibl>
</listBibl>