Qubit Mapping and Routing

Short Definition

Qubit mapping and routing transform a circuit written on abstract program qubits into a circuit whose operations are legal on a declared hardware architecture. Mapping assigns each live program qubit to a physical site. Routing changes that assignment, or realizes nonlocal interactions, using legal movement operations such as SWAPs, physical transport, bridge circuits, or teleportation-assisted transfer.

In compiler literature, program qubits are often called logical or virtual qubits. That use does not imply quantum error correction. On a fault-tolerant machine, one compiler “physical site” may itself denote an encoded patch or module. This page uses program qubit for a circuit wire and physical site for the resource selected at the mapping layer.

A complete routing task has the form

$$\begin{aligned} &\mathsf{Route} \bigl(C,\Theta,\pi_{\mathrm{in}},\mathbf c,\mathcal B\bigr) \\ &\qquad\longrightarrow \bigl(C_\Theta,\pi_{\mathrm{out}},\mathcal K\bigr). \end{aligned}$$

Here $C$ is a dependency-aware circuit, $\Theta$ is a versioned target contract, $\pi_{\mathrm{in}}$ is an optional initial assignment, $\mathbf c$ is the route cost, and $\mathcal B$ bounds compiler resources. The output $C_\Theta$ is target-legal, $\pi_{\mathrm{out}}$ records where every live program qubit finishes, and $\mathcal K$ certifies the route and its assumptions.

This page is the canonical home for initial placement, connectivity legalization, routing actions, map evolution, abstract route scheduling, final permutations, and route verification. Circuit Optimization owns algebraic circuit simplification. Gate Decomposition owns gate synthesis. The next page in this chapter owns calibration-, noise-, and crosstalk-weighted compilation; hardware and fault-tolerance pages own platform-specific transport and encoded-operation mechanisms.

The Target Is More Than a Coupling Graph

A simple fixed architecture is represented by a graph

$$G_\Theta = (V,E),$$

where vertices are physical sites and edges identify pairs that can support some native two-site interaction. This graph is useful, but edge existence alone does not establish that a requested gate is legal. A target contract also needs:

• the operation family supported on each edge or interaction zone;
• edge direction when the native operation is asymmetric;
• parameter domains, durations, and whether inverses are native;
• disabled sites and edges;
• sets of operations that may execute concurrently;
• movement, measurement, reset, and classical-control capabilities;
• time windows, zone capacities, and reconfiguration rules;
• input, output, and measurement-channel assignments;
• a target version and, when calibration is consumed, its epoch.

A general legality predicate is therefore better written as

$$\chi_\Theta \bigl( g;\, v_1,\ldots,v_k;\, t \bigr) \in \{0,1\}.$$

It asks whether operation $g$ may act on the ordered physical sites $(v_1,\ldots,v_k)$ at compiler time or schedule step $t$. A static undirected coupling graph is the special case in which $\chi_\Theta$ depends only on whether a pair is an edge.

For movable atoms, shuttled ions or spins, photonic switches, modular links, and encoded patches, the relevant architecture may be a time-dependent graph, a graph of zones and capacities, or a hypergraph of simultaneous operations. Forcing every platform into one unweighted graph can discard the constraint that dominates its route.

The Mapping Invariant

Let $Q_t$ be the set of live program qubits at step $t$. A placement is an injection

$$\pi_t:Q_t\hookrightarrow V.$$

Injectivity prevents two live program states from occupying the same physical site. The map can be partial when the device has spare sites, and its domain can change after allocation, measurement, deallocation, or reset.

If a two-qubit operation $g(q,r)$ is ready at step $t$, it is executable only when

$$\chi_\Theta \bigl( g;\, \pi_t(q),\, \pi_t(r);\, t \bigr) = 1.$$

For an undirected nearest-neighbor graph and a generic two-qubit gate, this reduces to

$$\bigl\{ \pi_t(q),\pi_t(r) \bigr\} \in E.$$

The compiler must preserve the relation between logical state and physical state throughout the route. If $P_{\pi_t}$ denotes the wire-permutation isometry induced by $\pi_t$, the invariant is schematically

$$\rho_{\mathrm{phys}}(t) = P_{\pi_t} \rho_{\mathrm{prog}}(t) P_{\pi_t}^\dagger$$

on the live data subspace, together with the declared states of spare and ancilla sites.

A SWAP changes the map

Suppose sites $u$ and $v$ are swapped. Let $s_{uv}$ exchange those two vertices. If $\pi_t$ maps program identities to their current sites, then

