AI-Assisted Discovery of CNOT Decompositions for Quantum Permutations on Constrained Topologies

Daniele Lizzio Bosco; Jacopo Cossio; Simone Faro; Francesco Pio Marino; Gabriele Messina; Carla Piazza; Giuseppe Serra

cs.AIOct 27, 2026

AI-Assisted Discovery of CNOT Decompositions for Quantum Permutations on Constrained Topologies

Authors: Daniele Lizzio Bosco, Jacopo Cossio, Simone Faro, Francesco Pio Marino, Gabriele Messina, Carla Piazza, Giuseppe Serra

Organizations: Department of Mathematical, Computer and Physical Sciences, University of Udine, Via delle Scienze 206, 33100 Udine, Italy · Department of Biology, University of Naples Federico II, Corso Umberto I 40, 80138 Napoli, Italy · Department of Mathematics and Computer Science, University of Catania, Viale Andrea Doria 6, 95125 Catania, Italy · Catania Astrophysical Observatory, Istituto Nazionale di Astrofisica, Via Santa Sofia 78, 95123 Catania, Italy

Abstract

Efficient quantum circuit compilation is challenging for quantum computers, where limited qubit connectivity can introduce substantial overhead in the implementation of logical operations. Recent AI-assisted synthesis methods have shown considerable potential for reducing circuit complexity, but their role in uncovering principles that can guide the design of new deterministic compilation algorithms remains largely unexplored. In this work, we investigate this perspective for the synthesis of quantum permutations into CNOT circuits under constrained qubit connectivity. Using AlphaCNOT as an exploratory tool, we identify a recurring decomposition for remote transpositions that improves on the construction based on adjacent SWAP routing. For two qubits at graph distance $d>1$ , the discovered pattern yields a topology-legal implementation using at most $6d-4$ CNOT gates, compared to the $6d-3$ gates required by the corresponding SWAP-based construction. We formalize this observation through a constructive proof to define Global Transpositions, a deterministic synthesis method that searches for a minimum-cost decomposition of an entire permutation into topology-aware logical transpositions. The resulting method subsumes optimal SWAP routing within its synthesis model and provides certified upper bounds on the topology-constrained CNOT cost. Our experiments also reveal circuits that cannot be expressed as concatenations of independently synthesized transpositions. Instead, these circuits exploit intermediate linear transformations that temporarily leave the permutation subgroup and combine partial effects of multiple logical operations, a mechanism we call intermediate CNOT fusion. Our results show that AI-assisted synthesis can support not only circuit optimization, but also the discovery of reusable identities, provable constructions, and hidden mechanisms in quantum circuit compilation.

Figures & tables

Panel of Figure 1 — Figure 1: Examples of coupling topologies considered in our experiments. Vertices represent physical qubits, while edges denote the allowed two-qubit interactions. The full set of topologies can be found in Kremer et al. (2024) .

Figure 2: The first local separation between SWAP routing and direct CNOT synthesis. The transposition

\tau(0,2)

on the path

0-1-2

costs

9

CNOTs when implemented as three adjacent SWAPs, but admits a direct topology-legal implementation with

8

CNOTs.

Topology	$d=1$	$d=2$	$d=3$	$d=4$	$d=5$	$d=6$	$d=7$
Formula $f(d)$	$3$	$8$	$14$	$20$	$26$	$32$	$38$
4L	3.00	8.00	14.00
4Y	3.00	8.00
5L	3.00	8.00	14.00	20.00
5T	3.00	8.00	14.00
6L	3.00	8.00	14.00	20.00	26.00

Table 1: Mean CNOT count found by AlphaCNOT (single shot) over all transpositions of distance

d

for selected topologies as defined in Kremer et al. (2024) . Values in bold represent averages that do not coincide with the formula

f(d)

, highlighting that in some cases AlphaCNOT was not able to obtain the observed upper bound.

Figure 3: Example of the recursive decomposition of

\tau(0,4)

with distance

4

, compared to a decomposition found by AlphaCNOT. Note that in the decomposition below, it is easy to recognize the components corresponding to the two copies of the SWAP between

q_{0}

and

q_{1}

S_{0,1}

(i.e., the

6

CNOTs between

q_{0}

and

q_{1}

). However, the remaining transposition

\tau(1,4)

cannot be easily decomposed into

S_{1,2}

and

C_{2,4}

Method	State space	Number of states	Generators	Naive algorithm	Worst-case time
Optimal SWAP	$S_{n}$	$n!$	$\|E\|$ adjacent SWAPs	BFS	$O(n!\,\|E\|)$
Global Transpositions	$S_{n}$	$n!$	$\binom{n}{2}$ weighted transpositions	Dijkstra	$O\!\left(n!\,n^{2}\log(n!)\right)$
Optimal CNOT	$\mathrm{GL}(n,\mathbb{F}_{2})$	$\displaystyle\prod_{k=0}^{n-1}(2^{n}-2^{k})$	$2\|E\|$ oriented CNOTs	BFS	$O\!\left(\|\mathrm{GL}(n,2)\|\,\|E\|\right)$

