LightSABRE

What it fills

• Satisfy the hardware connectivity constraint

  Place logical qubits on physical ones and schedule connectivity-repair operations — usually SWAPs — so that every two-qubit gate acts on a coupled pair. The problem combines subgraph isomorphism with token swapping.

A narrower version of SABRE (SWAP-based bidirectional heuristic search)

When it applies

Same applicability as SABRE. The claims are benchmark-relative, measured against named Qiskit versions and the benchmark set of Li et al.; they are not worst-case guarantees.

Requires

Every step this method names moves its route along, so there is nothing it needs alongside them.

Example

given  device coupling graph G on physical qubits; circuit DAG C on virtual qubits
       front layer F (currently executable gates) and lookahead extended set E
           (upcoming gates), with a distance table dist(i,j) precomputed from G
       an implementer-chosen lookahead weight k                                    (Eq. 1)

requires  a candidate swap (i,j) must have i or j as an operand of some gate in F,
    AND the hardware graph must have finite average per-qubit degree -- rings have
    degree 2, periodic grids 4, the heavy-hex lattice at most 3. Both premises are
    needed: "touches F" alone does not bound the candidate count, it is the bounded
    degree that turns it into a count the paper calls TYPICALLY proportional to |F|,
    which is the only sense in which swap selection is Theta(|F|)                (Sec. II 1)

requires  the extended set E capped to a constant size, or to gates within a constant
    two-qubit-depth window past F -- Qiskit's own implementation satisfies this, and
    it is what keeps a single swap from touching more than O(1) terms of eq (1),
    which the relative-scoring step below depends on                            (Sec. II 1)
    # typical case, not a guarantee: one swap affects at most 2 + |E| terms, and
    #   the whole extended set can be hit at once if E is filled by a star
    #   interaction graph -- the paper's own hedge is that this "typically does
    #   not apply for every candidate swap"                                     (Sec. II 1)

# --- SABRE heuristic, unchanged from Li et al. ------------------------------
H(F,E) = (1/|F|) * sum_{(i,j) in F} dist(i,j)  +  (k/|E|) * sum_{(i,j) in E} dist(i,j)
    # basic component (front layer) + lookahead component (extended set)        (Eq. 1)

# --- layout selection: try several starting layouts, keep the best -----------
for each of layout_trials initial layouts:                                      (Sec. II 3)
    # random by default, plus one seeded from the densest-connectivity subgraph
    #   of G, added automatically                                               (Sec. II 3)
    run ROUTE(layout, C) below with swap_trials fixed to 1
        # only ONE routing trial is used while scoring a layout, deliberately --
        #   minimizing swap count "does not necessarily result in a better layout
        #   being selected when using routing for layout purposes"              (Sec. II 2)
keep the layout whose trial produced the fewest swaps

# --- routing: run several stochastic trials in parallel, keep the best -------
for each of swap_trials random seeds, in parallel:                              (Sec. II 2)
    run ROUTE(layout, C) below
select the trial with fewest swap gates (or lowest depth, if depth is the chosen
    objective) as the final routed circuit
    # variance reduction over SABRE's single stochastic run; an empirical result
    #   over the benchmark set, not a worst-case guarantee. The paper credits the
    #   trials, not the new heuristic terms, with most of the quality gain       (Sec. III)

