{"id":"f96884f7-554c-4fb7-b3e2-7fe5b8ad0ba8","arxiv_id":"2607.03340","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.5,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Under extensivity and local-structure assumptions, the shot budget for fixed relative QAOA MaxCut performance scales as 1/m while SGD iterations stay size-independent.","lead":"For certain graph families, QAOA on MaxCut needs fewer measurement shots as the graph grows to hold fixed relative accuracy. This could cut sampling overhead for large combinatorial instances and complements known parameter-transfer results.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified beyond the reader's already-noted dependence on extensivity assumptions.","rationale":"The reader's identification of Assumption 1 as the weakest link is accurate and sufficient; the same extensivity underpins both Result A and the relative-error floor of Results B–C. The additional strong-convexity hypothesis used to obtain µ=Θ(m) is of the same character (plausible for the local limit, not rigorously proven for all p) but does not introduce a new failure mode. Numerics, while limited to N≤22, already show the predicted linear variance growth and inverse shot counts. Because the manuscript states its hypotheses clearly, supplies the supporting lemmas, and ships code, the CONDITIONAL/HIGH assessment stands without adjustment.","tokens_in":36135,"tokens_out":447,"duration_ms":33246,"concrete_test":"Using the light-cone/tree contraction for fixed p=1 or 2, evaluate |Fp(θ*;G)|/m on random 3-regular instances with N=50–200 at both transferable angles and freshly optimized angles; confirm the ratio remains bounded below by a positive constant independent of N (and that the normalized Hessian eigenvalues of the per-edge cost stay O(1)).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (1/m shot scaling for fixed relative error/suboptimality under extensive cost + linear PL/Lipschitz) is correctly derived from Janson's inequality, the known O(m) variance bound, and standard L-smooth + PL SGD analysis. Assumptions 1–3 are explicitly scoped to Benjamini–Schramm convergent families (regular, sparse ER) and are backed by the local-positivity lemmas (App. A) plus the local-limit argument for µ, L (App. C.2). The finite-difference versus parameter-shift distinction is handled cleanly. No hidden algebraic gap, sign error, or regime where the relative-concentration argument fails under the stated hypotheses was found; the result remains properly conditional exactly as the reader assessed.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The manuscript analyzes the measurement (shot) complexity of QAOA for MaxCut. Using Janson’s inequality on dependent edge terms and standard L-smooth + Polyak–Łojasiewicz SGD theory, it derives sufficient shot budgets to (a) estimate the cost to relative error δ with confidence 1−ε and (b) keep the SGD relative suboptimality below a target ξ*. Under an extensive-cost lower bound |⟨Cp⟩|≥κm and linear scaling of the PL and Lipschitz constants (Assumptions 1–3), the sufficient shots per cost evaluation scale as 1/m for finite-difference gradients (and as Θ(1) for parameter-shift), while the number of SGD iterations is Θ(1). The authors characterize the relevant graph classes via Benjamini–Schramm local limits, give practitioner calibration rules, and support the scalings with noiseless finite-shot simulations on regular, sparse Erdős–Rényi, and random connected graphs.","tokens_in":36304,"tokens_out":1069,"duration_ms":23615,"significance":"If the extensivity and linear PL/Lipschitz hypotheses hold for the intended families, the result is a genuine and useful contribution: it shows that a fixed relative performance target can become cheaper in shots as MaxCut instances grow, complementing known parameter-transfer / tree-QAOA concentration results. The finite-difference versus parameter-shift variance prefactors are treated carefully, the concentration argument via Janson is correctly applied to QAOA causal cones, and the paper supplies explicit sufficient conditions, practitioner heuristics, and public code. The claims are properly conditional rather than universal, which is appropriate. Strengths include transparent derivations, local-positivity lemmas supporting extensivity, and numerical checks that track the predicted 1/m trend on small but structured instances.","major_comments":[{"comment":"Assumption 1 (and Appendix A, Reasoning I) is load-bearing for the 1/m claim. Reasoning I lower-bounds |⟨Cp⟩| by m/2 using the (0,0) initialization together with monotonicity of the expected cost along the SGD trajectory. Noisy SGD need not be monotone pathwise. Either restrict the trajectory claim to expected progress / noise-free descent, or replace it by a weaker, rigorously controlled condition (e.g., that the optimizer remains in a region where |F|≥κm). Reasoning II (ensemble average under Benjamini–Schramm) and the local-positivity lemmas already give a cleaner route; elevating that route would remove the gap.","section":null},{"comment":"Assumptions 2–3 and Appendix C.2: the scalings µ=Θ(m) and L=Θ(m) rest on strong convexity of the limiting per-edge objective on a local region U. That landscape hypothesis is not checked numerically (e.g., Hessian spectra or empirical PL constants on the calibration graphs). Because Results B–C and the claim T=Θ(1) depend on µ/L=Θ(1), a short numerical check or a more prominent caveat that the iteration/shot conclusions are conditional on this local strong-convexity property would make the load-bearing hypothesis transparent.","section":null}],"minor_comments":[{"comment":"Notation for the sample mean of the cost is inconsistent in places (ˆCp vs ⟨ˆCp⟩, e.g. Lemma 3 / Appendix B). Pick one convention and use it throughout.","section":null},{"comment":"Fig. 4 reports minimal shot counts from a single graph instance per size; adding error bars or medians over the 10 instances already used elsewhere would better match the multi-instance protocol of Figs. 3 and 6–8.","section":null},{"comment":"In Sec. 4.3 the relative gap dt is evaluated from exact state-vector costs while only the gradient is shot-noisy. This is fine for testing the theory, but the practitioner heuristics (Sec. 3.5) should note that full shot noise on both cost and gradient may require a modestly larger budget.","section":null},{"comment":"Typographical: “Polyak- Lojasiewicz” should be “Polyak–Łojasiewicz” (or “Polyak-Lojasiewicz”) consistently; a few missing spaces after commas appear in the abstract and Sec. 1.","section":null},{"comment":"The open Conjecture 10 is interesting but not needed for the main theorems; a one-sentence pointer that the proved lemmas already cover the tree-like and path-repeatable cases used in the scaling claims would help readers.","section":null}],"recommendation":"minor_revision","confidential_remarks":"Solid, carefully scoped QAOA resource-scaling paper. The dependence on extensivity and local strong convexity is real but openly stated; with the two clarifications above it is suitable for a specialized quant-ph / quantum-algorithms venue. No novelty or citation concerns noted. Fit is good."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The one thing worth knowing is that they convert the usual extensive variance of MaxCut QAOA into a concrete 1/m shot budget for fixed relative error (and for relative SGD suboptimality under finite differences). That is not in the Brandao/tree-QAOA concentration papers; those give angle transfer and absolute cut guarantees, not shot-count scaling.\n\nWhat they do well: Janson is applied correctly to the dependent edge terms, the Farhi variance bound is used cleanly, and the SGD noise-floor argument is standard L-smooth + PL. The finite-difference vs parameter-shift distinction is handled carefully (ws = O(1) vs Theta(m)), and the iteration count comes out Theta(1) once mu and L are both linear in m. Appendix A’s local-positivity lemmas and the Benjamini–Schramm argument for mu/L are honest about the scope. Numerics on 3-regular, sparse ER, and random connected graphs line up with the predicted 1/m drop, and they ship code.\n\nSoft spots are real but proportional. Everything sits on Assumptions 1–3 (extensive cost, linear PL, linear Lipschitz). If the cost stops being extensive the 1/m claim collapses; they say so. The PL/Lipschitz linear scaling is argued via local limits rather than proved for every trajectory, and the numerical range is modest (N up to 22). None of that is hidden, and none of it is a derivation error.\n\nThis is for people who actually budget shots and TTS on large sparse MaxCut instances, and for anyone writing resource analyses of fixed-depth QAOA. It deserves a serious referee. I would engage with it and expect to cite the shot-scaling statements.","headline":"Clean, usable inverse-shot scaling for relative-error QAOA MaxCut under extensivity; the math holds and the result is new relative to the concentration literature.","tokens_in":36883,"tokens_out":458,"would_cite":true,"duration_ms":5169,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"For large MaxCut graphs of fixed local structure, QAOA needs fewer measurement shots to hit the same relative accuracy as the graph grows.","keywords":["QAOA","MaxCut","shot complexity","relative concentration","stochastic gradient descent","Benjamini-Schramm convergence","finite-difference gradients","variational quantum algorithms"],"falsifier":"On a sequence of bounded-degree graphs that keep the same local structure, measure the minimal shots needed to keep relative cost error below a fixed δ with fixed confidence: if that shot count does not fall roughly as 1/m, the central scaling claim is false.","tokens_in":37053,"feed_emoji":"📉","tokens_out":783,"duration_ms":6792,"temperature":0.7,"pith_summary":"This paper asks how many circuit measurements (shots) QAOA needs for the MaxCut problem, and how that number scales with graph size. Using concentration inequalities and optimization theory, the authors prove that when the expected cost grows linearly with the number of edges and the landscape smoothness constants scale the same way, the shot count per cost evaluation that is enough to keep a fixed relative error actually falls as one over the number of edges. The number of stochastic-gradient iterations needed stays independent of size. The same local-structure conditions that earlier work used to transfer angles from small graphs to large ones therefore also make the sampling budget shrink rather than grow. The result is backed by explicit sufficient bounds, a practitioner calibration recipe, and numerical checks on regular, Erdős–Rényi and random connected graphs. If the picture holds, large MaxCut instances become cheaper per relative-performance target, not more expensive.","feed_headline":"Bigger MaxCut graphs need fewer QAOA shots","feed_subtitle":"Relative accuracy improves with size when cost and variance both grow linearly with edges","key_machinery":"Relative concentration of the MaxCut cost: both expectation and variance scale linearly with m, so the relative standard deviation shrinks as 1/√m; Janson’s inequality then yields an inverse shot bound, and the same scaling plus PL/Lipschitz assumptions carries the argument through SGD.","core_discovery":"Under an extensive-cost lower bound and linear scaling of the Polyak-Łojasiewicz and Lipschitz constants, a sufficient shot budget per QAOA cost evaluation that guarantees fixed relative estimation error (or fixed relative SGD suboptimality) decreases as 1/m with the number of edges m, while the iteration count remains Θ(1).","pith_inferences":["The same relative-concentration argument may apply to other local-cost combinatorial problems (e.g., Max-k-SAT or Ising models with bounded degree) once an extensive lower bound is verified.","If absolute rather than relative accuracy is required, as in many VQE energy targets, the 1/m advantage disappears.","Hardware-aware implementations that already use shallow fixed-angle QAOA could further cut classical post-processing by deliberately lowering the shot schedule with instance size."],"forward_implications":["For Benjamini–Schramm convergent families (regular, sparse Erdős–Rényi, cycles) the total shot budget for fixed relative performance improves with size.","Angle-transfer methods that already avoid outer-loop optimization can also run with a shrinking measurement budget.","Finite-difference gradient estimators inherit the 1/m shot scaling; gate-wise parameter-shift estimators keep a size-independent shot count.","Practitioners can calibrate shots on small graphs and extrapolate by the inverse-size rule for larger instances of the same family."],"fun_headline_variants":["Larger MaxCut graphs need fewer QAOA shots","QAOA shot budget for MaxCut falls as 1/m with edges","Shot needs drop with size for MaxCut QAOA","Fewer measurements suffice on bigger MaxCut graphs","QAOA MaxCut relative error needs shrink with instance size"],"cache_read_input_tokens":32896,"weakest_assumption_plain":"The expected QAOA cost must stay at least a fixed positive fraction of the number of edges throughout the optimization; if the cost stops being extensive, the inverse-shot claim fails.","fun_headline_variants_meta":{"raw":{"variants":["Larger MaxCut graphs need fewer QAOA shots","QAOA shot budget for MaxCut falls as 1/m with edges","Shot needs drop with size for MaxCut QAOA","Fewer measurements suffice on bigger MaxCut graphs","QAOA MaxCut relative error needs shrink with instance size"]},"model":"grok-4.5","effort":"low","cost_usd":0.007722,"raw_usage":{"total_tokens":1849,"prompt_tokens":747,"num_sources_used":0,"completion_tokens":86,"cost_in_usd_ticks":77220000,"prompt_tokens_details":{"text_tokens":747,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1016,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":747,"tokens_out":86,"duration_ms":6788,"temperature":1.0,"reasoning_tokens":1016,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-12T03:10:00.050543+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"On a sequence of bounded-degree graphs that keep the same local structure, measure the minimal shots needed to keep relative cost error below a fixed δ with fixed confidence: if that shot count does not fall roughly as 1/m, the central scaling claim is false.","supporting_citations":[],"review_version":1}