Fetching the paper…

Reading the bibliography…

2019

Quantum Approximate Counting, Simplified

Aaronson, Scott, Rall, Patrick

Original
PDF
Post on X

Understand

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 $O\left( \frac{1}{\varepsilon}\sqrt{\frac{N}{K}}\right) $ 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.

Quantum Approximate Counting, Simplified · Around

Built on

Amplitude estimation without phase estimation
Original
Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, and T. Onodera N. Yamamoto · 1904
Earlier work this paper cites.
Simpler quantum counting
Original
C. R. Wie · 1907
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
P. W. Shor · 1994
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
L. K. Grover · 1996
Earlier work this paper cites.
Quantum measurements and the abelian stabilizer problem
A. Kitaev · 1996
Earlier work this paper cites.

Similar

Quantum lower bounds by polynomials
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf · 1998
Cited alongside, same era.
A framework for fast quantum mechanical algorithms
L. K. Grover · 1998
Cited alongside, same era.
Fast quantum algorithms for numerical integrals and stochastic processes
D. S. Abrams and C. P. Williams · 1999
Cited alongside, same era.
The quantum query complexity of approximating the median and related statistics
A. Nayak and F. Wu · 1999
Cited alongside, same era.

Then

Quantum lower bounds by quantum arguments
A. Ambainis · 2000
Later among the works it cites.
Quantum amplitude amplification and estimation
G. Brassard, P. Høyer, M. Mosca, and A. Tapp · 2002
Later among the works it cites.
Quantum speedup of Monte Carlo method
A. Montanaro · 2015
Later among the works it cites.
Optimal parallel quantum query algorithms
S. Jeffery, F. Magniez, and R. de Wolf · 2017
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…