{"id":"1a0126e9-9fa3-4ee2-a07f-a34e736dc093","arxiv_id":"1908.01745","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"A modified AQO and QAOA for weighted ground-state counting is proposed, but factor errors in the estimator and inverted complexity scaling invalidate the claimed speedup.","lead":"This paper modifies two quantum optimization algorithms, AQO and QAOA, to count weighted ground states of classical spin Hamiltonians. The authors claim a sub-quadratic speedup over classical Monte Carlo for counting edge covers, but algebraic errors in the counting estimator and the complexity formula break the method as written.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (31) is internally inconsistent: substituting the paper's own Eqs. (29)-(30) yields Pest ≈ M·P rather than P, so the counting protocol and the QAOA speedup built on it are invalid as written.","rationale":"The reader targeted Eq. (31), and the algebra confirms this is the right place. The paper's own moments in Eq. (29) are correct: <R_M> = M P_2/P and, to leading nontrivial order, M - <Q_M> = M(M-1)P_2/(2P^2). But plugging these into Eq. (31) does not produce P; it produces M P. The numerical consequence is that Algorithm 3's Pest is wrong by a factor equal to the number of collected ground states, so the relative-error guarantee is void. This is not a disagreement with a consensus or a missing proof; it is an internal algebraic inconsistency in the central step. The QAOA speedup claim inherits the error because total time is formed from this estimator, and Fig. 1's scaling is therefore not evidence for the abstract's sub-quadratic speedup claim. I also note Eq. (34) has the P_2-dependence inverted: S ~ P^2/(P_2 M^2) implies M ~ P/sqrt(P_2), so Tcount ~ P/sqrt(P_2), not sqrt(P_2)/P. That error understates the counting overhead in the same small-P_2/P^2 regime the paper highlights. Both defects are independently checkable and fixable (removing the stray M and inverting the moment ratio would restore consistency), but as submitted the central claim does not hold. Credit is due to the importance-sampling construction in Secs. 3.2-3.3, which appears internally coherent and numerically demonstrated in Fig. 4; the failure is in the conversion of samples into a count, not in the state-preparation algebra. This supports, rather than moves, the reader's REJECT verdict.","tokens_in":25362,"tokens_out":9917,"duration_ms":95963,"concrete_test":"Independently simplify Eq. (31) using Eqs. (29)-(30): the factor M(M-1) cancels with 2(M-<Q_M>) at leading order, leaving Pest ≈ M P, which is the claimed inconsistency. For a numerical check, take K=1000 equiprobable ground states with w = 10^{-3}, so P = 1 and P_2/P^2 = 10^{-3}; draw M = 10 samples from p(g) = w(g)/P, compute Q_M and R_M, and evaluate Eq. (31). Repeated trials give average Pest ≈ 10, not 1. The corrected estimator (M-1)R_M / [2(M-Q_M)] gives ≈ 1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing failure is the capture-recapture estimator in Sec. 3.4. With Q_M the number of distinct ground states among M measurements and R_M their total weight, the paper's Eqs. (29)-(30) give <R_M> = M P_2/P and M - <Q_M> ≈ M(M-1)P_2/(2P^2). Substituting these into Eq. (31), P ≈ M(M-1)<R_M> / [2(M-<Q_M>)], yields Pest ≈ M P, not P. The correct inversion is P ≈ (M-1)<R_M> / [2(M-<Q_M>)], with no factor M in the numerator. Because Algorithm 3 uses Eq. (31) verbatim, every reported estimate is too large by a factor of the number of ground-state measurements in the regime where the truncation is valid. This voids the relative-error guarantee in Eq. (6) and invalidates the central counting claim. The QAOA speedup comparison inherits the error, since Table 1 and Fig. 1 compute total time from this estimator. A separate algebraic error compounds the problem: Eq. (34) states Tcount ∝ sqrt(P_2)/P, whereas inverting Eq. (33) gives Tcount ∝ P/sqrt(P_2). This inverts the weight-moment dependence and understates the counting overhead when P_2/P^2 < 1, further undermining the claimed sub-quadratic speedup.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents modified adiabatic quantum optimization (AQO) and quantum approximate optimization (QAOA) protocols whose instantaneous wave function importance-samples the ground states of a classical spin Hamiltonian, i.e., |⟨g|ψ(t)⟩|² ∝ w(g). The authors then estimate the total weighted ground-state count P by repeated measurements and a classical capture-recapture analysis. They derive an analytical scaling for AQO, observe numerically T_QAOA ∼ 1/√P, and compare the total time against classical OMCS, claiming that AQO is not faster than OMCS while QAOA offers a sub-quadratic speedup for small-weight ground states. The concrete application is counting weighted edge covers on graphs.","tokens_in":25726,"tokens_out":16797,"duration_ms":152018,"significance":"The core idea—choosing the mixing Hamiltonian as a projector onto the initial state so that the symmetric subspace importance-samples ground states with prescribed weights—is elegant and potentially useful. The AQO spectral analysis in Sec. 3.2 appears sound and generalizes earlier results beyond Grover-type oracles. If the counting protocol and complexity claims were correct, the work would be a meaningful step toward NISQ-compatible ground-state counting. However, the central counting estimator and the reported complexity scaling contain algebraic errors that invalidate the main quantitative claims as written.","major_comments":[{"comment":"Equation (31) does not follow from Eqs. (29) and (30). Substituting ⟨R_M⟩ = M P_2/P and M − ⟨Q_M⟩ ≈ M(M−1)P_2/(2P^2) into Eq. (31) gives P_est ≈ M·P, not P. The correct inversion is P ≈ (M−1)⟨R_M⟩/[2(M−⟨Q_M⟩)]. Because Algorithm 3 uses Eq. (31) verbatim, every reported estimate is too large by the number of ground-state measurements M, and the relative-error/confidence guarantee in Eq. (6) is void. This is the load-bearing step of the counting protocol, so the algorithm as written does not estimate P.","section":"Sec. 3.4, Eq. (31)"},{"comment":"Equation (34) has the P_2 dependence inverted. With S ∼ O(1), Eq. (33) gives M ∼ (√|ln δ|/ε)·P/√P_2, hence T_count ∼ M/(1−η²) ∝ P/√P_2 = √(P²/P_2). The printed expression √(P_2/P²) is the reciprocal. Table 1 and the total-time comparisons in Figs. 1(b)–(d) inherit this error, so the claimed speedups and the statement that AQO is slower than OMCS are not supported by the derived scaling.","section":"Sec. 3.4, Eq. (34) and Table 1"},{"comment":"Equation (B.1) uses Mε as the half-width of the acceptance interval for Q_M, whereas the subsequent derivation and Eq. (32) require the half-width (M−⟨Q_M⟩)ε, as used in Eq. (B.2). As written, the confidence calculation is internally inconsistent; this should be corrected and the resulting S scaling re-derived.","section":"Appendix B, Eq. (B.1)"}],"minor_comments":[{"comment":"In the 'if Q_M = M' branch, the instruction 'Go to Step 3' creates an infinite loop; it should read 'Go to Step 2' so that additional ground states are collected after M is doubled.","section":"Algorithm 3, Step 5"},{"comment":"The comparison of physical CPU time for OMCS with a scaled gate count for QAOA is understandable, but the text should state clearly that constant factors are arbitrary and that the plotted 'total time' for QAOA excludes all classical post-processing and variational search overhead.","section":"Sec. 4, Fig. 1 caption"},{"comment":"The claim of a sub-quadratic speedup relies on the assumption that constant variational parameters can be found with O(1) search cost; the authors explicitly note this does not hold for all instances, so the generality of the speedup remains an unproven empirical observation rather than a demonstrated result.","section":"Sec. 3.3"}],"recommendation":"reject","confidential_remarks":"The algebraic errors in Sec. 3.4 are simple to identify, but they change the main complexity conclusions and could even reverse the paper's claim that AQO is slower than OMCS. The absence of a direct verification of P_est against exact values for small graphs is surprising and suggests the numerical pipeline was not checked against the printed equations. A careful correction and full re-analysis of the numerical results would be needed before the work can be considered further."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague —\n\nRead arXiv:1908.01745. Bottom line: the core importance-sampling idea for AQO and QAOA is genuinely new and mostly well argued, but the paper’s central counting estimator is algebraically wrong, and the error breaks the main claim.\n\nWhat it does well: The modification with Hx = −|ψ(0)⟩⟨ψ(0)| and initial state |ψ(0)⟩ restricts the evolution to a symmetric subspace in which the instantaneous wave function satisfies |⟨ψ(t)|g⟩|² / |⟨ψ(t)|g′⟩|² = w(g)/w(g′) for all ground states. The spectrum derivation leading to TAQO ~ 1/P is a real generalization of earlier Grover-oracle results, and the numerical QAOA scaling TQAOA ~ 1/√P is clearly presented. The edge-cover example is well chosen, and the paper is honest that AQO has no speedup.\n\nSoft spots: The counting step doesn’t work as written. From the paper’s own Eqs. (29)–(30), ⟨R_M⟩ = M P₂/P and M − ⟨Q_M⟩ ≈ M(M−1)P₂/(2P²). Substituting into Eq. (31) gives P_est ≈ M P, not P. The correct inversion is P ≈ (M−1)⟨R_M⟩/[2(M−⟨Q_M⟩)], without the extra M. Since Algorithm 3 uses Eq. (31) directly, the reported estimate is too large by a factor equal to the number of ground-state measurements in the regime where the truncation is valid. This voids the relative-error guarantee in Eq. (6). Eq. (34) has a separate error: inverting Eq. (33) gives T_count ∝ P/√P₂, not √P₂/P. That inverts the weight-moment dependence and understates the counting overhead when P₂/P² < 1, which is exactly the regime where they claim a speedup. Because Table 1 and Fig. 1 compute total time from this estimator, the QAOA speedup comparison inherits both errors. The estimator looks fixable—remove the factor M and redo the T_count derivation—and the importance-sampling part may be salvageable, but the paper as submitted does not establish its main result.\n\nThe citation pattern looks appropriate; the distinction from Refs. [71–74] is clear and fair. This paper is for anyone working on quantum counting or constrained sampling algorithms. It deserves a serious referee, not a desk reject, because the construction is novel and the failure is a correctable algebraic error rather than a fundamentally wrong approach. But it should be rejected in its current form and revised. I wouldn’t cite the current version.","headline":"The importance-sampling construction is a real step forward, but Eq. (31) is off by a factor of M and Eq. (34) inverts the weight-moment dependence, so the counting protocol and the QAOA speedup as claimed don't survive.","tokens_in":26226,"tokens_out":2825,"would_cite":false,"duration_ms":26952,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Modified QAOA and AQO count weighted ground states with user-set error and confidence.","keywords":["quantum algorithms","adiabatic quantum optimization","quantum approximate optimization","constrained sampling and counting","edge covers","engineering reliability","weighted ground-state counting","capture-recapture estimation"],"falsifier":"Substitute the paper's own expectations $\\langle R_M\\rangle = M P_2/P$ and $M - \\langle Q_M\\rangle \\approx M(M-1)P_2/(2P^2)$ into Eq. (31). If the result is $P \\approx M$ rather than $P$, the estimator is inconsistent with the derivation and the protocol as written fails to return the weighted count.","tokens_in":25175,"feed_emoji":"⚛️","tokens_out":6399,"duration_ms":59623,"temperature":0.7,"pith_summary":"This paper claims that by changing the initial state and the mixing Hamiltonian, AQO and QAOA can be turned from optimizers into importance samplers of ground states, enabling estimation of weighted ground-state counts with user-specified error and confidence. The key is that the modified evolution stays in a low-dimensional symmetric subspace, so every ground state is sampled with probability proportional to its weight. For edge-cover counting with small weights, the paper finds QAOA requires about $1/\\sqrt{P}$ steps per iteration and total time that scales sub-quadratically better than optimal Monte Carlo; AQO does not beat the classical baseline. The counting protocol itself rests on a capture-recapture estimator that converts measured distinct-state and weight totals into $P$.","feed_headline":"QAOA can count weighted ground states faster than Monte Carlo","feed_subtitle":"With small ground-state weights, the modified QAOA circuit needs fewer operations than classical sampling at fixed error and confidence.","key_machinery":"The central object is the symmetric subspace $H_S$ spanned by $|\\Phi_j\\rangle = \\sum_{\\varphi: H_z(\\varphi)=E_j} \\sqrt{w(\\varphi)}|\\varphi\\rangle / \\sqrt{N_j^{(1)}}$, together with the mixing Hamiltonian $\\hat H_x = -|\\psi(0)\\rangle\\langle\\psi(0)| = (U_0 - 1)/2$, where $|\\psi(0)\\rangle = \\sum_\\varphi \\sqrt{w(\\varphi)}|\\varphi\\rangle$ is the weighted initial state. This choice makes the projected Hamiltonian rank-one in $H_S$, so the spectrum is given by the algebraic equation $\\sum_j N_j^{(1)}/(\\beta E_j - \\lambda) = 1/\\alpha$, and the gap is bounded below by roughly $\\sqrt{P}$; that gap bound sets $T_{\\rm AQO} \\sim 1/P$. The same subspace guarantees importance sampling at all times. The counting step is carried by the capture-recapture estimator $P \\approx M(M-1)\\langle R_M\\rangle/(2(M-\\langle Q_M\\rangle))$, derived from truncated moments of the measured distinct-state count $Q_M$ and total weight $R_M$.","core_discovery":"The central claim is that replacing the usual transverse-field mixer with the rank-one projector $-|\\psi(0)\\rangle\\langle\\psi(0)|$ forces the evolution to stay in a symmetric subspace in which each ground state's amplitude remains proportional to the square root of its weight. As a result, after evolving to the ground-state manifold, computational-basis measurements are an importance sample of the weighted ground states, and a capture-recapture analysis of repeated measurements estimates the total weighted count $P$ with specified relative error and confidence. The paper derives an analytic AQO runtime $\\sim 1/P$, finds numerically that QAOA's per-iteration depth scales as $1/\\sqrt{P}$, and concludes that for small total ground-state weight QAOA's total time is sub-quadratically better than optimal Monte Carlo, while AQO is not.","pith_inferences":["A direct substitution of the paper's own expectation values into the capture-recapture estimator $P \\approx M(M-1)\\langle R_M\\rangle/(2(M-\\langle Q_M\\rangle))$ yields $P \\approx M$ rather than $P$, which suggests the estimator as written is inconsistent; a corrected estimator using higher moments of $Q_M$ or a different ratio would be needed to make the protocol self-consistent.","The observed near-constancy of the optimal QAOA angles suggests a transferable-parameter heuristic: optimize $\\alpha,\\beta$ once on small instances and reuse them on larger graphs of the same family; this is not tested in the paper but is a natural consequence of the numerical trend.","The symmetric-subspace construction applies to any weight function, so the same machinery could estimate other ground-state moments $P_\\mu$ for $\\mu>1$ by reweighting, which the paper does not pursue.","For graph families where $P$ is classically computable in polynomial time, the reported speedup would not translate to practical advantage; the paper's claim matters most for #P-hard counting instances, where no efficient classical exact algorithm is known."],"forward_implications":["For edge-cover instances with small total weight on ground states, the total number of one- and two-qubit gates in the QAOA protocol grows with graph size more slowly than OMCS's CPU time, giving a sub-quadratic speedup at fixed error and confidence.","The importance-sampling property holds throughout the evolution, not only at the final time, so the same circuits can be stopped early or used for weighted sampling tasks beyond counting.","Because $\\exp(-i\\beta \\hat H_z)$ can be implemented with polynomially many gates for Hamiltonians outside NP, the counting method reaches problems where Grover-oracle-based amplitude estimation cannot be applied.","The number of experimental repetitions needed for the statistical estimate scales as $\\sqrt{|\\ln\\delta|}/\\epsilon$ times $\\sqrt{P_2/P^2}$, which is more favorable in $\\epsilon$ and $\\delta$ than classical OMCS's $|\\ln\\delta|/(P\\epsilon^2)$.","If the QAOA variational parameters are nearly constant, as observed for many edge-cover instances, the parameter-search overhead can be $O(1)$ and the speedup survives; a greedy per-step search with overhead $T_{\\rm QAOA}^2$ would erase it."],"supporting_citations":[{"why":"Supplies the OMCS baseline and the classical sample-complexity scaling $|\\ln\\delta|/(P\\epsilon^2)$ that the quantum algorithms are compared against.","marker":"[78]"},{"why":"Supplies the Grover oracle/diffusion construction and the $1/\\sqrt{P}$ iteration count that the importance-sampling Grover variant and QAOA scaling are compared with.","marker":"[84]"},{"why":"Source of the fair-sampling idea for AQO with a modified mixer, generalized here to arbitrary weights and Hamiltonians.","marker":"[71]"},{"why":"Provides the AQO analysis for the restricted Grover-oracle Hamiltonian that the paper extends to arbitrary classical $\\hat H_z$.","marker":"[72]"},{"why":"Gives the adiabatic Grover gap argument underlying the AQO runtime bound.","marker":"[73]"},{"why":"Supplies the local adiabatic search runtime scaling used in the AQO bound.","marker":"[74]"},{"why":"Supplies the capture-recapture method that the repeated-measurement counting estimate builds on.","marker":"[89]"},{"why":"Source of the capture-recapture statistical analysis used to set confidence on the estimate.","marker":"[90]"},{"why":"Defines QAOA, the variational algorithm whose modified version is analyzed numerically.","marker":"[21]"}],"fun_headline_variants":["QAOA counts weighted ground states faster than Monte Carlo","QAOA beats Monte Carlo for weighted ground-state counts","Sub-quadratic QAOA speedup for weighted counting","QAOA sub-quadratic advantage for weighted ground states"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the capture-recapture estimator in Eq. (31) recovers the total weighted count from the measured number of distinct ground states and their total weight; if that estimator is inconsistent with the derivation, the counting protocol collapses.","fun_headline_variants_meta":{"raw":{"variants":["QAOA counts weighted ground states faster than Monte Carlo","QAOA beats Monte Carlo for weighted ground-state counts","Sub-quadratic QAOA speedup for weighted counting","QAOA sub-quadratic advantage for weighted ground states"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001187,"raw_usage":{"total_tokens":4921,"prompt_tokens":990,"completion_tokens":3931,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":606,"completion_tokens_details":{"reasoning_tokens":3866}},"tokens_in":606,"tokens_out":3931,"duration_ms":24551,"temperature":1.0,"reasoning_tokens":3866,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:05:27.084523+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Substitute the paper's own expectations $\\langle R_M\\rangle = M P_2/P$ and $M - \\langle Q_M\\rangle \\approx M(M-1)P_2/(2P^2)$ into Eq. (31). If the result is $P \\approx M$ rather than $P$, the estimator is inconsistent with the derivation and the protocol as written fails to return the weighted count.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the OMCS baseline and the classical sample-complexity scaling $|\\ln\\delta|/(P\\epsilon^2)$ that the quantum algorithms are compared against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Grover oracle/diffusion construction and the $1/\\sqrt{P}$ iteration count that the importance-sampling Grover variant and QAOA scaling are compared with."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Source of the fair-sampling idea for AQO with a modified mixer, generalized here to arbitrary weights and Hamiltonians."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the AQO analysis for the restricted Grover-oracle Hamiltonian that the paper extends to arbitrary classical $\\hat H_z$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the adiabatic Grover gap argument underlying the AQO runtime bound."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the local adiabatic search runtime scaling used in the AQO bound."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the capture-recapture method that the repeated-measurement counting estimate builds on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Source of the capture-recapture statistical analysis used to set confidence on the estimate."}],"review_version":1}