Exact layout synthesis by mathematical programming

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

The exact synthesizer is the reference against which heuristics are measured; the approximate variant, obtained by relaxing the same formulation, is the practical one, and a commutation-aware adjustment is available for QAOA-structured circuits. The underlying qubit assignment problem is NP-complete (Siraichi et al., Theorem 3.1), so no polynomial bound is available.

Requires

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

Example

given  a circuit whose placement and routing are to be decided together

encode placement and routing jointly as a mathematical program
    over a spacetime variable encoding
# the record names the encoding and states no part of it: no variables,
# no constraints, no objective, no solver

# form 1 -- the reference, not the working tool
solve the program exactly
    # the exact synthesizer is the reference against which heuristics
    # are measured
    # reported as an exponential reduction in time and space complexity
    # relative to some leading prior optimal approaches, while searching
    # a strictly larger solution space
    # no polynomial bound is available: the underlying qubit assignment
    # problem is NP-complete (Siraichi et al., Theorem 3.1)

# form 2 -- the practical one, out of the same formulation
relax the same formulation
    -> a fast near-optimal synthesizer
    # reported to beat leading heuristics by up to 100% on additional
    # gate cost and up to 10x on fidelity
    # and for QAOA by up to 75% on depth

for QAOA-structured circuits a commutation-aware adjustment is
    available
    # the record does not state what the adjustment changes in the
    # program, nor which of the two forms it adjusts, and gives it no
    # figure of its own

return the layout -- placement and routing, decided together

Cost, as the source states it

Reported as an exponential reduction in time and space complexity relative to some leading prior optimal approaches, while searching a strictly larger solution space. The approximate variant is reported to beat leading heuristics by up to 100% on additional gate cost and up to 10x on fidelity, and for QAOA by up to 75% on depth.

Implementations