$$\pi_{t+1} = s_{uv}\circ\pi_t.$$

The emitted SWAP moves the quantum states; the updated map records that movement for all later operations. Forgetting either side of this statement causes a compiler error. Applying a physical SWAP but retaining the old map mislabels states. Updating the map without a physical movement is valid only when a surrounding wire-permutation equivalence explicitly absorbs that relabeling, as at initial assignment or terminal readout.

Mapping is not a Pauli frame. A Pauli frame tracks known correctable operators without applying them immediately. A placement tracks which physical subsystem carries each program state. Both are classical metadata, but their update rules and semantic obligations differ.

Separate the Subproblems

Terminology varies across papers and tools, so a route certificate should name the actual tasks performed.

Task	Input decision	Output obligation
target selection	choose usable sites and interaction resources	selected target subarchitecture
initial placement	assign live program qubits before execution	injection $\pi_0$
routing	insert movement or nonlocal-interaction realizations	legal map sequence $\pi_0,\pi_1,\ldots$
scheduling	order and parallelize legal operations	resource- and dependency-valid times
final placement	retain or restore the ending permutation	$\pi_{\mathrm{out}}$ and output decoder
calibration-aware selection	weight sites, edges, conflicts, and durations	dated target-dependent ranking

The first five tasks belong here at the graph and capability level. The final row is the canonical scope of Error-Aware Compilation. In practice, solvers often combine placement, routing, and scheduling because decisions interact. The separation is about claims and interfaces, not a demand for isolated software passes.

Initial Placement

Before inserting movement, a compiler chooses where program qubits begin. Form an interaction graph or multigraph

$$H_C = (Q,W),$$

where a weighted edge $w_{qr}$ summarizes how often, how soon, or how critically $q$ and $r$ interact. A common proxy objective is

$$J(\pi_0) = \sum_{\{q,r\}\subseteq Q} w_{qr} d_G\bigl(\pi_0(q),\pi_0(r)\bigr),$$

where $d_G$ is shortest-path distance on the architecture graph. Discounting later gates gives larger weight to interactions whose poor placement would block the circuit immediately.

This objective is useful but incomplete:

• shortest distance does not include congestion or parallel conflicts;
• an interaction that repeats can share one favorable route;
• direction correction can change edge cost;
• spare sites can be valuable staging locations;
• an excellent placement for the first layer can be poor for the full circuit;
• symmetric circuit or hardware graphs create many equivalent assignments.

If every required interaction edge of $H_C$ embeds into $G_\Theta$ under one placement, no SWAP routing may be needed for a static circuit. Finding such an embedding already contains difficult graph problems. For general circuits, the placement is only the starting state of a dynamic routing problem.

Bidirectional methods can improve initial placement by routing a circuit forward, then traversing dependencies in reverse from the resulting map and repeating. This uses information from both ends without claiming an exact optimum. Randomized tie-breaking should be accompanied by a seed and candidate budget.

Front Layers and Lookahead

At any point, the front layer $F_t$ contains pending operations whose predecessors have executed. A legal front-layer gate can be emitted. If every front-layer interaction is nonlocal, the router chooses a movement action.

For a two-qubit gate $g(q,r)$ on an undirected graph, define its adjacency deficit

$$\delta_\pi(g) = \max \left\{ 0,\, d_G\bigl(\pi(q),\pi(r)\bigr)-1 \right\}.$$

One family of heuristic scores evaluates a candidate SWAP $s$ by

$$\begin{aligned} h(s) &= \sum_{g\in F_t} \delta_{\pi_s}(g) \\ &\quad+ \lambda \sum_{g\in L_t} w_g\, \delta_{\pi_s}(g) \\ &\quad+ \mu\,\Delta D(s) + \nu\,\Delta N_{2q}(s), \end{aligned}$$

where $\pi_s=s\circ\pi_t$, $L_t$ is a lookahead set, and the last two terms estimate depth and native two-qubit overhead. A decay or congestion term can discourage repeatedly moving the same qubits and favor parallel progress.

This is a search heuristic, not a physical error model and not an admissible lower bound unless its terms are designed as such. Different lookahead windows, tie breakers, and weight choices can yield different routes. Benchmark claims must report them.

Movement and Nonlocal Interaction Primitives

Routing need not mean “insert a SWAP on every shortest-path edge.” The target contract determines the available alternatives.

SWAP routing

On a gate model with CNOT in both required orientations,

