Improving and benchmarking NISQ qubit routers

Adrian Auer; In\'es de Vega; Vicente Pina-Canelles

REVIEW 3 major objections 5 minor 3 cited by

Improving and benchmarking NISQ qubit routers

T0 review · 3 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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…

desk verdict Useful router benchmark with a real empirical crossover, but the asymptotic depth separation that justifies extrapolating beyond N=200 is not derived. read the letter →

arxiv 2502.03908 v1 pith:U6SKDQ3U submitted 2025-02-06 quant-ph

Vicente Pina-Canelles , Adrian Auer , Inés de Vega This is my paper · ORCID

classification quant-ph

keywords qubitroutingSWAPinsertioncircuitdepthfidelitySABREheuristicNISQdevicesrandomquantumcircuitslatticeconnectivity

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Dear Colleague,

Quick 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.

The 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.

The 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.

That 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.

Two 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.

Who 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.

Referee Report

3 major / 5 minor

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.

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 (3)

[Section III B 1 a] 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 III B 1 b] 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 IV C, Eq. (18)] 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.

minor comments (5)

[Section II] Typo: 'lookeahead+decay' should be 'lookahead+decay'.
[Section IV B 2] Duplicate word: 'For the LC method and and lookahead SABRE heuristics' should read 'and the lookahead'.
[Section IV C] 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 III C, Eq. (12)] 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).
[Appendix D] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the analytical scalings are structural models checked numerically, and no fitted parameter or self-citation forces the central claim.

full rationale

The paper's derivation chain is self-contained. The SWAP-count scaling in Eq. (6) follows from a direct average of shortest path lengths, and the depth scalings in Eqs. (8) and (10) rest on an explicitly stated balanced-binary-tree model for basic SABRE and an asserted loss of that structure for lookahead. These are heuristic modeling assumptions, not definitions of the target conclusion; they are then compared to numerical data with fits that have free constants (e.g., Eq. (15) with parameters A and C, Eq. (16) with parameter A). The fits do not preset the qualitative log-vs-poly separation, because the exponents and the crossover emerge from fitting independent numerical data rather than being imposed by construction. The fidelity results in Fig. 4 are computed directly from Eq. (11) using measured S and D values, not from a fitted curve. The crossover analysis in Section IV C uses fits only to interpolate the crossover location from the same fidelity data, which is interpolation rather than a circular derivation of the main claim. The paper cites SABRE [1], Qiskit [6], and other external routers, but there are no self-citations carrying a load-bearing uniqueness argument. The weakest point is that the binary-tree structural model is an unverified assumption, and the lookahead O(poly(N)) scaling is asserted rather than derived; however, an unverified assumption or a weakly supported claim is a correctness risk, not circularity. No specific equation reduces to its own input, and no fitted parameter is renamed as a prediction. Therefore the circularity score is 0.

Assumptions & free parameters 5 free parameters · 6 assumptions · 0 invented entities

The paper's quantitative predictions rest on fitted scaling coefficients (A, C), a simplified fidelity model, and two structural assumptions about SWAP tree formation. The headline fidelity gain also depends on the chosen hardware noise parameters. These are standard benchmark choices but should be disclosed when quoting 84%.

free parameters (5)

A, C in SWAP scaling fit for path (Eq. 15) = A: basic 0.282, basic+decay 0.282, lookahead 0.255, lookahead+decay 0.257, lexicographic 0.283, qiskit 0.334; C: -1.18…
Fit coefficients for S(N)/G = A N + C on path connectivity; used to quantify SWAP overhead and feed into fidelity estimates.
A in depth scaling fit for path (Eq. 16) = basic 0.293, basic+decay 0.276
Fitted coefficient for D_tilde/G = A log N + (1 - A log 2).
A, C in SWAP scaling fit for square (Eq. 15) = A: basic 0.549, basic+decay 0.549, lookahead 0.466, lookahead+decay 0.466, lexicographic 0.435, qiskit 0.650; C: -1.16…
Fit coefficients for S(N)/G = A sqrt(N) + C on square connectivity.
A, C in depth scaling fit for square (Eq. 17) = basic: A=1.22, C=0.152; basic+decay: A=1.15, C=0.156
Fitted coefficients for D_tilde/G = A log(N)/sqrt(N) + C.
A, B, C, D in crossover fidelity fit (Eq. 18) = not reported in main text or appendix
Four-parameter fit of fidelity versus N used to locate the crossover qubit number; values are not given, which limits reproducibility.

