Quantum Approximate Counting, Simplified

Patrick Rall; Scott Aaronson

REVIEW 2 major objections 5 minor 13 references

Quantum Approximate Counting, Simplified

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that quantum approximate counting reaches optimal query complexity using only Grover iterations and no quantum Fourier transform.

desk verdict The QFT-free counting result is real and important, but the proof of Lemma 2 has a load-bearing modulo-2π gap that a referee must require the authors to fix. read the letter →

arxiv 1908.10846 v6 pith:FCHQC5HG submitted 2019-08-28 quant-ph cs.DS

Scott Aaronson , Patrick Rall This is my paper · ORCID

classification quant-phcs.DS MSC 81P68 PACS 03.67.Lx

keywords quantumapproximatecountingGrover'salgorithmamplitudeestimationFouriertransformquerycomplexityChernoffboundrotationlemmaphase

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks whether the quantum Fourier transform is genuinely necessary for the quadratic quantum speedup in approximate counting, or whether Grover iterations alone suffice. It answers with an algorithm that estimates the size $K$ of a marked subset of $[N]$ to relative error $\varepsilon$ using $O\!\left(\sqrt{N/K}\,\frac{1}{\varepsilon}\log\frac{1}{\delta}\right)$ oracle queries and $O(\log N)$ qubits, succeeding with probability at least $1-\delta$. The same bracket-shrinking strategy gives a QFT-free amplitude estimation algorithm with $O\!\left(\frac{1}{a}\,\frac{1}{\varepsilon}\log\frac{1}{\delta}\right)$ uses of the state-preparation unitary. A sympathetic reader would take this as showing that the counting speedup is Grover-like in substance, not merely in query count.

What carries the argument

The load-bearing object is the 'Grover coin': preparing $G^{(r-1)/2}|\psi\rangle$ and measuring in the computational basis gives heads with probability $\sin^2(r\theta)$, where $G$ is the Grover diffusion operator and $\theta=\arcsin\sqrt{K/N}$. The Rotation Lemma (Lemma 2) is the central identity: when $\theta_{\min}\le\theta\le\theta_{\max}$ with $\theta_{\max}=(1+\gamma)\theta_{\min}$ and $\gamma\le 1/5$, there exists an odd integer $r$, within a multiplicative window of $\pi/(\gamma\theta)$, such that a Chernoff-bounded number of coin tosses reliably moves the bracket toward the true $\theta$ while preserving the invariant. A preprocessing step first establishes $\theta_{\max}/\theta_{\min}\le(12/11)^2$, and a tuned amplification schedule makes the per-round query counts form a geometric series that cancels the $\log(1/\varepsilon)$ factors.

What would settle it

Run the algorithm on an error-free simulator for a range of $(K, N, \varepsilon, \delta)$, counting oracle queries and failures; if the measured failure probability exceeds $\delta$ for any parameter set, or if the query count grows faster than $\sqrt{N/K}\,\frac{1}{\varepsilon}\log\frac{1}{\delta}$ in the limit of small $\varepsilon$, the theorem's claimed bound is false. Alternatively, on noisy hardware with per-iteration depolarizing noise of strength $p$, measure the failure probability as $p$ increases; the ideal-model proof predicts no noise dependence, so any sharp rise in failure probability before $p$ reaches the level of rounding effects would falsify the practical version of the claim.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: for any nonempty marked set $S$ of size $K$ and any $\varepsilon,\delta>0$, there is a quantum algorithm that outputs $\hat K$ with $K(1-\varepsilon)<\hat K<K(1+\varepsilon)$ while making $O\!\left(\sqrt{N/K}\,\frac{1}{\varepsilon}\log\frac{1}{\delta}\right)$ membership-oracle queries and using $O(\log N)$ qubits, with success probability at least $1-\delta$. The algorithm first brackets the Grover angle $\theta=\arcsin\sqrt{K/N}$ up to a constant factor by running Grover iterations with growing odd $r$ and checking whether marked outcomes appear often enough. It then shrinks the bracket by a factor of $0.9$ per round, selecting $r$ through a Rotation Lemma so that the extreme bracketing angles lead to nearly orthogonal measurement outcomes. Theorem 3 adapts the same argument to amplitude estimation, estimating $a=|\langle\varphi|\psi\rangle|$ to relative error $\varepsilon$ with $O\!\left(\frac{1}{a}\,\frac{1}{\varepsilon}\log\frac{1}{\delta}\right)$ applications of the preparing unitary, again without a QFT.