$$\begin{aligned} \operatorname{SWAP}_{uv} &= \operatorname{CNOT}_{u\to v} \operatorname{CNOT}_{v\to u} \\ &\quad{}\times \operatorname{CNOT}_{u\to v}. \end{aligned}$$

The native cost can differ when direction reversal, basis changes, or specialized exchange interactions are required. A SWAP adjacent to a useful two-qubit gate may also be synthesized jointly for lower cost. Count emitted native operations, not only abstract SWAP nodes.

Restoring the initial map is not automatically necessary. If later operations and measurements use $\pi_{\mathrm{out}}$, leaving qubits permuted can save substantial work. Restoration is required only when an interface, repeated kernel, or external consumer demands a particular output placement.

Direction reversal

Connectivity and direction are different constraints. When local Hadamards and one directed CNOT are legal,

$$\begin{aligned} \operatorname{CNOT}_{t\to c} &= (H_c\otimes H_t) \\ &\quad{}\times \operatorname{CNOT}_{c\to t} (H_c\otimes H_t). \end{aligned}$$

This reverses the gate without moving either state. A native CZ is symmetric under exchange of endpoints, while a calibrated cross-resonance-like instruction may not be. The compiler must reason from the target operation definitions, not arrow art alone.

Bridge circuits

On a path $a-b-c$, a remote CNOT from $a$ to $c$ can be implemented while restoring the unknown state on $b$. Apply, in temporal order,

$$\begin{array}{c} \operatorname{CNOT}_{a\to b}, \\ \operatorname{CNOT}_{b\to c}, \\ \operatorname{CNOT}_{a\to b}, \\ \operatorname{CNOT}_{b\to c}. \end{array}$$

For computational-basis bits, the intermediate values are

$$\begin{aligned} b_1&=b\oplus a, \\ c_1&=c\oplus b\oplus a, \\ b_2&=b_1\oplus a=b, \\ c_2&=c_1\oplus b_2=c\oplus a. \end{aligned}$$

Linearity extends the identity to arbitrary quantum states. The bridge uses four CNOTs and leaves the placement unchanged. Whether it beats a SWAP-based route depends on future interactions, direction, native synthesis, and whether the final permutation may change.

Physical transport and teleportation

Some platforms move carriers or trapping potentials rather than compile motion into logical SWAP gates. Transport still consumes time, zones, control bandwidth, and error budget, and several moves may conflict.

Teleportation-assisted routing consumes pre-established entanglement, a Bell measurement, classical communication, feedforward or a tracked correction, ancilla sites, and an acceptance policy. It can outperform unitary SWAP routing on some graphs and resource models, but “distance-independent teleportation” does not mean free or instantaneous routing. Quantum Teleportation owns the state-transfer semantics; Modular Architectures owns physical module boundaries, interfaces, and capacity. Distributed Quantum Computing owns teledata placement, cross-QPU gates, partitioning, and distributed execution, while Quantum Network Architectures owns entanglement inventory and network routing.

Worked Example: Route on a Four-Site Path

Let the physical graph be

$$v_0-v_1-v_2-v_3,$$

with initial placement

$$\begin{aligned} \pi_0(A)&=v_0, &\pi_0(B)&=v_1, \\ \pi_0(C)&=v_2, &\pi_0(D)&=v_3. \end{aligned}$$

The requested gate $g(A,D)$ is illegal because the endpoints are distance three. Apply SWAP$(v_0,v_1)$ and then SWAP$(v_1,v_2)$. The maps become

$$\begin{aligned} \pi_1 &: (A,B,C,D) \mapsto (v_1,v_0,v_2,v_3), \\ \pi_2 &: (A,B,C,D) \mapsto (v_2,v_0,v_1,v_3). \end{aligned}$$

Now $A$ and $D$ occupy adjacent sites $v_2$ and $v_3$, so the gate is legal.

The physical line is fixed while program identities move. After two SWAPs, $\pi_2(A)=v_2$ and $\pi_2(D)=v_3$, making the requested interaction legal. The final map is $(B,C,A,D)$ from left to right and need not be restored if later gates and readout use it consistently.

The route uses two abstract SWAPs, which are six CNOTs under the elementary three-CNOT decomposition. But restoring the initial placement would use two more SWAPs. If the next gate is $g(A,C)$, the un-restored map is favorable because $A$ and $C$ are already adjacent. This is why routing one gate at a time without lookahead can be expensive.

