SABRE (SWAP-based bidirectional heuristic search)

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.

When it applies

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.

Requires

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

Example

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

Cost, as the source states it

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.

Implementations

• SABRE reference implementation (Li, Ding and Xie)

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

  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.

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

  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.

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

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

What it needs

Nothing below this — it bottoms out here.

Other ways to fill the same slot

Different approaches

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

Narrower versions of this one

• LightSABRE a narrower version of SABRE (SWAP-based bidirectional heuristic search)

  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.

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

• Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices↗Gushu Li, Yufei Ding, Yuan Xie · 2018theory yes · simulation yes · hardware no
• Qubit allocation↗Siraichi, Santos, Collange, Pereira · 2018nobody has read this paper for what it reports
• LightSABRE: A Lightweight and Enhanced SABRE Algorithm↗Henry Zou, Matthew Treinish, Kevin Hartman, Alexander Ivrii, Jake Lishman · 2024theory ? · simulation yes · hardware no