The University of Arizona
Please note that this event has ended!

Adaptive Quantum Algorithm for Proportion Estimation

Special Colloquium

Adaptive Quantum Algorithm for Proportion Estimation
Series: Special Colloquium
Location: ENR2 S107
Presenter: Yunpeng Zhao, Arizona State University

Consider a Boolean function f:{0,1,…,N-1}?{0,1}, where x?{0,1,…,N-1} is called a good element if f(x)=1 and a bad element otherwise. Estimating the proportion of good elements is one of the most fundamental problems in statistics and computer science. The error bound of the confidence interval based on the classical sample proportion scales as O(1/vn) according to the central limit theorem, where n is the number of times the function f is queried. Quantum algorithms can break this fundamental limit.  We propose an adaptive quantum algorithm for proportion estimation and prove that the error bound achieves O(1/n) up to a double-logarithmic factor. The algorithm is based on Grover’s algorithm, without the use of quantum phase estimation. We show with an empirical study that our algorithm uses a similar number of quantum queries to achieve the same level of precision compared to other algorithms, but the non-quantum part of our algorithm is significantly more efficient.