For this isolated nonlocal CNOT, a four-CNOT bridge through two intermediate edges is not directly available: the bridge identity above spans distance two, whereas $A$ and $D$ begin at distance three. A router can compare multi-bridge, movement, and partial-permutation strategies under the declared alphabet.

Lower Bounds and Hardness

Shortest-path distance gives local lower bounds. If two tokens begin at distance $d$ and only adjacent SWAPs can move them, at least $d-1$ SWAP operations involving their approach are needed before they become adjacent. If both can move in parallel on disjoint edges, the corresponding depth lower bound is

$$D_{\mathrm{move}} \geq \left\lceil \frac{d-1}{2} \right\rceil.$$

Other required gates can share those movements, so summing this bound over all interactions generally double-counts work.

For a complete target permutation $\pi_*$, define

$$\Phi(\pi) = \sum_{q} d_G\bigl(\pi(q),\pi_*(q)\bigr).$$

One adjacent SWAP changes the distances of two tokens and can reduce $\Phi$ by at most two. Therefore

$$N_{\mathrm{SWAP}} \geq \left\lceil \frac{\Phi(\pi)}{2} \right\rceil$$

for that permutation-routing problem. The bound need not be tight because tokens obstruct one another and shortest paths contend for edges.

General mapping contains subgraph embedding, token swapping, scheduling, and multiobjective search. Exact minimum-SWAP mapping is NP-complete even under restricted graph and shallow-circuit conditions. This does not make every instance hard: paths, trees, repeated interaction patterns, fixed small architectures, and bounded circuit windows can admit efficient or exact specialized methods. It does explain why production routers mix exact solvers, bounds, decomposition, and heuristics.

Routing Algorithms

No single algorithm dominates every width, topology, circuit family, and cost model.

Method	Strength	Limitation
shortest-path greedy	fast and easy to diagnose	ignores future gates and congestion
front-layer lookahead	scales to large circuits and arbitrary graphs	heuristic quality depends on scoring and ties
bidirectional traversal	improves initial placement using both circuit directions	repeated heuristic search is not proof of optimality
A*, dynamic programming, SAT, SMT	exact within modeled scope	state space grows rapidly
integer programming	joint assignment, movement, and objective constraints	practical optimality is usually limited to small instances or windows
hierarchical partitioning	exploits modules, grids, or zones	cut decisions can trap later interactions
template and block routing	reuses good routes for repeated motifs	depends on motif recognition and boundary maps
SWAP networks	predictable depth for all-pairs or structured interactions	can over-route sparse, ordered workloads
teleportation-assisted routing	can reduce depth on suitable resource graphs	requires entanglement, ancillas, measurement, and feedforward

An exact solver should report its optimality gap, timeout, and model. A heuristic should report seeds, candidate counts, lookahead, and runtime. “Best route found” and “minimum route” are different claims.

Assignment constraints in exact models

An integer formulation can use binary variables $x_{qv}^{(t)}$ indicating whether program qubit $q$ occupies site $v$ at step $t$. Basic placement constraints are

$$\begin{aligned} \sum_{v\in V} x_{qv}^{(t)} &= 1 \qquad \text{for every live }q, \\ \sum_{q\in Q_t} x_{qv}^{(t)} &\leq 1 \qquad \text{for every }v. \end{aligned}$$

Additional variables encode legal transitions, gate execution, ordering, parallel conflicts, and costs. Products such as “$q$ is at $u$ and $r$ is at $v$” must be linearized in a binary integer model. The resulting formulation is valuable for small exact instances and as a bounded-window guide, but its mathematical optimum is only as faithful as the target and objective encoded.

Structured SWAP Networks

When many pairs must interact, routing each gate independently wastes structure. On a line of $n$ sites, alternate the edge matchings

$$\begin{aligned} M_{\mathrm{even}} &= \bigl\{ (v_0,v_1),(v_2,v_3),\ldots \bigr\}, \\ M_{\mathrm{odd}} &= \bigl\{ (v_1,v_2),(v_3,v_4),\ldots \bigr\}. \end{aligned}$$

Applying $n$ alternating SWAP layers reverses token order and makes every pair adjacent exactly once as the pair crosses. A desired two-qubit operation can be performed when its pair meets, sometimes fused with the SWAP. Thus an all-pairs interaction pattern has linear routing depth on a line even though it contains $\binom n2$ pair interactions.

Generalized SWAP networks extend the idea to selected pair sets and higher-arity interactions. They are especially useful when an algorithm permits reordering of commuting terms, as in some Hamiltonian-simulation and variational circuits. Reordering must be justified by Circuit Optimization or by the algorithm’s approximation contract; routing cannot silently change noncommuting gate order.

