{"id":"e2adeb91-ab07-4d86-8a31-c87a15b8f575","arxiv_id":"2508.21718","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An exact branch-and-bound solver for generalized qubit mapping shows that the standard layering constraint raises optimal SWAP counts and circuit depth, most strongly on sparsely connected hardware graphs.","lead":"This paper presents an exact branch-and-bound algorithm for a generalized qubit mapping problem that can include or drop the standard gate-layering constraint and gate execution times, and it reports that dropping layering yields provably better optimal circuits, especially on sparsely connected hardware. A smart generalist would read it to learn how much quantum compilation quality is lost by a modeling assumption used by nearly all quantum compilers.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Admissibility of hG (Eq. 11–12) is asserted but unproved; no independent exact check is provided, so the 'proven optimal' claim is not yet validated.","rationale":"The reader's weakest_assumption identifies exactly the unproven admissibility of hG, and I agree that this is the most load-bearing concern. Without a proof or independent verification of admissibility, the paper's foundational claim of finding 'proven optimal' solutions is not established; every empirical comparison of layered vs non-layered optima inherits this risk. The other concerns (survivor bias in the 59-instance Y-graph SWAP comparison, the weaker layering mode, the missing compiler comparison) are secondary: they affect the strength or interpretation of the empirical conclusions, but the admissibility issue threatens the validity of all reported optima. I did not find a concrete counterexample to Eq. 11—the terms appear individually valid—so the concern is not a demonstrated error but a missing proof and missing external validation. This warrants keeping the CONDITIONAL verdict until the check is performed. If the independent exact solver comparison passes, the concern would be resolved and the verdict could move toward ACCEPT.","tokens_in":14362,"tokens_out":22870,"duration_ms":265522,"concrete_test":"For all 4-qubit Linear and Y instances with depth parameter 10 (300 instances per topology), run Algorithm 1 and an independent exact solver (e.g., the MILP of Nannicini et al. [14], or exhaustive best-first over the same state space) and compare objective values (depth and SWAP count) for both layered and non-layered modes. Additionally, instrument the search to record every expanded node n and verify hD(n) ≤ OPT(n) by computing OPT(n) with the independent solver for a random sample of 100 nodes per instance; if any violation is found, admissibility fails. If all comparisons match, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central 'proven optimal' claim rests on the admissibility of hD = max(hQ, hG) (Eq. 13), and for the SWAP objective hS (Eq. 14). The paper states in one sentence that H_n(i, π, j) (Eq. 11) is a lower bound on the earliest start of gate gi, but gives no formal proof. The min over paths/edges in Eq. 12 is asserted to preserve the bound, and the restriction to first-unscheduled common gates is also asserted. Since the search is best-first (Algorithm 1) with no incumbent-based pruning, a single overestimate of any H_n term can make the search pop a suboptimal goal first and return a non-optimal mapping. The terms in Eq. 11 are individually plausible (serialization of remaining gates on each qubit plus necessary SWAPs), but a formal admissibility proof is absent. Moreover, all reported 'optimal' solutions come from this same implementation; there is no cross-check against an independent exact solver (e.g., the MILP of Nannicini et al. [14]) or brute-force enumeration, so a subtle bug or an overestimate case would go undetected. This is load-bearing for both the algorithmic contribution and the layered-vs-non-layered comparison.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents an exact branch-and-bound algorithm for a generalized Qubit Mapping Problem. Search states are partial schedules of circuit gates and SWAP gates; the algorithm maintains a Pareto front over states with the same assignment and unscheduled-gate set, and expands the open node with the smallest lower bound. Three lower bounds are introduced: hQ based on remaining qubit serialization times, hG based on path/router lower bounds for individual gates, and hS based on the longest current hardware distance among unscheduled gates. The algorithm can optimize depth, SWAP count, or a weighted combination, and can enforce or relax a layered schedule structure. The experiments compare layered versus non-layered optimal solutions on random circuits over Linear, Grid, and Y hardware graphs with 4–6 qubits, reporting that relaxing layering reduces depth and SWAP counts, most strongly on the Y graph. The central claims are that the algorithm returns proven optimal solutions and that the non-layered formulation materially improves compilation quality on sparse hardware.","tokens_in":14619,"tokens_out":9996,"duration_ms":126945,"significance":"If the lower-bound claims are correct, the paper contributes a flexible exact framework for small QMP instances and gives concrete, well-defined evidence about the cost of the layered-schedule abstraction. The study is designed without fitted parameters, and the layered-versus-non-layered comparison compares two optimal solutions of well-defined model variants, so the reported gaps are not forced by construction. However, the optimality guarantee rests entirely on the admissibility of hG, which is asserted but not proved, and no independent exact solver or brute-force check is used to confirm the claimed optimal values. The significance is therefore conditional: the conceptual framework is valuable, but the paper's headline claims need a rigorous admissibility proof and external validation before they are fully supported.","major_comments":[{"comment":"The admissibility of hG is asserted but not proved. It is stated that H_n(i,π,j) in Eq. (11) is a lower bound on the earliest start of gate g_i, and that taking the minimum over paths/edges in Eq. (12) preserves this property, but no lemma or theorem is provided. Since Algorithm 1 is best-first and returns the first goal node popped, any single overestimate of an H_n term can cause a suboptimal solution to be returned. The further restriction in Eq. (12) to 'first unscheduled common gates' is also asserted without proof. Please supply a formal proof of each step, and also state and prove the conditions under which hS in Eq. (14) is admissible for the SWAP-count objective.","section":"§3.3, Definitions 4–5, Eqs. (11)–(13)"},{"comment":"All reported 'optimal' solutions come from the same implementation with no independent verification. A subtle bug or an overestimating term in hG would invalidate both the algorithmic claim and the layered-versus-non-layered comparison. I recommend cross-checking the implementation against an independent exact method, e.g. the MILP formulation of [14] for the layered mode and brute-force or SAT enumeration for small non-layered instances (at least n≤4 with small depth), and reporting per-variant convergence rates and timeouts.","section":"§4, Table 3 and overall experiments"},{"comment":"Table 3 is difficult to parse: six columns are defined but some rows appear to contain only four or five numeric entries. In particular, the Y-graph / num-SWAPs row must state clearly whether N_S=811 and N==59 or N=811 and N_S=59. If only 59 instances are used for the reported RMD=30.79%, the empirical improvement claim is based on a small and potentially nonrepresentative subset; if N_S=811, this concern is largely resolved but the table must still be unambiguous. Also clarify how RMD handles cases where the layered objective value y_L is zero.","section":"§4.2, Table 3"}],"minor_comments":[{"comment":"Typo: 'can find find proven optimal solutions' should read 'can find proven optimal solutions'.","section":"Abstract"},{"comment":"Grammar: 'The Pareto front value domain in the algorithm will must then be extended' should be 'will then be extended'.","section":"§3.4"},{"comment":"The text promises 'comparing our methods to existing compilers', but Section 4 only compares the layered and non-layered variants of Algorithm 1. Either add such comparisons or adjust the wording.","section":"§4 introduction"},{"comment":"For reproducibility, please provide the random seeds used for circuit generation or make the instance set and implementation publicly available. The paper currently states that the implementation is in Python but gives no code or data link.","section":"§4.1"},{"comment":"The parity plots omit non-converged instances; it would be helpful to report the number of instances shown in each panel (or in the caption) so that the visual comparison can be interpreted alongside Table 3.","section":"Figures 4 and 5"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope and addresses a meaningful question, but the main contribution depends on an unproved lower-bound admissibility claim and lacks independent optimality validation. Both issues appear fixable within the scope of a revision. I would be willing to review a revised version that contains a rigorous proof of admissibility for hG (and hS) and at least a small-instance verification against an independent exact solver."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Plainly: this is worth a serious referee. The core deliverable is not a new complexity result but a concrete, quantifiable answer to a question people usually skip—what does the fixed-layer assumption cost in exact qubit mapping. They build one branch-and-bound framework that can toggle layering, gate durations, and depth-vs-SWAP objective, and they show on small sparse graphs that releasing the layer constraint improves proven-optimal solutions: on the Y graph, depth improves by 6.38% RMD (815/900 solved) and SWAP count by 30.79% on the 59/811 instances where both solved. The effect is consistent in direction across topologies and objectives, which lends it credibility.\n\nThe search framework is coherent: best-first expansion with Pareto dominance pruning per state, qubit-based and gate-based lower bounds, and a clean extension to SWAP-count minimization. The bounds are individually plausible. The comparison is between two optimal solutions of well-defined model variants, not a fitted heuristic, so the empirical gap is not circular.\n\nThe load-bearing weakness is that admissibility of hG/hD is asserted, not proved. One short paragraph says H_n(i,pi,j) is a lower bound on the earliest start, but there is no theorem, no proof, and no independent exact cross-check. Since the search is best-first and prunes dominated nodes, one underestimate in any H_n term could let a suboptimal goal pop first and return a non-optimal mapping. I am not saying the bound is wrong—the terms are reasonable—but “proven optimal” should be backed by either an admissibility proof or a sanity check against a different exact solver on small instances.\n\nSecond soft spot: the headline empirical claim in the Y/SWAP row rests on 59 of 811 solved instances, so survivor bias is real. The paper does report the solved counts, which is good, but the RMD is computed only on jointly solved cases. Also, the implemented layering mode is weaker than the standard grouped QMP, so the reported cost of layering is a lower bound on the real cost. And the introduction promises a comparison with existing compilers that the results section never delivers.\n\nWho is this for? People working on exact compilation methods or benchmark studies for QMP. The main finding—that layer relaxation matters most on sparse, high-centrality graphs—is useful even if absolute numbers shift. I would send it to peer review. It needs an admissibility proof and an independent check before the optimality claim is bulletproof, but the problem is well posed and the framework is reusable.","headline":"A unified exact B&B that quantifies the cost of the layering assumption—useful, credible in direction, but the admissibility of the gate lower bound is asserted rather than proven, and the strongest empirical row rests on few solved instances.","tokens_in":15159,"tokens_out":1795,"would_cite":true,"duration_ms":21018,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"An exact branch-and-bound solver shows that dropping layering constraints can cut SWAP counts by 30% on sparse quantum hardware.","keywords":["qubit mapping","qubit routing","branch and bound","lower bounds","SWAP gates","circuit depth","layering","quantum compilation"],"falsifier":"Enumerate all feasible schedules for a small instance, such as a four-qubit linear graph with three gates, and compare the formula in Eq. (11) with the true earliest start of each unscheduled gate at each search node; if any term ever exceeds the true earliest start, the lower bound is invalid and the proven-optimal claim collapses. Alternatively, solve the same instances with an independent exact method and check for a returned solution better than the algorithm's.","tokens_in":14213,"feed_emoji":"⚛️","tokens_out":8393,"duration_ms":84186,"temperature":0.7,"pith_summary":"Quantum compilers usually group gates into layers and insert SWAPs only between layers, which restricts reordering and ignores gate durations. This paper builds an exact branch-and-bound algorithm for the Qubit Mapping Problem that can either impose or relax the layering assumption while tracking gate execution times. It uses this solver to find proven optimal solutions for small circuits on linear, grid, and Y-shaped hardware graphs, and reports that on sparsely connected hardware the optimal non-layered solutions are substantially better: relative mean deviation of 6.38% in depth and 30.79% in SWAP count on the Y graph. If the lower bounds are admissible as claimed, this provides a way to measure exactly how much standard layered compilation loses and a platform for heuristic variants.","feed_headline":"Dropping layer limits cuts SWAPs by 30% on sparse quantum chips","feed_subtitle":"An exact branch-and-bound solver quantifies how much standard layered quantum compilation loses on small circuits.","key_machinery":"Central is the search node (assignment map, unscheduled-gate set, per-qubit depth map), kept only when on the Pareto front of its state class. Expansion schedules a minimal circuit gate or a SWAP gate. The depth bound hD = max(hQ, hG) combines a per-qubit residual-time bound with a path-based bound: for each unscheduled gate, H_n(i, pi, j) estimates earliest start from hardware-path depths plus remaining gate durations and SWAP move times, minimized over paths and edge positions. For SWAP count, hS adds current SWAPs to the longest current distance minus one. Layering mode adds recursive layer indices and blocks scheduling a layer-l gate before all layer-(l-1) gates.","core_discovery":"The paper presents an exact branch-and-bound algorithm for the Qubit Mapping Problem. Each search node stores the current virtual-to-physical qubit assignment, the unscheduled gates, and each physical qubit's earliest completion time; dominated states are discarded via a Pareto front. Expansion schedules a minimal circuit gate or a SWAP gate, guided by lower bounds hQ, hG, and hS, which the authors claim are admissible, so the first complete schedule found is optimal. Running this solver with layering on and off, ignoring layers lowers optimal depth by 6.38% relative mean deviation on the Y graph (815/900 instances solved) and optimal SWAP count by 30.79% (59/811 solved), with smaller gains","pith_inferences":["The gap between layered and unlayered optima likely grows with graph centrality imbalance: star or heavy-hex topologies with one busy hub could show even larger losses than the Y graph, because routing through a hub forces SWAPs inside what would be a fixed layer.","The unproved admissibility of hG can be checked independently: brute-force enumeration of all feasible completions on the smallest instances would reveal whether any term in Eq. (11) ever exceeds the true earliest start of a gate.","The same state-space and Pareto-front machinery could be extended to weighted objectives on noisy qubits, turning the solver into an exact error-rate minimizer rather than a depth or SWAP proxy optimizer.","The lower bounds described here could be reused in an anytime A* variant for larger circuits, sacrificing the proven-optimal guarantee when aggressive pruning is applied."],"forward_implications":["On sparsely connected hardware, the layering restriction carries a measurable, provable cost: on the Y graph the gap reaches 30.79% in optimal SWAP count.","On well-connected hardware such as a grid, layering costs little (0.09% depth relative mean deviation), so the added complexity of unlayered exact compilation is not warranted there.","Optimizing for depth also tends to reduce SWAP count because SWAP gates are long, but optimizing for SWAP count does not reliably reduce circuit depth.","Because the algorithm returns proven optima only when the lower bounds are admissible, deliberately weakening those bounds turns the same search into a fast heuristic platform."],"supporting_citations":[{"why":"Supplies the layered exact QMP baseline via integer programming whose restrictions this paper relaxes and compares against.","marker":"[14]"},{"why":"Provides the closest prior branch-and-bound for time-optimal qubit mapping, which this work generalizes by avoiding a time-indexed discretization.","marker":"[19]"},{"why":"Earlier non-layered A* approach for SU(4) circuits, motivating the no-layering model and its optimality focus.","marker":"[21]"},{"why":"Proves qubit allocation NP-complete, establishing the hardness that exact search must confront.","marker":"[16]"},{"why":"Shows quantum circuit compilation is NP-hard, used to justify exact methods limited to small instances.","marker":"[3]"},{"why":"Grounds the best-first node-selection strategy and the admissibility condition for lower bounds in the search.","marker":"[8]"}],"fun_headline_variants":["Exact solver: dropping layers cuts quantum SWAPs by 30%","Layered quantum mapping loses 6% depth, 30% SWAPs","Branch-and-bound proves unlayered mapping outperforms","Quantum compilation: skip layers for 30% fewer SWAPs","Exact optimization reveals layer penalty in qubit mapping"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The guarantee of proven optimality depends on the unproved claim that every term in the path-based lower-bound formula is never larger than the true earliest time an unscheduled gate can start; if that fails, the search can prune the optimum.","fun_headline_variants_meta":{"raw":{"variants":["Exact solver: dropping layers cuts quantum SWAPs by 30%","Layered quantum mapping loses 6% depth, 30% SWAPs","Branch-and-bound proves unlayered mapping outperforms","Quantum compilation: skip layers for 30% fewer SWAPs","Exact optimization reveals layer penalty in qubit mapping"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000347,"raw_usage":{"total_tokens":1802,"prompt_tokens":876,"completion_tokens":926,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":620,"completion_tokens_details":{"reasoning_tokens":836}},"tokens_in":620,"tokens_out":926,"duration_ms":8241,"temperature":1.0,"reasoning_tokens":836,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T14:03:31.192684+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all feasible schedules for a small instance, such as a four-qubit linear graph with three gates, and compare the formula in Eq. (11) with the true earliest start of each unscheduled gate at each search node; if any term ever exceeds the true earliest start, the lower bound is invalid and the proven-optimal claim collapses. Alternatively, solve the same instances with an independent exact method and check for a returned solution better than the algorithm's.","supporting_citations":[{"cited_title":"Optimal qubit as- signment and routing via integer programming","cited_arxiv_id":null,"evidence_quote":"Supplies the layered exact QMP baseline via integer programming whose restrictions this paper relaxes and compares against."},{"cited_title":"Time- optimal qubit mapping","cited_arxiv_id":null,"evidence_quote":"Provides the closest prior branch-and-bound for time-optimal qubit mapping, which this work generalizes by avoiding a time-indexed discretization."},{"cited_title":"Compiling su (4) quantum circuits to ibm qx architectures","cited_arxiv_id":null,"evidence_quote":"Earlier non-layered A* approach for SU(4) circuits, motivating the no-layering model and its optimality focus."},{"cited_title":"Qubit allocation","cited_arxiv_id":null,"evidence_quote":"Proves qubit allocation NP-complete, establishing the hardness that exact search must confront."},{"cited_title":"On the complexity of quantum cir- cuit compilation","cited_arxiv_id":null,"evidence_quote":"Shows quantum circuit compilation is NP-hard, used to justify exact methods limited to small instances."},{"cited_title":"Generalized best-first search strategies and the optimality of A*","cited_arxiv_id":null,"evidence_quote":"Grounds the best-first node-selection strategy and the admissibility condition for lower bounds in the search."}],"review_version":1}