Applies to arbitrary coupling graphs, sparse ones included. It is a heuristic with no optimality guarantee, and the underlying qubit assignment problem is NP-complete (Siraichi et al., Theorem 3.1). The paper claims an exponential speedup over the best known algorithm with comparable or better benchmark results, but states no bound on inserted SWAP count. Quality and convergence degrade on large circuits, which is the problem LightSABRE was built to address.

The circuit's two-qubit interaction graph or DAG; the device coupling graph; optionally per-edge error rates and gate durations.

1. Abstract circuit → Routed circuitinsert SWAPs to satisfy the coupling graph

   SABRE turns an abstract circuit and a device coupling graph into a routed, hardware-compliant circuit by repeatedly executing every front-layer gate in $F$ whose mapped qubits $\pi(q_1),\pi(q_2)$ are adjacent, and otherwise inserting a SWAP. assumption: only SWAP insertion changes the mapping, and the coupling graph is symmetric, so a CNOT runs in either direction on a connected pair. Each candidate SWAP touching a qubit in $F$ is scored by $H=\max(decay(q_1),decay(q_2))\cdot\{\frac{1}{|F|}\sum_{g\in F} D_{\pi(g.q_1),\pi(g.q_2)} + W\cdot\frac{1}{|E|}\sum_{g\in E} D_{\pi(g.q_1),\pi(g.q_2)}\}$, where $D$ is the coupling graph's shortest-path distance, approximation: E is a fixed-size window of near-term successor gates standing in for the rest of the circuit, and $decay(q_i)=1+\delta$ grows whenever $q_i$ was just swapped, discouraging overlapping SWAPs. The lowest-scoring SWAP updates $\pi$; this repeats until $F$ empties, and $\pi$'s own start point is refined by alternating forward/reverse traversals, each seeding the next with its final mapping.

   approximationassumption

An initial logical-to-physical mapping and a routed circuit, costed in added SWAP count and added depth.

given  a circuit of g gates, and a coupling graph on N physical qubits
       -- arbitrary coupling graphs, sparse ones included

build the dependency DAG of the circuit
    # O(g) in the gate count

# the initial mapping, obtained bidirectionally
traverse the circuit forward, then traverse it in reverse,
    taking the final mapping of one pass as the seed for the other
# the record states the two traversals and the seeding, and does not
# state where the first pass's mapping comes from, nor how many times
# the two passes run

run the SWAP-based search --
    insert SWAPs guided by a lookahead cost function
    # the record says only that the insertion is guided by a lookahead
    # cost function: not the form of the function, not which SWAPs are
    # candidates, and not how the search walks the DAG
    # at most O(N^2.5) per two-qubit gate, against O(exp(N)) for the
    # exhaustive mapping-based search it replaces: the claimed
    # exponential speedup is in search complexity
    # one heuristic evaluation is O(N)

# a decay term trades added depth against added gate count -- the
# record states that effect and no value for it

return the initial mapping and the inserted SWAPs

# a heuristic with no optimality guarantee -- the underlying qubit
# assignment problem is NP-complete (Siraichi et al., Theorem 3.1)
# no bound on the inserted SWAP count is stated

# quality and convergence degrade on large circuits, which is the
# problem LightSABRE was built to address

The paper's own worst-case accounting: the SWAP-based search costs at most $O(N^{2.5})$ per two-qubit gate, where $N$ is the number of physical qubits, against $O(\exp(N))$ for the exhaustive mapping-based search it replaces — the claimed exponential speedup is in search complexity. Dependency-DAG construction is $O(g)$ in the gate count and one heuristic evaluation is $O(N)$. A classical compilation cost, with no bound stated on inserted SWAP count. LightSABRE's abstract adds implementation figures: about 200 times faster in Qiskit 1.2.0 than the 0.20.1 implementation, and an average 18.9% fewer SWAPs than the original.

• LightSABRE

  A re-engineered SABRE — the Qiskit production implementation, largely rewritten in Rust — whose algorithmic changes improve both runtime and routing quality on large circuits. The release-valve mechanism it carries was already present in the Qiskit 0.20.1 baseline it is measured against.

  What would earn it a path of its own: Every recorded difference is implementation engineering, measured as benchmark constants on the same routine. The map draws constructions, not implementation pipelines; a surface for implementations — build, data structures, release policy — is what would give this a path of its own.