Load-bearing premise

The proof assumes an ideal, noiseless quantum query model in which each Grover iteration is exact, so the measurement probability is exactly $\sin^2(r\theta)$ and repeated trials are independent; if hardware noise or an approximate diffusion operator breaks this, the Chernoff-bound analysis no longer guarantees the stated success probability.

Editorial extensions

If this is right

Approximate counting can be implemented with Grover iterations and $O(\log N)$ qubits, avoiding the QFT and its associated overhead, without worsening the query complexity.
The $O\!\left(\sqrt{N/K}\,\frac{1}{\varepsilon}\log\frac{1}{\delta}\right)$ bound is optimal, so dropping the QFT costs nothing in the query model.
Amplitude estimation, a subroutine behind quantum speedups for mean estimation, trace estimation, and partition-function estimation, becomes available in a QFT-free form with the same quadratic improvement.
The algorithm supplies the first rigorous analysis of the Grover-only approach, where earlier sketches left correctness unproved and failed to account for estimation error.
The explicit constants and simple structure make the algorithm a concrete candidate for implementations that support Grover iterations but not controlled-phase estimation.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The bracket-shrinking scheme is a general template: any observable whose squared sine is controlled by an unknown angle could be estimated by the same rotation-selection and Chernoff update, suggesting a QFT-free route to eigenvalue estimation that the paper does not pursue.
The noiseless query model is the main vulnerability; a plausible testable extension is to add per-iteration depolarizing noise and measure how the failure probability grows, which would map the boundary of the ideal-model claim.
Because the proof needs adaptivity and odd rotation counts, a depth-limited or parallel version would likely need different machinery, and the paper's open problem suggests a concrete research direction rather than a settled extension.
The amplitude-estimation generalization appears to apply directly to any Monte-Carlo-style estimation that can be expressed as a probability, so the same QFT-free bound should carry over to mean estimation and integration tasks with the usual error translation.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

I read the paper carefully. The headline is correct: this is the first rigorous QFT-free approximate counting algorithm with query complexity O(√(N/K)(1/ε)log(1/δ)), matching BHMT, and the amplitude-estimation extension is a natural byproduct. The construction is genuinely simple—Grover coin flips plus Chernoff bounds—and the paper is honest about the unproven sketches by Grover, Abrams–Williams, Suzuki et al., and Wie. That contextualization is accurate, not self-serving.

The real problem is in Lemma 2, the engine of the paper. In the high-θ case the proof shows rθ ≥ 0.29π and rθ ≤ 0.701π, then concludes sin²(rθ) ≥ sin²(0.29π). That inference is invalid because rθ is near 2πk, not near 0; sin² is periodic and non-monotone. The proof drops the 2πk term in both the lower and upper bounds. The intended statement is that rθ mod 2π lies in [0.29π, 0.701π], and that does follow from the definition of k plus the earlier bounds |rθmin − 2πk| ≤ π/1000 and |rθmax − (2πk + π/2)| ≤ π/5 + π/1000, but the authors never supply that modulo argument. This is not a cosmetic typo: Lemma 2 produces the distinguishing coin for both branches, and its r-bounds are used later to cancel the log(1/ε) factors. So the written proof of Theorem 1 and Theorem 3 is incomplete at this point.

There is also a smaller issue in equations (46)–(47), where the r-bounds have reversed inequality signs relative to the derivation. That affects only constant factors in the query-complexity analysis, so it is secondary but should be cleaned up.

The reader's note about equation (21) is minor and does not trouble me. The stress-test note, however, is on target: Lemma 2 needs an explicit modulo-2π argument. I would bet the theorem is true and the gap is repairable—the algorithm is simple enough, and the intended geometry of Figure 1 is clear—but the proof as written is not complete.