# --- ROUTE(layout, C): one trial's main loop ----------------------------------
ROUTE(layout, C):
    swaps_since_progress = 0
    while F is not empty:
        if some gate in F has both operands adjacent under layout:
            execute it, remove it from F, advance F from C's DAG
            swaps_since_progress = 0
            continue

        H0 = H(F,E)                                    # heuristic before any swap
        for each candidate swap (i,j):
            # LightSABRE's core algorithmic change: the same swap minimises
            #   H_{i<->j} and H_{i<->j} - H0 for ANY constant H0, so H0 need
            #   never be evaluated directly -- score (i,j) only by the O(1)
            #   terms of eq (1) it actually changes                             (Sec. II 1)
            score(i,j) = H_{i<->j} - H0                 # O(1) work per candidate
            # the SABRE baseline this beats, Theta(|F|^2), is itself quoted under
            #   the assumption that max |E| is at most a constant proportion of
            #   max |F|; drop that and neither figure holds                      (Sec. II 1)
            if depth heuristic enabled:
                score(i,j) += D * delta_depth(i,j) / 3
                    # D is a weight; delta_depth is the change in TWO-QUBIT gate
                    #   depth from applying (i,j) and the immediately routable
                    #   gates after it; /3 because one SWAP is three CNOTs       (Eq. 2)
                    # costs runtime: true depth impact must be tracked per
                    #   candidate, including the follow-on gates                (Sec. II 6 a)
            if critical-path heuristic enabled:
                score(i,j) += alpha ^ rank_gate
                    # alpha is a constant in (0,1); rank_gate is a gate's rank on
                    #   the critical path, rank 1 being the gate of highest depth.
                    #   Ranks come from descendant counts on the ABSTRACT circuit,
                    #   so they are computed once and never recomputed as gates
                    #   are routed                                              (Eq. 3)
                    # READ THIS BEFORE USING EQ. 3. The paper writes eq (3) as the
                    #   bare term alpha^rank_gate and never says which gate
                    #   rank_gate refers to for a given candidate (i,j) -- unlike
                    #   the depth term, it is given no per-swap binding at all.
                    #   Nor does it state a sign: with alpha in (0,1) the term is
                    #   LARGEST at rank 1, so ADDING it to a score the loop then
                    #   MINIMIZES penalises the most critical gate, the reverse of
                    #   the paper's stated aim that "gates on the critical path are
                    #   given higher priority". The usable form under a minimized
                    #   score is to SUBTRACT alpha^rank_gate; the paper as printed
                    #   adds it. Taking the printed form on faith is a sign error,
                    #   so this line is recorded as the source has it, flagged  (Sec. II 6 b)
                    # the paper also reports this component "generally produces
                    #   results similar to the basic heuristic unless the critical
                    #   path term is given significant weighting"               (Sec. II 6 b)
        apply the candidate swap with lowest score, random tie-break
        swaps_since_progress += 1

        # --- release valve: NOT a LightSABRE algorithmic contribution -- the
        #   paper states it was already present in the Qiskit 0.20.1 baseline
        #   this paper's 200x speedup is measured against; recorded here only
        #   because it is still part of the routing loop             (Abstract; Sec. III B)
        if swaps_since_progress > some heuristically chosen threshold:
            undo the swaps back to the state at the last routed gate
            g = the front-layer gate with the smallest operand distance
            find the shortest path between g's two physical qubits by Dijkstra
            apply swaps from both path ends inward until g's qubits meet
            route g; swaps_since_progress = 0
            # escapes an arbitrarily deep local minimum of eq (1) by construction;
            #   the paper calls greedily routing one gate inefficient in general,
            #   reports it is only very infrequently necessary on real circuits,
            #   and so builds it to cost nothing when it does not trigger       (Sec. II 7)

    return the routed circuit and the layout used

return  the routed circuit and initial layout from the best trial above
# NOT part of this construction: the Rust reimplementation that the paper credits
#   with most of the ~200x wall-clock speedup over Qiskit 0.20.1 changes no
#   candidate is chosen or rejected -- it is engineering, not algorithm   (Sec. I; Abstract)
# also not shown here: control-flow and disjoint-connectivity-graph handling
#   (Secs. II 4-5), which extend which circuits this loop applies to, not how
#   a swap is scored or chosen
# the "decay" heuristic Qiskit ships as LightSABRE's actual default setting is
#   inherited from the original SABRE configuration, not one of the two new
#   terms (depth, critical path) introduced above; this paper names it as a
#   setting string and never defines it                                (Sec. III, Table I)

Cost, as the source states it