assumptions (6)

domain assumption Fidelity factorizes as f^G times exp(-sum t_idle/T1) (Eq. 11), with independent gate errors and Markovian relaxation only.
Chosen noise model; excludes single-qubit gate errors, T2, crosstalk and measurement errors.
domain assumption Random circuits with two-qubit gates on uniformly sampled pairs represent an average quantum circuit for benchmarking (Section III).
Justified by citations to random-circuit models, but remains a modeling choice.
ad hoc to paper Basic SABRE SWAP networks form balanced binary trees, giving log-depth per tree (Section III B 1 a).
Structural claim used to derive D_tilde/G = Theta(log N) for path and Theta(log N / sqrt N) for square; not formally proved.
ad hoc to paper Lookahead term destroys binary tree structures and yields O(poly(N)) depth (Section III B 1 b).
Asserted without a bound or derivation; underpins the asymptotic advantage of basic heuristics.
domain assumption Hardware parameters f=99.99%, t_TQG=35ns, T1=700us are representative projected NISQ values (Section IV A).
Crossover locations and headline fidelity gains depend on these values, which come from Refs [34,35].
standard math For N=2 on a path, routed depth equals original depth G, fixing the offset in Eq. (16) (Appendix D).
Boundary condition used to reduce the number of fit parameters.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Improving and benchmarking NISQ qubit routers." pith.science (2026). https://pith.science/paper/U6SKDQ3U

@misc{pith2026250203908,
  author       = {Pith},
  title        = {Pith review of: Improving and benchmarking NISQ qubit routers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/U6SKDQ3U}},
  note         = {Machine review of arXiv:2502.03908}
}

abstract

Quantum computers with a limited qubit connectivity require inserting SWAP gates for qubit routing, which increases gate execution errors and the impact of environmental noise due to an overhead in circuit depth. In this work, we benchmark various routing techniques considering random quantum circuits on one-dimensional and square lattice connectivities, employing both analytical and numerical methods. We introduce circuit fidelity as a comprehensive metric that captures the effects of SWAP and circuit depth overheads. Leveraging a novel approach based on the SABRE algorithm, we achieve up to $84\%$ higher average circuit fidelity for large devices within the NISQ range, compared to previously existing methods. Additionally, our results highlight that the optimal routing choice critically depends on the qubit count and the hardware characteristics, including gate fidelities and coherence times.

Figures

Figures reproduced from arXiv: 2502.03908 by the authors.