Routing and Scheduling Interact

At one abstract time step, two-site operations can execute in parallel only when their resource sets and target exclusions are compatible. On a simple graph, a SWAP layer is a matching

$$M_t\subseteq E$$

whose edges share no vertices. Real targets can add coupler, zone, control-line, or crosstalk conflicts. A conflict graph on candidate operations turns legal parallel batches into independent sets of that graph.

A route with fewer SWAPs can have greater depth if its movements serialize on one bottleneck. A route with more SWAPs can finish sooner by using disjoint paths. Relevant cost components include

$$\begin{aligned} \mathbf c_{\mathrm{route}} = \bigl(& N_{\mathrm{move}},\, D_{\mathrm{move}},\, N_{2q}^{\mathrm{native}},\, D_{2q}^{\mathrm{native}}, \\ & D_{\mathrm{total}},\, N_{\mathrm{anc}},\, N_{\mathrm{meas}},\, \tau_{\mathrm{compile}} \bigr). \end{aligned}$$

Physical durations, error rates, crosstalk, and drift turn this into a dated hardware-aware objective. Those weights belong to Error-Aware Compilation and Control, Readout, and Calibration.

Architecture-Specific Movement

The abstract map should survive changes in movement mechanism.

Architecture model	Typical route action	Constraint that a bare graph misses
fixed sparse gate array	SWAP, bridge, direction correction	edge gate family and simultaneous coupler use
long-range collective modes	choose interacting subset or reorder chain	spectral crowding and concurrency
shuttling or transport	move carriers through channels and junctions	occupancy, collision avoidance, heating, recooling
reconfigurable tweezer array	rearrange atoms or interaction zones	path planning, loss, handoff, zone capacity
modular processor	local SWAP plus entanglement-assisted transfer	pair inventory, heralding, retries, classical latency
photonic architecture	switches, delays, fusion, feedforward	loss, timing modes, detector and switch availability
encoded logical patches	deformation, lattice surgery, teleportation	patch area, code cycles, factories, decoder timing

Hardware Overview and its platform pages own these physical mechanisms. A portable routing IR should represent movement intent and resource use without pretending that three CNOTs are the universal physical meaning of SWAP.

Outputs, Measurement, and Reuse

The final placement is part of program meaning. If terminal measurements produce physical bits $m_v$, the program output for qubit $q$ is read from

$$y_q = m_{\pi_{\mathrm{out}}(q)}$$

unless a later classical permutation has already restored program order. Returning a raw physical bit string without the map can make a correctly executed circuit appear wrong.

Mid-circuit measurement and reset permit site reuse only when the IR proves that the old quantum value is dead and the target reset establishes the required new state. Conditional branches can have different live sets and placements; reconverging control flow needs compatible maps or explicit reconciliation. Speculative reuse across a branch is unsafe if the measurement outcome remains live or the reset postcondition is weaker than assumed.

A repeated circuit kernel may require $\pi_{\mathrm{out}}=\pi_{\mathrm{in}}$ to compose cleanly. Alternatively, the compiler can alternate two kernels or specialize the next iteration to the changed map. The cheaper choice is an interface decision, not a universal rule.

Verification and Route Certificates

A route checker can be much simpler than the search algorithm. Replay the emitted artifact while maintaining the map:

1. validate that $\pi_{\mathrm{in}}$ is injective and uses enabled sites;
2. check every native operation against arity, orientation, and $\chi_\Theta$;
3. update $\pi_t$ after each SWAP, transport, teleportation, allocation, or release;
4. preserve circuit dependencies and classical conditions;
5. verify ancilla initialization and restoration;
6. derive $\pi_{\mathrm{out}}$ and the measurement-output permutation;
7. compare the routed circuit with the input semantics by translation validation where practical.

For static SWAP-based unitary routing, a symbolic wire-permutation checker can remove movement gates while updating labels and recover the original program circuit. Small instances can also be checked by full matrices. Dynamic, teleportation-assisted, and measurement-based routes require channel or instrument semantics rather than a unitary miter.

A useful certificate records:

Field	Minimum content
input	circuit hash, dependency order, gate and parameter conventions
target	site and edge set, capabilities, direction, disabled resources, version
mapping	initial map, every map-changing action, final map
route	inserted operations, schedules, branch-specific maps, output permutation
objective	native counts, depths, movement, ancillas, compiler budget and ordering
search	algorithm, lookahead, timeout, seed, candidate count, optimality gap if any
validation	route checker, semantic checker, result, residual if approximate
provenance	compiler and pass versions, target epoch, source map

