{"id":"07c42f10-7665-40e1-991e-05f9d0e95731","arxiv_id":"2502.03908","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A SABRE heuristic that keeps only the basic and decay terms outperforms lookahead-based routers in fidelity for larger NISQ devices under a thermal relaxation noise model.","lead":"The authors benchmark qubit routing methods for noisy quantum computers and find that a simplified SABRE variant, basic+decay, delivers higher circuit fidelity for 40 to 200 qubits than standard lookahead-based routers. The result matters because it shows that the best routing choice depends on device size and noise, and a small compiler change can noticeably improve execution fidelity.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The Θ(log N) vs O(poly(N)) depth separation rests on an unverified balanced-binary-tree model for basic SABRE and an assertion for lookahead; without a direct test, the asymptotic crossover claim is not established.","rationale":"The Reader's weakest_assumption correctly identifies the balanced-binary-tree structure as the load-bearing element of the analytical scaling argument. I agree, and I add that the lookahead side is even less supported: Section III B 1 b contains no derivation, no fit, and no quantitative prediction beyond the qualitative label O(poly(N)), despite the numerical section reporting only 'quick linear growth' for lookahead on the path. The numerical benchmark up to N=200 is consistent with the claimed crossover and is a useful contribution, but the paper presents the scaling result as the reason the basic+decay heuristic will remain best for larger NISQ devices. If the tree model is wrong, the analytical foundation for that conclusion collapses even if the finite-size numerical advantage persists. This does not change the Reader's CONDITIONAL verdict: the paper should be accepted only after the scaling argument is either rigorously derived or directly validated, ideally with released code and data. The proposed dependency-tree height test would settle whether the balanced-binary-tree mechanism actually appears in SABRE's routed circuits, and whether lookahead genuinely destroys it.","tokens_in":15392,"tokens_out":18140,"duration_ms":188460,"concrete_test":"Re-run the benchmark, using released code or a faithful reimplementation, for N=100, 200, and 400 on the path connectivity, routing 50 random circuits with basic and lookahead SABRE; then extract from each routed circuit the Figure 2c dependency graph by connecting each TQG to the previous-layer TQG acting on the same qubits, and measure the height h(K) of each tree against its number of TQG nodes K. If h(K) is Θ(log K) for basic and Θ(poly(K)) for lookahead, the Section III B mechanism is verified; if the two heuristics produce comparable tree heights, the claimed Θ(log N) vs O(poly(N)) depth separation and the asymptotic superiority conclusion lose their analytical foundation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim hinges on Section III B's asymptotic depth separation: basic SABRE is predicted to have D/G = Θ(log N) on paths (Eq. 8) and Θ(log N/√N) on squares (Eq. 10), while lookahead is assigned O(poly(N)). The basic-side argument (III B 1 a) is not derived from the SABRE update rule: it assumes that SWAP paths 'naturally' form balanced binary trees, so a tree with Θ(N) gates has height Θ(log N), and that this structure survives the greedy loss function. The lookahead-side argument (III B 1 b) is even weaker: it asserts that including the extended layer destroys the trees, and therefore each SWAP gate 'must' contribute O(poly(N)) depth, but no mechanism or fit is given; the numerical text only reports 'quick linear growth' of D/G for lookahead on a path. The tree picture also sits uneasily with the elementary fact that a front-layer pair at distance Θ(N) requires Θ(N) sequential SWAP layers, so the log N prediction depends on an amortization by future-layer gates that is assumed, not shown. If the true exponents are closer than Θ(log N) vs O(poly(N))—say both are Θ(log N), or basic is Θ(1) and lookahead Θ(N)—the crossover in Section IV C remains numerically valid for N≤200, but the extrapolation to 'larger devices within the NISQ range' and the asymptotic rationale for the headline fidelity gains are unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper benchmarks qubit routing techniques on path and square lattice connectivities, proposes a new SABRE-based heuristic called basic+decay, and introduces circuit fidelity as a combined metric of SWAP count and depth overhead. The authors derive scaling predictions for SWAP count and depth, present numerical simulations for N from 10 to 200 qubits, and report that basic+decay yields up to 84% (square) and 256% (path) higher fidelity than the previous best method, with a crossover in the best router as a function of N and noise parameters.","tokens_in":15839,"tokens_out":2891,"duration_ms":30846,"significance":"The numerical study is substantial and useful: 50 random circuits per data point, fits with high r-squared for the SWAP-count scaling forms, and a clear, reproducible comparison of several standard routers. The proposal of basic+decay as a simple, effective heuristic is a practical contribution, and the fidelity metric sensibly combines gate errors and depth-induced decoherence. However, the central asymptotic claim—that basic SABRE has Θ(log N) depth per gate on paths while lookahead heuristics scale as O(poly(N))—rests on an unverified structural model of SWAP networks. If that model is correct, the paper's conclusions about larger NISQ devices are well supported; if not, the extrapolation beyond the simulated range is not. The work would be strengthened by direct tests of the tree-structure assumption and by fitting or deriving the lookahead depth scaling.","major_comments":[{"comment":"The Θ(log N) depth prediction for the basic heuristic is not derived from the SABRE update rule; it assumes that SWAP paths for distant qubits 'naturally' form balanced binary trees and that this structure survives the greedy loss function. This is the load-bearing assumption behind Eq. (8) and Eq. (10). The elementary observation that a single front-layer pair at distance Θ(N) requires Θ(N) sequential SWAP layers is not addressed; the argument depends on amortization by future-layer gates, which is asserted rather than shown. I ask the authors to provide a direct test of the tree model: for the routed circuits, measure the actual tree height and branching factor (or the distribution of SWAP-path lengths per layer), and show that the balanced-tree structure appears for the basic heuristic and disappears for lookahead. Without such evidence, the asymptotic separation is a conjecture.","section":"Section III B 1 a"},{"comment":"The claim that the lookahead term 'eliminates' the binary tree structures and therefore each SWAP gate 'must' introduce O(poly(N)) depth on average is asserted without a mechanism and without a fit. The numerical text (Section IV B 1) reports 'quick linear growth' for lookahead depth, but no fit parameters or r-squared are given for that growth, and 'quick linear growth' is not the same as establishing O(poly(N)) as opposed to, say, Θ(log N) with a larger constant. Since the crossover and the extrapolation to larger devices depend on the contrast between Θ(log N) and O(poly(N)), the authors should fit the lookahead-depth data to competing forms (logarithmic, power-law, linear) and report which is statistically supported over the simulated range.","section":"Section III B 1 b"},{"comment":"The crossover-fit function F(N) = A B^{C N^D} is an ad hoc four-parameter curve, and the paper does not report goodness-of-fit or cross-validation for the fits used to locate the crossover in Fig. 6. More importantly, the statement that a crossover 'is expected to happen eventually for any such noise parameters' (Section IV C) follows only if the exponential-in-depth advantage of the basic heuristics relative to lookahead persists asymptotically, which is exactly the scaling claim whose basis I question above. The numerical crossover for N ≤ 200 can stand as an empirical observation, but the asymptotic claim should be separated from it and either proven or explicitly labelled as a conjecture.","section":"Section IV C, Eq. (18)"}],"minor_comments":[{"comment":"Typo: 'lookeahead+decay' should be 'lookahead+decay'.","section":"Section II"},{"comment":"Duplicate word: 'For the LC method and and lookahead SABRE heuristics' should read 'and the lookahead'.","section":"Section IV B 2"},{"comment":"The ratio 'fidling/fTQG' in the text should be typeset with subscripts, e.g., f_idling/f_TQG, and defined once in the text rather than only implicitly via 'idling fidelity' in Fig. 6.","section":"Section IV C"},{"comment":"The notation f^{Θ(GN^{1/d})} is an abuse of the exponential notation; it should be made explicit that this is f raised to a power that scales as Θ(GN^{1/d}), and the same comment applies to Eqs. (13)-(14).","section":"Section III C, Eq. (12)"},{"comment":"The offset term (1 − A log 2) in Eq. (16) is presented as fixing D(2) = G by construction; it would be clearer to state that the fit parameter A is the only free parameter and that this constraint is an assumption about the N = 2 behavior, not a derivation.","section":"Appendix D"}],"recommendation":"major_revision","confidential_remarks":"The paper's main numerical findings are believable and the new heuristic is a reasonable practical suggestion. My concern is that the abstract and conclusions present the asymptotic scaling separation as established, whereas the analytical argument in Section III B is a plausibility argument with two unverified structural assumptions. I would be comfortable with publication after the authors either (a) provide direct measurements of the tree structure and fits for the lookahead depth scaling, or (b) substantially soften the asymptotic claims and frame the advantage as a numerical observation for the studied NISQ range. The current manuscript's central claim is defensible but needs additional support at one load-bearing point."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear Colleague,\n\nQuick take: this is a useful benchmark paper, and the central empirical finding—that a stripped-down SABRE variant (\"basic+decay\") gives higher fidelity on random circuits for N beyond a crossover around 40–60 qubits—looks real in the numerical data. The up-to-84% and 256% fidelity ratios are visible in the plotted curves, not fitted illusions. What is less solid is the analytical scaling story meant to explain why this should continue to larger NISQ devices.\n\nThe genuinely new piece is the basic+decay heuristic: SABRE's basic term plus the decay factor, without the lookahead term. It's a simple component ablation, but I don't see it in the prior literature, and using circuit fidelity (rather than SWAP count/depth alone) as the benchmark metric is a legitimate and useful move. The numerical work is reasonably careful: 50 random circuits per point, N from 10 to 200, scaling fits with high r-squared. The empirical scaling of SWAP count and depth for basic SABRE is convincing within the range studied.\n\nThe soft spot is Section III B. The Θ(log N) prediction for basic SABRE rests on an assumption that SWAP paths organize into balanced binary trees, so each tree contributes logarithmic depth. That is asserted, not derived from SABRE's greedy update rule, and it sits awkwardly with the obvious fact that a front-layer gate between qubits at distance Θ(N) requires Θ(N) sequential SWAP layers unless amortized by future gates—which is exactly what the tree assumption is supposed to provide, but no mechanism is shown. The lookahead side is weaker still: the paper asserts that including the lookahead term \"destroys\" the trees and therefore each SWAP contributes O(poly(N)) depth, but gives no mechanism and no fit. The numerical data show lookahead depth growing roughly linearly on a path, which is consistent with O(poly(N)) but is never fitted or bounded. So the asymptotic separation between Θ(log N) and O(poly(N)) is not established.\n\nThat matters because the conclusion that basic+decay is \"a more effective choice for larger devices\" extrapolates beyond the N≤200 data. Within the studied range the crossover is directly visible and the recommendation is plausible. But the theoretical rationale for extrapolation is unsupported.\n\nTwo smaller issues: no code or data are released, and the fidelity model is simplified (constant gate fidelity, single T1, no error bars on fidelity). Both are fixable. The citation pattern looks fair; the main prior work (SABRE, Lightsaber) is acknowledged.\n\nWho should read this: anyone working on NISQ compilation or routing benchmarks. It deserves a serious referee, but the referee should push for a rigorous treatment of the scaling argument or a reframing that drops the asymptotic claim and sticks to the numerical range. I'd be happy to engage with a revised version.","headline":"Useful router benchmark with a real empirical crossover, but the asymptotic depth separation that justifies extrapolating beyond N=200 is not derived.","tokens_in":16293,"tokens_out":2544,"would_cite":true,"duration_ms":24608,"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":"The paper argues that removing the lookahead term from SABRE's loss function, keeping the decay factor, raises circuit fidelity by up to 84% on square lattices and 256% on paths, because basic routing keeps depth logarithmic while…","keywords":["qubit routing","SWAP insertion","circuit depth","circuit fidelity","SABRE heuristic","NISQ devices","random quantum circuits","lattice connectivity"],"falsifier":"Route random circuits with $G=10N$ on a path using basic SABRE and measure $\\tilde D/G$ at $N=100$ and $N=200$; the paper's fit predicts a difference of $A\\log 2\\approx 0.203$ between these points. If the measured increase is not close to that value, or if lookahead+decay still gives higher fidelity beyond the predicted crossover on a square lattice, the central scaling claim fails.","tokens_in":15204,"feed_emoji":"🔀","tokens_out":10888,"duration_ms":101630,"temperature":0.7,"pith_summary":"The paper is trying to establish that the right metric for choosing a qubit router on a noisy intermediate-scale quantum computer is circuit fidelity, not SWAP count or depth alone, and that under this metric the best choice is a stripped-down version of the SABRE routing heuristic. Removing the lookahead term from SABRE's loss function while keeping the decay factor yields 'basic+decay', which the authors report gives up to 84% higher average execution fidelity on square-lattice connectivities and 256% on one-dimensional paths relative to the best previous method at each device size. The mechanism is a scaling difference: on a path, basic SABRE keeps routed depth per gate at $\\Theta(\\log N)$, while lookahead heuristics pay $O(\\mathrm{poly}(N))$ in depth. A sympathetic reader should care because if the claim holds, extra routing sophistication is not just unnecessary but actively harmful for larger NISQ devices, and simple greedy routing becomes the rational default.","feed_headline":"Dropping lookahead boosts qubit-router fidelity up to 84%","feed_subtitle":"A stripped SABRE variant keeps depth logarithmic and beats fancier routers on larger devices.","key_machinery":"The carrying object is the SABRE router, a greedy SWAP-insertion heuristic whose loss function has three components: a basic term measuring how much a candidate SWAP shortens distances between qubits in the current front layer, a lookahead term doing the same for the following layer, and a decay factor penalizing repeated use of the same qubit. The paper's new mechanism is the balanced binary tree that emerges when only the basic term guides SWAP placement: symmetric SWAP paths for distant qubits nest into trees whose height is logarithmic, making the per-SWAP depth contribution $\\Theta(\\log N/N)$; combined with $\\Theta(N)$ SWAPs on a path and $\\Theta(\\sqrt{N})$ on a square, the routed depth per gate becomes $\\Theta(\\log N)$ and $\\Theta(\\log N/\\sqrt{N})$ respectively. The lookahead term is the mechanism that destroys those trees, and the decay factor is a depth-reducing addition that preserves them. Circuit fidelity, modeled as the product of per-gate fidelity raised to the total gate count and qubit-idling thermal relaxation, is the metric that converts these depth scalings into the reported advantage.","core_discovery":"The central claim, stated on the paper's own terms, is that SABRE's basic term alone is a more effective router for random circuits on NISQ-scale devices than the full lookahead+decay heuristic that the original SABRE work treated as the mature variant. The paper introduces basic+decay, a loss function containing only the front-layer distance term and the decay penalty, and argues that the omission of lookahead is a structural advantage: without it, the SWAP paths introduced for distant gates nest into balanced binary trees whose height is logarithmic in the number of gates, so routed depth per gate scales as $\\Theta(\\log N)$ on a path and $\\Theta(\\log N/\\sqrt{N})$ on a square lattice. With lookahead, the router interleaves SWAPs that would belong to different trees, destroying the tree structure and inflating depth to $O(\\mathrm{poly}(N))$. Since circuit fidelity is dominated by decoherence during the extra depth once SWAP counts are comparable, basic+decay overtakes all other routers beyond a crossover that shifts with two-qubit gate fidelity and coherence time; for the paper's projected NISQ parameters the crossover sits near $N=40$ on a path and $N=60$ on a square lattice.","pith_inferences":["The tree-scaling argument is developed for random circuits, so structured circuits with many long-range entangling gates may not produce the same balanced trees; extending the claim to algorithms such as the quantum Fourier transform is an open question the paper does not settle.","A direct hardware experiment on a 60-100 qubit square-lattice device, comparing basic+decay with lookahead+decay on random circuits under the paper's noise parameters, would isolate whether the depth mechanism survives realistic crosstalk and calibration drift; this test is implied but not performed here.","If the tree mechanism is the reason for the advantage, router design for other lattice connectivities, such as hexagonal or heavy-hex graphs, could deliberately preserve tree structures instead of optimizing an extended-layer objective; this generalization is not tested in the paper."],"forward_implications":["For the noise parameters used in the paper, basic+decay becomes the best router beyond about 40 qubits on a path and 60 qubits on a square lattice, with the gap widening as the device grows.","The crossover point depends on hardware quality: the paper finds it can move from $N=40$ up to $N=82$ as two-qubit gate fidelity and coherence time improve, so no single router is universally best.","SWAP count alone is insufficient for router comparison: the lookahead heuristics place fewer SWAPs, yet lose in fidelity because their depth overhead dominates decoherence.","The best practical strategy according to the paper is to route each circuit with several methods and select the best result, since basic+decay wins on average but can lose by up to 24.5% on individual square-lattice circuits."],"supporting_citations":[{"why":"Defines the SABRE algorithm and its basic, lookahead, and decay loss terms, the object the paper modifies.","marker":"[1]"},{"why":"Supplies the standard implementation of the SABRE heuristics and the BasicSwap pass used as benchmark baselines.","marker":"[6]"},{"why":"Supplies the lexicographical comparison router, a baseline the new heuristic must beat, and the observation that initial mapping has a smaller effect than routing scaling.","marker":"[7]"},{"why":"Provides the prior benchmark that identifies SABRE as the best-performing router, setting the baseline for the fidelity comparison.","marker":"[16]"},{"why":"Supplies the random-circuit layer structure, $\\Theta(N)$ gates per layer, on which the depth-scaling argument is built.","marker":"[26]"},{"why":"Supplies the balanced-binary-tree height property that gives the logarithmic depth scaling.","marker":"[30]"},{"why":"Supplies the independent-error assumption used to write circuit fidelity as a product of gate fidelities and idle-time relaxation.","marker":"[31]"}],"fun_headline_variants":["No-lookahead router beats full SABRE by up to 84%","Stripped SABRE: simpler routing, 84% higher fidelity","SABRE without lookahead wins on NISQ devices","Why dropping lookahead improves qubit routing","Basic+decay router: logarithmic depth, 84% gain"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The depth advantage collapses if SWAP chains for distant qubits do not naturally stack into balanced tree shapes when lookahead is removed, because the logarithmic depth scaling is derived from those trees.","fun_headline_variants_meta":{"raw":{"variants":["No-lookahead router beats full SABRE by up to 84%","Stripped SABRE: simpler routing, 84% higher fidelity","SABRE without lookahead wins on NISQ devices","Why dropping lookahead improves qubit routing","Basic+decay router: logarithmic depth, 84% gain"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000122,"raw_usage":{"total_tokens":1091,"prompt_tokens":933,"completion_tokens":158,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":549,"completion_tokens_details":{"reasoning_tokens":65}},"tokens_in":549,"tokens_out":158,"duration_ms":2082,"temperature":1.0,"reasoning_tokens":65,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T00:15:41.656819+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Route random circuits with $G=10N$ on a path using basic SABRE and measure $\\tilde D/G$ at $N=100$ and $N=200$; the paper's fit predicts a difference of $A\\log 2\\approx 0.203$ between these points. If the measured increase is not close to that value, or if lookahead+decay still gives higher fidelity beyond the predicted crossover on a square lattice, the central scaling claim fails.","supporting_citations":[{"cited_title":"basic\": the loss function contains only the “ba- sic","cited_arxiv_id":null,"evidence_quote":"Defines the SABRE algorithm and its basic, lookahead, and decay loss terms, the object the paper modifies."},{"cited_title":"opposite","cited_arxiv_id":null,"evidence_quote":"Supplies the standard implementation of the SABRE heuristics and the BasicSwap pass used as benchmark baselines."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the lexicographical comparison router, a baseline the new heuristic must beat, and the observation that initial mapping has a smaller effect than routing scaling."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the prior benchmark that identifies SABRE as the best-performing router, setting the baseline for the fidelity comparison."},{"cited_title":"McKinney, M","cited_arxiv_id":null,"evidence_quote":"Supplies the random-circuit layer structure, $\\Theta(N)$ gates per layer, on which the depth-scaling argument is built."},{"cited_title":"Spatio-Temporal Characterization of Qubit Routing in Connectivity-Constrained Quantum Processors","cited_arxiv_id":"2402.00469","evidence_quote":"Supplies the balanced-binary-tree height property that gives the logarithmic depth scaling."}],"review_version":1}