• OLSQ, the exact SMT layout synthesizer

  • Optimal Layout Synthesis for Quantum Computing

  Tan and Cong's ICCAD'20 paper says of itself "we present two synthesizers, one optimal and one approximate but nearly optimal" (Abstract); OLSQ is the optimal one. The task is layout synthesis for quantum computing (LSQC): the input is "a list of quantum gates or operations" on logical qubits together with a coupling graph $(P, E)$ of physical qubits and their connections, and the output is "the spacetime coordinates $(t_l, x_l)$ for all the input gates and the SWAP gates inserted, and a final mapping $\pi : Q \to P$ providing which physical qubit to measure for each logical qubit" (Sec. 2). The complaint against prior optimal work is that those approaches "either just focus on specific coupling graphs, or has some implicit and unnecessary constraints" (Sec. 1). The paper's own optimality claim is stated as a strictly larger search: "by relaxing the gate placement under the dependency constraints, OLSQ explores a larger solution space than other gate-by-gate [22, 26] and level-by-level [6] 'optimal' approaches, so its results are sometimes even better" (Sec. 1). The named prior exact approach it is measured against throughout Sec. 5.1 is Wille, Burgholzer and Zulehner's DAC'19 IBM QX mapper.

  OLSQ "formulates LSQC as a satisfiability modulo theories optimization problem (SMT)", and "[t]his problem is then passed to Z3 SMT solver [9] which guarantees optimal solutions" (Sec. 1). The variables are a per-timestep mapping $\pi_q^t$ of each logical qubit to a physical qubit, a time coordinate $t_l$ and a space coordinate $x_l$ for each gate, and Boolean SWAP-use indicators $\sigma_k^t$ on each coupling-graph edge (Sec. 4.2). Three objectives are built from those variables and one is chosen per run (Sec. 4.4): depth $d \triangleq \max_{0,1,\dots,L-1} t_l$, SWAP cost $c \triangleq \sum_{k=0}^{K-1}\sum_{t=0}^{T-1}\sigma_k^t$, and the log-fidelity sum of Eq. (12), whose inputs are the measurement, single-qubit and two-qubit fidelity functions $f_0$, $f_1$ and $f_2$ supplied with the problem. The objective is made additive rather than multiplicative -- "To use addition rather than multiplication in the objective, we take the log of $f_0$, $f_1$, and $f_2$" -- and then made integral: "To be compatible with other data and variables, which are all integer, we scale up every log fidelity value by 1000 and round it to the nearest integer" (Sec. 4.4). A SWAP is modelled as three CX gates, so $\log f_{SWAP} = 3\log f_2$, and it occupies a fixed number of slots, "We set $S = 3$ as default" (Sec. 4.3). The solve is a loop over a time bound: "we initially set the time coordinate upper bound $T$ to the largest length of dependency chain", and "if the model is unsatisfiable, we geometrically increase $T$ each time by $(1+\epsilon)^x$ until it is satisfiable. We set $\epsilon = 0.3$ in our experiment" (Sec. 4.6). The paper bounds its own optimality claim in the same paragraph: "This means that OLSQ is optimal up to a certain time coordinate upper bound $T$. For depth optimization, the optimality is guaranteed. However, for SWAP cost and fidelity optimization, sometimes increasing $T$ even more can lead to better results." Table 1 sizes the encoding at $O(T\cdot N + L)$ variables and $O(T\cdot N\cdot L)$ constraints, against $O(L_2\cdot N!)$ variables for Wille et al. and $O(T\cdot(N^4+I))$ for Bhattacharjee et al., where $N$ is the physical qubit count, $L$ the gate count, $L_2$ the two-qubit gate count and $I$ the number of levels of gates.

  "We selected a comprehensive set of benchmarks from various sources including [2, 11, 16, 24]" (Sec. 5) -- Amy, Maslov, Mosca and Roetteler 2013; Gokhale, Javadi-Abhari, Earnest, Shi and Chong 2020; Nam, Ross, Su, Childs and Maslov 2018; and the authors' own QUEKO benchmarks from their optimality study. What the exact synthesizer itself consumed is the nine programs behind Table 2's thirteen instances: six circuits -- or, adder, qaoa5, mod5mils_65, 4gt13_92 and 4mod5-v1_22 -- and the three QUEKO instances that Tables 2 and 3 call queko_05_0, queko_10_3 and queko_15_1, filed in the repository under iccad20/benchmark/ as 16QBT_05CYC_TFL_0.qasm, 16QBT_10CYC_TFL_3.qasm and 16QBT_15CYC_TFL_1.qasm. The same directory carries seven further circuits named *_after_heavy (tof_4, tof_5, barenco_tof_4, barenco_tof_5, mod_mult_55, vbe_adder_3, rc_adder_6), but those appear only in Table 3, under the transition-based synthesizer, and OLSQ was never run on one. The architecture side of each Table 2 instance is one of four coupling graphs: IBM QX2 (5 physical qubits, Figure 2a), a 2-by-3 grid, a 2-by-4 grid, and the 16-qubit Rigetti Aspen-4 (Figure 2c). Figure 2 also carries the two graphs the paper's other two experiments use, IBM Melbourne and a 23-qubit part of Google Sycamore. Error rates are second-hand and only partial: "We used the fidelity profile of IBM QX2, Figure 2a, and IBM Melbourne 2d, from [15]", the TriQ paper of Murali et al. (Sec. 5), and for the rest the Table 2 note states "We do not have fidelity profile of the architectures with *, so we use a uniform fidelity profile based on the average fidelity of IBM QX2", which covers every grid and Aspen-4 row in that table.

  The released artefact is olsq, a Python package at https://github.com/UCLA-VAST/OLSQ under a BSD 3-Clause licence ("Copyright (c) 2020, Daniel (Bochen) Tan"), installed with `pip install -U olsq`. Its setup.py declares version 0.0.4.1, requires networkx>=2.5 and z3-solver>=4.8.9.0, and sets python_requires>=3.6. The solver is olsq/solve.py, which imports Int, IntVector, Bool, Optimize, Implies, And, Or, If and sat from z3; the exact synthesizer is selected by the constructor's second argument, OLSQ(objective_name, "normal"), with objective_name one of "depth", "swap" or "fidelity". A device is supplied through setdevice, either constructed from properties (nqubits, connection, swap_duration, and fmeas/fsingle/ftwo for fidelity runs) or loaded by a default_-prefixed name from olsq/devices/; a program through setprogram as a QASM string, a QASM file, or the package's own IR. Deprecated Cirq and Qiskit front ends live in olsq/olsq_cirq/ and olsq/olsq_qiskit/. The paper's footnote 4 points at the same repository for the experiment material -- "We made all the benchmarks and detailed results open-source" (Sec. 5) -- and the repository holds it under iccad20/benchmark/ and iccad20/result/, the latter carrying per-instance .qasm and .txt outputs for OLSQ at each of the three objectives alongside the Wille et al. output it was compared with. The repository's README carries a Unitary Fund support badge.

  No quantum device was run. Every number is produced by a classical solver, and fidelity is computed rather than measured: "To evaluate fidelity, we inputted the result from different synthesizers to Qiskit, decomposed, and calculated the product of all gate fidelity" (Sec. 5). "The evaluations were run on an Ubuntu 16.04 server with two Intel Xeon E5-2699v3 CPUs and 128GB memory", with Python 3.8.2 and "Cirq 0.8.0, Pytket 0.5.4, Qiskit 0.18.0, and Z3-Solver 4.8.7.0"; the Wille et al. and TriQ baselines "were built with Cmake 3.13.4 and GNU Make 4.1" and linked against the Z3 library in the Z3-Solver package (Sec. 5). Table 2 reports 13 LSQC instances over IBM QX2, a 2-by-3 grid, a 2-by-4 grid and Rigetti Aspen-4, each solved three times, once per objective. The headline against the prior exact approach is "on all instances of benchmark program and architecture, OLSQ-SWAP matches the performance of Wille et al. and sometimes is even better" (Sec. 5.1); on adder over IBM QX2 that is Wille et al. at 6 added CX gates, depth 18 and fidelity 0.335 in 1 s against OLSQ-SWAP at 3, 16 and 0.407 in 40 s. The memory argument is the sharper one: on the three QUEKO instances over the 16-qubit Aspen-4 graph, "All these evaluations of Wille et al. are aborted because our server runs out of the memory limit we set (32GB). In contrast, OLSQ-SWAP reach the optimal SWAP cost (0) within a relatively short period of time" -- at depth 6, 11 and 16 in 70, 8E2 and 5E3 seconds respectively (Table 2). Figure 7 plots solver runtime against physical qubit count for 4mod5-v1_22 and adder over three devices -- IBM QX2, a 2 by 3 grid and a 2 by 4 grid, at 5, 6 and 8 qubits -- under a dashed line the note calls "an exponential fit of Wille et al.'s results": "the runtime of Wille et al. is nearly exponential. On the other hand, the runtime of OLSQ-SWAP does not show this exponential growth" (Sec. 5.1). The figure's note lists a fourth device, the 16-qubit Rigetti Aspen-4, but neither panel is ticked past 8 qubits and Table 2 has no adder or 4mod5-v1_22 row on Aspen-4: that graph carries only the three QUEKO instances, where Wille et al. produced no runtime at all. So the claim rests on three points per benchmark. Two caveats belong with those numbers. The baseline was given bidirectional edges as pairs of unidirectional ones, so "the runtime data we collect, for comparison with OLSQ, are smaller than those appeared in the original reference [26]" (Sec. 5.1). And OLSQ is not uniformly faster on the small instances: Table 2's 4mod5-v1_22 over IBM QX2 took Wille et al. 0.5 s against OLSQ-SWAP's 20 s, and or over IBM QX2 0.2 s against 5 s, even though the same table's adder over a 2-by-4 grid runs 1E3 s against 10 s the other way.

