Routing Quantum Programs Without Flattening Them

Quantum programs are written with functions, loops and recursion, but today's compilers throw that structure away before mapping the program onto a chip. Physical quantum processors only let certain pairs of qubits interact, so a compiler must insert SWAP gates, which move quantum states between neighbouring qubits, until every two-qubit gate acts on adjacent qubits. Every widely used router does this on a single flat list of gates. Flattening is costly in two ways. Recursive or repeated subroutines blow up in size before routing even starts. The router also works with no knowledge of which gates belong together, so it cannot reuse work across the many calls to the same subroutine. We propose to route programs module by module. For each subroutine and each target chip, the compiler precomputes a few routed versions, called templates. Each template is indexed by where the subroutine's input and output qubits sit on the chip. A whole program is then assembled by choosing one template per call site and paying explicitly for the permutations needed to join them.

The idea comes from an old lesson in machine translation. Rule-based translation systems became maintainable once they split into three stages. Analysis parsed the source language. Transfer mapped only what actually differed between the two languages. Synthesis generated target-language detail, and it did so without leaking back into the stages before it. In our design the hardware-independent program is the transfer layer. "Where this subroutine's qubits must sit on this chip" is a target-language detail, and it belongs in synthesis. The bet is that preserving module boundaries through routing can deliver compile time that grows linearly on structured programs and SWAP overhead no worse than flat routing. Where the program repeats structure, overhead may be better, because boundary layouts are chosen jointly across the whole program rather than drifting as a single router walks through the gate list.

Core Claim

Current quantum toolchains force a trade-off, described in the research file as a contradiction between modular synthesis and flat routing. Modular Synthesis of Efficient Quantum Uncomputation compiles high-level Silq programs function by function. Silq is a language that automatically cleans up temporary qubits. The paper's compiler avoids the exponential growth of inlining-based tools: at recursion depth 10 it reports about 500 gates against over 85,000 for Unqomp. That paper stops at the logical-circuit level and does not map modules onto hardware connectivity. The standard routers that come next, compared in Benchmarking Quantum Circuit Transformation With QKNOB Circuits, all take a flat circuit. On the 53-qubit Rochester depth benchmark, the best of them (SABRE) reaches an average depth ratio of 3.23, against 1.42 for the benchmark's built-in solution. The modularity gained upstream is lost at exactly the stage where hardware cost is decided.

Our claim is that routing can be made compositional. The QKNOB result itself hints at why. Its near-optimal built-in solutions exist because the circuits are assembled from presynthesized subcircuits joined by known links. Knowing the module structure is precisely what makes a cheap mapping findable. We propose a router that recovers that knowledge from the source program instead of from benchmark construction.

The Mechanism

Take a module $f$, which is a subroutine or a gate definition, and a target coupling graph $G$. The synthesis stage produces up to $K$ routed templates for $f$ on $G$. Each template $t$ comes with an entry layout $\ell_{\text{in}}(t)$, an exit layout $\ell_{\text{out}}(t)$ and an internal SWAP cost $c(t)$. A layout here means an assignment of the module's qubits to physical qubits, expressed relative to a small region of the chip so that one template can be reused anywhere the region repeats.

Consider a sequence of call sites $1, \dots, n$. At each site the compiler chooses one template $t_i$ from the template set of the module being called. It then minimises

$$C = \sum_{i=1}^{n} c(t_i) + \sum_{i=1}^{n-1} \pi\big(\ell_{\text{out}}(t_i), \ell_{\text{in}}(t_{i+1})\big),$$

where $\pi$ is the SWAP cost of permuting one layout into the next on $G$. This is a shortest-path problem with $K$ states per call site, so it runs in $O(nK^2)$ time. That is the reason for the decomposition: the search over template choices never explodes combinatorially.

Recursion is handled by memoising templates keyed on (module, depth, entry layout). The routed body at depth $d$ is built from routed templates at depth $d-1$, so compile time tracks the number of distinct keys rather than the size of the inlined circuit.

Inside each template we run SABRE itself as the local router. Any difference from flat SABRE therefore comes from structure and the joint choice of boundary layouts, not from a better local heuristic.

Isabelle and Macklovitch, in Transfer and MT Modularity, argued that transfer components become polluted when target syntax creeps into them, and that such details must be pushed into synthesis. That argument motivates our boundary rule: the transfer-level program never mentions coupling graphs. The same paper also warns that decoupling transfer from target choices creates non-deterministic search. That warning constrains the design and is why template choice is bounded by $K$ and solved by dynamic programming rather than open-ended search.

We considered the declarative graph unification of Independent Transfer Using Graph Unification for matching layouts. We rejected it for this stage because the matching problem here has a numeric cost, and a shortest-path formulation handles that directly.

Research Program

The compiler needs program hierarchy from three sources.

The first is Silq programs. We will take the per-function static single assignment output of the modular uncomputation compiler, a form in which every value is assigned exactly once. This covers the recursive Iterate and Etareti routines, adders, Grover and Shor.

