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 SerraarXiv 2026 · arXiv

TL;DR

Researchers used an AI-based optimizer, AlphaCNOT, to discover new, more efficient ways to implement quantum permutations on hardware with limited connectivity. Their findings include a new provable identity for remote transpositions that saves CNOT gates compared to standard SWAP-based methods and the identification of "Intermediate CNOT Fusion," where the AI finds shortcuts by temporarily leaving the mathematical space of permutations.

What Problem Does This Paper Address?

In the current "NISQ" (Noisy Intermediate-Scale Quantum) era, hardware is a major bottleneck. While a quantum algorithm might assume any two qubits can talk to each other, physical processors usually only allow interactions between adjacent qubits on a specific coupling graph.

To bridge this gap, compilers traditionally use SWAP gates to move information across the chip until the required qubits are neighbors. However, each SWAP is typically decomposed into three CNOT gates. On noisy hardware, CNOTs are the primary source of error and execution time. The challenge is: can we find CNOT-level decompositions for these movements that are more efficient than just stacking SWAPs?

Methods

The authors employ a two-pronged approach:

  1. AI-Assisted Exploration: They use AlphaCNOT, a reinforcement learning tool that combines Deep Neural Networks with Monte Carlo Tree Search (MCTS). Unlike traditional compilers that think in terms of SWAPs, AlphaCNOT searches directly in the space of CNOT gates allowed by the hardware topology.
  2. Deterministic Formalization: By inspecting the AI's "creative" solutions, the authors identified recurring patterns. They formalized these into a new deterministic algorithm called Global Transpositions (GT). This algorithm treats the problem as finding a minimum-cost path in a weighted Cayley graph of the symmetric group, where edges are weighted by the CNOT cost of specific transpositions.

Datasets

The study doesn't use a static dataset but rather evaluates performance across various coupling topologies (line, T-shape, Y-shape, etc.) and permutations of different sizes (up to 8 qubits).

  • Topologies: 3L, 4L, 4Y, 5L, 5T, 6L, 6T, 6Y, 7L, 7T, 7Y, 8F, 8H, 8T, 8T2.
  • Permutations: Randomly sampled permutations from the symmetric group $S_n$. For small qubit counts (4 qubits), they evaluated all 24 possible permutations.
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 [8].

Key Insights and Ideas

  • The $6d-4$ Identity: The most significant "aha" moment was discovering that a transposition between two qubits at distance $d > 1$ can be implemented in $6d-4$ CNOTs. The standard SWAP-based approach requires $6d-3$ CNOTs. While saving a single gate might seem small, it proves that standard routing is fundamentally sub-optimal at the CNOT level.
  • AI as a Discovery Tool: The paper highlights that AI shouldn't just be a black-box optimizer. By looking at how AlphaCNOT solved problems, the researchers were able to extract a constructive proof for a new mathematical identity.
  • Intermediate CNOT Fusion: The AI often outperformed the authors' own "Global Transpositions" algorithm. It did this by exploiting "fusion"—combining the effects of multiple transpositions into a single block of gates. Crucially, during these fused operations, the state of the register temporarily becomes a general linear transformation that is not a permutation, only returning to a permutation at the very end.
Comparison between standard SWAP routing (9 CNOTs) and the discovered direct decomposition (8 CNOTs) for a distance-2 transposition.

Key Results

  • Consistent Improvement: Across all tested topologies, AlphaCNOT achieved the lowest mean CNOT counts.
  • Quantifiable Gains: For a set of sampled targets, the mean CNOT count dropped from 23.85 (standard SWAP) to 22.55 (Global Transpositions) and finally to 21.83 (AlphaCNOT).
  • Optimal Benchmarking: For 4 and 5-qubit systems, the authors used exhaustive Breadth-First Search (BFS) to find the absolute mathematical minimum CNOT count. AlphaCNOT frequently hit these optimal values, whereas Global Transpositions (which is restricted to the permutation subgroup) could not.
Visualization of 'Fusion' where AlphaCNOT (bottom) saves a gate compared to the Global Transpositions model (top) by synthesizing the entire permutation jointly.

Limitations and Future Work

  • Scalability: The "Global Transpositions" algorithm relies on Dijkstra's algorithm over the permutation space ($n!$), which becomes computationally expensive as the number of qubits increases.
  • Characterizing Fusion: While the authors identified "Intermediate CNOT Fusion" as a powerful mechanism, they do not yet have a theoretical framework to predict when it's possible or how to generate it deterministically without the AI.
  • Generalization: The current work focuses on CNOT-only circuits (linear reversible circuits). Future work could extend this methodology to include other gate sets (like Clifford+T) or different types of logical operations beyond permutations.

Summary updated

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.
BibTeX
@misc{bosco2026ai,
  author = {Daniele Lizzio Bosco and Jacopo Cossio and Simone Faro and Francesco Pio Marino and Gabriele Messina and Carla Piazza and Giuseppe Serra},
  title = {{AI-Assisted Discovery of CNOT Decompositions for Quantum Permutations on Constrained Topologies}},
  year = {2026},
  eprint = {2610.37045},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.37045},
}
Figure