# Optimal Layout Synthesis for Deep Quantum Circuits on NISQ Processors with 100+ Qubits

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 31 references that are in the map.
- First posted on arXiv 18 Mar 2024.

## Builds on (most cited first, 6 of 6)

- [Qubit Mapping and Routing via MaxSAT](https://mlsanity.com/paper/2208.13679/) (2022)
- [Optimality Study of Existing Quantum Computing Layout Synthesis Tools](https://mlsanity.com/paper/2002.09783/) (2020)
- [Optimal Layout Synthesis for Quantum Circuits as Classical Planning (full version)](https://mlsanity.com/paper/2304.12014/) (2023)
- [Optimization of Quantum Circuit Mapping using Gate Transformation and Commutation](https://mlsanity.com/paper/1907.02686/) (2019)
- [Optimal Layout Synthesis for Quantum Computing](https://mlsanity.com/paper/2007.15671/) (2020)
- [Constraint programming models for depth-optimal qubit assignment and SWAP-based routing](https://mlsanity.com/paper/2306.08629/) (2023)

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

- [Optimal Layout-Aware CNOT Circuit Synthesis with Qubit Permutation](https://mlsanity.com/paper/2408.04349/) (2024)
- [CNOT-Optimal Clifford Synthesis as SAT](https://mlsanity.com/paper/2504.00634/) (2025)
- [Depth-Optimal Quantum Layout Synthesis as SAT](https://mlsanity.com/paper/2506.06752/) (2025)

## Abstract (arXiv)

Layout synthesis is mapping a quantum circuit to a quantum processor. SWAP gate insertions are needed for scheduling 2-qubit gates only on connected physical qubits. With the ever-increasing number of qubits in NISQ processors, scalable layout synthesis is of utmost importance. With large optimality gaps observed in heuristic approaches, scalable exact methods are needed. While recent exact and near-optimal approaches scale to moderate circuits, large deep circuits are still out of scope. In this work, we propose a SAT encoding based on parallel plans that apply 1 SWAP and a group of CNOTs at each time step. Using domain-specific information, we maintain optimality in parallel plans while scaling to large and deep circuits. From our results, we show the scalability of our approach which significantly outperforms leading exact and near-optimal approaches (up to 100x). For the first time, we can optimally map several 8, 14, and 16 qubit circuits onto 54, 80, and 127 qubit platforms with up to 17 SWAPs. While adding optimal SWAPs, we also report near-optimal depth in our mapped circuits.