This paper deserves a serious referee and should not be desk-rejected. Would I bring it to a reading group? Yes, precisely to work through the modulo argument and see whether the constants in Lemma 2 need adjustment. Would I cite it? Likely yes, as the standard reference for QFT-free amplitude estimation, once the proof is fixed.

My recommendation: send it to peer review, and require a revised Lemma 2 with a correct modulo-2π proof. The core contribution is solid enough that this should be a minor revision, not a rejection.

Referee Report

2 major / 5 minor

Summary. The paper presents a quantum approximate counting algorithm that, for any nonempty marked set S of size K, estimates K to within relative error ε with probability at least 1−δ using O(sqrt(N/K)(1/ε)log(1/δ)) oracle queries and O(log N) qubits, using only Grover iterations and no quantum Fourier transform. It then extends the method to amplitude estimation, claiming O((1/a)(1/ε)log(1/δ)) applications of the state-preparation unitary and its inverse. The proof proceeds in two stages: a preprocessing loop that obtains constant-factor bounds on the Grover angle θ, and an adaptive refinement loop driven by a structural claim called the Rotation Lemma, with a carefully tuned amplification schedule that cancels the log(1/ε) factors in the query complexity.

Significance. If the identified proof gaps are repaired, this is a valuable conceptual contribution: it shows rigorously that the QFT is not needed for optimal approximate counting, and it supplies a self-contained, elementary analysis with explicit constants. The paper does not improve on the BHMT asymptotic query complexity, but it answers a natural structural question and offers a simpler algorithm that may be more attractive for near-term implementations. The treatment of prior work is careful, and the Rotation Lemma together with the amplification schedule is a genuine technical contribution. The manuscript's main value is therefore conceptual and expository, with a fully rigorous analysis as its central selling point.

major comments (2)

[Lemma 2, Eqs. (42)-(44)] In the high-θ case, the proof establishes only the absolute bound rθ ≥ 0.29π (Eq. (42)) together with rθ ≤ 2πk + 0.701π (Eq. (43)), and then concludes sin²(rθ) ≥ sin²(0.29π). This does not follow, because rθ is close to 2πk with k ≥ 1 and sin² is periodic; an angle of 2πk + 0.29π and an angle of 2πk + 0.71π have very different squared sines. The argument must show that rθ mod 2π lies in an interval such as [0.29π, 0.701π] up to the small rounding terms, using rθmin ≈ 2πk and r∆θ ≈ π/2 together with θ ≥ (1 + 0.9γ)θmin. This missing modulo argument is load-bearing, because Lemma 2 is what justifies both the correctness of step 2 and the r-bounds used in Eqs. (20)-(25).
[Step 1, Eq. (9)] The Chernoff bound displayed in Eq. (9) is not valid as an upper bound for all terms in the union bound. With p = sin²(rθ) ≤ 0.33q where q = (12/11)^{2(1+t−t0)} ≤ 1, the inequality (1/3 − p)² ≥ 0.22001 − 0.22q fails for small q; for instance q = 0.1 gives the left-hand side about 0.09 and the right-hand side about 0.198. The subsequent exponential-integral estimate therefore does not follow as written. The conclusion appears salvageable—for example, the crude bound p ≤ 0.33 gives δ_t ≤ exp(−2m(1/3 − 0.33)²), and the union sum is dominated by t = t0−1—but the proof as printed needs a corrected bound.

minor comments (5)

[Eq. (46)] The inequality direction in the displayed upper-bound chain for r is wrong: since θmin ≤ θ, one has π/(γθmin) ≥ π/(γθ), so the step replacing θmin by θ in an upper bound is invalid. The intended bound can be recovered using θmin ≥ θ/(1+γ), but this should be stated explicitly.
[Lemma 2, numerical values] The value sin²(0.29π) = 0.662 (and the corresponding Chernoff gap 0.162) appears inaccurate; numerically sin²(0.29π) ≈ 0.624. The lower bound still exceeds 1/2, so the argument is unaffected in substance, but the constants should be corrected.
[Eq. (15)] The equality in Eq. (15) should be an inequality: since (12/11)^t θ > 5/8, one has sin²(((12/11)^t θ) − π/500) ≥ sin²(5/8 − π/500), not equality. This is a minor presentational issue.
[Remark on K = 0] The side remark that the algorithm can also determine whether there are no marked items is not supported by the stated procedure: step 1 exits only when a marked item is observed at least one third of the time, which never happens when K = 0. If K = 0 is to be covered, a stopping rule for step 1 must be specified.
[Lemma 2 statement, threshold wording] Lemma 2 states the update condition as 'if more heads are observed,' while the algorithm and proof use 'at least half the time' (X/m ≥ 1/2). The threshold should be stated consistently, since for even m these differ.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the algorithm and its analysis are self-contained given standard Grover mechanics and Chernoff bounds.