The second is Q# programs lowered to QIR, Microsoft's LLVM-based quantum intermediate representation, taken from the 120-program IBM Quantum Challenge dataset used by Dataflow-Based Optimization for Quantum Intermediate Representation Programs. We read the QIR before that paper's inlining pass runs, so function boundaries survive.

The third is OpenQASM circuits from QASMBench: A Low-level QASM Benchmark Suite for NISQ Evaluation and Simulation, where declared gate definitions serve as modules.

The synthesis stage is written once per target: IBM Q Tokyo, IBM Q Rochester and Google Sycamore from QKNOB, plus an IBM heavy-hex device. We will measure whether adding a target requires any change to the transfer layer. The prediction is zero changes. If that fails, it is a direct sign of the leakage the file identifies in Quantum Circuit Transformations with a Multi-Level Intermediate Representation Compiler, whose QCOR dialect stack mixes hardware constraints into higher-level lowering.

Baselines

The naive reference point is to inline everything and route with Qiskit StochasticSWAP from a trivial initial layout. This is what a user gets from a default flat pipeline, and it fixes the floor for SWAP count and depth.

The strongest competitor is to inline everything and route with SABRE. Benchmarking Quantum Circuit Transformation With QKNOB Circuits reports that SABRE was consistently best on both SWAP count and depth across the tested devices, with an average depth ratio of 3.23 on 53Q_depth_Rochester against a built-in ratio of 1.42. For fairness, flat SABRE gets the same wall-clock budget as our full pipeline. Template construction is included in that budget. SABRE spends its budget on extra random layout trials and bidirectional passes, and we report the best of its trials. Beating it means either lower mean SWAP count and depth ratio at equal budget, or equal quality with compile time that grows linearly rather than super-linearly in recursion depth. For the uncomputation-heavy programs, the gate-count reference is the modular synthesis paper's figure of about 500 gates at depth 10 against over 85,000 for Unqomp. Unqomp's output is what flat SABRE would have to route.

Two ablations isolate the key ingredient. The first, naive modular routing, routes each module once with $K=1$ and a fixed entry layout and inserts permutations at every boundary. It tests whether choosing boundary layouts jointly matters, or whether merely preserving boundaries suffices. The second varies $K$ from 1 to 8 to trace the quality–compile-time curve. All variants share the same inner SABRE and the same targets.

Why not just…?

Why not just inline and give SABRE more compute? This is the real threat. On circuits without repeated structure, flat SABRE sees cross-boundary optimisation opportunities that our templates cannot. We therefore expect no quality gain on unstructured QASMBench kernels and say so in advance. The equal-budget comparison settles the matter. If flat SABRE matches our quality even on recursive and repeated-call programs, our contribution shrinks to compile-time scaling alone, and we will report it that way. The QKNOB gap between 3.23 and 1.42 suggests there is room SABRE does not reach, but that gap exists on circuits built from known pieces, and it remains to be shown on real programs.

Why not just route each function separately and stitch? This is our first ablation. Isolated routing leaves each module's exit layout arbitrary. The boundary permutations can then dominate the total cost when a small module is called many times. If the ablation matches the full method, the dynamic program is unnecessary and we will drop it.

Why not just use MLIR dialects as in QCOR? Quantum Circuit Transformations with a Multi-Level Intermediate Representation Compiler provides multi-level lowering but still flattens before routing, since it inserts mirror-circuit checks into the flat circuit. It has no notion of a routed module reusable across call sites. Our design could be implemented as an MLIR dialect. The contribution is the template interface, not a new IR.

Why not have a language model emit hardware code directly? Qiskit HumanEval: An Evaluation Benchmark for Quantum Code Generative Models reports that no model passed either of its two difficult tasks, even a model fine-tuned on Qiskit. Routing adds hard hardware-adjacency constraints on top of that difficulty, so we do not treat it as a serious competitor for this question.

Proposed Experiments

The first experiment is an oracle test on QKNOB. We give the router the true subcircuit decomposition on Tokyo, Rochester and Sycamore and measure how far the depth ratio moves from SABRE's 3.23 toward the built-in 1.42. This bounds what module knowledge can buy. If the oracle does not beat SABRE, the idea fails and we stop.

The second experiment uses the recursive Silq benchmarks. We plot routed SWAP count, CX count and compile time against recursion depth from 1 to 10, using templates on top of modular uncomputation compared with Unqomp output routed by flat SABRE. The decisive check is linear compile time together with routed CX count no worse than flat SABRE on the modularly synthesised circuit.

The third experiment runs the 120 IBM Quantum Challenge programs and QASMBench's medium- and large-scale circuits. We report SWAP and depth distributions against both flat baselines, split into programs with and without repeated calls to test the predicted asymmetry.

The fourth experiment is a portability audit. After adding the heavy-hex target, we count the lines changed in the transfer layer and in the synthesis layer.

The fifth, if hardware access allows, re-runs small QASMBench kernels on IBM devices to confirm that reduced SWAP counts translate into fidelity. No per-kernel fidelity baseline from QASMBench was found in the file, so this comparison will be between our method and flat SABRE measured on the same runs.