• TB-OLSQ, the transition-based approximate synthesizer

  • Optimal Layout Synthesis for Quantum Computing

  The second of the two synthesizers in the same paper, built from an observation about waste in the exact one. On the quantum adder of Figure 1 over IBM QX2, "the time upper bound is $T = 15$. However, the mapping to physical qubits changed only once at time 8. Thus, for any specific logical qubit $q$, the variables $\pi_q^t$ are the same from $t = 0$ to 7 and $t = 8$ to 14. This is a huge redundancy" (Sec. 4.7). The scaling motive is stated beside it: "the total search space for the solver is exponential to $N$ and $T$. Although a cutting edge quantum processor has only $N = 53$ [3], $T$ as determined by quantum programs can easily grow to be quite large" (Sec. 4.7). The paper positions this variant as the one that competes with heuristics rather than with exact methods, comparing it in Sec. 5.2 against t|ket⟩ and TriQ.

  The change is to coarse-grain time. "Formally, a transition is a set of parallel SWAP gates", and mapping variables are kept only between transitions instead of at every $t$ (Sec. 4.7); on the quantum adder "there are only 8 mapping variables compared to the original 60 mapping variables". The formulation edits are named exactly: "We change the $<$ in Equation 2 to $\le$, since now even if two input gates have dependency, they can still be assigned to the same gate block", then "We set $S = 1$ and remove Equation 8 and Equation 9" (Sec. 4.7). The bound loop changes with it: "The coarse-grain time upper bound $T$ is initially set to 1, so the solver will search for a solution without any transition. If the solver returns 'unsatisfiable', we will increase $T$ by 1 each time until it finds a solution that optimizes the given objective", and depth "would just be $T - 1$, since there are exactly $T - 1$ gate blocks in the resulting circuit". The same bound on optimality as OLSQ's applies, in the sentences that immediately follow: "If SWAP cost or fidelity is set as objective, TB-OLSQ will find the optimal solution that has up to $T - 1$ transitions. Just like OLSQ, there may be better solutions if $T$ is increased even more" (Sec. 4.7). Exact times are recovered afterwards -- "we can use as-soon-as-possible (ASAP) scheduling to derive all the exact time coordinates of the gates. After scheduling, the resulting format is exactly the same as that of OLSQ" (Sec. 4.7). Table 1 gives the resulting size as $O(B\cdot N + L)$ variables and $O(B\cdot N\cdot L)$ constraints, with $B$ the number of gate blocks standing in for OLSQ's $T$.

  Table 3's 22 rows are the same benchmark corpus as Table 2 extended upward in size: or, adder, qaoa5, mod5mils_65, 4gt13_92 and 4mod5-v1_22 at 3 to 5 logical qubits, the three QUEKO instances at 16, and the *_after_heavy circuits tof_4, barenco_tof_4 (7 logical qubits), tof_5, barenco_tof_5, mod_mult_55 (9), vbe_adder_3 (10) and rc_adder_6 (14). The architectures are IBM QX2, Rigetti Aspen-4 and IBM Melbourne, with the IBM QX2 and IBM Melbourne fidelity profiles taken from the TriQ paper (Sec. 5). No source is named for Aspen-4's: Table 3 repeats Table 2's note, "We do not have fidelity profile of the architectures with *, so we use a uniform fidelity profile based on the average fidelity of IBM QX2", although no Table 3 row carries an asterisk -- the asterisks are in Table 2. The two baselines are software, not published numbers: t|ket⟩ through Pytket 0.5.4, and TriQ built from its own repository at https://github.com/prakashmurali/TriQ.

  The same released package as the exact synthesizer -- olsq, Python, BSD 3-Clause, https://github.com/UCLA-VAST/OLSQ, `pip install -U olsq` -- with the transition-based mode chosen at construction. The README's own line is that the `mode` argument takes `normal` or `transition`, and that the latter "stands for TB-OLSQ in the paper, which is usually much faster with little loss of optimality." In olsq/solve.py the argument sets a single flag, self.if_transition_based, which then governs the device's swap duration and the initial depth bound. The README's headline claim for it is "TB-OLSQ can reduce SWAP count by 70% and increase fidelity by 1.30x compared to leading previous works at the time of publication." Per-instance outputs are in the repository under iccad20/result/.

  Same classical setup as the exact synthesizer: the Ubuntu 16.04 server with two Intel Xeon E5-2699v3 CPUs and 128GB memory, Python 3.8.2, Z3-Solver 4.8.7.0, and fidelity computed by decomposing the output in Qiskit 0.18.0 and multiplying gate fidelities; no quantum hardware was involved. Against the exact synthesizer: "We find that TB-OLSQ-SWAP has no observable degradation on CX cost compared to OLSQ-SWAP, neither does TB-OLSQ-Fidelity compared to OLSQ-Fidelity on fidelity. This means that our transition-based approach is almost exact; it also hugely increases efficiency, e.g. solving queko_15_1 takes the former 9E4 seconds while taking the latter 30 seconds" (Sec. 5.2) -- "the former" being OLSQ and "the latter" TB-OLSQ, which is the only reading the claimed speedup allows. That 9E4 is not reproduced by the paper's own tables: Table 2 gives queko_15_1 on Aspen-4 as 5E3 s for OLSQ-SWAP, 5E3 s for OLSQ-Depth and 1E4 s for OLSQ-Fidelity, and Table 3 carries no runtime column at all. Against the heuristics: "Compared to t|ket⟩, TB-OLSQ-SWAP often reduces the CX cost by large margins, 69.2% in geometric mean", and "Compared to TriQ, TB-OLSQ-Fidelity often increases the fidelity, even up to 10.0x on some larger programs" (Sec. 5.2), with Table 3's geometric-mean fidelity boost at 1.30x. The 10.0x row is mod_mult_55 at 9 logical qubits on IBM Melbourne: TriQ 50 added CX gates, depth 126, fidelity 7.76E-4 against TB-OLSQ-Fidelity's 24, 68 and 7.77E-3; the next largest is 3.26x on vbe_adder_3. The largest absolute CX saving is rc_adder_6 at 14 logical qubits on IBM Melbourne, 174 added CX gates and depth 186 for t|ket⟩ against 27 and 80, an 84.5% reduction, on the row where TriQ hit "timeout (24 hrs)". As a percentage it is not the largest: six rows reach a 100% reduction because TB-OLSQ-SWAP inserts no SWAP at all -- qaoa5 and 4gt13_92 on IBM QX2, all three QUEKO instances on Aspen-4, and adder on IBM Melbourne -- and those are what the abstract's "by up to 100%" counts. The paper reports where it loses as well: three Table 3 rows have a fidelity boost below 1.00x (4mod5-v1_22 on IBM QX2 and or on IBM Melbourne at 0.96x, barenco_tof_4 on IBM Melbourne at 0.98x), six rows have a CX cost reduction of 0, and the text explains that "TB-OLSQ-Fidelity optimizes fidelity with the fewest transitions possible, but the number of transitions has no direct link to fidelity, so it is possible to find solutions with higher fidelity and more transitions", and bounds the loss: "However, compared to TriQ, the fidelity loss of OLSQ in these cases remain less than 5%" (Sec. 5.2).

