{"id":"68fdf26b-525c-438b-b2b0-647bec4e293d","arxiv_id":"2504.16468","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"HAQA prunes a quantum processor's coupling graph to a small, fidelity-scored community before SAT/SMT mapping, yielding large solver speedups while mostly preserving or improving circuit quality.","lead":"This paper presents HAQA, a method that picks a small, high-quality region of a quantum chip before running an optimal qubit-mapping solver, shrinking the problem and making it much faster. It reports hundreds-fold speedups and better circuit fidelity on IBM Eagle and Heron benchmarks, but the gains come with caveats about how the comparisons were made.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Solution quality is verified only on circuits the unmodified baselines can finish; on the timeout instances that produce the largest speedups (Table 6: >345x to 632x), no reference mapping exists, so 'ensuring solution quality' is unsubstantiated exactly where HAQA is claimed to shine.","rationale":"The paper's central claim bundles a speedup (up to 632.76x/286.87x) with quality preservation ('ensuring solution quality') and average fidelity improvement. For the speedup to be meaningful, the pruning must not silently degrade depth, swap count, or fidelity on the instances where it is applied. The timing evidence for the speedup itself is credible: HAQA genuinely reduces the solver's search space from 127/133 qubits to roughly nq+1, and the 25-sample timing tables show a monotone pattern (small gains on small circuits, huge gains where the baseline times out), matching the complexity analysis' direction. The vulnerable link is quality preservation. Section 6.3 restricts all depth/swap/fidelity comparisons to circuits solvable by both unmodified baselines, i.e., Tables 8-11 cover at most 17/25 (Qsynth) and 9-10/25 (TB-OLSQ2) samples. The omitted rows are the large instances (nG=40-79) where the baseline exceeds the 3600s limit — the instances producing the headline ratios (>345x, >546x, 632.76x). For these, no reference solution exists, so no one has checked whether the k=1 region is sufficient; the reader's flagged assumption (Section 4.3: k=1 expansion supplies enough ancillary qubits and high-fidelity paths) is untested precisely where it matters most. The compared subset already shows the pruning costs quality on individual rows: fidelity losses of -17.8% and -17.02% on Heron (Table 10), -1.72% and -2.64% on others, and depth/swap increases such as barenco_tof_4 84->90 depth and vqe_8_3_5_100 10->13 swaps. Because the wrapped solvers are optimal within the selected region, any deviation from a full-graph optimum is entirely attributable to HAQA's pruning, and the paper never measures this gap on hard instances. A separate but reinforcing gap is the absence of an omega=0 ablation for the fidelity-aware term (Eq. 6), leaving the causal link between fidelity-aware region selection and the measured fidelity gains unverified. None of this indicates fabrication: the timings are internally consistent, the code is released, and the scaling predictions (Eqs. 26-29) are falsifiable. However, the headline speedup numbers are not yet evidence that the speedup is achieved 'without quality loss' in the target regime. The CONDITIONAL verdict is the right one; it should be conditioned on a hard-instance quality check against an enlarged-region or long-budget reference.","tokens_in":19182,"tokens_out":13759,"duration_ms":134302,"concrete_test":"Run QSynth-v2 and TB-OLSQ2 on IBM Eagle with the HAQA-selected region expanded to k=2 (Algorithm 2, feasible with the released code) for the currently time-outing instances in Table 6 — mod_mult_55, qft_8, vqe_8_0_10_100, vqe_8_0_5_100, vqe_8_1_10_100, vqe_8_2_10_100, vqe_8_3_10_100, vqe_8_4_10_100 — and compare depth, swap count, and simulated Hellinger fidelity against the reported HAQA k=1 solutions. If any instance shows more than ~2 extra swaps, ~6 extra depth, or >5% fidelity loss relative to the k=2 reference, the headline acceleration in the target regime is partially bought by quality degradation and the paper's 'ensuring solution quality' claim fails; if all gaps stay within the margins observed in Tables 8-11, the central claim survives this check.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 6.3 states the fidelity comparison is 'focusing exclusively on circuits solvable by both QSynth-v2 and TB-OLSQ2.' Consequently Tables 8-11 include only 17/25 (Qsynth-Eagle), 17/25 (Qsynth-Heron), 10/25 (TB-OLSQ2-Eagle), and 9/25 (TB-OLSQ2-Heron) of the benchmark circuits. The excluded rows are the large ones — adder_n10_transpiled, barenco_tof_5, mod_mult_55, qft_8, and the vqe_8_* circuits with nG up to 79 — precisely the instances whose baseline timeouts produce the headline speedups (Table 6: >345.79x, >546.17x, 632.76x). For these instances no reference depth, swap count, or fidelity is reported, so the claim that speedup is not bought by quality loss has no evidence in the target regime. The compared subset already shows per-instance degradation: Table 10 (Heron/Qsynth) reports adder_n10_transpiled fidelity -17.8% and barenco_tof_4 -17.02%, Table 8 reports tof_5 -1.72%, and depth/swap increase on several rows (barenco_tof_4: 84->90 depth, 8->9 swaps; vqe_8_3_5_100: 10->13 swaps; vqe_8_4_5_100: 8->11 swaps). Only averages are preserved. Because Qsynth-v2 and TB-OLSQ2 are optimal solvers, every within-region result is optimal only for the pruned region; the global-optimality gap is entirely attributable to the pruning, and the paper never bounds it on hard instances.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes HAQA, a wrapper around solver-based qubit mappers (Qsynth-v2 and TB-OLSQ2) that first identifies a small region of the hardware coupling graph using a community-detection procedure guided by both topology and two-qubit-gate fidelity, then expands the region by one layer of neighboring qubits, and finally runs the baseline solver only on the induced subgraph. The claimed results are large speedups (up to 632.76x for Qsynth-v2 and 286.87x for TB-OLSQ2), improved Hellinger fidelity on average (up to 52.69% and 238.28% respectively), and roughly preserved depth and swap counts. A complexity analysis argues that the number of solver variables and constraints is reduced from quantities depending on the full hardware graph to quantities depending essentially on the logical qubit count.","tokens_in":19491,"tokens_out":6950,"duration_ms":67673,"significance":"If the claims are fully validated, HAQA would be a practically useful and easily adoptable front-end for exact qubit mappers, and the paper has several strengths: the complexity analysis is explicit and grounded in the published variable/constraint counts of the two baselines, the code is made available, and the speedup trend is large and consistent across two modern IBM architectures. However, the current validation is incomplete: quality metrics are reported only on a subset of circuits, no fidelity-agnostic control isolates the effect of the hardware-guided selection, a central fidelity formula appears incorrect, and a key parameter of the method is not reported. These issues must be addressed before the central claims can be considered established.","major_comments":[{"comment":"The fidelity, depth, and swap evaluation is restricted to circuits solvable by both baselines, which excludes adder_n10_transpiled, barenco_tof_5, mod_mult_55, qft_8, and the vqe_8_*_10_100 circuits. These are precisely the instances whose baseline timeouts produce the largest speedups in Tables 6-7. For these circuits no reference depth, swap count, or fidelity is reported, so the paper's claim that the acceleration is not bought by quality loss is unsupported in the very regime where HAQA is asserted to be most valuable. The reported subset also contains clear per-instance degradations, e.g., Table 10 reports -17.8% fidelity for adder_n10_transpiled and -17.02% for barenco_tof_4, Table 8 reports -1.72% for tof_5, and several rows show increased depth or swap count (barenco_tof_4, vqe_8_3_5_100, vqe_8_4_5_100). The authors should report quality metrics for all circuits on which the baseline terminates, and for the timeout instances they should either run the baselines with a larger timeout or provide a bound on the optimality gap introduced by the region pruning.","section":"Eq. (1)"},{"comment":"The Hellinger fidelity formula is incorrect as written. The standard expression is HF = (1 - (1/2) * sum_i (sqrt(p_op_i) - sqrt(p_on_i))^2)^2, not the expression with (p_op - p_on)^2 that appears in Eq. (1). If Eq. (1) was actually used in the simulations, the reported metric is not Hellinger fidelity; if instead a correct library function was used, the equation should be fixed. Either way, the central fidelity metric must be stated correctly for the results to be reproducible and interpretable.","section":"Eq. (1)"},{"comment":"The reward function F = Q + ωE introduces a parameter ω, but the text immediately switches to calling it 'the weight parameter w' and never reports the chosen value or a sensitivity analysis. Since Q and E have different scales and the fidelity-aware region selection is a core claimed contribution, omitting this parameter makes the experiments irreproducible and leaves open the possibility that the results depend strongly on an arbitrary choice. Please specify the value used and provide a brief sensitivity study over ω (including ω = 0 as a connectivity-only control).","section":"Section 4.2, Eq. (6)"},{"comment":"The experiments compare HAQA-wrapped solvers against global solvers, but this conflates the effect of reducing the graph size with the effect of the hardware-guided, fidelity-aware region selection. To support the claim that the community-based and fidelity-aware selection (rather than merely using a smaller graph) is responsible for the speedup and fidelity gains, the authors should add a control that runs the baseline solver on a same-size region chosen by a topology-only criterion (e.g., ω = 0) or by a random connected subgraph. A comparison with the subgraph-identification method of Guo et al. [26] would also help position the contribution.","section":"Section 6.2 (experimental design)"},{"comment":"The expansion factor k is tuned on the same benchmark set that is later used for the main evaluation: Table 5 reports eight vqe circuits on IBM Heron, and k = 1 is then adopted for the headline results. This is a form of test-set tuning. The authors should either select k on a separate validation set or demonstrate that the main conclusions are stable across k = 0, 1, 2 for all benchmark circuits and both architectures.","section":"Section 6.1, Table 5"}],"minor_comments":[{"comment":"Both equations are labeled with n^b_var,tbolsq2; the second should be n^w_var,tbolsq2 for the worst case.","section":"Section 5, Eqs. (18)-(19)"},{"comment":"Algorithm 2 uses the variable S in the expansion loop, but S is not defined in that algorithm; it should likely refer to the current region Pr or the growing set Pf. Also, the loop iterates over the fixed edge set Er, so it is unclear how multi-hop expansion is actually implemented.","section":"Algorithm 2"},{"comment":"The notation is inconsistent: Eq. (6) uses ω but the surrounding text uses w for the same weight parameter. Please unify the notation.","section":"Section 4.2, Eq. (6)"},{"comment":"The definitions of d_min and d^b_min/d^w_min are never used in the analysis; either use them or remove them to avoid confusion.","section":"Table 4"},{"comment":"There is a typo in the heading 'Sovler-based qubit mapping'; it should be 'Solver-based qubit mapping'.","section":"Section 2.2"},{"comment":"The use of '>' in the Acc-Ratio column for timeout baselines should be explained explicitly in the caption; currently the reader has to infer that those entries are lower bounds, while the text later reports exact 'up to' values from non-timeout rows.","section":"Tables 6-7"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a timely and practical problem and the speedup results are striking, but the experimental validation needs substantial strengthening before publication: a correct fidelity formula, a specified parameter setting, and a control that isolates the effect of the region-selection strategy. The incomplete quality reporting on the largest instances is the main barrier to accepting the 'ensuring solution quality' claim. I would encourage the editor to request a revision rather than a rejection, as the core complexity argument is reasonable and the issues appear fixable within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nRead HAQA. Bottom line: this is a genuine engineering contribution for solver-based qubit mapping, but the paper overclaims the scope of its quality guarantee. The core trick — use Fast Newman community detection with a fidelity-weighted reward to identify a small hardware subgraph, then hand that subgraph to the SMT/SAT solver — is a natural extension of Guo et al. [26], and the complexity analysis in Section 5 is a real step beyond that work. The reported speedups are consistent with the variable/constraint reductions: when you cut a 127-qubit graph to about nq+1 qubits, Qsynth-v2 and TB-OLSQ2 should get dramatically faster. I see no sign the acceleration numbers are fabricated. The fidelity improvement on the solvable subset is also credible, and the paper includes code, which helps.\n\nThe soft spots are real but concentrated in the evaluation section. The largest speedups in Tables 6 and 7 come from baselines that hit the 3600s timeout, and for those instances there is no reference depth, swap count, or fidelity. The fidelity tables include only 17/25, 17/25, 10/25, and 9/25 of the benchmarks. The paper's claim that HAQA \"ensures solution quality\" is therefore unverified precisely in the regime where it is most useful. Also: k is tuned on the same benchmark set used for evaluation, the reward weight ω is never reported, and there is no fidelity-agnostic control (e.g., modularity-only region selection) that would let you isolate how much of the fidelity gain comes from the fidelity term. These are fixable with an honest breakdown, but they matter.\n\nMinor: the abstract reports 632.76x and 286.87x as exact ratios, while the tables mark them with '>' because they are derived from 3600s timeouts. That is an overstatement. Equations 18 and 19 have the same label, and there are typos, but these don't affect the method.\n\nIf I were refereeing, I would send this out. The acceleration story is robust and useful for practitioners; the quality-guarantee claim needs to be scaled back and re-verified with a proper control and per-instance reporting on the hard circuits. With those revisions it would be a solid systems paper.\n\nBring to reading group? Maybe, if anyone works on compilation. I'd cite it if I needed a baseline for region-pruning approaches. Verdict: conditional accept after major revision.","headline":"HAQA is a real, useful engineering contribution for solver-based qubit mapping, but its quality guarantee is only verified on the easy circuits, not the hard ones where the speedups are largest.","tokens_in":20098,"tokens_out":1635,"would_cite":true,"duration_ms":16094,"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":"Most quantum circuits never need the whole chip: pruning the coupling graph to a small high-fidelity region makes optimal qubit-mapping solvers up to 632x faster while preserving solution quality.","keywords":["qubit mapping","quantum layout synthesis","SAT/SMT solvers","community detection","fidelity-aware compilation","coupling graph pruning","Hellinger fidelity","quantum circuit optimization"],"falsifier":"Take a circuit and a device where the only high-fidelity route between two frequently interacting logical qubits runs through qubits outside the $k=1$ expanded community, and lower the reported fidelity of all region edges to force that situation. If HAQA's pruned solver then returns a mapping with strictly more swaps, larger depth, or lower Hellinger fidelity than the unpruned solver would find within the same time budget, the paper's claim that pruning preserves solution quality fails.","tokens_in":18903,"feed_emoji":"⚛️","tokens_out":5874,"duration_ms":55884,"temperature":0.7,"pith_summary":"The paper proposes HAQA, a pre-processing wrapper for solver-based qubit mapping. It prunes a processor's full coupling graph down to a small, highly connected, high-fidelity region centered on the logical qubits, then hands that region to an existing solver. The claim is that this pruning shrinks the solver's variable and constraint counts from hardware-scale to circuit-scale, producing hundred-fold speedups (up to 632.76x for Qsynth-v2 and 286.87x for TB-OLSQ2) without degrading circuit depth or swap count and with average-to-large gains in Hellinger fidelity. A sympathetic reader would care because solver-based mapping, though optimal, currently times out on large chips; if HAQA works, near-optimal mapping becomes practical on 100+ qubit devices.","feed_headline":"Pruning the chip graph makes qubit-mapping solvers up to 632x faster","feed_subtitle":"Restricting search to a small high-fidelity region preserves depth and swaps and often raises output fidelity.","key_machinery":"The load-bearing object is the final mapping graph $C_f = (P_f, E_f)$ chosen by two steps: Recursive Community Fusion, an agglomerative merging of coupling-graph nodes scored by $F = Q + \\omega E$, where $Q$ is modularity and $E$ is the average two-qubit gate fidelity of the merged community, and Community Expansion, which adds $k$ rings of adjacent physical qubits to supply ancillas for swaps. This graph replaces the whole chip in the solver call. Its role is to convert the solver's complexity dependence on chip size $n_P, n_E$ into a dependence on circuit size $n_q$ and maximum degree $d_{\\max}$; equations (26)-(29) express the pruned variable, clause, and constraint counts in terms of qubit and edge pruning ratios, and this substitution is the mechanism behind the claimed polynomial acceleration.","core_discovery":"HAQA's central claim is that global optimal layout synthesis can be replaced by region-guided synthesis without losing solution quality. Recursive community fusion uses a modularity-plus-fidelity reward $F = Q + \\omega E$ to build a hierarchy of connected subgraphs; community expansion then adds one ring of neighbor qubits ($k=1$). The resulting final mapping graph has $n_P \\le n_q d_{\\max} + 1$ qubits in the worst case and $n_P = n_q + 1$ in the best case, so the solver's hardware-dependent terms drop from $O(n_P)$/$O(n_E)$ to polynomial in $n_q$. On 25 benchmark circuits run against two baseline solvers on 127- and 133-qubit devices, the wrapper reports average speedups above 57x and peak speedups of 632.76x and 286.87x, with circuit depth and swap counts essentially unchanged and Hellinger fidelity up 52.69% and 238.28% in the best cases. The paper also gives a transferable complexity framework: substituting the pruned graph's vertex and edge counts into the solvers' variable and clause formulas predicts the polynomial reduction that the runtime data exhibits.","pith_inferences":["Editorial: The $k=1$ expansion rule tunes a trade-off that likely depends on circuit structure; circuits whose interaction graph is denser than the device's local community may need a larger ring, and the paper's own Table 5 already hints that $k=2$ can hurt. A testable extension is to set $k$ per circuit from the ratio of logical-graph edges to region edges.","Editorial: Because region selection is guided by an average edge-fidelity score, the method's fidelity gains rely on the accuracy of the device's reported two-qubit error rates; if those drift, the chosen region's advantage may shrink. Re-running HAQA with shuffled or outdated fidelity maps would quantify this sensitivity.","Editorial: The complexity-transfer argument suggests a broader recipe: any solver-based optimization whose variables scale with the hardware graph can be wrapped by a topology-aware region selector. Applying the same pruning ratios to routing or gate-scheduling problems is a natural next test."],"forward_implications":["Solver-based qubit mapping, previously limited to roughly 50 two-qubit gates before timing out, can be applied to deep circuits on 100+ qubit processors.","Fidelity information enters the mapping process without changing the solver's discrete formulation, because region selection does the fidelity work before solving begins.","The acceleration is predicted by complexity analysis: variable and clause counts for Qsynth-v2 drop by up to quadratic polynomial order, and for TB-OLSQ2 by linear polynomial order.","HAQA is solver-agnostic, so wrapping other SAT or SMT mappers with the same region-pruning procedure should transfer the speedup.","Mapping quality is preserved in depth and swap count, so users do not trade optimality for speed."],"supporting_citations":[{"why":"Supplies the modularity-based community-detection procedure that HAQA adapts for recursive region fusion.","marker":"[27]"},{"why":"Shows the prior subgraph-identification idea that restricting physical qubits to the logical count can accelerate SMT-based layout synthesis.","marker":"[26]"},{"why":"Is the TB-OLSQ2 baseline whose variable and constraint formulas HAQA reduces.","marker":"[16]"},{"why":"Is the Qsynth-v2 baseline whose SAT variable and clause counts anchor the complexity analysis.","marker":"[18]"},{"why":"Defines optimal layout synthesis, the problem HAQA accelerates.","marker":"[8]"},{"why":"Establishes qubit mapping as NP-complete, motivating the pruning strategy.","marker":"[21]"},{"why":"Provides the simulator used to compute Hellinger fidelity in noisy versus ideal scenarios.","marker":"[28]"}],"fun_headline_variants":["Chip-graph pruning speeds qubit mapping 632x","Fidelity-aware region search accelerates qubit mapping","Community-based qubit mapping: 632x faster, higher fidelity","Guide qubit mapping by hardware fidelity for 632x speedup","Prune the chip graph, keep fidelity: qubit mapping 632x faster"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The central assumption is that a small region of the chip around the circuit's logical qubits, the logical count plus one layer of neighboring qubits, always contains enough high-fidelity routing paths that the optimal global solution loses nothing.","fun_headline_variants_meta":{"raw":{"variants":["Chip-graph pruning speeds qubit mapping 632x","Fidelity-aware region search accelerates qubit mapping","Community-based qubit mapping: 632x faster, higher fidelity","Guide qubit mapping by hardware fidelity for 632x speedup","Prune the chip graph, keep fidelity: qubit mapping 632x faster"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000188,"raw_usage":{"total_tokens":1379,"prompt_tokens":1042,"completion_tokens":337,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":658,"completion_tokens_details":{"reasoning_tokens":248}},"tokens_in":658,"tokens_out":337,"duration_ms":3434,"temperature":1.0,"reasoning_tokens":248,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:02:32.032511+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a circuit and a device where the only high-fidelity route between two frequently interacting logical qubits runs through qubits outside the $k=1$ expanded community, and lower the reported fidelity of all region edges to force that situation. If HAQA's pruned solver then returns a mapping with strictly more swaps, larger depth, or lower Hellinger fidelity than the unpruned solver would find within the same time budget, the paper's claim that pruning preserves solution quality fails.","supporting_citations":[{"cited_title":"Physical Review E 69(6) (2004)","cited_arxiv_id":null,"evidence_quote":"Supplies the modularity-based community-detection procedure that HAQA adapts for recursive region fusion."},{"cited_title":"https://www.ibm.com/quantum/qiskit Springer Nature 2021 LATEX template Article Title 27 Appendix A Coupling Graphs (a) IBM Eagle","cited_arxiv_id":null,"evidence_quote":"Provides the simulator used to compute Hellinger fidelity in noisy versus ideal scenarios."}],"review_version":1}