Circuit Transformations for Quantum Architectures

1 Introduction

• Automated architecture-aware transformations address a gap left by circuit-specific studies and prior approaches that can require exponential-time searches or solve NP-hard placement problems.The work focuses on logical-level circuits and does not explicitly model fault tolerance.Source: §1 · p. 2
• The goal is to produce function-preserving circuits whose two-qubit gates respect hardware connectivity, minimizing depth or size overhead with polynomial worst-case runtime.The hardware is modeled as a simple graph, with qubits as vertices and possible two-qubit interactions as edges.Source: §1 · pp. 1, 3
• The transformations combine qubit-movement algorithms with heuristic placements; a greedy alternative inserts swaps to reduce distances between qubits needed for two-qubit gates.The authors implement the algorithms in software and compare them with Qiskit’s circuit transformation.Source: §1 · p. 3
• Partial Routing via Matchings handles subset movements with unconstrained destinations for other qubits, while Partial Token Swapping extends a general-graph algorithm to a 4-approximation for minimizing swaps.The paper also gives routing algorithms for paths, complete graphs, and generalized hierarchical products, including Cartesian-product and modular architectures.Source: §1 · p. 3
• Circuit-transformation performance varies by circuit type and architecture: greedy swaps are among the best for size, while depth results differ across grids, modular architectures, and quantum signal processing circuits.For depth, specialized transformations do best on random grid circuits, Qiskit does well on modular architectures, and greedy swaps do best for quantum signal processing circuits.Source: §1 · p. 3

2 Constructing Circuit Transformations

• An architecture-respecting transformation preserves circuit functionality, uses injective initial and final qubit mappings, and places each two-qubit gate on an architecture edge.The general construction uses a mapper for placement and a permuter for moving qubits.Source: §2 · p. 4

2.1.1 Partial Functions and Partial Permutations

• A partial permutation is a bijective partial function from a set to itself, allowing only some elements to be mapped.A completion extends it to a total permutation by mapping the remaining domain and image elements.Source: §2.1.1 · p. 5

2.1.2 Directed Acyclic Graph Representation of a Circuit

• Circuit size counts gates, while circuit depth counts layers in the gate-dependency DAG.The section treats depth as corresponding to parallel execution time and size as the total number of operations.Source: §2.1.2 · p. 5

2.2.1 Qiskit Circuit Transformation

• The described Qiskit transformation samples randomized distance weights, greedily seeks swaps that reduce its objective, and falls back to routing gates individually if trials fail.When a trial succeeds, it uses the successful swap sequence with the fewest swaps before executing the layer's gates.Source: §2.2.1 · p. 6

2.2.2 Greedy Swap Circuit Transformation

• The greedy swap transformation selects disjoint swaps that reduce total gate distance, then executes available gates; its deterministic fallback ensures the circuit is completed.Repeated fallback reaches the selected gate within diam(G) + 1 iterations; the stated time bound is O(|C||E| diam(G)).Source: §2.2.2 · pp. 6–7

2.2.3 Constructing Architecture-aware Circuit Transformations

• The general transformation alternates mapper-selected placements, permuter-generated swaps, and execution of currently feasible gates.The mapper and circuit transformation may use different permuters, and the stated running time is O(|C| (t_m + |V| + t_p)).Source: §2.2.3 · pp. 7–8

3 Partial Permutations via Transpositions

• The routing algorithms implement partial permutations through transpositions constrained to graph edges.The paper calls these algorithms permuters.Source: §3 · p. 8
• Routing via Matchings captures the goal of minimizing the depth of a qubit permutation on an architecture.The passage identifies Token Swapping as the framework for minimizing circuit size.Source: §3 · p. 8
• Routing via Matchings and Token Swapping capture the paper's respective depth- and size-minimization goals for qubit movement.Source: §3 · p. 8

3.1 Partial Routing Via Matchings

• Partial Routing via Matchings minimizes matching depth for routing a partial permutation, completing its undefined assignments.It generalizes Routing via Matchings, which handles total permutations.Source: §3.1 · p. 8

3.1.1 Complete Graph

• For complete graphs, disjoint mappings need one matching; other partial permutations use a completion and the standard algorithm, retaining a routing-number bound of 2.The complete-graph permuter runs in O(n) time.Source: §3.1.1 · p. 9

3.1.2 Path Graph

