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
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
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 τ(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 τ(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 q0 and q1S0,1 (i.e., the 6 CNOTs between q0 and q1 ). However, the remaining transposition τ(1,4) cannot be easily decomposed into S1,2 and C2,4 .
Method
State space
Number of states
Generators
Naive algorithm
Worst-case time
Optimal SWAP
Sn
n!
∣E∣ adjacent SWAPs
BFS
O(n!∣E∣)
Global Transpositions
Sn
n!
(2n) weighted transpositions
Dijkstra
O(n!n2log(n!))
Optimal CNOT
GL(n,F2)
k=0∏n−1(2n−2k)
2∣E∣ oriented CNOTs
BFS
O(∣GL(n,2)∣∣E∣)
Table 2: Naive exact search complexity for the three synthesis models.
Figure 4: Intermediate CNOT fusion on 4L for σ=[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 ×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.
Figure 5: Visualizations of some decompositions found by Global Transpositions (GT) and AlphaCNOT with non-trivial intermediate CNOT fusions.
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.
Quantum unitary synthesis addresses the problem of translating abstract quantum algorithms into sequences of hardware-executable quantum gates. Solving this task exactly is infeasible in general due to the exponential growth of the underlying combinatorial search space. Existing approaches suffer from misaligned optimization objectives, substantial training costs and limited generalization across different qubit counts. We mitigate these limitations by using supervised learning to approximate the minimum description length of residual unitaries and combining this estimate with stochastic beam search to identify near optimal gate sequences. Our method relies on a lightweight model with zero-shot generalization, substantially reducing training overhead compared to prior baselines. Across multiple benchmarks, we achieve faster wall-clock synthesis times while exceeding state-of-the-art methods in terms of success rate for complex circuits.
Lukas Theißinger, Thore Gerlach, David Berghaus +1
University of Bonn · European Space Agency, Advanced Concepts Team · Fraunhofer IAIS
Qubit routing is a fundamental problem in quantum compilation, known to be NP-hard. Its dynamic nature makes local routing decisions propagate and compound over time, making global efficient solutions challenging. Existing heuristic methods rely on local rules with limited lookahead, while recent learning-based approaches often treat routing as a generic sequential decision problem without fully exploiting its underlying structure. In this paper, we introduce QAP-Router, framing qubit routing based on a dynamic Quadratic Assignment Problem (QAP) formulation. By modeling logical interactions, or quantum gates, as flow matrices and hardware topology as a distance matrix, our approach captures the interaction-distance coupling in a unified objective, which defines the reward in the reinforcement learning environment. To further exploit this structure, the policy network employs a solution-aware Transformer backbone that encodes the interaction between the flow matrix and the distance matrix into the attention mechanism. We also integrate a lookahead mechanism that blends naturally into the QAP framework, preventing myopic decisions. Extensive experiments on 1,831 real-world quantum circuits from the MQTBench, AgentQ and QUEKO datasets show that our method substantially reduces the CNOT gate count of routed circuits by 15.7%, 30.4% and 12.1%, respectively, relative to existing industry compilers.
Kien X. Nguyen, Ankit Kulshrestha, Ilya Safro +1
Department of Computer and Information Sciences, University of Delaware, USA · Quantum Lab, Fujitsu Research of America, USA