Passing the route checker proves modeled legality and semantic preservation. It does not prove that stale hardware, calibration error, crosstalk, leakage, or transport failure will be negligible.

Benchmarking Routing Claims

Routing results are comparable only when they share:

• the same input circuit and pre-routing gate alphabet;
• the same target sites, edges, directions, and disabled resources;
• the same allowance for final permutations and ancillas;
• the same post-routing decomposition and cleanup;
• the same count and depth definitions;
• the same compiler timeout and hardware-aware weights;
• the same benchmark instances, parameter bindings, and random seeds.

Report both abstract and native overhead. At minimum include input and output two-qubit count, input and output depth, abstract SWAP or transport count, native decomposition, final permutation, compile time, and verification status. A shortest-path sum is a heuristic proxy, not a measured hardware success probability.

Common Mistakes

• Calling a coupling graph the complete target specification.
• Treating “logical qubit” in a mapper as proof that error correction is in use.
• Updating the placement after a SWAP but forgetting that the physical state moved, or vice versa.
• Restoring the initial placement when the output interface permits a final permutation.
• Returning measurement bits in physical-site order without the output map.
• Assuming an undirected edge supports both orientations of every gate.
• Counting one abstract SWAP as one native two-qubit gate.
• Routing each gate greedily without considering later interactions.
• Summing pairwise distance lower bounds that reuse the same movement.
• Equating fewer SWAPs with lower depth, duration, or physical error.
• Comparing routers after different optimization and decomposition passes.
• Treating teleportation as free because its gate depth is independent of graph distance.
• Reusing a measured site without proving liveness and reset postconditions.
• Claiming optimality after a heuristic reaches a local fixed point.

Exercises

1. Update a placement

Let $\pi(A)=v_0$, $\pi(B)=v_2$, and $\pi(C)=v_3$. A SWAP exchanges $v_2$ and $v_3$. Find the new placement.

Solution

Let $s_{23}$ exchange $v_2$ and $v_3$. Then

$$\pi' = s_{23}\circ\pi.$$

Therefore

$$\begin{aligned} \pi'(A)&=v_0, &\pi'(B)&=v_3, \\ \pi'(C)&=v_2. \end{aligned}$$

Only program qubits occupying the swapped sites change location.

2. Bound one interaction on a path

Two program qubits occupy sites at distance $d=6$ on a path. Give lower bounds on adjacent-SWAP count and movement depth before they can interact.

Solution

They must reduce their distance from $6$ to $1$. Each adjacent SWAP moving one of the two tokens can reduce the distance by at most one, so

$$N_{\mathrm{SWAP}}\geq5.$$

If both tokens move toward one another on disjoint edges, one layer can reduce the distance by at most two. Hence

$$D_{\mathrm{move}} \geq \left\lceil\frac52\right\rceil = 3.$$

Other tokens and edge conflicts can make either bound unattainable.

3. Verify the bridge circuit

Verify on basis bits that the four-CNOT bridge on $a-b-c$ implements CNOT$(a,c)$ and restores $b$.

Solution

The temporal updates are

$$\begin{aligned} (a,b,c) &\mapsto (a,b\oplus a,c) \\ &\mapsto (a,b\oplus a,c\oplus b\oplus a) \\ &\mapsto (a,b,c\oplus b\oplus a) \\ &\mapsto (a,b,c\oplus a). \end{aligned}$$

Thus $a$ and $b$ are restored while $c$ is flipped exactly when $a=1$. Because CNOT circuits act linearly on basis states, this establishes the unitary identity on arbitrary superpositions.

4. Compare two initial placements

On the path $v_0-v_1-v_2-v_3$, let interaction weights be $w_{AB}=4$, $w_{AC}=1$, and $w_{CD}=3$. Compare

$$\begin{aligned} \pi_1&:(A,B,C,D)\mapsto(v_0,v_1,v_2,v_3), \\ \pi_2&:(A,B,C,D)\mapsto(v_1,v_0,v_2,v_3) \end{aligned}$$

using the weighted-distance objective.

Solution

For $\pi_1$,

$$J(\pi_1) = 4(1)+1(2)+3(1) = 9.$$

For $\pi_2$, the distances are $d(A,B)=1$, $d(A,C)=1$, and $d(C,D)=1$, so

