# Optimality Study of Existing Quantum Computing Layout Synthesis Tools

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Feb 2020.

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

- [AlphaRouter: Quantum Circuit Routing with Reinforcement Learning and Tree Search](https://mlsanity.com/paper/2410.05115/) (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)
- [Quantum Kernel Estimation With Neutral Atoms For Supervised Classification: A Gate-Based Approach](https://mlsanity.com/paper/2307.15840/) (2023)
- [Depth-Optimal Quantum Layout Synthesis as SAT](https://mlsanity.com/paper/2506.06752/) (2025)
- [QAP-Router: Tackling Qubit Routing as Dynamic Quadratic Assignment with Reinforcement Learning](https://mlsanity.com/paper/2605.12365/) (2026)
- [CO-MAP: A Reinforcement Learning Approach to the Qubit Allocation Problem](https://mlsanity.com/paper/2605.13638/) (2026)

## Abstract (arXiv)

Layout synthesis, an important step in quantum computing, processes quantum circuits to satisfy device layout constraints. In this paper, we construct QUEKO benchmarks for this problem, which have known optimal depths and gate counts. We use QUEKO to evaluate the optimality of current layout synthesis tools, including Cirq from Google, Qiskit from IBM, mathsft|mathsfketrangle from Cambridge Quantum Computing, and recent academic work. To our surprise, despite over a decade of research and development by academia and industry on compilation and synthesis for quantum circuits, we are still able to demonstrate large optimality gaps: 1.5-12x on average on a smaller device and 5-45x on average on a larger device. This suggests substantial room for improvement of the efficiency of quantum computer by better layout synthesis tools. Finally, we also prove the NP-completeness of the layout synthesis problem for quantum computing. We have made the QUEKO benchmarks open-source.