• On paths, a heuristic completion feeds standard path routing; the proven routing depth is at most n, while tighter parameterized bounds remain open.The completion is constructed in O(|V|) time, and the overall permuter takes O(|V|^2).Source: §3.1.2 · p. 9

3.1.3 Hierarchical Product

• On hierarchical products, the algorithm routes ham(v) representative sets per round across G2 and then G1, in at most ceil(deg(π)/ham(v)) rounds before local routing.The final stage routes vertices to their destinations independently within each G2 copy.Source: §3.1.3 · p. 12
• The hierarchical-product routing number has lower bound 2ceil(deg(π)/ham(v))−1, and the section shows this bound is tight up to constant factors.A permutation on P_2n gives routing depth between 2n−1 and 2n.Source: §3.1.3 · pp. 12–13

3.1.4 Modular Graphs

• For modular graphs, routing only one token to a communicator vertex per round saves one matching per round.The modular architecture is modeled as a hierarchical product of complete graphs.Source: §3.1.4 · p. 13

3.1.5 Cartesian Product

• The choice and ordering of representative-vertex sets matters in practice, motivating the Cartesian-product heuristic for low-depth partial-permutation implementations.The heuristic is presented as tending to produce low-depth implementations, not as a guarantee.Source: §3.1.5 · p. 14
• For Cartesian products, a heuristic chooses minimum-weight perfect matchings for rows using costs based on changes in routing time.Rows are processed in random order, and the routing-time estimate uses the permuter for G2.Source: §3.1.5 · p. 14

3.2 Partial Token Swapping

• Partial Token Swapping minimizes edge transpositions implementing a completion of a partial permutation, thereby optimizing the induced circuit for size.It generalizes Token Swapping, which is restricted to total permutations.Source: §3.2 · pp. 14–15

3.2.1 Approximation Algorithm for Partial Token Swapping

• The algorithm adds no-token swaps: it first moves a token to a tokenless neighbor when that move brings it closer to its destination.Its other mechanisms include unhappy swaps and happy swap chains that reduce token-to-destination distances.Source: §3.2.1 · p. 16, §3.2 · p. 16
• The algorithm uses at most 4 · rs(G, π) transpositions for a partial permutation on any simple connected graph.Here, rs(G, π) is the minimum number of edge transpositions implementing a completion of π.Source: §3.2 · p. 15, §3.2.1 · p. 16
• On paths with n > 2, the modified algorithm can have an asymptotic approximation ratio of 3, despite the total-permutation tree algorithm's 2-approximation.The authors leave the best approximation ratio on trees and general graphs open.Source: §3.2.1 · p. 17
• The permuter runs in O(S|E|) time, bounded above by O(|V|^2|E|), excluding the one-time all-pairs distance computation.Happy and unhappy swaps and no-token swaps each take O(|E|) time to find.Source: §3.2.1 · p. 17

• Mappers use routing number and routing size to express placement costs, replacing them in practice with upper bounds from the permuters.Source: §4 · p. 17
• A mapper constructs a placement—a bijective partial function from circuit qubits to architecture vertices—relative to the current placement.The induced partial permutation is p composed with the inverse of the current placement.Source: §4 · pp. 17–18
• The paper describes mapper strategies for optimizing circuit depth and circuit size.It also bounds mapper time complexity as a function of the permuter's time complexity, t_p.Source: §4 · p. 18

4.1 Circuit Depth Mappers

• Circuit-depth mappers choose placements for gates in the first layer using a maximum matching of the architecture graph.Source: §4.1 · p. 18

4.1.1 Greedy Depth Mapper

• The greedy depth mapper repeatedly places the highest-cost remaining gate at its lowest-cost location, using routing number to measure cost.It selects placements on a maximum matching and recomputes the matching after each iteration.Source: §4.1.1 · p. 18

4.1.2 Incremental Depth Mapper

• The incremental depth mapper guarantees placement of only the lowest-cost gate, then seeks placements for other gates that do not exceed its cost threshold.It uses routing number to select the first gate and edge placement.Source: §4.1.2 · pp. 18–19
• The incremental mapper assumes the architecture's all-pairs distance matrix is available, which can be precomputed in Θ(|V|^3) time.Source: §4.1.2 · p. 19

4.2 Circuit Size Mappers

• Circuit-size mappers assume no gate can be performed in place; otherwise, they return an empty placement because that gate can be executed without moving qubits.Source: §4.2 · p. 19

4.2.1 Greedy Size Mapper

