{"id":"f0a81809-f544-4594-87b5-a64a7c6f1be7","arxiv_id":"1908.10846","paper_version":6,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Quantum approximate counting can match the optimal query complexity without the quantum Fourier transform, using only Grover iterations and classic coin-estimation analysis.","lead":"This paper proves that quantum approximate counting can be done with Grover iterations alone, without the quantum Fourier transform, while keeping the optimal query complexity. The same simplification is extended to amplitude estimation, a widely used quantum subroutine.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2's high-θ separation step is not justified as written: it concludes sin²(rθ)≥sin²(0.29π) from an absolute lower bound rθ≥0.29π, although rθ≈2πk and sin² is periodic; the proof needs an explicit modulo-2π argument.","rationale":"The reader's weakest_assumption focused on noise/decoherence and the preprocessing ratio, which are external to the formal query model and are not the main risk to the paper's central claim. The real soft spot is internal: the proof of the Rotation Lemma, on which step 2's correctness and query-complexity cancellation both rest, contains an invalid inference from an absolute angle bound to a bound on sin², because the angle is effectively taken modulo 2π without being stated. This is more substantive than the rounding-term typo in eq. (21) noted by the reader, since it concerns the key probabilistic separation rather than a lower-order query-counting term. The theorem may still be correct—the gap appears repairable by making the modulo-2π reduction explicit—but as written the proof is not fully rigorous at the most load-bearing step. This reinforces the existing CONDITIONAL verdict rather than changing it.","tokens_in":11022,"tokens_out":31297,"duration_ms":306089,"concrete_test":"Re-derive the high-θ case of Lemma 2 with β := rθ − 2πk made explicit. Using |rθmin − 2πk| ≤ π/1000, |rθmax − (2πk + π/2)| ≤ π/5 + π/1000, k closest to θmin/(4Δθ), and γ ≤ 1/5, prove β ≥ 0.29π and β ≤ 0.701π for every θ ∈ [(1+0.9γ)θmin, θmax]. Alternatively, run an exhaustive numerical scan over γ ∈ (0, 0.2], integer k closest to 1/(4γ), worst-case rounding and θmin ∈ (0, π/1000], checking min sin²(rθ) on the high-θ interval; if it ever dips below 0.5, the lemma is false, and if it stays above, the paper needs only a modulo-2π rewrite.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing spot is the proof of Lemma 2, the Rotation Lemma, which is the engine of step 2. In the high-θ case the proof shows rθ ≥ ... ≥ 0.29π and immediately concludes sin²(rθ) ≥ sin²(0.29π). But rθ is approximately 2πk (with k chosen in the lemma), so an absolute lower bound of 0.29π does not control sin²: sin² is π-periodic and non-monotone, and rθ could be, say, nπ + 0.29π, nπ + 0.71π, or other values with very different squared sines. The required separation is that rθ mod 2π lies in [0.29π, 0.701π]. The preceding bounds (rθmin ≈ 2πk, |rθmax − (2πk + π/2)| ≤ π/5 + π/1000) suggest such a modulo bound is true and repairable, but it is not stated or proved. Since Lemma 2 supplies both the distinguishing coin and the r-bounds used in equations (20)-(25), this gap is load-bearing for Theorem 1 and Theorem 3. Separately, the r upper bound in eq. (46) has a similar reversed-inequality typo, but that one affects only constant factors.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":11231,"tokens_out":24672,"duration_ms":211810,"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":[{"comment":"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).","section":"Lemma 2, Eqs. (42)-(44)"},{"comment":"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.","section":"Step 1, Eq. (9)"}],"minor_comments":[{"comment":"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.","section":"Eq. (46)"},{"comment":"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.","section":"Lemma 2, numerical values"},{"comment":"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.","section":"Eq. (15)"},{"comment":"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.","section":"Remark on K = 0"},{"comment":"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.","section":"Lemma 2 statement, threshold wording"}],"recommendation":"major_revision","confidential_remarks":"The paper's novelty is primarily conceptual and expository rather than asymptotic; the editor may wish to weigh whether that fits the journal's scope. The main theorem is likely correct, but the two proof gaps identified in the major comments must be fixed before the paper can be accepted, because the manuscript's central claim is its rigorous analysis. The related-work discussion appears balanced and accurate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThere 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.\n\nThe 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.\n\nThis 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.\n\nMy 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.","headline":"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.","tokens_in":11828,"tokens_out":9362,"would_cite":true,"duration_ms":85474,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"The paper proves that quantum approximate counting reaches optimal query complexity using only Grover iterations and no quantum Fourier transform.","keywords":["quantum approximate counting","Grover's algorithm","amplitude estimation","quantum Fourier transform","query complexity","Chernoff bound","rotation lemma","phase estimation"],"falsifier":"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.","tokens_in":2052,"feed_emoji":"⚛️","tokens_out":3054,"duration_ms":92323,"temperature":0.7,"pith_summary":"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.","feed_headline":"Grover-only counting matches the optimal quantum speedup","feed_subtitle":"A simple adaptive algorithm estimates the number of marked items to relative error ε with no quantum Fourier transform.","key_machinery":"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.","core_discovery":"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