• QAOA-OLSQ, the commutation-aware two-pass synthesizer

  • Optimal Layout Synthesis for Quantum Computing

  The commutation-aware adjustment of TB-OLSQ, and the one the method record means by that phrase. The paper keeps its own count at two synthesizers and presents this as an improvement of the second: "In addition, we improve TB-OLSQ for QAOA programs (QAOA-OLSQ) by considering commutation" (Sec. 6). Its starting point is a failure of the other two: "If we input the QAOA program, Figure 6a, and IBM QX2 coupling graph, Figure 2a, to OLSQ or TB-OLSQ, the best result is probably just an identity mapping and the output looks the same with Figure 6a. OLSQ and TB-OLSQ cannot reduce depth because the four ZZ gates all depend on the gate before it, imposing the default dependencies" (Sec. 4.8). The cause is an assumption both share with the field: "Like many other related works, both OLSQ and TB-OLSQ assume that any commutation is performed prior to LSQC and thus will indeed add $(g_l, g_{l'})$ as a dependency, eliminating the possibility of $t_l > t_{l'}$" (Sec. 4.8). The application is named: the comparison is with "t|ket⟩, which was utilized in a leading QAOA experiment study [4]" (Sec. 1), that study being Arute et al.'s QAOA on non-planar graph problems.

  Two solver passes over the phase-separation stage of a QAOA program. First, the dependency constraints are dropped from the transition-based formulation: "in the phase separation stage, all the ZZ gates are commutable, so none of the collisions are real dependencies. Thus, we simply remove the constraints in Equation 2 in TB-OLSQ", which yields "blocks of original ZZ gates with the fewest transitions possible to make all the qubit pairs adjacent required by these ZZ gates" (Sec. 4.8). Second, that output is re-solved for depth: "we input this result to OLSQ with depth as objective and, again, remove the constraints in Equation 2. Since the gates are already mapped to valid edges on the coupling graph, OLSQ does not need to insert any new SWAP gates. Thus, we disable all the $\sigma_k^t$ variables in OLSQ for speedup" (Sec. 4.8). The mixing stage needs no layout synthesis at all, because "single-qubit gates are always executable" (Sec. 4.8).

  "We conduct evaluation with the same settings in [4]: the coupling graph is part of Google Sycamore with 23 physical qubits, as shown in Figure 2b. We generate random 3-regular graphs with node count $M$ from 10 to 22" -- even values only, since "the product of $M$ and the vertex degree must be even" -- and "for each edge $(i, j)$ in a 3-regular graph, we append a corresponding gate $ZZ(q_i, q_j)$ to the phase separation stage" (Sec. 5.3). The circuits are therefore generated, not drawn from a benchmark suite. Table 4's figures are averages over more than one graph per size -- its note reads "All data are geometrical means and have one digit precision" -- and the repository's iccad20/result/qaoa-olsq/ holds directories 10, 12, 14, 16, 18, 20 and 22 to match, with an uneven sample: three QAOA-OLSQ and three TB-OLSQ results at sizes 10, 12 and 14 (qaoaolsq_M_0 through _2, tbolsq_M_0 through _2), and ten of each at sizes 16, 18, 20 and 22.

  No separate release, and the released olsq package (https://github.com/UCLA-VAST/OLSQ, Python, BSD 3-Clause) exposes only half of the procedure. The half it does expose is the dependency hook: the setdependency method of olsq/solve.py, whose docstring works the QAOA case as its own example and ends `dependency = [] # since ZZ gates are commutable`, so removing the Equation 2 constraints is done by passing an empty list. The second pass's other step, disabling every $\sigma_k^t$ variable, has no public knob: solve.py builds the SWAP indicators unconditionally as `sigma = [[Bool("ifswap_e{}_t{}".format(i, j))`, and the constructor's `mode` argument sets only self.if_transition_based, which governs the swap duration and the initial depth bound. The package README documents the normal and transition modes but does not name QAOA-OLSQ. What the repository does carry is the experiment output, under iccad20/result/qaoa-olsq/.

  The 23-qubit Google Sycamore graph here is a compilation target, not a machine that was run: the outputs are circuits, counted in software. "The phase separation is given to t|ket⟩, TB-OLSQ, and QAOA-OLSQ for LSQC and their results are fed to Cirq for statistics on SWAP cost and depth. We consider all ZZ gates and SWAP gates to have unity depth" (Sec. 5.3), with Cirq 0.8.0 and Pytket 0.5.4 on the same Ubuntu 16.04 server (Sec. 5). Table 4's geometric means: "even without considering the commutation relations, TB-OLSQ reduces depth by 59.5% in geometric mean and reduces SWAP cost by 29.4% in geometric mean. QAOA-OLSQ further reduces both depth and SWAP cost, by 70.2% and 53.8% in geometric mean compared to t|ket⟩" (Sec. 5.3). Per size, QAOA-OLSQ's depth reduction against t|ket⟩ runs 59.3, 67.3, 68.3, 70.2, 75.5, 75.7 and 73.7% for $M = 10$ to 22, and its SWAP reduction 23.6, 46.2, 48.0, 62.6, 65.7, 68.8 and 61.8% -- both peaking at $M = 20$ and easing at the largest instance, $M = 22$, where t|ket⟩ gives depth 29.8 and 38.4 SWAPs, TB-OLSQ 10.3 and 17.8, and QAOA-OLSQ 7.8 and 14.2. The shape of the win is that QAOA-OLSQ's depth stays between 5.6 and 7.8 across the whole sweep $M = 10$ to 22 while t|ket⟩'s runs from 16 up to 30.6 at $M = 20$ and 29.8 at $M = 22$. Commutation is what buys the SWAP saving at the small end: at $M = 10$ TB-OLSQ's SWAP reduction is 0 (7.3 against t|ket⟩'s 7.3) while QAOA-OLSQ's is 23.6% (5.5).

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.

• 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

• Optimal Layout Synthesis for Quantum Computing↗Bochen Tan, Jason Cong · 2020theory yes · simulation yes · hardware no
• Qubit allocation↗Siraichi, Santos, Collange, Pereira · 2018nobody has read this paper for what it reports