{"id":"b6315e55-a123-41c4-b171-12dbbab15795","arxiv_id":"2607.08138","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":4,"one_line_summary":"Adaptive min-vertex-cut qubit freezing plus bias folding makes DC-QAOA partition every graph (to n=10k) while matching quality on separable instances and beating QAOA2 at equal coverage.","lead":"FrozenLGP fixes divide-and-conquer QAOA’s failure on dense graphs by classically freezing a min-cut set of obstructing vertices and folding their edges into local bias terms. It turns partitionability into an enforceable property, reaching 100% coverage where the standard baseline often aborts.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"Large-n 100% coverage and Bf=κ−(k−1) thresholds rest on a polynomial upper-bound driver whose agreement with exact MVC is shown only for n=12–24.","rationale":"The reader correctly isolates the single most load-bearing premise for the headline coverage claim: the large-scale numbers are generated by a scoped relaxation whose fidelity to exact MVC is demonstrated only at moderate n. The paper is transparent about the scoping (Sec. 3.2, App. F.5) and supplies supporting evidence (δ=κ tightness, Table 5 agreement, exact staircase on regular graphs), so the concern does not invalidate the engineering contribution or the small-n quality results; it simply justifies keeping the verdict CONDITIONAL until larger exact checks or public code close the gap. No stronger internal inconsistency (e.g., in the freeze-and-fold identity or the phase-priority guarantee) was found. Quality extrapolation to 10 k is a secondary, already-noted limitation. Consequently the reader’s CONDITIONAL / HIGH assessment stands.","tokens_in":33922,"tokens_out":613,"duration_ms":31671,"concrete_test":"Select 20–30 high-connectivity instances (BA d=7, dense ER, d-regular d≥6) at n=40–80 where exact node-split max-flow remains tractable; recompute freeze sets F, minimal feasible Bf, and freezing-only coverage curves with both exact Algorithm 1 and the upper-bound driver under identical k=6. If |F| or the Bf threshold differs on >10% of instances, or if CPP invocation rates diverge, the n=10 k claims do not represent exact FrozenLGP.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The strongest claim’s scalability half (100% decomposition coverage to n=10 000, sharp topology-predicted recovery at Bf=κ−(k−1), ρ up to ~39%) is produced exclusively by the polynomial-time upper-bound driver of Appendix F.5, not by the exact min-vertex-cut Algorithm 1 of Sec. 3.2. The paper states the bound is tight when δ=κ (true for the studied families) and shows exact agreement on a 48-instance common set with n=12–24 (Table 5). Outside that regime it remains possible that the driver returns strictly larger freeze sets, different separators, or more frequent CPP fallbacks; any systematic over-freezing would inflate reported reduction ratios, shift the observed coverage knee, and weaken the claim that the large-scale numbers faithfully represent the “provably minimum” MVC procedure advertised in the abstract and Sec. 3. Quality preservation and QAOA2 comparisons are shown only up to n=100, so they do not independently corroborate the 10 k-scale partition results.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The manuscript proposes FrozenLGP, a three-phase decomposition front end for divide-and-conquer QAOA. When standard Large Graph Partitioning fails to find a small vertex separator, Phase 2 freezes a minimum vertex cut of the residual graph (via node-split max-flow) and folds the removed couplings into linear Ising biases on active neighbors; Phase 3 (CPP) is a deterministic midpoint-split fallback with classical cut-edge rescoring that guarantees coverage on graphs no vertex-removal method can bipartition. Partition-level experiments across BA, dense ER, two-cluster, and random d-regular families up to n=10,000 report 100% coverage versus 4.6% for Phase-1-only DC-QAOA on high-connectivity instances, with a sharp recovery threshold at B_f=κ−(k−1). End-to-end MaxCut (mainly n≤20 and vs QAOA2 up to n=100) shows quality preservation on DC-QAOA-solvable instances, recovery of previously unsupported dense graphs, and higher approximation ratios than QAOA-in-QAOA at equal full coverage, with noise simulations indicating reduced entangling-gate exposure.","tokens_in":34245,"tokens_out":1611,"duration_ms":26661,"significance":"If the claims hold, FrozenLGP fills a genuine gap in the DC-QAOA stack: decomposition has been treated as a given, yet it is the gatekeeper, and standard LGP aborts on dense or high-connectivity graphs. Making partitionability enforceable via energy-preserving freezing, while keeping separator-based exact reconstruction when possible, is a clean design point relative to arbitrary-partition methods (QAOA2) and exponential circuit-cutting reconstruction (CutQC). Strengths include a topology-predicted freeze budget that is confirmed as a step function on d-regular graphs, strict phase priority (zero freeze overhead when LGP succeeds), transparent comparison to full-coverage alternatives, bootstrap CIs / TOST equivalence tests on the common solvable set, and resource-footprint arguments via transpilation. These make the work a useful, falsifiable contribution to distributed NISQ optimization rather than a purely heuristic partitioner.","major_comments":[{"comment":"Sec. 4.1–4.2 and Appendix F.5: the headline 100% coverage to n=10,000, the B_f=κ−(k−1) threshold, and reduction ratios up to ~39% are produced exclusively by the polynomial-time upper-bound driver, not by exact Algorithm 1 (MVC). Exact agreement is shown only on a 48-instance set with n=12–24 (Table 5). Although the paper scopes tightness to δ=κ families, the abstract and Sec. 3 still advertise a “provably minimum” MVC procedure as the source of the large-scale numbers. Either (i) strengthen validation of driver vs exact MVC at substantially larger n (or on more families), or (ii) restate abstract/claims so that large-n coverage and thresholds are explicitly attributed to the upper-bound driver, with exact MVC reserved for the moderate-scale check. Without that, the scalability half of the strongest claim is not fully supported as stated.","section":null},{"comment":"Sec. 4.3–4.4 vs Sec. 4.1: end-to-end approximation quality (preservation vs DC-QAOA, recovery of unsupported dense graphs, and superiority to QAOA2) is demonstrated only up to n≤20 (dense unsupported set) and n≤100 (QAOA2 head-to-head), while the 10k-scale regime reports only preprocessing metrics. Table 3 also shows that at n≤20 classical heuristics already reach AR≈0.994–1.000, so that block mainly tests coverage and non-degradation. The manuscript should more sharply separate what is established at each scale and avoid implying that quality preservation at n≤100 independently corroborates the n=10^4 partition results. A limited larger-n quality probe (even with classical leaf solvers or coarser QAOA settings) or an explicit “partition-only beyond n=100” boundary in the abstract would close this gap.","section":null},{"comment":"Sec. 3.2 / Algorithm 1 and Appendix C: the quantum overhead is bounded by 2^{m_max} (or 2^{m_max−1} under bit-flip symmetry) per partition, with default m_max=3. On recursive decompositions of dense graphs this multiplies across levels; Appendix D notes that inherited nonzero bias disables the symmetry halving. The paper does not quantify cumulative sub-circuit counts or wall-clock quantum cost on the same n=10^3–10^4 instances used for coverage, only leaf counts and NRL (Fig. 13). Because the operating point B_f∈{2,3} is justified partly by “minimal downstream quantum cost,” a load-bearing cost accounting (total enumerated assignments × leaf count under recursion) should be reported for the high-connectivity families, or the claim should be limited to per-partition overhead.","section":null}],"minor_comments":[{"comment":"Abstract and Introduction: “provably minimum” / “exactly minimal set” language should be cross-referenced to the Appendix F.5 scoping so readers do not equate Algorithm 1 with the large-n driver before reaching the appendix.","section":null},{"comment":"Fig. 1 caption and Sec. 3.1: the five-node toy example is clear, but the shared-separator duplication vs frozen-node exclusion could be labeled more explicitly in panels (b) vs (e) for readers new to DC-QAOA MDR.","section":null},{"comment":"Table 2: NRL for DC-QAOA (1.90) is averaged only over the 4.6% successful subset while FrozenLGP’s NRL is over all instances; the caption explains this, but a row restricted to the common solvable set would make the comparison less easy to misread.","section":null},{"comment":"Appendix I: the CPP rescoring ablation is underpowered (few CPP-firing instances); stating that non-significance is weak evidence of equivalence (as the text partly does) in the main Sec. 3.3 would help.","section":null},{"comment":"Typos / polish: “This paper makes two testable claims” (Sec. 4 opening) reads as a fragment; “ann= 10,000” style missing spaces appear in Appendix F; arXiv IDs and journal formatting of references are uneven.","section":null},{"comment":"Data availability: “available from the corresponding author upon reasonable request” is weak for a methods paper whose main claims are empirical; releasing the partition driver and benchmark instance seeds would substantially strengthen reproducibility.","section":null}],"recommendation":"major_revision","confidential_remarks":"The work is a solid systems/algorithms contribution for NISQ QAOA and is a good fit for a quantum-computing or hybrid-algorithms venue. The main risk is overstated scalability language in the abstract relative to the driver used in Sec. 4.1; if the authors reframe cleanly and add either larger-n driver validation or cumulative quantum-cost numbers, I would expect a straightforward path to acceptance. No concerns about novelty disclosure or citation pattern beyond the usual need to keep QAOA2/CutQC comparisons prominent."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"Punchline: this is a practical front end that stops divide-and-conquer QAOA from dying on dense graphs. Standard LGP needs a small vertex separator and returns nothing when it cannot find one; FrozenLGP freezes a min vertex cut (max-flow on the node-split network), folds the edges into h-biases, and falls back to a simple connectivity-preserving split so coverage hits 100%. That is the actual new piece—freezing and bias folding already exist for fidelity inside fixed circuits; putting exact MVC at the partitioning layer to enforce bipartition is the move.\n\nWhat they do well is clear. Phase priority means zero freeze overhead when ordinary LGP works, and they show quality equivalence on the common set (TOST inside ±0.02 AR). Partition experiments are large (hundreds of instances, n to 10k, BA/ER/regular/two-cluster), the Bf = κ−(k−1) threshold is predicted from connectivity and lands exactly on d-regular graphs, and the head-to-head with QAOA2 at equal k/p/shots is the right comparison: both full coverage, FrozenLGP keeps separator reconstruction exact and wins on AR as n grows. Noise and resource arguments (fewer CNOTs per sub-circuit) are consistent with the design. Math is standard Ising linearity and Menger/max-flow; citations cover Li et al., QAOA2, CutQC, FrozenQubits without obvious gaps.\n\nSoft spots in proportion. All headline scalability (100% to 10k, ρ ~39%) is from the polynomial upper-bound driver, not exhaustive Algorithm 1. They scope tightness to δ=κ families and check exact agreement only on n=12–24 (48 instances). That is honest but real: if the driver over-freezes outside that window, reduction ratios and the knee shift. End-to-end MaxCut quality is mainly n≤20 (vs DC-QAOA/monolithic) and n≤100 (vs QAOA2); the 10k regime is preprocessing only. Code is request-only. None of that sinks the core claim—coverage recovery and quality preservation where both methods run look solid—but it caps how hard you can lean on the extreme-scale numbers.\n\nWho it is for: people building distributed/NISQ QAOA pipelines who hit separator failure on dense MaxCut-like graphs. Worth a serious referee. I would engage: cite the method when I need a topology-robust DC front end, and ask for public artifacts plus a larger-n quality check if I were reviewing.","headline":"Real fix for DC-QAOA’s dense-graph abort: min-cut freezing at the partition layer, full coverage, and better quality than QAOA2 at equal settings—large-n numbers rest on a scoped upper-bound driver.","tokens_in":34893,"tokens_out":658,"would_cite":true,"duration_ms":12080,"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":"Freezing a minimal set of obstructing vertices turns partitionability into an enforceable property, so divide-and-conquer QAOA covers dense graphs that previously aborted.","keywords":["QAOA","divide-and-conquer QAOA","graph partitioning","qubit freezing","MaxCut","NISQ","minimum vertex cut","Ising bias folding"],"falsifier":"Run the exact exhaustive minimum-vertex-cut partitioner and the paper’s upper-bound driver on a common suite of dense random-regular and BA graphs at n = 100–500; if coverage or the predicted freeze-budget threshold Bf = κ − (k − 1) diverges, the headline scalability claim fails.","tokens_in":34779,"feed_emoji":"❄️","tokens_out":755,"duration_ms":13006,"temperature":0.7,"pith_summary":"Standard divide-and-conquer QAOA aborts on dense or highly connected graphs because it needs a small vertex separator that simply does not exist. This paper claims that an adaptive front-end called FrozenLGP can force a valid bipartition by classically freezing the smallest set of obstructing vertices (found via a max-flow minimum-vertex-cut) and folding their energetic contributions into linear bias terms on the remaining active qubits. The result is 100 percent decomposition coverage up to 10,000-vertex graphs across multiple topology families, while approximation quality is preserved on the sparse instances that ordinary divide-and-conquer already solves and is competitive with or better than other full-coverage strategies. Because freezing also strips entangling gates, the same mechanism improves noise robustness on near-term hardware. A sympathetic reader cares because it removes the structural gatekeeper that currently blocks distributed QAOA from the hard graphs that matter most.","feed_headline":"Freezing qubits forces every graph to partition for QAOA","feed_subtitle":"Dense graphs that once aborted now reach 100% coverage while MaxCut quality holds","key_machinery":"Adaptive qubit freezing via minimum-vertex-cut (MVC) computed by node-split max-flow: the smallest set F of vertices whose classical spin assignment (+1 or −1) severs residual connectivity is frozen, and each removed coupling Ju,v is folded into the linear bias hu of every surviving neighbor, so the energetic contribution is preserved without any quantum gate.","core_discovery":"FrozenLGP converts partitionability from an assumption into an enforceable property: when no small vertex separator exists, it freezes the provably minimum obstructing vertex set obtained as a max-flow minimum vertex cut, folds the removed interactions into Ising linear biases on neighboring active qubits, and thereby recovers a valid bipartition whose sub-circuit Hamiltonians remain rigorous. Across families up to 10,000 vertices this yields 100 percent coverage versus 4.6 percent for the standard baseline on high-connectivity instances, while end-to-end MaxCut quality is statistically indistinguishable from ordinary divide-and-conquer where both succeed and higher than QAOA-in-QAOA at equa","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Freezing min-cut vertices forces 100% QAOA partitioning coverage","Adaptive freezes convert partition failure into enforceable QAOA property","FrozenLGP freezes obstructors to bipartition any graph for QAOA","Qubit freezes preserve Ising energy for 100% dense-graph QAOA coverage","Min obstructing qubits frozen to enable robust QAOA divide-and-conquer"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"That the polynomial-time upper-bound partitioner used for all large-scale coverage numbers is tight enough that the reported 100 percent coverage and the exact freeze-budget threshold still hold for the true minimum-vertex-cut algorithm on graphs far larger than the moderate set where the two were checked head-to-head.","fun_headline_variants_meta":{"raw":{"variants":["Freezing min-cut vertices forces 100% QAOA partitioning coverage","Adaptive freezes convert partition failure into enforceable QAOA property","FrozenLGP freezes obstructors to bipartition any graph for QAOA","Qubit freezes preserve Ising energy for 100% dense-graph QAOA coverage","Min obstructing qubits frozen to enable robust QAOA divide-and-conquer"]},"model":"grok-4.5","effort":"low","cost_usd":0.010238,"raw_usage":{"total_tokens":2361,"prompt_tokens":886,"num_sources_used":0,"completion_tokens":107,"cost_in_usd_ticks":102380000,"prompt_tokens_details":{"text_tokens":886,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1368,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":886,"tokens_out":107,"duration_ms":12540,"temperature":1.0,"reasoning_tokens":1368,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-10T12:28:03.485504+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Run the exact exhaustive minimum-vertex-cut partitioner and the paper’s upper-bound driver on a common suite of dense random-regular and BA graphs at n = 100–500; if coverage or the predicted freeze-budget threshold Bf = κ − (k − 1) diverges, the headline scalability claim fails.","supporting_citations":[],"review_version":1}