full rationale

The paper's derivation chain is self-contained. Theorem 1 is proved by an explicit algorithm: step 1 produces constant-factor bounds via repeated Grover-coin measurements and Chernoff bounds; step 2 invokes Lemma 2, whose proof is carried out entirely inside this paper using elementary trigonometric estimates and Chernoff bounds. The constants (12/11, 0.9, 1000, 10^5) are explicit design choices, not fitted parameters, and no output quantity is reused as an input to define itself. The final estimate K_hat = N sin^2(theta_max) is a deterministic function of the maintained interval, not a re-statement of any fitted value. The generalization to amplitude estimation reuses the same argument after renaming theta = arcsin(a/1000), which is a legitimate reduction rather than a disguised assumption. Citations to BHMT, Grover, and Nayak-Wu are external and used only for context, comparison, or the optimality lower bound; they are not load-bearing for the proof. The paper also cites no prior work of its own, so there is no self-citation chain. The skeptical objection about Lemma 2's step from r*theta >= 0.29*pi to sin^2(r*theta) >= sin^2(0.29*pi) is a technical correctness gap about periodicity, possibly repairable, but it is not circularity: the proof does not assume what it is trying to prove. Honest non-finding: score 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No empirical free parameters: the constants (12/11, 5/8, 0.9, 1000, 10^5) are hand-chosen but any nearby values would preserve the asymptotic complexity; they are not fitted to data. No new physical entities are introduced. The analysis relies on standard Grover mechanics, Chernoff bounds, and a standard exponential-integral estimate.

assumptions (5)

domain assumption Grover rotation property: applying G^{(r-1)/2} to the uniform superposition yields state sin(rθ)|marked> + cos(rθ)|unmarked> (eq. 1).
Standard result from Grover's algorithm; used as the starting point for the coin toss analysis.
standard math Chernoff bound for independent Bernoulli trials.
Used throughout step 1 and step 2 to bound failure probabilities of the coin estimates.
standard math Exponential integral identity Ei(x) ≤ e^x for x>1.
Used in the step 1 union bound over t (eqs. 11-13).
domain assumption A query to the membership oracle corresponds to the phase oracle U|x> = (-1)^{x∈S}|x>.
This is the standard query model; the algorithm's complexity is measured in these queries.
domain assumption Padding with unmarked items to ensure K/N ≤ 10^{-6} does not change the asymptotic query complexity.
The paper states this WLOG at the start of the proof of Theorem 1; padding multiplies N by a constant that is absorbed in the O-notation.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Quantum Approximate Counting, Simplified." pith.science (2026). https://pith.science/paper/FCHQC5HG

@misc{pith2026190810846,
  author       = {Pith},
  title        = {Pith review of: Quantum Approximate Counting, Simplified},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FCHQC5HG}},
  note         = {Machine review of arXiv:1908.10846}
}

abstract

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. 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.

Figures

Figures reproduced from arXiv: 1908.10846 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 3 canonical work pages

[1]

Ambainis

A. Ambainis. Quantum lower bounds by quantum arguments. J. Comput. Sys. Sci. , 64:750--767, 2002. Earlier version in STOC'2000. quant-ph/0002066

arXiv 2002
[2]

D. S. Abrams and C. P. Williams. Fast quantum algorithms for numerical integrals and stochastic processes. quant-ph/9908083, 1999

arXiv 1999
[3]

Beals, H

