Technical Summary: Generating Compilers for Qubit Mapping and Routing

1. Problem Statement

The execution of quantum circuits on physical quantum processing units (QPUs) requires solving the qubit mapping and routing (QMR) problem. A compiler must map logical circuit qubits to physical device qubits and plan the execution of gates while adhering to the specific connectivity and error constraints of the target hardware.

The landscape of quantum hardware is incredibly diverse and rapidly evolving. It includes various physical realizations (superconducting circuits, trapped ions, neutral atoms), diverse connectivity topologies (linear arrays, grids, fully connected traps), and varying error correction schemes (from no error correction in NISQ devices to surface codes in fault-tolerant architectures). Currently, addressing a new QMR problem typically requires researchers to restart the process from scratch: establishing hardness results, identifying connections to graph-theoretic problems, and developing specialized compilation algorithms for each specific hardware configuration. This paper asks whether it is possible to automatically synthesize a compiler from a specification of architectural constraints rather than manually engineering a new solver for every emerging architecture.

2. Methodology

The authors propose Amaro (Abstract MApping and ROuting), a framework that unifies QMR problems through a common core structure and automatically generates compilers.

2.1 Abstract Formulation: Device State Machines

The core insight is that all QMR problems can be modeled as a device state machine. A solution is viewed as a sequence of device states, where each state captures:

• The current mapping of circuit qubits to physical locations.
• The set of gates executed in parallel at that time step.
• The transitions between states (e.g., swap operations or identity transformations).

The authors define an abstract QMR problem where the specific constraints of a hardware architecture dictate which states are valid (realizable) and which transitions are allowed.

2.2 The Amaro Language

To facilitate the specification of these abstract problems, the authors designed Amaro, a domain-specific language (DSL). An Amaro program defines a concrete QMR problem by specifying:

• RouteInfo: Constraints on valid states, specifically how gates are realized (e.g., mapping a two-qubit gate to an edge in a connectivity graph or a path in a lattice).
• TransitionInfo: Constraints on valid transitions between states (e.g., swap operations between adjacent qubits or identity transitions where the map remains static).
• Cost: The optimization objective (e.g., minimizing the number of swap gates, time steps, or maximizing success probability).

Amaro programs are concise; for instance, the specification for the standard NISQ problem requires only 12 lines of code.

2.3 The Parametric Solver

The authors present a generic, parametric solver that takes an Amaro specification and instantiates a compiler for that specific problem. The solver employs an approximate, iterative approach based on maximal-state construction:

1. Maximal-State Construction: In each iteration, the solver attempts to construct a "maximal state" by routing as many gates from the current front layer of the circuit as possible.
2. Monotonicity and Non-Interference: The solver leverages two properties to optimize this process. If the problem is monotonic (subsets of realizable states are also realizable), a single pass can find a maximal state. If the problem is non-interfering (routing one gate does not block another), the maximal state is unique and order-independent.
3. Search Strategies: For problems that are not non-interfering (where gate paths may conflict), the solver uses simulated annealing to search for the optimal ordering of gates to maximize the number of routed instructions. Similarly, the solver uses simulated annealing to search for the optimal initial qubit mapping.
4. Output: The process repeats, updating the qubit map via valid transitions, until all gates in the circuit are routed.

3. Key Contributions

• Abstract Formulation: A unified view of QMR problems based on device state machines, providing a uniform way to think about diverse hardware constraints.
• Specification Language (Amaro): A DSL that allows for the concise expression of unique architectural constraints, enabling the definition of new QMR problems with minimal code.
• Parametric Solver: A powerful, generic algorithm that automatically instantiates a compiler from an Amaro specification. It balances solution quality and runtime through approximate methods (maximal-state construction and simulated annealing).
• Empirical Evaluation: A comprehensive evaluation across seven distinct case studies, ranging from NISQ architectures to fault-tolerant surface code and interleaved logical qubits.

4. Experimental Results

The authors evaluated the generated compilers against state-of-the-art, handwritten specialized solvers on a benchmark suite of 243 application circuits.

• NISQ (NISQMR): The generated compiler is competitive with Qiskit (using the Sabre algorithm) and QSynth2. It matches or outperforms Qiskit on approximately 48% of benchmarks and finds optimal solutions in 66/73 cases where QSynth2 terminates.
• Variable Error (NISQ-VE): When accounting for varying error rates on links, the Amaro-generated compiler produces solutions with success probabilities equivalent to Qiskit on average, demonstrating the ability to optimize for reliability rather than just gate count.
• Surface Code (SCMR): The generated compiler outperforms the specialized tool DASCOT, finding better solutions in 57% of cases and matching or beating it in 92% of cases where both terminate.
• Reconfigurable Atom Arrays (RAA): The solver significantly outperforms the Enola compiler, finding higher-quality solutions in 97% of cases where at least one tool terminates.
• Interleaved Logical Qubits (ILQ): The solver produces strictly higher-quality solutions than the baseline greedy compiler for 93% of cases.
• Trapped Ions (TIQMR): The solver significantly outperforms the Shaper algorithm, reducing costs by at least 50% in all cases where both terminate and solving 27 benchmarks where Shaper fails.

In terms of runtime, the generated compilers generally converge to high-quality solutions within minutes (e.g., reaching a 10% threshold of the best solution within ~300–600 seconds for 80% of benchmarks), making them suitable for industrial-scale compilation.

5. Significance and Claims

The paper claims that the diversity of quantum hardware necessitates a shift from manual, specialized compiler development to automated synthesis. By identifying the common core structure of QMR problems, Amaro allows researchers and developers to specify constraints for new architectures (including emerging fault-tolerant schemes) and automatically generate competitive compilers.

The authors emphasize that their approach simplifies the development of quantum compilers for new and emerging architectures. While the generated compilers are approximate and do not guarantee optimality (as QMR is NP-hard), they are shown to be highly competitive with specialized, hand-crafted solvers in both solution quality and runtime. The work suggests that a "write once, generate many" approach is viable for the quantum compilation stack, potentially accelerating the adaptation of quantum software to the rapidly changing hardware landscape.