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.

Ten pages, no figures, three algorithms

Cited by in corpus (11)

• Quantum speedup of Monte Carlo methods
• Quantum computing for finance
• Low depth algorithms for quantum amplitude estimation
• Quantum Differentially Private Sparse Regression Learning
• A quantum algorithm to approximate the linear structures of Boolean functions
• Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
• A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
• Some Error Analysis for the Quantum Phase Estimation Algorithms
• Hybrid Quantum-Classical Algorithm For Robust Optimization via Stochastic-Gradient Online Learning
• Quantum Chebyshev's Inequality and Applications
• Quantum Coin Method for Numerical Integration