{"id":"aa242ccc-d761-47fc-8507-3138a6f21d1f","arxiv_id":"2607.10274","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":5.5,"correctness_risk":"low","formal_verification":"none","parameter_count":5,"one_line_summary":"Greedy, problem-dependent SWAP-layer sequences on 2D grids roughly halve QAOA circuit depth and CZ count for sparse MaxCut and MIS graphs, improving hardware approximation ratios by up to ~6–9%.","lead":"A problem-aware routing method for QAOA on 2D qubit grids cuts circuit depth and two-qubit gate count roughly in half for sparse optimization graphs. That reduction lets experiments reach 80 qubits and raises measured approximation ratios by several percent on IBM hardware.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified; the restricted basis and limited greedy lookahead are disclosed and do not undermine the reported factor-of-two gains versus the line baseline.","rationale":"The reader correctly isolates the restricted layer basis plus limited lookahead as the weakest modeling choice. That choice is fully disclosed, the classical cost is tunable (App. A), and the empirical evidence against the actual baselines used (line, hybrid, fixed-grid, SABRE) remains consistent across simulation scalings and hardware runs. No stronger concern—e.g., an unsupported scaling derivation, circular comparison, or hardware artifact that would reverse the AR ordering—emerges on a second reading. The optimistic CZ-budget shading in Fig. 5 is only illustrative and does not affect the measured AR numbers. Consequently the ACCEPT verdict and low correctness risk stand.","tokens_in":28800,"tokens_out":495,"duration_ms":26470,"concrete_test":"Re-transpile the ten n=80 RR d=3 instances of Fig. 4 with k_max=7 (and k_append≤5) using the same extended basis; if mean SWAP-layer count falls by more than 15–20 % relative to the published greedy numbers, the fixed-hyperparameter results understate the method’s potential and the search restriction becomes more material.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (factor-of-two reduction in SWAP layers/depth/CZ count for sparse QAOA cost layers on grids, plus the resulting hardware AR gains) is empirically supported by the direct comparisons in Sec. IV and Figs. 4–7. The search is confined to sequences drawn from the small fixed basis B_grid / B_extended_grid with k_max=5 and I=5 (Sec. III.B, App. A). This is a genuine limitation on absolute optimality, yet it is not load-bearing for the claim as stated: the method still beats the fixed S_grid strategy, the hybrid/line strategies, and SABRE on the same coupling maps, the O(√n) scaling holds in the sparse regime analyzed in App. C, and the hardware AR improvements (up to 6.6 % / 9.3 %) track the measured gate reductions. No internal inconsistency or unsupported leap appears.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The manuscript develops a problem-dependent transpilation method for blocks of commuting two-qubit gates (primarily QAOA cost layers) on rectangular 2D grid coupling maps. It introduces a hybrid line-on-grid baseline and a greedy search that builds SWAP-layer sequences from a fixed hardware-native basis (B_grid or its extension) while iteratively refining the initial mapping via SAT. For sparse instances—MaxCut on 3-regular graphs and MIS on Erdős–Rényi graphs with q≈0.08—the method reduces SWAP-layer count, two-qubit depth and CZ count by roughly a factor of two relative to the standard line SWAP strategy, yields an asymptotic O(√n) improvement consistent with routing-diameter arguments, and produces measurable gains in mean approximation ratio (up to 6.62 % for MC and 9.32 % for MIS) on ibm_miami hardware for circuits up to 80 qubits.","tokens_in":29097,"tokens_out":1038,"duration_ms":17804,"significance":"If the reported factor-of-two resource reductions and the associated hardware approximation-ratio gains hold under broader scrutiny, the work supplies a practical, immediately usable compilation improvement for sparse QAOA and related Ising-model circuits on emerging grid-connected superconducting devices. The asymptotic analysis in Appendix C, the multi-baseline numerical comparisons (line, hybrid, fixed grid, SABRE), and the unmitigated hardware runs with fixed or carefully transferred angles constitute reproducible evidence that problem-aware routing can extend the feasible size of noisy QAOA experiments. The explicit disclosure of the restricted SWAP-layer basis and the tunable classical pre-processing cost (k_max, I) further strengthens the contribution by making the trade-offs transparent.","major_comments":[{"comment":"Sec. III.B and App. A fix k_max=5 and I=5 for all main-text benchmarks. While the hyper-parameter sweep in Fig. A1 shows that these values are reasonable, the absolute optimality claim relative to “standard methods” would be more robust if the authors quantified, for at least one representative n=80 instance, how much further the SWAP-layer count can be reduced by larger k_max or by an unrestricted (non-layer) router. Without that, the factor-of-two advantage is well-supported against the chosen baselines but remains an upper bound on the residual gap to a fully adaptive router.","section":null},{"comment":"App. E derives the ~3600-CZ “feasibility” threshold from optimistic error rates (p_CZ~10^{-3}) that are lower than the median of ibm_miami. Fig. 5 then uses this threshold to delineate the region “enabled” by the greedy method. Because the hardware results themselves (Fig. 7) already demonstrate successful execution of circuits well above that optimistic budget, the threshold is not load-bearing for the experimental claims; however, the language in Sec. IVA that equates the threshold with practical reachability should be softened or recalibrated to the actual device error rates used in Sec. IVB.","section":null}],"minor_comments":[{"comment":"Fig. 4 caption states that Line (SABRE) results are omitted from panels (b) and (e) because they fall outside the plotted range; a brief numerical range in the caption or a log-scale inset would help the reader gauge the magnitude of the SABRE depth penalty.","section":null},{"comment":"Eq. (5) uses a logical disjunction of permuted coupling maps; a short clarifying sentence that the resulting matrix is then interpreted as an adjacency matrix for the implementable edges would remove any ambiguity about the Boolean-to-graph conversion.","section":null},{"comment":"In Sec. IIA the MIS penalty is fixed at M=2 with a brief justification; a one-sentence reference to the known closed-form threshold for independence constraints would make the choice fully self-contained.","section":null},{"comment":"Appendix G describes the angle-transfer procedure for MIS; the explicit formula for λ (Eq. G.2) is useful, but the main text could note that the same transfer is used for all p=2 MIS hardware runs so that readers do not have to hunt for it.","section":null},{"comment":"Typographical consistency: “Erdős–Rényi” appears both with and without the diacritic in figure labels; standardise throughout.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is a solid, well-executed methods paper that sits comfortably within the scope of a quantum-computing or quantum-information journal. The self-citations to prior SWAP-strategy and SAT-mapping work are appropriate tool references rather than circular claims. I see no novelty or citation-pattern concerns that would require editorial intervention beyond ordinary peer review."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This is a clean compiler paper that does what it claims. The new piece is the greedy search over a small fixed basis of grid-native SWAP layers, interleaved with SAT remapping of the initial layout. They also add a hybrid baseline that keeps the line SWAP network but fires extra RZZ gates on unused grid edges. Both beat the fixed grid strategy of Weidenfeller et al. and the usual line strategy; the greedy version is the clear winner on sparse instances.\n\nWhat they do well is the evidence stack. App. C derives the O(sqrt(n)) depth and O(n^{3/2}) or O(n^{5/2}) CZ scalings for sparse RR and ER graphs and matches them to high-R fits. Multi-instance circuit metrics (Figs. 4-6, D1-D2) show consistent factor-of-two reductions versus line and hybrid, and still beat SABRE on depth even when SABRE wins on raw gate count. Hardware on ibm_miami for p=1,2 QAOA (fixed angles for MaxCut, transferred+COBYLA for MIS) tracks those gate savings: up to 6.6% and 9.3% relative AR lifts, no post-selection or mitigation. Circularity is low; baselines are external.\n\nSoft spots are real but secondary. The search is confined to B_grid / B_extended with k_max=5 and I=5; that is disclosed and does not break the claim against the stated baselines, but absolute optimality is open. No code release. The ~3600-CZ feasibility shading uses optimistic error rates. MIS angles rely on transfer heuristics. None of these overturn the measured gains.\n\nThis is for people who actually run QAOA or Ising evolution on grid-connected hardware and care about gate budget. It is incremental relative to the cited SWAP-strategy and SAT-mapping work, but the combination is useful and the data are honest. Send it to peer review; a serious referee will tighten the hyperparameter discussion and ask for code, not reject it.","headline":"Solid systems paper: greedy problem-aware SWAP-layer search on grids cuts sparse QAOA cost-layer depth/CZ count ~2x vs line routing, with matching hardware AR gains up to 80 qubits.","tokens_in":29716,"tokens_out":533,"would_cite":true,"duration_ms":7341,"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":"A problem-aware greedy SWAP strategy on 2D grids roughly halves QAOA circuit depth for sparse graphs, raising hardware approximation ratios by several percent up to 80 qubits.","keywords":["QAOA","circuit transpilation","SWAP strategies","2D grid connectivity","MaxCut","Maximum Independent Set","commuting gates","sparse graphs"],"falsifier":"Transpile the same family of 3-regular MaxCut and q=0.08 Erdős–Rényi MIS instances with an unrestricted or larger-basis router and check whether the resulting SWAP-layer counts, depths and CZ counts fall well below the greedy figures reported in the paper; if they do, the factor-of-two advantage disappears.","tokens_in":29666,"feed_emoji":"⚛️","tokens_out":744,"duration_ms":8179,"temperature":0.7,"pith_summary":"QAOA cost layers are blocks of commuting two-qubit gates whose interaction graph often does not match a device's limited connectivity, so compilers must insert many SWAP gates. On rectangular grids the usual fixed line-based SWAP network is wasteful when the problem graph is sparse. This paper shows that alternating a greedy search over a small basis of hardware-native SWAP layers with SAT-based remapping of the qubit layout produces substantially shorter routing sequences for those sparse instances. The resulting circuits need about half as many SWAP layers, half the two-qubit depth, and half the CZ gates of the standard line strategy. That reduction is large enough to run QAOA for MaxCut on 3-regular graphs and Max Independent Set on low-density Erdős–Rényi graphs up to 80 qubits on present hardware, lifting measured mean approximation ratios by as much as 6.6 % and 9.3 %, respectively. The same asymptotic scaling argument implies that further hardware improvements will widen the size window in which the grid-aware method remains advantageous.","feed_headline":"Greedy grid SWAPs cut QAOA depth in half for sparse problems","feed_subtitle":"Problem-aware routing on 2-D lattices lifts hardware approximation ratios several percent up to 80 qubits","key_machinery":"The greedy problem-dependent transpilation loop: depth-limited exhaustive search over sequences drawn from a small basis of grid-native SWAP layers (B_grid or its eight-layer extension), followed by outer-loop SAT remapping of the qubit layout, which together produce a shorter routing path that realises exactly the required interactions.","core_discovery":"For sparse commuting two-qubit blocks on rectangular 2-D grids, a greedy construction of problem-dependent SWAP-layer sequences drawn from a fixed hardware-native basis, interleaved with SAT remapping of the initial layout, reduces the number of SWAP layers, the two-qubit depth, and the CZ count by roughly a factor of two relative to the standard line SWAP strategy, enabling practical QAOA experiments up to 80 qubits and improving mean approximation ratios by up to 6.6 % (MaxCut) and 9.3 % (MIS).","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Greedy SWAP layers halve QAOA depth on 2D grids for sparse graphs","Problem-aware routing cuts QAOA depth and CZ count by half","Adaptive grid SWAPs enable 80-qubit QAOA with higher approx ratios","Sparse commuting blocks transpile 2x shorter via greedy SWAP sequences","2D lattice SWAP construction doubles efficiency for MaxCut MIS QAOA"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"That a small fixed set of hardware-native SWAP layers plus a shallow greedy lookahead is already enough to find near-optimal routing for the sparse graphs under study; if better non-layer or adaptive bases exist, the claimed factor-of-two gain over standard methods shrinks.","fun_headline_variants_meta":{"raw":{"variants":["Greedy SWAP layers halve QAOA depth on 2D grids for sparse graphs","Problem-aware routing cuts QAOA depth and CZ count by half","Adaptive grid SWAPs enable 80-qubit QAOA with higher approx ratios","Sparse commuting blocks transpile 2x shorter via greedy SWAP sequences","2D lattice SWAP construction doubles efficiency for MaxCut MIS QAOA"]},"model":"grok-4.5","effort":"low","cost_usd":0.004842,"raw_usage":{"total_tokens":1417,"prompt_tokens":819,"num_sources_used":0,"completion_tokens":88,"cost_in_usd_ticks":48420000,"prompt_tokens_details":{"text_tokens":819,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":510,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":819,"tokens_out":88,"duration_ms":4819,"temperature":1.0,"reasoning_tokens":510,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T12:59:05.646853+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Transpile the same family of 3-regular MaxCut and q=0.08 Erdős–Rényi MIS instances with an unrestricted or larger-basis router and check whether the resulting SWAP-layer counts, depths and CZ counts fall well below the greedy figures reported in the paper; if they do, the factor-of-two advantage disappears.","supporting_citations":[],"review_version":1}