Source-linked AI summary
On the qubit routing problem
Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, Seyon Sivarajah
TL;DR
Qubit routing is required to adapt abstract quantum circuits to hardware with restricted connectivity. The paper presents t|ket⟩’s architecture-agnostic routing method, which globally evaluates mappings across timesteps and matches or beats other systems while reducing runtime and gate overhead.
Problem
Abstract quantum circuits require routing before execution because hardware connectivity constraints may require additional SWAP gates.
Method
The paper describes t|ket⟩’s heuristic routing algorithm, which evaluates candidate mappings across multiple timesteps to optimize circuits globally.
Results
The method matches or beats other circuit-mapping systems on compiled-circuit depth and total gate count, with mean RD of 2.64 and RC of 2.61 for ibmqx5 and 1.73 and 1.69 for IBM Tokyo.
Takeaways & Limitations
t|ket⟩ provides hardware-compatible routing with minimal extra gate overhead and is described as flexible, general, and scalable.
Takeaways & Limitations
The routing formulation assumes all gates are equal, whereas real devices have gate-specific fidelities and runtimes and fluctuating qubit properties.
Abstract
from arXiv · showhide
We introduce a new architecture-agnostic methodology for mapping abstract quantum circuits to realistic quantum computing devices with restricted qubit connectivity, as implemented by Cambridge Quantum Computing's tket compiler. We present empirical results showing the effectiveness of this method in terms of reducing two-qubit gate depth and two-qubit gate count, compared to other implementations.
I. INTRODUCTION
Quantum circuit theory assumes unrestricted qubit interactions, whereas realistic hardware permits gates only between neighboring qubits in a fixed topology. The paper presents t|ket⟩ as a platform-independent routing solution designed to preserve hardware compatibility while limiting circuit overhead.
- Motivation: Realistic devices require circuits to be modified so interacting qubits become adjacent in hardware memory.The circuit model allows gates between arbitrary qubits, unlike fixed two- or three-dimensional hardware topologies.
- Motivation: Qubit routing inserts SWAP gates to conform an abstract circuit to a specific device’s connectivity, making it a necessary compiler stage.Routing can require many or all qubits to move, increasing circuit size and depth.
- Prior work: Optimal general routing is computationally difficult because qubit assignment corresponds to sub-graph isomorphism and swap selection to token-swapping.The cited methods include an exact approach exponential in qubit number and heuristics evaluated on small circuits.
- Contribution: t|ket⟩ implements a platform-independent heuristic that matches or beats other mapping systems on compiled-circuit depth and total gate count.The method also has much reduced runtime, allowing larger circuits to be routed.
- Contribution: The routing module is part of a broader t|ket⟩ platform offering hardware gate-set translation, circuit optimization, and quantum software framework support.The paper states that these additional capabilities will be described in future papers.
A. Example: routing on a ring
Routing on a ring slices the circuit, maps logical qubits to graph nodes, and inserts swaps when required interactions are non-adjacent. The t|ket⟩ approach evaluates mappings globally across timesteps and accommodates directed hardware through gate inversion and SWAP synthesis.
- Initial mapping: The circuit is divided into timesteps containing disjoint pairs of qubits that must interact through two-qubit gates.Single-qubit gates can be ignored for routing because they do not constrain connectivity.
- Initial mapping: A reasonable initial mapping places q1, q3, q2, q4 on nodes 1, 2, 3, 4, making the first two timesteps adjacent.The mapping is illustrated in Fig. 3.
- Candidate swaps: At the third timestep, q1 and q2 are non-adjacent, so swapping nodes 1 and 3 or nodes 2 and 3 creates alternative configurations.The alternatives are shown in Fig. 4; later interactions influence which swap is preferable.
- Candidate swaps: As circuits grow, candidate swaps increase dramatically and improving one pair can worsen another, requiring a global trade-off across interactions.The worst case requires O(n^2) swaps to transform between arbitrary n-node configurations, while some regular graphs admit better bounds.
- Global routing: The t|ket⟩ routing algorithm evaluates candidate mappings across multiple timesteps rather than optimizing each transition independently.This global evaluation is identified as the core of the routing algorithm.
- Directed routing: Directed architectures require gate-orientation handling: CNOT inversion uses Hadamards, and a SWAP can be synthesized from three unidirectional CNOTs and four Hadamards.The resulting circuit must remain conformant to the architecture digraph after simplification.
III. THE t|ket⟩ROUTING PROCEDURE
The t|ket⟩ routing procedure guarantees compilation to any architecture represented by a connected graph through four stages: slicing, initial placement, routing, and cleanup.
- Procedure overview: The procedure supports arbitrary-depth circuits and any architecture represented as a connected graph.Its four stages are decomposition into timesteps, initial placement, routing across timesteps, and final cleanup.
- Slicing the circuit: The input circuit is partitioned into horizontal timesteps using the circuit’s partial gate ordering and a greedy traversal.A new timestep begins when a two-qubit gate requires a qubit already used in the previous timestep.
- Slicing the circuit: Each timestep contains disjoint pairs of logical qubits scheduled for simultaneous two-qubit interactions.The example produces four timesteps with pair sets listed explicitly in the procedure.
- Slicing the circuit: The illustrative slicing in the procedure differs from the slicing shown in Fig. 1.This distinction is stated explicitly after the example timestep sequence.
- Slicing the circuit: Timestep density measures the number of simultaneous gates, with d = 1 when every qubit participates in a two-qubit gate and sparse timesteps near zero.The density is used for analysis rather than as a practical routing constraint.
B. Initial Mapping
t|ket⟩ builds an initial logical-to-physical mapping from interaction structure, then iteratively routes slices by executing available gates and selecting SWAPs that improve future executability.
- Initial mapping: t|ket⟩ constructs an interaction graph from successive timesteps, retaining edges only when both qubits have degree below 2.Each connected component is a line or ring; rings are broken by removing one edge.
- Initial mapping: Disconnected qubits are omitted from the initial placement and added later during routing.They represent qubits that never interact or whose first interaction depends on another qubit’s earlier interactions.
- Initial mapping: The initial placement maps the interaction graph onto a high-degree, low-diameter architecture subgraph, using a greedy line embedding when possible.For Hamiltonian-connected architectures, this arrangement lets most gates in the first two timesteps execute without swaps.
- Routing loop: The routing loop takes the sliced circuit and current mapping, executes compatible gates, allocates unmapped qubits, and inserts SWAPs when the current timestep remains unfinished.After each selected SWAP, the mapping is updated and the process continues until the input circuit is consumed.
- SWAP selection: Candidate SWAPs are ordered using a distance vector that approximates the swaps needed for the current and subsequent timesteps.The sequence stops after one candidate remains or a predefined cutoff; disjoint swaps and shortest-path brute force provide escape strategies when strict improvement fails.
- Implementation: Dynamic timestep computation can improve results by recomputing the next slice after each mapping update rather than preslicing the circuit.This avoids unnecessary sequentialisation.
D. SWAP synthesis and clean-up
After routing, t|ket⟩ synthesizes inserted SWAPs into gates supported by the target hardware and applies routing-preserving cleanup rewrites.
- SWAP synthesis: Unsupported primitive SWAPs are replaced with hardware-appropriate gates after routing.A final cleanup pass can remove some inserted gates when the input circuit was already optimized.
- Clean-up: Cleanup rewrites must preserve the existing routing, using rewrite rules between one- and two-qubit circuits.The allowed rules depend on the hardware-supported gate set.
- Architecture representation: Quantum architectures are represented as connected graphs whose nodes are qubits and whose edges specify allowed two-qubit interactions.The work considers ring, cyclic butterfly, square-grid, IBM Q 20 Tokyo, and Rigetti 19Q-Acorn graphs.
V. RESULTS
The evaluation measures routing overhead on NISQ-relevant devices, emphasizing empirical behavior because shallow circuits and small qubit counts make constant factors important.
- Evaluation setting: NISQ devices have small qubit counts and shallow circuit depths, motivating empirical evaluation rather than asymptotic analysis alone.The paper evaluates scaling on synthetic circuits and compares t|ket⟩ with competing compiler implementations.
- Metrics: Routing adds SWAP gates that increase circuit depth and total gate count, so the main architecture-independent metric here is depth increase.The total gate count depends on the architecture’s supported gate set.
- Architectures: The evaluated architecture set includes rings, square grids, cyclic butterflies, IBM Q 20 Tokyo, and Rigetti 19Q-Acorn.The architecture graphs encode permitted qubit interactions.
- Metrics: A SWAP counts as one additional gate and therefore induces at most one additional timestep in the comparison with classical sorting algorithms.This convention avoids counting a decomposition such as three CNOT gates.
1. Scaling with depth
The experiments test routing across circuit depths, architecture sizes, densities, and connectivity patterns using randomized circuits and multiple hardware-like graphs.
- Scaling with depth: 1000 random density-d = 1 circuits were generated for each initial depth t ∈ [2, 10], routed with t|ket⟩, and evaluated using R.Density d = 1 means the circuits contain no single-qubit gates.
- Scaling with depth: The depth experiments compare a 64-node ring, square grid, and cyclic butterfly with 20-node IBM and Rigetti architectures.A common circuit set was used within each size group to eliminate sampling bias.
- Scaling with depth: The ratio R is approximately constant as circuit depth increases, with architecture connectivity dominating its behavior.The ratio appears to converge for circuits deeper than 5, and d = 1 circuits represent the worst routing case.
- Scaling with architecture size: Architecture-size scaling uses single-timestep random circuits with densities d ∈ {0.5, 0.67, 1.0} and randomly initialized mappings.For each architecture of size n, the protocol generates 10n circuits and computes N after routing.
- Scaling with architecture size: The size study evaluates rings with r ∈ [10, 200], square grids with r ∈ [3, 13], and cyclic butterflies with r ∈ [2, 6].These ranges vary the number of nodes according to each architecture’s construction.
- Scaling with architecture size: Routing overhead appears to grow with graph diameter, while the fitted exponent varies slightly with circuit density.Ring and square-grid fits use log-log regression; cyclic-butterfly fits use log-log(log) regression.
- Benchmark comparison: The benchmark comparison targets CNOT count and depth on IBM architectures because CNOT is their only two-qubit operation and has lower fidelity than single-qubit operations.SWAP synthesis is performed for a more realistic device evaluation.
B. Realistic Benchmarks
The paper evaluates t|ket⟩ on 156 realistic algorithmic circuits across ibmqx5 and IBM Tokyo, measuring CNOT depth and count. It reports approximately linear overhead, faster completion than competing compilers, and comparable performance to Zulehner et al. under total-gate metrics.
- Benchmark setup: 156 benchmark circuits spanning 6–16 qubits and 7 to more than half a million gates were routed on ibmqx5 and IBM Tokyo.The circuits perform various algorithms and form a standard realistic test set.
- Benchmark setup: CNOT count and depth were selected as figures of merit because both target architectures use CNOT as their only two-qubit operation.The choice also reflects the lower fidelity of CNOT operations relative to single-qubit operations.
- t|ket⟩ performance: Mean routing ratios were RD = 2.64 and RC = 2.61 for ibmqx5, versus RD = 1.73 and RC = 1.69 for IBM Tokyo.The reported ratios compare output with input CNOT depth and count, respectively.
- Compiler comparison: t|ket⟩ completed the entire benchmark set in 15 mins, while QISKit, Project Q, and Quilc did not complete it within the allotted time.The competing compilers were each given at least an hour per example on the same powerful computer.
- Compiler comparison: Quilc and t|ket⟩ exhibited very similar performance, while the other tested compilers showed significantly higher overhead.The comparison used least-squares lines of best fit in Fig. 14.
- Published comparison: Zulehner et al.’s algorithm achieved comparable performance to t|ket⟩ when evaluated using total gate count and depth.Quilc was excluded from this comparison because it generates a different gate set.
VI. CONCLUSION
The conclusion presents t|ket⟩ routing as a flexible, general, scalable solution for hardware-compatible compilation with minimal extra gate overhead. It identifies reinforcement learning and device-specific gate properties as directions for future work.
- Conclusion: t|ket⟩ routing provides hardware compatibility with minimal extra gate overhead and is described as flexible, general, and scalable.The paper outlines the routing procedure and the figures of merit used to assess performance across graphs.
- Future work: The paper identifies reinforcement learning as an alternative routing approach and anticipates implementing multiple approaches for different algorithms and architectures.These possibilities are presented as extensions of the current work.
- Future work: The routing analysis assumes all gates are equal, whereas real devices have gate-specific fidelities and run times that affect scheduling and error overhead.Incorporating these constraints and measuring performance is left for future work.
Appendix A: Dynamical routing versus sorting networks
The appendix contrasts adaptive dynamical routing with fixed classical sorting networks. Sorting algorithms offer known routing constructions, but their input-independent comparisons and timestep-by-timestep structure can create unnecessary work and miss globally better solutions.
- Sorting networks: On a ring with n nodes, cyclic odd-even sorting compares sequentially all even and odd labeled edges and sorts any input in exactly n − 1 time steps.The appendix uses this as an example of a classical sorting-based routing method.
- Sorting networks: For ring, square, and cyclic butterfly graphs, the appendix summarizes graph degree, diameter, and sorting-network depth overhead.The depth overhead is the quantity N introduced in Section V.
- Dynamical routing: Classical sorting networks are unadaptive because they use the same comparison sequence regardless of the input circuit.This can leave unnecessary comparisons when circuits are sparse.
- Dynamical routing: Routing sequentially timestep by timestep concatenates locally optimal solutions that can be far from globally optimal.The appendix argues that a good method should account for a SWAP gate’s influence across multiple timesteps and optimize globally.
- Benchmark reporting: The benchmark tables distinguish total-gate metrics from CX-only metrics, identify time-outs and unavailable data, and mark the best row performance.The t|ket⟩ comparison ratio is below 1 when t|ket⟩ performs better than the best other compiler.
- Benchmark reporting: The ground_state_estimation circuit produces anomalously low post-routing values because an error lets t|ket⟩’s cleanup pass eliminate almost the entire circuit.This is an example-specific benchmark caveat.
B.2. CX only comparison on ibmqx5
The ibmqx5 CX-only comparison reports routing results using CX count and CX depth, with figures organized around compiler performance and benchmark rows. The supplied passages also include an example of anomalously low routed values caused by an erroneous circuit.
- CX-only metrics: Figure 17 compares ibmqx5 routed circuits using CX count and CX depth only.Its charts zoom into the initial segment of the corresponding CX-only comparison in Fig. 14.
- CX-only metrics: Table V is a CX-gates-only comparison on ibmqx5 involving Project Q 0.7.0.The table title identifies the architecture, metric scope, and compiler version.
- Benchmark data: The benchmark row shown for urf4_187 reports 224028 input gates and 185975 output gates, with another reported pair of 568938 and 481368.The supplied row does not label which displayed columns correspond to each pair.
- Benchmark reporting: In the comparison tables, g denotes gate count and d denotes circuit depth, while dashes indicate time-outs or unavailable published data depending on the table.For CX-only tables, gate count and depth refer specifically to CX count and CX depth.
- Cross-architecture comparison: Figure 18 presents the corresponding CX-count and CX-depth comparison for IBM Tokyo.It is described as a zoomed-in view of the lower-row results in Fig. 14.