# Qubit Mapping and Routing via MaxSAT

arXiv: https://arxiv.org/abs/2208.13679 · HTML: https://mlsanity.com/paper/2208.13679/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Aug 2022.

## Built on by (most cited first, 8 of 8)

- [Quantum Circuit Synthesis and Compilation Optimization: Overview and Prospects](https://mlsanity.com/paper/2407.00736/) (2024)
- [Optimal Layout Synthesis for Quantum Circuits as Classical Planning (full version)](https://mlsanity.com/paper/2304.12014/) (2023)
- [Optimal Layout Synthesis for Deep Quantum Circuits on NISQ Processors with 100+ Qubits](https://mlsanity.com/paper/2403.11598/) (2024)
- [RobustState: Boosting Fidelity of Quantum State Preparation via Noise-Aware Variational Training](https://mlsanity.com/paper/2311.16035/) (2023)
- [Profiling quantum circuits for their efficient execution on single- and multi-core architectures](https://mlsanity.com/paper/2407.12640/) (2024)
- [A general optimization solver based on OP-to-MaxSAT reduction](https://mlsanity.com/paper/2604.21961/) (2026)
- [QAP-Router: Tackling Qubit Routing as Dynamic Quadratic Assignment with Reinforcement Learning](https://mlsanity.com/paper/2605.12365/) (2026)
- [Fidelity-Aware Scheduling of Quantum Circuits on Multi-QPU Systems](https://mlsanity.com/paper/2609.09980/) (2026)

## Abstract (arXiv)

Near-term quantum computers will operate in a noisy environment, without error correction. A critical problem for near-term quantum computing is laying out a logical circuit onto a physical device with limited connectivity between qubits. This is known as the qubit mapping and routing (QMR) problem, an intractable combinatorial problem. It is important to solve QMR as optimally as possible to reduce the amount of added noise, which may render a quantum computation useless. In this paper, we present a novel approach for optimally solving the QMR problem via a reduction to maximum satisfiability (MAXSAT). Additionally, we present two novel relaxation ideas that shrink the size of the MAXSAT constraints by exploiting the structure of a quantum circuit. Our thorough empirical evaluation demonstrates (1) the scalability of our approach compared to state-of-the-art optimal QMR techniques (solves more than 3x benchmarks with 40x speedup), (2) the significant cost reduction compared to state-of-the-art heuristic approaches (an average of ~5x swap reduction), and (3) the power of our proposed constraint relaxations.