$$J(\pi_2) = 4(1)+1(1)+3(1) = 8.$$

The proxy favors $\pi_2$. This does not prove that its full routed circuit has lower depth or native error.

5. Handle a final permutation

A three-qubit program finishes with

$$\begin{aligned} \pi_{\mathrm{out}}(q_0)&=v_2, &\pi_{\mathrm{out}}(q_1)&=v_0, \\ \pi_{\mathrm{out}}(q_2)&=v_1. \end{aligned}$$

Physical measurements return $(m_{v_0},m_{v_1},m_{v_2})=(1,0,1)$. What is the program-order result?

Solution

Read each program qubit from its final site:

$$\begin{aligned} y_{q_0}&=m_{v_2}=1, \\ y_{q_1}&=m_{v_0}=1, \\ y_{q_2}&=m_{v_1}=0. \end{aligned}$$

The program-order bit tuple is $(1,1,0)$. Restoring the physical placement before measurement would be unnecessary if this classical permutation is recorded.

6. Reverse a directed CNOT

Show that conjugating CNOT$_{c\to t}$ by Hadamards on both qubits reverses its direction.

Solution

Hadamard exchanges $X$ and $Z$. The CNOT conjugation rules are

$$\begin{aligned} X_c&\mapsto X_cX_t, & Z_c&\mapsto Z_c, \\ X_t&\mapsto X_t, & Z_t&\mapsto Z_cZ_t. \end{aligned}$$

Conjugating the entire gate by $H_c\otimes H_t$ exchanges the $X$ and $Z$ roles, producing the propagation rules of CNOT$_{t\to c}$. Therefore

$$\begin{aligned} \operatorname{CNOT}_{t\to c} &= (H_c\otimes H_t) \operatorname{CNOT}_{c\to t} \\ &\quad{}\times (H_c\otimes H_t). \end{aligned}$$

The identity is useful only if all three operations are legal in the target profile.

7. Use the permutation potential

On a path with sites $v_0,\ldots,v_4$, five tokens occupy reverse order relative to their target. Compute $\Phi$ and the resulting SWAP-count lower bound.

Solution

The token destined for $v_i$ starts at $v_{4-i}$, so its distance is $|4-2i|$. Thus

$$\Phi = 4+2+0+2+4 = 12.$$

Each adjacent SWAP can reduce $\Phi$ by at most two, giving

$$N_{\mathrm{SWAP}} \geq \left\lceil\frac{12}{2}\right\rceil = 6.$$

For reversal on a five-site path, every pair of tokens must cross, so the true minimum is $\binom52=10$. The potential bound is valid but not tight.

8. Compare movement with a bridge

On $a-b-c$, compare a remote CNOT from $a$ to $c$ using a bridge with a route that swaps $a$ and $b$, executes the adjacent CNOT, and restores the original map. Assume each SWAP costs three CNOTs.

Solution

The bridge costs four CNOTs and preserves the map. The restore-route costs

$$3+1+3=7$$

CNOTs. Under this isolated count model, the bridge is cheaper.

If the final permutation may change, the router can use one SWAP plus the useful CNOT for a cost of four CNOTs and retain the changed map. Future gates, direction constraints, and native fused implementations can therefore change the ranking.

9. Design a route certificate

List the evidence needed to support “the mapped circuit is legal on this processor and adds only six two-qubit gates.”

Solution

Identify the input circuit and dependency order; target sites, enabled edges, directions, operation definitions, concurrency rules, and target version; initial, intermediate, and final maps; every inserted movement operation; ancilla and reset assumptions; and the physical-to-program output permutation.

For the count claim, specify whether six means abstract CNOTs, native entanglers, or decomposed SWAP overhead, and record the cleanup passes applied. Include the router, settings, timeout, and seed; route-replay validation; semantic translation validation; output circuit hash; and both old and new resource counts. A dated calibration epoch is additionally required if the route was chosen from error or duration data.

Research Status

Graph-based placement, SWAP insertion, token-swapping formulations, front-layer heuristics, exact small-instance solvers, and structured SWAP networks are established parts of quantum compilation. The combinatorial hardness of general minimum-overhead mapping is established; practical optimality remains instance- and model-specific.

Active work concerns joint routing and synthesis, scalable exact bounds, time-dependent and zoned architectures, carrier transport, modular and teleportation-assisted routing, encoded-patch movement, dynamic-circuit resource reuse, learned heuristics, and multiobjective optimization. A 2025 cross-architecture survey documents how strongly the problem changes between fixed-coupling, trapped-ion, and neutral-atom systems. Benchmark improvements on one topology or circuit family should not be generalized without matching target, objective, timeout, and postprocessing.

