# Quantum Approximate Counting, Simplified

arXiv: https://arxiv.org/abs/1908.10846 · HTML: https://mlsanity.com/paper/1908.10846/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Aug 2019.

## Built on by (most cited first, 6 of 6)

- [Des-q: a quantum algorithm to provably speedup retraining of decision trees](https://mlsanity.com/paper/2309.09976/) (2023)
- [Discrete Randomized Smoothing Meets Quantum Computing](https://mlsanity.com/paper/2408.00895/) (2024)
- [Quantum Boosting using Domain-Partitioning Hypotheses](https://mlsanity.com/paper/2110.12793/) (2021)
- [Tunable Quantum Neural Networks in the QPAC-Learning Framework](https://mlsanity.com/paper/2205.01514/) (2022)
- [Efficient option pricing with unary-based photonic computing chip and generative adversarial learning](https://mlsanity.com/paper/2308.04493/) (2023)
- [Towards Noise-Resilient Quantum Multi-Armed and Stochastic Linear Bandits](https://mlsanity.com/paper/2603.18431/) (2026)

## Abstract (arXiv)

In 1998, Brassard, Hoyer, Mosca, and Tapp (BHMT) gave a quantum algorithm for approximate counting. Given a list of N items, K of them marked, their algorithm estimates K to within relative error varepsilon by making only Oleft( frac1varepsilon√fracNKright)  queries. Although this speedup is of "Grover" type, the BHMT algorithm has the curious feature of relying on the Quantum Fourier Transform (QFT), more commonly associated with Shor's algorithm. Is this necessary? This paper presents a simplified algorithm, which we prove achieves the same query complexity using Grover iterations only. We also generalize this to a QFT-free algorithm for amplitude estimation. Related approaches to approximate counting were sketched previously by Grover, Abrams and Williams, Suzuki et al., and Wie (the latter two as we were writing this paper), but in all cases without rigorous analysis.