Benchmark-relative rather than a bound: the Qiskit 1.2.0 implementation is approximately 200 times faster than the implementation in Qiskit 0.20.1, and gives an average 18.9% decrease in SWAP gate count against the SABRE algorithm of Li et al. across the same benchmark circuits.

Implementations

• LightSABRE in Qiskit (SabreLayout and SabreSwap)

  • LightSABRE: A Lightweight and Enhanced SABRE Algorithm

  The paper is written by IBM Quantum authors about work done inside a shipping compiler rather than in a research prototype: it "details the modifications made to the SABRE algorithm within Qiskit [2] to address runtime, quality, and other concerns relevant to an industrial-strength quantum compiler" (Sec. I). The problem statement is that SABRE, published in 2018 and "establishing itself as the state of the art for the quantum hardware and circuit sizes available at that time", had become too slow for the larger device sizes and more complex circuits that followed (Sec. I). Two further gaps are named as things the original algorithm does not cover: classical control flow, "which the original SABRE does not address" (Sec. I), and disjoint connectivity graphs, on which "the original SABRE algorithm would not function correctly" (Sec. II 4). The Abstract's charge against SABRE is narrower than either of those: that it "struggles with scalability and convergence on large circuits". Circuits with millions of gates are named in the same Abstract as what LightSABRE is built to handle, not as a stated SABRE failure. The named target is Qiskit 1.2.0, measured against the Qiskit 0.20.1 implementation and against the SABRE algorithm of Li, Ding and Xie.

  The core algorithmic change is relative scoring: the swap minimising $H_{i\leftrightarrow j}$ is the same swap that minimises $H_{i\leftrightarrow j} - H_0$ for any constant $H_0$, so each candidate is scored only by the terms of eq. (1) it changes, which for an extended set of bounded size is $O(1)$ terms; the paper states this takes the cost of choosing a best swap from $\Theta(|F|^2)$ to $\Theta(|F|)$. The second complexity rests on a condition the paper states in the same subsection and does not carry into the result: it calls the number of candidate swaps "typically proportional to" $|F|$, because "most hardware topology families have some finite average connectivity for each qubit" (Sec. II 1). On top of that: multiple layout and routing trials run in parallel under different RNG seeds with the fewest-swap (or lowest-depth) output kept, deliberately using only one routing trial while routing is being used for layout selection (Sec. II 2); one extra layout trial seeded by default from the most densely connected subgraph of the connectivity graph, plus a hook for caller-supplied starting layouts (Sec. II 3); connected-component analysis of both the coupling graph and the circuit DAG with greedy placement, so disjoint architectures route at all (Sec. II 4); recursive routing of each control-flow branch as the operation is encountered, with a SWAP epilogue appended to every branch to restore the layout in force when the operation was reached, which keeps the lookahead undisturbed (Sec. II 5); two new optional heuristic terms, depth $D\Delta\mathrm{depth}/3$ (eq. 2) and critical path $\alpha^{r_{gate}}$ (eq. 3), each with constant or set-size-scaled weighting and each independently combinable (Sec. II 6); and a release valve that backtracks to the last routed gate and greedily routes one front-layer gate along a Dijkstra shortest path (Sec. II 7). The release valve is presented as LightSABRE's own work relative to Li et al. — Sec. I lists it among LightSABRE's improvements and Sec. II 7 sits under the heading IMPROVEMENTS — but it is not new in the benchmarked version: Qiskit 0.20.1, the baseline the 200x speedup is measured against, "already introduced" it (Abstract; Sec. III B). Feeding the Sec. II 3 provision for starting layouts other than random ones, Qiskit ships separate analysis passes run before layout and routing: `VF2Layout`, which checks by subgraph isomorphism whether the circuit embeds perfectly into the connectivity map so that no routing is needed, and `SabrePreLayout`, which extends that to circuits that map "almost" perfectly. `SabrePreLayout` augments the connectivity graph with extra edges joining every pair of nodes within a distance $d$ of each other in the original graph (typically $d = 2$), solves the subgraph isomorphism problem against that augmented graph using rustworkx, and can optionally minimise the number of longer-distance edges used by solving further isomorphism problems. Its worked examples are a 19-qubit ring mapped onto a 20-qubit ring inside a heavy-hex topology with one qubit missing, and a 21-qubit ring mapped onto a 20-qubit ring with the extra qubit attached through a degree-3 vertex. The motivation given for it is an unquantified observation, with no figure, table or sweep reported behind it: "We have observed that as device connectivity maps increase in size, the quality of fully random initial layouts tends to deteriorate significantly" (Sec. II 3). The implementation was rewritten "primarily using the Rust programming language" (Abstract), with the first parts ported at Qiskit 0.22.0 according to Sec. III B — the Fig. 8 and Fig. 8a captions instead give that release as 0.22.4, and the paper reconciles the two nowhere.

  Table I runs "the same set of benchmark circuits used in Li's paper": qft_10, qft_16, rd84_142, adr4_197, radd_250, z4_268, sym6_145, misex1_241, rd73_252, cycle10_2_110, square_root_7, sqn_258, rd84_253, co14_215, sym9_193 and 9symml_195. The other sweeps use generated circuits: QFT circuits of various sizes against a 127-qubit heavy-hex backend (Figs. 1a, 1b, 4a, 4b); 500 Quantum Volume circuits "ranging from 10 qubits to 50, with original depths ranging from 10 to 25" across three coupling maps, of which the captions name heavy-hex and square (Sec. II 6 c, Figs. 5a, 5b); Bernstein-Vazirani circuits from 10 to 19998 qubits against a 142x142 directed grid (Fig. 7); one 50-qubit Quantum Volume circuit against 57-qubit heavy-hex connectivity, transpiled 100 times (Fig. 8); and, for the layout comparison of Fig. 2, a 16-qubit `EfficientSU2` circuit with circular entanglement. The paper names no target coupling map for Table I. It names none for Fig. 2 either, saying only that the panels use "coupling maps from experiments on" that example — neither the text nor the figure's artwork carries a topology label, the artwork bearing no text at all beyond the panel letters (A), (B) and (C). No download location is given for any of these circuits.

  Shipped in Qiskit itself (https://github.com/Qiskit/qiskit, Apache-2.0), not as a standalone release. The Python entry points are the `SabreLayout` transformation pass at `qiskit/transpiler/passes/layout/sabre_layout.py` and the `SabreSwap` pass at `qiskit/transpiler/passes/routing/sabre_swap.py`; both are wrappers that call into the Rust crate at `crates/accelerate/src/sabre/` (`route.rs`, `layout.rs`, `heuristic.rs`, `layer.rs`, `neighbor_table.rs`, `sabre_dag.rs`, `swap_map.rs`) through `qiskit._accelerate.sabre.sabre_layout_and_routing` and `qiskit._accelerate.sabre.sabre_routing`. The companion seeding pass is `SabrePreLayout`, an `AnalysisPass` at `qiskit/transpiler/passes/layout/sabre_pre_layout.py`, which builds the augmented coupling map in Python and delegates the isomorphism search to `VF2Layout`; `EfficientSU2` is the Qiskit circuit-library class at `qiskit/circuit/library/n_local/efficient_su2.py`, which accepts `entanglement='circular'`. All of these are present at the repository tag 1.2.0, released 2024-08-15 — the version of the Table I benchmark and the endpoint of the Fig. 8 release sweep, though not the version behind every measurement in the paper.

  Quality, Table I: "an average decrease of 18.9% across the benchmark circuits" in CNOT gates added (Sec. III and the Table I caption, whose gO column is "the CNOT gates added by original SABRE"; the Abstract states the same 18.9% as a decrease "in SWAP gate count"). That is measured against original SABRE, with LightSABRE averaged over 50 runs using Qiskit 1.2.0 while original SABRE uses a single run; against LightSABRE constrained to SABRE's own configuration the average is -17.4%. The per-circuit spread runs from -40.1% on qft_10 (54 CNOTs added by original SABRE, 32.3 +/- 2.4 by LightSABRE at default settings) to -5.4% on rd84_142 (105 against 99.3 +/- 9.6). The two configurations compared are `swap_trials=1, layout_trials=5, max_iterations=3, heuristic=decay` to match SABRE, and `swap_trials=20, layout_trials=20, max_iterations=4, heuristic=decay` as the default. The paper credits the trials rather than the new heuristic terms: "These improvements are mainly due to the use of multiple trials in the layout and routing phases" (Sec. III). Runtime: "From 0.20.1 to 1.2.0, SABRE became approximately 200 times faster" (Fig. 8a), measured on one 50-qubit Quantum Volume circuit against 57-qubit heavy-hex connectivity over 100 repetitions with 4 iterations throughout — but not at a constant trial count. The Fig. 8 caption applies the 20 layout and 20 routing trials only "for Qiskit-terra versions >= 0.23", and Sec. III B names 0.23 as the release that introduced multiple trials at all, so on the paper's own account the 0.20.1 endpoint cannot have run them; Sec. III B's body sentence omits the version restriction and reads as though the whole sweep used 20 and 20, while the caption is the qualified statement. That release sweep ran on Python 3.9.9 on an AMD Ryzen Threadripper 3970x running Linux 6.10.3. Scaling: Bernstein-Vazirani from 10 to 19998 qubits against a 142x142 directed grid with 20 layout and routing trials and 4 iterations, generated on Qiskit 1.0.2 "as bugs introduced in 1.1.0 prevented scaling this large", on Python 3.12.5 on the same Threadripper 3970x under Linux 6.10.3. Heuristic comparison on QFT against the 127-qubit heavy-hex backend: lookahead and decay give "approximately 15% fewer swaps than the basic heuristic" (Fig. 4a) but "nearly twice the circuit depth" (Fig. 4b); on the 500 Quantum Volume circuits "the heuristics provide minimal difference in swap count" (Fig. 5a). The `SabrePreLayout` seeding pass is reported only qualitatively, as the three-panel Fig. 2 on the 16-qubit EfficientSU2 example: panel (A), SABRE alone, leaves "certain pairs of qubits that are connected in the abstract circuit ... separated by significant distances in the physical circuit"; panel (B), the pass run before SABRE, gives "a better configuration where all connected nodes are at most distance-2 apart in the physical map" but is called still suboptimal, "with a qubit isolated from a pair of red qubits ... and gaps in the boxed blue qubits"; panel (C), with the additional minimisation feature enabled, "displays the optimal layout". No swap count, CNOT count, depth or runtime is given for that pass. Every number in the paper is a compile-time measurement: no circuit is reported as executed on a quantum device or on a simulator, and the 127-qubit heavy-hex, 57-qubit heavy-hex, 142x142 grid and square maps appear only as transpilation targets. A machine is named only in the Fig. 7 and Fig. 8 captions (the Threadripper 3970x above); Table I and Figs. 1, 4 and 5 name none.

What it needs

Nothing below this — it bottoms out here.

Other ways to fill the same slot

Different approaches

• SABRE (SWAP-based bidirectional heuristic search)

  Insert SWAPs guided by a lookahead cost function, and obtain a good initial mapping by traversing the circuit forward and then in reverse, so the final mapping of one pass seeds the other. A decay term trades added depth against added gate count.

• Exact layout synthesis by mathematical programming

  Encode placement and routing jointly as a mathematical program over a spacetime variable encoding and solve it exactly. Relaxing the same formulation yields a fast near-optimal synthesizer.

In the Atlas

No record in the Atlas covers this yet. The catalogue is circuits and primitives; this part of the literature is not in it.

Sources

• LightSABRE: A Lightweight and Enhanced SABRE Algorithm↗Henry Zou, Matthew Treinish, Kevin Hartman, Alexander Ivrii, Jake Lishman · 2024theory ? · simulation yes · hardware no