• The greedy size mapper follows the greedy depth mapper but substitutes routing size for routing number.Source: §4.2.1 · p. 19

4.2.2 Simple Size Mapper

• The simple size mapper places only the lowest-cost gate at its lowest-cost architecture-edge location.Its time complexity is O(|L||E|t_p).Source: §4.2.2 · p. 19

4.2.3 Extension Size Mapper

• The extension size mapper adds another gate only when its heuristic predicts that placing it now saves at least zero transpositions.It starts with the placement from the simple size mapper and estimates saved transpositions using routing size before and after the placement.Source: §4.2.3 · pp. 19–20

4.2.4 Qiskit-based Mapper

• The Qiskit-based mapper selects one swap minimizing S per iteration, allows up to |V|^2 iterations, and falls back to the simple size mapper if trials fail.It returns the placement induced by the swaps rather than modifying the output circuit.Source: §4.2.4 · p. 20

5 Results

• Implementations are checked by comparing output-state fidelity for original and transformed random circuits on 11 qubits.The check uses random input states.Source: §5 · p. 20

5.1 Evaluation Criteria

• The benchmarks use 10 random circuits per size and one QSP circuit per data point, with each transformation limited to 8GB RAM and two days.Random circuits have 20 layers of randomly paired qubits and Haar-random two-qubit unitaries; the QSP benchmark uses one pair of phased iterates.Source: §5.1 · pp. 20–21
• Grid dimensions are balanced at ceil(sqrt(N)) per side, and modular dimensions are balanced to test a comparatively hard routing case.The grid choice minimizes routing time for the stated strategy among grids with the same number of qubits; balanced modular dimensions are chosen because more elongated modules require less qubit movement.Source: §5.1 · p. 21
• Weighted size sums gate weights, while weighted depth is the maximum weighted path through the circuit DAG.The evaluation assigns costs 1 to one-qubit gates, 10 to CNOT gates, and 30 to swap gates.Source: §5.1 · p. 21

5.2 Numerical Results

• Up to 100 qubits, tf(s,qiskit) gives the best weighted size on grids; tf(s,simple) leads on modular architectures through 121 qubits.The greedy swap transformation is also among the strongest for weighted size and transforms larger circuits within the time limit.Source: §5.2 · p. 22
• On grids, tf(d,incremental) shows slower weighted-depth growth than transformations without depth-optimized permuters; tf(d,qiskit) outperforms Qiskit’s transformation.On modular graphs, Qiskit’s transformation minimizes weighted depth, while tf(d,qiskit) begins closing the gap at larger sizes; the authors cannot determine whether it later performs better because Qiskit’s transformation lacks data for those sizes.Source: §5.2 · p. 22
• For larger QSP circuits, the greedy transformation wins on weighted depth and size, while tf(s,qiskit) also performs fairly well on depth.The latter targets circuit size rather than depth.Source: §5.2 · p. 22

6 Conclusion and Future Work

• Partial Routing via Matchings models depth-oriented qubit movement, and Partial Token Swapping models size-oriented movement; the paper gives a 4-approximation for the latter on general graphs.The routing procedures cover paths, complete graphs, generalized hierarchical products, Cartesian products, and modular architectures.Source: §6 · p. 22
• The authors combine heuristic mappers with permuters to construct transformations, with mappers applicable to any connected simple graph given a permuter.Mappers seek qubit placements that allow succinct circuit execution.Source: §6 · p. 22
• For weighted size, the greedy transformation is among the best across cases, while depth results are more varied across routing strategies and architectures.Algorithms using Partial Routing via Matchings can perform well for random circuits, but Qiskit’s and the greedy transformations also lead in some cases.Source: Figure 1 · p. 23, §6 · p. 24
• The authors identify architecture-specific performance understanding, overhead bounds, and realistic resource estimates as future directions.They also hope the tools can inform architecture design under realistic hardware constraints.Source: §6 · p. 24
• Future work includes testing whether routing beyond swap gates helps and improving mappers with lookahead or architecture-specific strategies.Lookahead would consider later circuit layers.Source: §6 · p. 24
• Simple-graph architecture models omit hardware details such as CNOT direction and differences in gate costs and times, which may vary over time.The authors describe adapting to variable costs and asynchronous operations as challenging but potentially worthwhile for architectures mixing fast and slow operations.Source: §6 · p. 24
• The paper makes its source code, benchmark circuits, and results publicly available under a license.The results are provided in TSV format.Source: §6 · p. 24