Qubit Mapping and Routing

Qubit mapping assigns each circuit qubit to a physical site. Routing moves states, or realizes interactions at a distance, so that the circuit can run with the available connections. The central rule is to track which state is where after every movement. A SWAP changes both the physical state and the assignment used to interpret later gates and measurements.

Here a program qubit is a circuit wire. Compiler papers also call it a logical or virtual qubit; that terminology alone does not imply error correction. A physical site at this level might be one device qubit or an encoded patch, depending on the architecture.

Required background. Circuit representations define operations and outputs; circuit optimization determines legal reorderings; the circuit model and multi-qubit gates give the tensor, CNOT and SWAP conventions used below.

Qubit interactions on a hardware 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 execution 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. Some device sites can be unused, and the domain changes when quantum values are allocated or released. Measurement alone does not necessarily release a qubit: its post-measurement state may still be needed. Reset replaces the old state, but its site remains occupied if the program retains the new state.

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

To express the relation precisely, first consider the ideal unitary model with a fixed number of qubits. Pad the program register $Q$ with spare sites $S$, then let $P_{\pi_t}$ permute this complete register into physical order. For initially independent spare states,

$$\rho_{\mathrm{phys}}(t) =P_{\pi_t}(\rho_Q(t)\otimes\sigma_S)P_{\pi_t}^\dagger.$$

The spares need not be in $|0\rangle$ for an ordinary SWAP. If they are correlated with other systems, permute the full joint state instead of assuming a product. With measurement or branching, apply the appropriate branch map and carry the classical result as well. A placement records subsystem locations; by itself it does not describe physical noise or an unapplied teleportation correction.

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. Changing labels without moving states is valid when the surrounding preparation, operations and output interpretation are changed consistently. It cannot relocate an unknown state already supplied at a fixed input port.

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.

Initial Placement

When input preparation can be assigned freely, choose where program qubits begin before inserting movement. If an incoming quantum state already occupies a specified port, its placement is fixed unless the cost of moving it is included. 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, the graph alone does not force SWAPs. The chosen edge must still support the required gate and direction. 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. For a unitary circuit, reverse traversal is a search through the interaction order, not physical execution backwards in time. Measurement, allocation and branch-dependent maps need additional treatment. Using both ends can help but does not guarantee improvement or an 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

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

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.

The distance is finite only within a connected component. A required interaction between disconnected components needs an additional link or a different placement; repeated local SWAPs cannot create connectivity.

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,

$$\operatorname{SWAP}_{uv} = \operatorname{CNOT}_{u\to v} \operatorname{CNOT}_{v\to u} {}\times \operatorname{CNOT}_{u\to v}.$$

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,

$$\operatorname{CNOT}_{t\to c} = (H_c\otimes H_t) {}\times \operatorname{CNOT}_{c\to t} (H_c\otimes H_t).$$

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 derives state transfer; Modular Architectures explains physical module interfaces and capacity. Distributed Quantum Computing develops cross-processor gates and placement, while Quantum Network Architectures explains entanglement delivery 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. Decision versions asking whether a route exists within a SWAP budget are NP-complete even for restricted graph and shallow-circuit families. The corresponding optimization problems are NP-hard. 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 swaps each pair of tokens exactly once. A pair may be adjacent at other times too; the unique crossing supplies a convenient interaction slot. A desired two-qubit operation can be performed when its pair meets, sometimes fused with the SWAP. This gives an all-pairs interaction pattern in linear depth in a model where each pair gate and SWAP take bounded time and disjoint edges can operate in parallel. There are still $\binom n2$ pair interactions and that many SWAPs; linear depth does not mean a linear operation count.

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

$$\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).$$

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, transfer between traps, 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 explain 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. A copied classical outcome may remain live after the measured qubit is released and its site reset. Keep that bit in classical storage for later feedforward. What forbids reuse is a still-needed quantum state, an unpreserved classical result, or an inadequate preparation for the next use.

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.

Checking a routed circuit

Replay the route while updating the placement. Each gate must act on the correct program states, use an allowed physical edge and direction, and respect dependencies and simultaneous-operation limits. At the end, derive the output permutation from the accumulated map instead of guessing it from the final circuit drawing.

For a static SWAP route, track wire labels to translate the emitted gates back to the original program. Small instances can also be checked by matrix multiplication. Bridge circuits preserve the map but still need their operator identity checked. Teleportation and adaptive routes additionally require classical labels, corrections and branch-dependent outputs; a single wire permutation cannot check them all.

Compare routing costs using the same input circuit, gate alphabet, connectivity, final-placement freedom and cleanup rules. Two abstract SWAPs normally mean six CNOTs in the elementary decomposition, but neighboring useful gates can cancel or fuse with them. Count the actual emitted native operations when estimating execution cost. A legal ideal circuit still has implementation noise; error-aware compilation explains how calibration changes the choice among legal routes.

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

For an otherwise unconstrained path, moving the endpoints toward each other attains both bounds. Additional required gates, fixed intermediate states or hardware concurrency restrictions can force more work.

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

$$\operatorname{CNOT}_{t\to c} = (H_c\otimes H_t) \operatorname{CNOT}_{c\to t} {}\times (H_c\otimes H_t).$$

The conjugation rules determine the unitary up to phase. Both sides leave $|00\rangle$ unchanged, fixing that phase to one. The identity is useful only when the directed CNOT and local Hadamards are available.

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. Reuse a measured site while retaining its classical result

Prepare a Bell pair $(|00\rangle+|11\rangle)/\sqrt2$ on sites $a,b$. Measure $a$ in the $Z$ basis, store the result $m$ in classical memory, reset $a$ to $|0\rangle$, and apply $X^m$ to $b$. May $a$ be reused while the classical value $m$ is still needed? What state remains on $b$?

Solution

Conditioned on $m$, the pair becomes $|m\rangle_a|m\rangle_b$. Resetting $a$ replaces its state by $|0\rangle$ without erasing the stored classical bit. The correction gives $X^m|m\rangle_b=|0\rangle_b$ in both branches. The old quantum value at $a$ is no longer used, so a fresh qubit can occupy that site even while $m$ is retained for the correction. If the classical bit is lost before the correction, the unconditioned state of $b$ is $I/2$ instead.

10. Follow an all-pairs SWAP network

Starting with tokens $(A,B,C,D)$ on four consecutive sites, alternate SWAPs on edges $(0,1),(2,3)$ with a SWAP on $(1,2)$ for four layers. List the pairs that cross and the final order. How many SWAPs are used?

Solution

Layer	Crossing pairs	Order after the layer
1	$AB$, $CD$	$B,A,D,C$
2	$AD$	$B,D,A,C$
3	$BD$, $AC$	$D,B,C,A$
4	$BC$	$D,C,B,A$

Every unordered pair crosses exactly once, using $2+1+2+1=6$ SWAPs in four layers. The final order is reversed. Interactions inserted at these crossings add their own duration unless fused with the SWAP. The order of these slots is usable only when the requested gates can be performed in that order; a network is not permission to reorder noncommuting operations.

References

• É. 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.
• S. Brierley, “Efficient implementation of quantum circuits with limited qubit interactions,” Quantum Information and Computation 17, 1096–1104 (2017), arXiv:1507.04263.
• 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.
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th anniversary ed., Cambridge University Press (2010), doi:10.1017/CBO9780511976667.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.