Table 2: Naive exact search complexity for the three synthesis models.

Figure 4: Intermediate CNOT fusion on

4L

for

\sigma=[2,3,1,0]

. Global Transpositions realizes three independently synthesized transpositions using

14

CNOTs, whereas direct AlphaCNOT synthesis realizes an optimal decomposition in

13

gates.

topology	SWAP $\times 3$	Global Transpositions	AlphaCNOT	Optimal CNOT
$4L$	$8.64$	$8.18$	$8.03$	$8.03$
$4Y$	$8.04$	$7.83$	$7.59$	$7.59$
$5L$	$15.03$	$14.21$	$13.73$	$13.71$
$5T$	$13.50$	$12.92$	$12.46$	$12.42$
$6L$	$22.59$	$21.24$	$20.37$	–
$6T$	$19.20$	$18.28$	$17.67$	–

Table 3: Mean CNOT count over

100

target permutations per constrained topology (for

4

qubits, all

24

permutations are considered). AlphaCNOT results are obtained with

10

repetitions. Results for Optimal CNOT are obtained with bidirectional BFS.

Panel of Figure 5 — Figure 5: Visualizations of some decompositions found by Global Transpositions (GT) and AlphaCNOT with non-trivial intermediate CNOT fusions.

Quantum Circuit Synthesis

See all 20 papers

AlphaCNOT: Learning CNOT Minimization with Model-Based Planning
Apr 15, 2026Jacopo Cossio, Daniele Lizzio Bosco, Riccardo Romanello +2Quantum Circuit Optimization Quantum Circuit Synthesis
University of Udine, Italy · University of Udine & University “Federico II” of Naples, Italy
Beyond Reinforcement Learning: Fast and Scalable Quantum Circuit Synthesis
Feb 16, 2026Lukas Theißinger, Thore Gerlach, David Berghaus +1Quantum Circuit Synthesis Quantum Circuit Compilation
University of Bonn · European Space Agency, Advanced Concepts Team · Fraunhofer IAIS
QAP-Router: Tackling Qubit Routing as Dynamic Quadratic Assignment with Reinforcement Learning
May 12, 2026Kien X. Nguyen, Ankit Kulshrestha, Ilya Safro +1Quantum Circuit Compilation Combinatorial Optimization
Department of Computer and Information Sciences, University of Delaware, USA · Quantum Lab, Fujitsu Research of America, USA

Apr 15, 2026J/K move · Enter open · S save

AlphaCNOT: Learning CNOT Minimization with Model-Based Planning

Jacopo Cossio, Daniele Lizzio Bosco, Riccardo Romanello, Giuseppe Serra+1

University of Udine, Italy · University of Udine & University “Federico II” of Naples, Italy

Quantum Circuit Optimization Quantum Circuit Synthesis Quantum Circuit Compilation Quantum RL

Open paper AskPDF arXiv

Quantum circuit optimization is a central task in Quantum Computing, as current Noisy Intermediate Scale Quantum devices suffer from error propagation that often scales with the number of operations. Among quantum operations, the CNOT gate is of fundamental importance, being the only 2-qubit gate in the universal Clifford+T set. The problem of CNOT gates minimization has been addressed by heuristic algorithms such as the well-known Patel-Markov-Hayes (PMH) for linear reversible synthesis (i.e., CNOT minimization with no topological constraints), and more recently by Reinforcement Learning (RL) based strategies in the more complex case of topology-aware synthesis, where each CNOT can act on a subset of all qubits pairs. In this work we introduce AlphaCNOT, a RL framework based on Monte Carlo Tree Search (MCTS) that address effectively the CNOT minimization problem by modeling it as a planning problem. In contrast to other RL- based solution, our method is model-based, i.e. it can leverage lookahead search to evaluate future trajectories, thus finding more efficient sequences of CNOTs. Our method achieves a reduction of up to 32% in CNOT gate count compared to PMH baseline on linear reversible synthesis, while in the constraint version we report a consistent gate count reduction on a variety of topologies with up to 8 qubits, with respect to state-of-the-art RL-based solutions. Our results suggest the combination of RL with search-based strategies can be applied to different circuit optimization tasks, such as Clifford minimization, thus fostering the transition toward the "quantum utility" era.

Abstract

Quantum Circuit Synthesis

Explore similar work

AlphaCNOT: Learning CNOT Minimization with Model-Based Planning

Beyond Reinforcement Learning: Fast and Scalable Quantum Circuit Synthesis

QAP-Router: Tackling Qubit Routing as Dynamic Quadratic Assignment with Reinforcement Learning