**Figure 2.** (a) SWAP network incurred by a single TQG. (b) SWAP network incurred by a large number of TQGs, [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Average SWAP gate count S (top) and average depth D˜ (bottom) ratios with respect to the number of gates of the original random circuits, G, over 50 random circuits, for (a) the path connectivity, where the SWAP count has been fit to a curve of the form (15) (setting d = 1) and the depth incurred by the basic SABRE heuristics has been fit to a curve of the form (16); and (b) the square connectivity, where the SWAP c… view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: Average quantum circuit execution fidelity according to Eq. ( [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]

**Figure 5.** Figure 5: Ratio of the quantum circuit execution fidelity when routing quantum circuits using the basic+decay heuristic over the previous best method at each data point, for the path and square connectivities, yielding maximum improvements in fidelity of 256% and 84% respectivel…

**Figure 7.** Figure 7: SWAP gate count (top) and depth (bottom) [PITH_FULL_IMAGE:figures/full_fig_p012_7.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Graph Reinforcement Learning for Calibration-Aware Quantum Circuit Routing
quant-ph 2026-06 conditional novelty 6.0 of 10

A calibration-aware graph RL router achieves pooled mean fidelity of 0.727 on nine MQT Bench circuits across three IBM calibration snapshots, outperforming SABRE-best20 (0.440) and target-aware SABRE (0.481).
Position: Quantum Program Generation Must Prioritize Validity Over Probabilistic Scaling
cs.LG 2026-07 conditional novelty 5.0 of 10

The paper argues that probabilistic scaling alone cannot fix the validity gap in quantum circuit generation, so quantum code assistants must build verification into generation rather than filter outputs after the fact.
A Cost-Effective Quantum Boolean-Phase SWAP Gate with Only Two CNOT Gates
quant-ph 2025-07 reject novelty 3.0 of 10

A two-CNOT swap-like gate is introduced whose transpiled version has lower gate count and depth than the standard three-CNOT SWAP, at the cost of user-selected phase distortions.

Reference graph

Works this paper leans on

53 extracted references · 38 canonical work pages · cited by 3 Pith papers

[1]

basic": the loss function contains only the “ba- sic

"basic": the loss function contains only the “ba- sic” term (2)

work page
[2]

lookahead

"lookahead": the loss function contains both the “basic” (2) and “lookahead” terms (3)

work page
[3]

critical path

"decay": the loss function contains all three terms (2)-(4). Throughout this manuscript, we refer to this heuristic as lookeahead+decay. Additionally to the heuristics for the SABRE loss func- tion previously described, we introduce in our analysis a novel heuristic that includes only the “basic” term (2) and the decay factor (4), which is referred as bas...

work page
[4]

The number of SW AP gates, S. The execution of quantum gates introduces a significant source of error in the computation, as they are subject not only to environmental noise during their implemen- tation, but also to imperfect control. These SW AP gates may need to be transpiled into other TQGs and single-qubit gates, which typically have error rates one ...

work page
[5]

The depth of a quantum circuit is a measure of how much time is required to execute it

The depth of the routed quantum circuit, ˜D, which fulfills ˜D ≥ D where D is the depth of the origi- nal circuit. The depth of a quantum circuit is a measure of how much time is required to execute it. It is related to the errors introduced by environ- mental noise on top of those accounted for by the infidelities of the gates applied

work page
[6]

opposite

The fidelity of execution, which depends on both S and ˜D. Ideally, we wish to find properties of the connectivi- ties and the routers which are predictive of the perfor- mance of routing any given quantum circuit. However, each quantum circuit has a different structure, given by its sequence of gates G. These generally result in vastly different SW AP ne...

work page
[7]

Path connectivity We use the Path connectivity as a starting point for our analysis, because there is only one possible path along its edges between any two qubits qj and qk, which allows us to study the scaling of depth in a simple way. a. Basic heuristic— We model a routed random circuit on a Path connectivity using the basic SABRE heuristics as follows:

work page
[8]

Because each layer of TQGs of a random circuit contains Θ( N ) gates [26], the front layer F also contains Θ(N ) gates

work page

Show all 53 references

[9]

A constant fraction of the gates in F act on pairs of qubits that are Θ( N ) qubits apart [26]
[10]

2a, containing Ljk − 1 SW AP gates and spanning ⌈Ljk /2⌉ circuit layers

Each SW AP path introduced for a gate between qubits qj and qk has a shape like that of Fig. 2a, containing Ljk − 1 SW AP gates and spanning ⌈Ljk /2⌉ circuit layers
[11]

smaller” paths separated by Θ(1) qubits fit into “larger

Naturally, some of the “smaller” paths separated by Θ(1) qubits fit into “larger” ones separated by Θ(N ) qubits, which gives rise to binary tree-like structures when maximally parallelized (see Fig- ures 2b and 2c). More specifically, because the paths are symmetric (see Fig....
[12]

Square connectivity a. Basic heuristic— Obtaining the scaling of depth in two-dimensional lattices may not seem so straightfor- 5 0 10 20 30 40 50 60 70S/G SWAP count and Depth (Path) 0 1 2 3 4 5 6 7 8S/G SWAP count and Depth (Square) 25 50 75 100 125 150 175 200 N 1 2 3 4 5 6...
[13]

3a, we observe that the number of SW AP gates grows linearly with N , as predicted in Eq

Path connectivity In Fig. 3a, we observe that the number of SW AP gates grows linearly with N , as predicted in Eq. (6), and con- firmed by fitting the data for each router to a curve of the form S(N )/G = AN 1/d + C , (15) where A, Care parameters of the fit, and d = 1. The d...
[14]

3b a scaling of S proportional to √ N , as predicted in Eq

Square connectivity In the case of the square connectivity, we observe in Fig. 3b a scaling of S proportional to √ N , as predicted in Eq. (6), and confirmed by fitting the data to curves of the form (15), withd = 2. Ordered from best to worst, we have the LC approach, the loo...
[15]

basic” heuristic as merely a foundation for the more complex

treated the “basic” heuristic as merely a foundation for the more complex ”lookahead+decay” heuristic, our findings demonstrate that the “basic” heuristic is, in fact, a more effective choice for larger devices within the NISQ range. This insight enables us to design a novel l...
[16]

G. Li, Y. Ding, and Y. Xie, Tackling the qubit mapping problem for nisq-era quantum devices, in Proceedings of the Twenty-Fourth International Conference on Architec- tural Support for Programming Languages and Operating Systems, ASPLOS ’19 (Association for Computing Ma- chine...

2019
[17]

G. Li, Y. Ding, and Y. Xie, Towards efficient supercon- ducting quantum processor architecture design (2019), arXiv:1911.12879 [quant-ph]

2019 arXiv
[18]

M. Y. Siraichi, V. F. d. Santos, C. Collange, and F. M. Q. Pereira, Qubit allocation, in Proceedings of the 2018 In- ternational Symposium on Code Generation and Opti- mization, CGO ’18 (Association for Computing Machin- ery, New York, NY, USA, 2018) p. 113–125

2018
[19]

Finigan, M

W. Finigan, M. Cubeddu, T. Lively, J. Flick, and P. Narang, Qubit allocation for noisy intermediate-scale quantum computers (2018), arXiv:1810.08291 [quant- ph]

2018 arXiv
[20]

Zulehner, A

A. Zulehner, A. Paler, and R. Wille, Efficient mapping of quantum circuits to the ibm qx architectures, in 2018 Design, Automation & Test in Europe Conference & Ex- hibition (DATE) (2018) pp. 1135–1138

2018
[21]

Javadi-Abhari, M

A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Na- tion, L. S. Bishop, A. W. Cross, B. R. Johnson, and J. M. Gambetta, Quantum computing with qiskit (2024), arXiv:2405.08810 [quant-ph]

2024 arXiv
[22]

Cowtan, S

A. Cowtan, S. Dilkes, R. Duncan, A. Krajenbrink, W. Simmons, and S. Sivarajah, On the Qubit Routing Problem, in 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019), Leibniz International Proceedings in Informat- ics (LIPIcs), Vol. 13...

2019
[23]

X. Zhou, Y. Feng, and S. Li, A monte carlo tree search framework for quantum circuit transformation, in Proceedings of the 39th International Conference on Computer-Aided Design , ICCAD ’20 (Association for Computing Machinery, New York, NY, USA, 2020)

2020
[24]

Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2, 79 (2018)

J. Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2, 79 (2018)

2018
[25]

Holmes, S

A. Holmes, S. Johri, G. G. Guerreschi, J. S. Clarke, and A. Y. Matsuura, Impact of qubit connectivity on quan- tum algorithm performance, Quantum Science and Tech- nology 5, 025009 (2020)

2020
[26]

McKinney, M

E. McKinney, M. Xia, C. Zhou, P. Lu, M. Hatridge, and A. K. Jones, Co-designed architectures for modular su- perconducting quantum computers, in 2023 IEEE Inter- national Symposium on High-Performance Computer Ar- chitecture (HPCA) (2023) pp. 759–772

2023
[27]

Wintersperger, H

K. Wintersperger, H. Safi, and W. Mauerer, Qpu- system co-design for quantum hpc accelerators (2022), arXiv:2208.11449 [cs.AR]

2022 arXiv
[28]

Weidenfeller, L

J. Weidenfeller, L. C. Valor, J. Gacon, C. Tornow, L. Bello, S. Woerner, and D. J. Egger, Scaling of the quantum approximate optimization algorithm on su- perconducting qubit based hardware, Quantum 6, 870 (2022)

2022
[29]

Bandic, C

M. Bandic, C. G. Almudever, and S. Feld, Interaction graph-based characterization of quantum benchmarks for improving quantum circuit mapping techniques, Quan- tum Machine Intelligence 5, 10.1007/s42484-023-00124-1 (2023)

2023 doi
[30]

S. B. Rached, C. G. Almudever, E. Alarcon, and S. Abadal, Spatio-temporal characterization of qubit 10 routing in connectivity-constrained quantum processors (2024), arXiv:2402.00469 [quant-ph]

2024 arXiv
[31]

S. Li, X. Zhou, and Y. Feng, Benchmarking quan- tum circuit transformation with qknob circuits (2024), arXiv:2301.08932 [quant-ph]

2024 arXiv
[32]

Wille, A

R. Wille, A. Lye, and R. Drechsler, Optimal swap gate insertion for nearest neighbor quantum circuits, in 2014 19th Asia and South Pacific Design Automation Confer- ence (ASP-DAC) (2014) pp. 489–494

2014
[33]

M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, Cambridge, England, 2010)

2010
[34]

A. Deb, G. W. Dueck, and R. Wille, Exploring the po- tential benefits of alternative quantum computing archi- tectures, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 40, 1825 (2021)

2021
[35]

H. Zou, M. Treinish, K. Hartman, A. Ivrii, and J. Lish- man, Lightsabre: A lightweight and enhanced sabre al- gorithm (2024), arXiv:2409.08368 [quant-ph]

2024 arXiv
[36]

Kurniawan, L

H. Kurniawan, L. Rodr ´ ıguez-Soriano, D. Cuomo, C. G. Almudever, and F. G. Herrero, On the use of calibra- tion data in error-aware compilation techniques for nisq devices (2024), arXiv:2407.21462 [quant-ph]

2024 arXiv
[37]

Escofet, A

P. Escofet, A. Gonzalvo, E. Alarc´ on, C. G. Almud´ ever, and S. Abadal, Route-forcing: Scalable quantum cir- cuit mapping for scalable quantum computing architec- tures, in 2024 IEEE International Conference on Quan- tum Computing and Engineering (QCE) , Vol. 01 (2024) pp. 909–920

2024
[38]

Note1, |F | and |E| represent the number of gates in the front layer F and extended layer F , respectively. gate.qi is the i-th qubit involved in the gate, D[q1][q2] represents the distance in the coupling graph between qubits q1, q2, and π(q) is the position of qubit q in the...
[39]

W. Hu, Y. Yang, W. Xia, J. Pi, E. Huang, X.-D. Zhang, and H. Xu, Performance of superconducting quantum computing chips under different architecture designs, Quantum Information Processing 21, 10.1007/s11128- 022-03571-0 (2022)

2022 doi
[40]

A. W. Cross, L. S. Bishop, S. Sheldon, P. D. Nation, and J. M. Gambetta, Validating quantum computers using randomized model circuits, Phys. Rev. A 100, 032328 (2019)

2019
[41]

P. Yuan, J. Allcock, and S. Zhang, Does qubit connectiv- ity impact quantum circuit complexity?, IEEE Transac- tions on Computer-Aided Design of Integrated Circuits and Systems 43, 520 (2024)

2024
[42]

A. Wack, H. Paik, A. Javadi-Abhari, P. Jurcevic, I. Faro, J. M. Gambetta, and B. R. Johnson, Quality, speed, and scale: three key attributes to measure the performance of near-term quantum computers (2021), arXiv:2110.14108 [quant-ph]

2021 arXiv
[43]

Farhi, J

E. Farhi, J. Goldstone, and S. Gutmann, A quan- tum approximate optimization algorithm (2014), arXiv:1411.4028 [quant-ph]

2014 arXiv
[44]

A. G. Fowler, S. J. Devitt, and L. C. L. Hollenberg, Imple- mentation of shor’s algorithm on a linear nearest neigh- bour qubit array, Quantum Info. Comput. 4, 237–251 (2004)

2004
[45]

Black, Dads: The on-line dictionary of algorithms and data structures (2020)

P. Black, Dads: The on-line dictionary of algorithms and data structures (2020)

2020
[46]

Arute, K

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin,...

2019
[47]

Bharti, A

K. Bharti, A. Cervera-Lierta, T. H. Kyaw, T. Haug, S. Alperin-Lea, A. Anand, M. Degroote, H. Heimonen, J. S. Kottmann, T. Menke, W.-K. Mok, S. Sim, L.-C. Kwek, and A. Aspuru-Guzik, Noisy intermediate-scale quantum algorithms, Rev. Mod. Phys.94, 015004 (2022)

2022
[48]

Sivarajah, S

S. Sivarajah, S. Dilkes, A. Cowtan, W. Simmons, A. Edg- ington, and R. Duncan, t—ket 〉: a retargetable compiler for nisq devices, Quantum Science and Technology 6, 014003 (2020)

2020
[49]

Ezratty, Where are we heading with nisq? (2023), arXiv:2305.09518 [quant-ph]

O. Ezratty, Where are we heading with nisq? (2023), arXiv:2305.09518 [quant-ph]

2023 arXiv
[50]

Ghosh, A

J. Ghosh, A. Galiautdinov, Z. Zhou, A. N. Korotkov, J. M. Martinis, and M. R. Geller, High-fidelity controlled- σZ gate for resonator-based superconducting quantum computers, Phys. Rev. A 87, 022309 (2013)

2013
[51]

Acharya, D

R. Acharya, D. A. Abanin, L. Aghababaie-Beni, I. Aleiner, T. I. Andersen, M. Ansmann, F. Arute, K. Arya, A. Asfaw, N. Astrakhantsev, J. Atalaya, R. Babbush, D. Bacon, B. Ballard, J. C. Bardin, J. Bausch, A. Bengtsson, A. Bilmes, S. Blackwell, S. Boixo, G. Bortoli, A. Bourassa,...

2024
[52]

1a) comprising N qubits

Path connectivity Assume a device with path graph connectivity P (see Fig. 1a) comprising N qubits. Then N − 1 of its pairs of qubits have distance 1, N −2 pairs of qubits have distance 2... and i pairs of qubits have distance N − i. There- fore, the sum of all shortest paths ...
[53]

(5) for calculating ⟨L⟩C, where we average the distance across all qubit pairs, considering each qubit pair only once

Square lattice Recall Eq. (5) for calculating ⟨L⟩C, where we average the distance across all qubit pairs, considering each qubit pair only once. An alternative way to do so is to consider each pair twice, and divide by 2: ⟨L⟩C(N ) = 1 N (N − 1) NX k=1 NX j=1 Ljk . (A1) Assume ...

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.

[1] [1]

basic": the loss function contains only the “ba- sic

"basic": the loss function contains only the “ba- sic” term (2)

work page

[2] [2]

lookahead

"lookahead": the loss function contains both the “basic” (2) and “lookahead” terms (3)

work page

[3] [3]

critical path

"decay": the loss function contains all three terms (2)-(4). Throughout this manuscript, we refer to this heuristic as lookeahead+decay. Additionally to the heuristics for the SABRE loss func- tion previously described, we introduce in our analysis a novel heuristic that includes only the “basic” term (2) and the decay factor (4), which is referred as bas...

work page

[4] [4]

The number of SW AP gates, S. The execution of quantum gates introduces a significant source of error in the computation, as they are subject not only to environmental noise during their implemen- tation, but also to imperfect control. These SW AP gates may need to be transpiled into other TQGs and single-qubit gates, which typically have error rates one ...

work page

[5] [5]

The depth of a quantum circuit is a measure of how much time is required to execute it

The depth of the routed quantum circuit, ˜D, which fulfills ˜D ≥ D where D is the depth of the origi- nal circuit. The depth of a quantum circuit is a measure of how much time is required to execute it. It is related to the errors introduced by environ- mental noise on top of those accounted for by the infidelities of the gates applied

work page

[6] [6]

opposite

The fidelity of execution, which depends on both S and ˜D. Ideally, we wish to find properties of the connectivi- ties and the routers which are predictive of the perfor- mance of routing any given quantum circuit. However, each quantum circuit has a different structure, given by its sequence of gates G. These generally result in vastly different SW AP ne...

work page

[7] [7]

Path connectivity We use the Path connectivity as a starting point for our analysis, because there is only one possible path along its edges between any two qubits qj and qk, which allows us to study the scaling of depth in a simple way. a. Basic heuristic— We model a routed random circuit on a Path connectivity using the basic SABRE heuristics as follows:

work page

[8] [8]

Because each layer of TQGs of a random circuit contains Θ( N ) gates [26], the front layer F also contains Θ(N ) gates

work page