# Optimal Layout-Aware CNOT Circuit Synthesis with Qubit Permutation

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 34 references that are in the map.
- First posted on arXiv 8 Aug 2024.

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

- [Optimal Layout Synthesis for Quantum Circuits as Classical Planning (full version)](https://mlsanity.com/paper/2304.12014/) (2023)
- [Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis](https://mlsanity.com/paper/1907.05087/) (2019)
- [QuantumCircuitOpt: An Open-source Framework for Provably Optimal Quantum Circuit Design](https://mlsanity.com/paper/2111.11674/) (2021)
- [Classical Planning as QBF without Grounding (extended version)](https://mlsanity.com/paper/2106.10138/) (2021)
- [Optimal Layout Synthesis for Deep Quantum Circuits on NISQ Processors with 100+ Qubits](https://mlsanity.com/paper/2403.11598/) (2024)
- [Global Synthesis of CNOT Circuits with Holes](https://mlsanity.com/paper/2308.16496/) (2023)

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

- [CNOT-Optimal Clifford Synthesis as SAT](https://mlsanity.com/paper/2504.00634/) (2025)
- [CNOT Minimal Circuit Synthesis: A Reinforcement Learning Approach](https://mlsanity.com/paper/2510.23304/) (2025)
- [Dynamic Tree Databases in Automated Planning](https://mlsanity.com/paper/2511.12677/) (2025)
- [A 12-CNOT Double Qubit Excitation Gate](https://mlsanity.com/paper/2608.11733/) (2026)

## Abstract (arXiv)

CNOT optimization plays a significant role in noise reduction for Quantum Circuits. Several heuristic and exact approaches exist for CNOT optimization. In this paper, we investigate more complicated variations of optimal synthesis by allowing qubit permutations and handling layout restrictions. We encode such problems into Planning, SAT, and QBF. We provide optimization for both CNOT gate count and circuit depth. For experimental evaluation, we consider standard T-gate optimized benchmarks and optimize CNOT sub-circuits. We show that allowing qubit permutations can further reduce up to 56% in CNOT count and 46% in circuit depth. In the case of optimally mapped circuits under layout restrictions, we observe a reduction up to 17% CNOT count and 19% CNOT depth.