Further Connections

• Circuit Intermediate Representations defines target capabilities, typed resources, dependencies, timing constraints, and output mappings consumed by a router.
• Circuit Optimization owns commutation, gate fusion, structured rewrites, and abstract depth reduction before and after routing.
• Error-Aware Compilation ranks legal placements, routes, schedules, and gate realizations using dated device evidence, uncertainty, and held-out validation.
• Gate Decomposition turns abstract SWAPs, bridges, direction corrections, and useful gates into the declared target alphabet.
• Quantum Software Stack places routing between target-independent circuit lowering and controller-ready execution.
• Circuit Model fixes wire, measurement, feedforward, and resource semantics.
• Multi-Qubit Gates owns CNOT, CZ, SWAP, exchange, Toffoli, and measured parity operations.
• Hardware Overview defines physical encodings, native interactions, topology, movement, and target evidence.
• Modular Architectures develops cut capacity, entanglement inventory, contention, heralding, retries, and distributed route contracts.

References

1. M. Y. Siraichi, V. F. dos Santos, S. Collange, and F. M. Q. Pereira, “Qubit allocation,” in Proceedings of CGO 2018, 113–125 (2018), doi:10.1145/3168822.
2. A. Zulehner, A. Paler, and R. Wille, “An efficient methodology for mapping quantum circuits to the IBM QX architectures,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 38, 1226–1236 (2019), doi:10.1109/TCAD.2018.2846658.
3. G. Li, Y. Ding, and Y. Xie, “Tackling the qubit mapping problem for NISQ-era quantum devices,” in Proceedings of ASPLOS 2019, 1001–1014 (2019), doi:10.1145/3297858.3304023.
4. A. Cowtan, S. Dilkes, R. Duncan, A. Krajenbrink, W. Simmons, and S. Sivarajah, “On the qubit routing problem,” in TQC 2019, LIPIcs 135, 5:1–5:32 (2019), doi:10.4230/LIPIcs.TQC.2019.5.
5. A. M. Childs, E. Schoute, and C. M. Unsal, “Circuit transformations for quantum architectures,” in TQC 2019, LIPIcs 135, 3:1–3:24 (2019), doi:10.4230/LIPIcs.TQC.2019.3.
6. B. O’Gorman, W. J. Huggins, E. G. Rieffel, and K. B. Whaley, “Generalized SWAP networks for near-term quantum computing,” arXiv:1905.05118 (2019), arXiv:1905.05118.
7. S. Brierley, “Efficient implementation of quantum circuits with limited qubit interactions,” Quantum Information and Computation 17, 1096–1104 (2017), arXiv:1507.04263.
8. É. Bonnet, T. Miltzow, and P. Rzążewski, “Complexity of token swapping and its variants,” Algorithmica 80, 2656–2682 (2018), doi:10.1007/s00453-017-0387-0.
9. G. Nannicini, L. S. Bishop, O. Günlük, and P. Jurcevic, “Optimal qubit assignment and routing via integer programming,” ACM Transactions on Quantum Computing 4, 1–31 (2022), doi:10.1145/3544563.
10. I. D. Kivlichan et al., “Quantum simulation of electronic structure with linear depth and connectivity,” Physical Review Letters 120, 110501 (2018), doi:10.1103/PhysRevLett.120.110501.
11. S. Hillmich, A. Zulehner, and R. Wille, “Exploiting quantum teleportation in quantum circuit mapping,” in Proceedings of ASP-DAC 2021, 792–797 (2021), arXiv:2011.07314.
12. P. Zhu, S. Zheng, L. Wei, X. Cheng, Z. Guan, and S. Feng, “The complexity of quantum circuit mapping with fixed parameters,” arXiv:2207.08438 (2022), arXiv:2207.08438.
13. D. Devulapalli, E. Schoute, A. Bapat, A. M. Childs, and A. V. Gorshkov, “Quantum routing with teleportation,” Physical Review Research 6, 033313 (2024), doi:10.1103/PhysRevResearch.6.033313.
14. C. Zhu et al., “Quantum compiler design for qubit mapping and routing: A cross-architectural survey of superconducting, trapped-ion, and neutral atom systems,” arXiv:2505.16891, version 2 (2025), arXiv:2505.16891.
15. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th anniversary ed., Cambridge University Press (2010), doi:10.1017/CBO9780511976667.