• SABRE reference implementation (Li, Ding and Xie)

  • Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices

    Gushu Li, Yufei Ding, Yuan Xie · 2018

  About

  The paper that introduces SABRE also builds and runs it. Its problem statement is that "most quantum algorithms cannot be directly executed on the Noisy Intermediate-Scale Quantum (NISQ) devices" because of limited coupling between physical qubits, so a compiler must supply an initial logical-to-physical mapping and the intermediate mapping transitions that let each two-qubit gate execute. The authors' stated target is the algorithm of Zulehner et al., which they call the Best Known Algorithm (BKA), stating that it "has beaten the other two solutions" among the existing approaches applicable to an arbitrary coupling graph (IBM's and Siraichi et al.'s); Zulehner et al.'s is the only one of the three actually run in the evaluation.

  Methods

  SABRE was run with the extended set size $|E|$ fixed to 20 and the weight $W$ to 0.5; the decay parameter $\delta$ increases from 0.001 and the decay function "is reset every 5 search steps or after a CNOT gate is executed". For each benchmark the algorithm was executed 5 times from a different initial mapping, each execution running 3 traversals (forward-backward-forward), and the best result of the 5 attempts is reported. The reported $t_1$ is the runtime of the first traversal and $t_{op}$ the runtime of all 3. The baseline was not reimplemented: Zulehner et al.'s published source code was downloaded, "only the embedded hardware model is modified to be the same IBM 20-qubit chip model", then recompiled with full optimization and executed on the same server. A separate sweep of $\delta$ produced the depth-versus-gate-count trade-off curves of Fig. 8, which the paper reports "for 9 benchmarks".

  Data

  26 benchmark circuits, drawn from two earlier papers — "The benchmarks are selected from previous work [12], [33]", Siraichi et al. and Zulehner et al. — in the four groups Table II's footnote names: small quantum arithmetic, quantum simulation (each of its three members an Ising model), quantum Fourier transform, and large quantum arithmetic. Their provenance is named: "quantum programs from IBM's QISKit, some functions from RevLib, and some algorithms compiled from Quipper and ScaffCC". They span 4 to 20 logical qubits and 21 to 34,881 original gates.

  Code

  The artefact is named SABRE and, on the authors' own statement, "is implemented in pure Python without any parallelization or C/C++ accelerated library".

  Results

  No circuit was executed on a quantum device: the target is a hardware model, "the coupling graph from IBM's latest Q 20 Tokyo chip", with all couplings symmetric and CNOT allowed in both directions between each connected pair. Every run was on a classical server with "2 Intel Xeon E5-2680 CPUs (48 logical cores) and 378GB memory" under CentOS 7.5, Linux kernel 3.10. On the small benchmarks the additional gate count "could be significantly reduced by 91% or even fully eliminated" against BKA; on the Ising models the paper calls the optimal solution trivial, "since the ising model in quantum mechanics only considers nearby coupling energy", and reports that "SABRE can still find the optimal solution". In the paper's discussion of large-size cases the reverse-traversal initial mapping let SABRE "outperform BKA with the updated initial mapping and reduce the number of additional gates by 10% on average". The scalability gap is reported as memory and wall time on the same machine: on qft_16 "BKA requires more than 40GB memory and 474.81 seconds runtime while SABRE only required about 200MB memory and 0.08 seconds runtime", and on ising_model_16 and qft_20 BKA "requires more than 378GB memory and can not be executed on our server" while SABRE completed both — the paper writes "SABRE can still solve it in 0.1 seconds with about 300MB memory", against Table II's $t_{op}$ of 0.01 s and 0.102 s for the two. Sweeping $\delta$ gave "about 8% variation in generated circuit depth by varying the number of gates". The runtime comparison carries the authors' own caveat, that BKA "is written in C++ and compiled with GCC O3 optimization, while SABRE is implemented in pure Python", and that "the intrinsic speed difference between C++ and Python can be over 100 times".