R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. J. of the ACM , 48(4):778--797, 2001. Earlier version in FOCS'1998, pp. 352-361. quant-ph/9802049

arXiv 2001
[4]

Brassard, P

G. Brassard, P. H yer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. In S. J. Lomonaco and H. E. Brandt, editors, Quantum Computation and Information , Contemporary Mathematics Series. AMS, 2002. quant-ph/0005055

arXiv 2002
[5]

L. K. Grover. A fast quantum mechanical algorithm for database search. In Proc. ACM STOC , pages 212--219, 1996. quant-ph/9605043

arXiv 1996
[6]

L. K. Grover. A framework for fast quantum mechanical algorithms. In Proc. ACM STOC , pages 53--62, 1998. quant-ph/9711043. http://dx.doi.org/10.1145/276698.276712 doi:10.1145/276698.276712

work page Pith review arXiv 1998
[7]

Jeffery, F

S. Jeffery, F. Magniez, and R. de Wolf. Optimal parallel quantum query algorithms. Algorithmica , 79(2):509--529, Oct 2017. http://dx.doi.org/10.1007/s00453-016-0206-z doi:10.1007/s00453-016-0206-z

work page doi:10.1007/s00453-016-0206-z 2017
[8]

A. Kitaev. Quantum measurements and the abelian stabilizer problem. ECCC TR96-003, quant-ph/9511026, 1996

arXiv 1996

Show all 13 references

[9]

Montanaro

A. Montanaro. Quantum speedup of M onte C arlo method. Proc. Roy. Soc. London , A471, 2015

2015
[10]

Nayak and F

A. Nayak and F. Wu. The quantum query complexity of approximating the median and related statistics. In Proc. ACM STOC , pages 384--393, 1999. quant-ph/9804066

1999 arXiv
[11]

P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. , 26(5):1484--1509, 1997. Earlier version in FOCS'1994. quant-ph/9508027

1997 arXiv
[12]

Suzuki, S

Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, and T. Onodera N. Yamamoto. Amplitude estimation without phase estimation. 2019. http://arxiv.org/abs/1904.10246 arXiv:1904.10246

2019 arXiv
[13]

C. R. Wie. Simpler quantum counting. 2019. http://arxiv.org/abs/1907.08119 arXiv:1907.08119

2019 arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Ambainis

A. Ambainis. Quantum lower bounds by quantum arguments. J. Comput. Sys. Sci. , 64:750--767, 2002. Earlier version in STOC'2000. quant-ph/0002066

arXiv 2002

[2] [2]

D. S. Abrams and C. P. Williams. Fast quantum algorithms for numerical integrals and stochastic processes. quant-ph/9908083, 1999

arXiv 1999

[3] [3]

Beals, H

R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. J. of the ACM , 48(4):778--797, 2001. Earlier version in FOCS'1998, pp. 352-361. quant-ph/9802049

arXiv 2001

[4] [4]

Brassard, P

G. Brassard, P. H yer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. In S. J. Lomonaco and H. E. Brandt, editors, Quantum Computation and Information , Contemporary Mathematics Series. AMS, 2002. quant-ph/0005055

arXiv 2002

[5] [5]

L. K. Grover. A fast quantum mechanical algorithm for database search. In Proc. ACM STOC , pages 212--219, 1996. quant-ph/9605043

arXiv 1996

[6] [6]

L. K. Grover. A framework for fast quantum mechanical algorithms. In Proc. ACM STOC , pages 53--62, 1998. quant-ph/9711043. http://dx.doi.org/10.1145/276698.276712 doi:10.1145/276698.276712

work page Pith review arXiv 1998

[7] [7]

Jeffery, F

S. Jeffery, F. Magniez, and R. de Wolf. Optimal parallel quantum query algorithms. Algorithmica , 79(2):509--529, Oct 2017. http://dx.doi.org/10.1007/s00453-016-0206-z doi:10.1007/s00453-016-0206-z

work page doi:10.1007/s00453-016-0206-z 2017

[8] [8]

A. Kitaev. Quantum measurements and the abelian stabilizer problem. ECCC TR96-003, quant-ph/9511026, 1996

arXiv 1996