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, Frédéric Dupuis, Sébastien Gambs, Alain TapparXiv 2011 · arXiv

Introduction

Estimating the average value of a large dataset is a fundamental task in computer science. While classical algorithms require $O(1/\epsilon^2)$ samples to achieve an error of $\epsilon$, quantum computing promises a quadratic speedup. This paper presents a quantum algorithm that reaches the theoretical lower bound of $\Omega(1/\epsilon)$ for mean estimation, closing a long-standing gap in quantum complexity. Furthermore, the authors apply this optimal mean estimation tool to the problem of finding the median—the most representative point—of a dataset under an arbitrary distance metric.

Problem Statement

The primary challenge addressed is the query complexity of mean and median estimation. Classically, finding the median of $N$ points under an arbitrary distance metric requires $O(N^2)$ distance calculations. In the quantum realm, previous algorithms for mean estimation were off by a logarithmic factor ($O(\frac{1}{\epsilon} \log \log \frac{1}{\epsilon})$). This research aims to provide an asymptotically optimal $O(1/\epsilon)$ algorithm for mean estimation and leverage it to significantly speed up median finding.

Methodology

The authors propose three core algorithms to address these challenges:

Mean Estimation Algorithms

  1. mean1 (Amplitude Estimation): Utilizing a generalization of Grover's search, this algorithm maps function values to quantum rotations and employs the Quantum Fourier Transform (QFT) to extract the average. It achieves the optimal $O(1/t)$ error for $t$ queries.
  2. mean2 (Bit-wise Estimation): This variation estimates the count of 1s in each bit position of the data's binary representation independently. It is particularly effective for sparse data where the mean is very small.

Median Estimation

The median algorithm finds a point that minimizes the average distance to all other points. It nests the mean estimation algorithm within a quantum minimum-finding routine (Dürr and Høyer).

Algorithm 3: Median estimation using nested quantum search and majority voting.

As shown in Algorithm 3, the process involves defining a distance function $F_i(x)$ for each point $i$. To handle the probabilistic nature of quantum mean estimation, a Majority Voting technique (based on Chernoff bounds) is used to boost the success probability of the estimates $\tilde{d}_i$ before finding the minimum.

Key Insights

  • Optimal Complexity: The paper proves that $O(1/\epsilon)$ query complexity is achievable for mean estimation, matching the theoretical lower bound.
  • Error Management via Majority Voting: Nesting probabilistic quantum algorithms can lead to compounding errors. The authors demonstrate that repeating the mean estimation $O(\log N)$ times and taking the majority ensures sufficient reliability for the global minimum-finding step.
  • Algorithmic Selection: The choice between mean1 and mean2 depends on the data distribution. While mean1 is generally optimal, mean2 excels in specific scenarios like sparse datasets.

Results

The proposed algorithms demonstrate significant improvements in query complexity:

  • Mean Estimation: The mean1 algorithm yields an estimate $\tilde{m}$ with error $O(1/t)$ using $4t$ queries, which is the physical limit for quantum systems.
  • Median Estimation:
    • With mean1, the median is approximated with $O(1/t)$ error in $O(t \sqrt{N} \log N)$ queries.
  • With mean2, the median is approximated in $O(N \log N)$ queries. Compared to the classical $O(N^2)$ requirement, these quantum approaches offer a substantial speedup as the dataset size $N$ increases.

Conclusion and Future Work

This work establishes an optimal quantum framework for mean and median estimation under arbitrary metrics. While the algorithms assume a "black-box" distance function, future research could explore how specific geometric structures (e.g., Euclidean space) might allow for further optimizations. Additionally, investigating the impact of various data distributions (e.g., Gaussian vs. Power Law) on algorithm selection remains an open area for study.

Summary updated

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.
BibTeX
@misc{brassard2011optimal,
  author = {Gilles Brassard and Frédéric Dupuis and Sébastien Gambs and Alain Tapp},
  title = {{An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance}},
  year = {2011},
  eprint = {1106.4267},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1106.4267},
}
Figure