Quantum Approximate Counting, Simplified: A Grover-Only Algorithm Estimates K to Within Relative Error ε with Probability 1 − δ Using O(√(N/K) ε⁻¹ log(1/δ)) QueriesResearch Paper
Approximate counting asks for the number of marked items in a list of items, to within a multiplicative factor , when the marked set can only be accessed through a membership oracle. Brassard, Høyer, Mosca and Tapp (arXiv:quant-ph/0005055) gave a quantum algorithm that uses queries, which is optimal. Their…