Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.37045

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

Published Oct 27, 2026• 0 citations
arXivHTMLPDF

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.

DOI
10.48550/arxiv.2610.37045

Related papers

Towards Optimal Topology Aware Quantum Circuit Synthesis

Marc G. Davis, Ethan Smith, Ana Tudor +3 more

We present an algorithm for compiling arbitrary unitaries into a sequence of gates native to a quantum processor. As CNOT gates are error-prone for the foreseeable Noisy-Intermediate-Scale Quantum devices era, our A* inspired algorithm minimizes their count while accounting for connectivity. We discuss the formulation of synthesis as a search problem as well as an algorithm to find solutions. For a workload of circuits with complexity appropriate for the NISQ era, we produce solutions well within the best upper bounds published in literature and match or exceed hand tuned implementations, as well as other existing synthesis alternatives. In particular, when comparing against state-of-the-art available synthesis packages we show 2.4× average (up to 5.3×) reduction in CNOT count. We also show how to re-target the algorithm for a different chip topology and native gate set while obtaining similar quality results. We believe that tools like ours can facilitate algorithmic exploration and guide gate set discovery for quantum processor designers, as well as being useful for optimization in the quantum compilation tool-chain.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Oct 1, 2020•88 citations

AlphaCNOT: Learning CNOT Minimization with Model-Based Planning

Jacopo Cossio, Daniele Lizzio Bosco, Riccardo Romanello +2 more

Quantum circuit optimization is a central task in quantum computing, as current NISQ 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 two-qubit gate in the universal Clifford+T set. Minimizing CNOT gates is therefore particularly important, as these gates exhibit higher error rates and they typically introduce additional routing overhead due to hardware constraints. The problem of CNOT gate 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 qubit pairs. We introduce AlphaCNOT, an RL framework based on Monte Carlo Tree Search that effectively addresses the CNOT minimization problem by modeling it as a planning problem. In contrast to other RL-based solutions, 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 24.62% in CNOT count compared with the PMH baseline on linear reversible synthesis, and a consistent gate count reduction on different topologies with up to 8 qubits, also 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, thus fostering the transition toward the "quantum utility" era.

cs.AICross-listedarXiv:2604.13812•Apr 16, 2026•0 citations

Using Topology-Aware Reinforcement Learning to Synthesize Quantum Linear Reversible Circuits

Giovanni Acampora, Allegra Cuzzocrea, Marco Lapegna +2 more

In the Noisy Intermediate-Scale Quantum (NISQ) era, efficient quantum circuit synthesis is essential for optimizing limited qubit resources and mitigating noise effects. Quantum Linear Reversible Circuits (QLRCs) are a fundamental class of circuits with applications in quantum compilation or quantum error correction. They are composed exclusively of CX and SWAP gates, which are among the noisiest operations on current quantum hardware. Therefore, their efficient synthesis is pivotal for executing QLRCs on NISQ processors, which have restricted connectivity between qubits. In this direction, we introduce a Reinforcement Learning (RL)-based synthesis approach using Proximal Policy Optimization (PPO) to synthesize QLRCs on generic topologies of up to five qubits. This work extends previous work that did not handle different topologies of quantum processors. Our method dynamically adapts to hardware constraints, learning optimal or near-optimal gate decompositions. We compare our approach against Qiskit’s synthesis methods for QLRCs, demonstrating that our RL-based synthesizer consistently achieves lower CX gate depth. These results highlight the potential of RL-driven quantum circuit synthesis as a powerful alternative to traditional heuristic-based techniques, paving the way for more efficient AI-based quantum compilation strategies in the NISQ era.

International Joint Conference on Neural Networks (IJCNN)•Jun 30, 2025•0 citations

Logical-to-Physical Compilation for Reducing Depth in Distributed Quantum Systems

Folkert de Ronde, Stephan Wong, Sebastian Feld

Quantum computing is expected to become a foundational technology for solving problems that exceed the capabilities of classical systems. As quantum algorithms and hardware technologies continue to advance, the need for scalable architectures becomes increasingly clear. Distributed quantum computing offers a promising path forward by interconnecting multiple smaller processors into a larger, more powerful system. However, distributed quantum computing introduces significant circuit depth overhead, as logical operations are typically decomposed into sequential physical procedures that require entanglement generation. These sequential operations limit the reliability of quantum algorithms in the NISQ era due to noise. In this work, we present a compiler that integrates logical-to-physical decomposition with depth-aware rescheduling to reduce the execution cost of distributed quantum circuits. The compiler identifies sequences of logical CNOT gates that share a control or target qubit, reschedules them into parallel instruction groups, and applies decompositions that allow multiple gates to be executed simultaneously using distributed shared entanglement resources. An algorithm is proposed that ensures parallelism is created when possible while keeping logical equivalence and that circuit depth is never increased. Benchmark results demonstrate that the compiler consistently reduces circuit depth for circuits containing inherently sequential CNOT structures, while leaving already-parallel circuits unchanged. These results highlight the value of combining scheduling and hardware-aware decomposition, and establish the compiler as a practical tool for improving the fidelity of distributed quantum computations.

quant-pharXiv:2603.29536•International Conference on Computer Communications and Networks (ICCCN)•Apr 1, 2026•0 citations

Link-middle-cut lower bounds for Clifford circuit synthesis

Søren Fuglede Jørgensen

Minimizing the number of CNOT gates required to synthesize a Clifford operator is a central problem in quantum circuit optimization. We extend the link--middle--cut (LMC) framework for linear reversible circuits to Clifford operators represented by binary symplectic tableaux. By introducing block-support connectivity graphs and determinantal invariants, we obtain efficiently computable lower bounds on ancilla-free CNOT complexity. We prove that these bounds are tight for qubit permutations: a permutation of $n$ qubits with $k$ cycles requires exactly $3(n-k)$ CNOT gates, even when arbitrary one-qubit Clifford gates are available. We also derive efficiently computable bounds for synthesis up to a permutation of the output qubits, corresponding to free qubit relabeling. Finally, we further demonstrate the utility of the bound by using it as an admissible heuristic for $A^*$-based Clifford synthesis and show that, on benchmark instances, the resulting search can prove optimality beyond what was possible with earlier SAT-based methods, and that it may be used in combination with earlier $A^*$ heuristics to improve the CNOT counts obtained through heuristic search.

quant-pharXiv:2609.16208•Sep 16, 2026•0 citations

Heuristics for Quantum Compiling with a Continuous Gate Set

Marc Davis, Ethan Smith, Ana Tudor +3 more

We present an algorithm for compiling arbitrary unitaries into a sequence of gates native to a quantum processor. As accurate CNOT gates are hard for the foreseeable Noisy- Intermediate-Scale Quantum devices era, our A* inspired algorithm attempts to minimize their count, while accounting for connectivity. We discuss the search strategy together with metrics to expand the solution frontier. For a workload of circuits with complexity appropriate for the NISQ era, we produce solutions well within the best upper bounds published in literature and match or exceed hand tuned implementations, as well as other existing synthesis alternatives. In particular, when comparing against state-of-the-art available synthesis packages we show 2.4x average (up to 5.3x) reduction in CNOT count. We also show how to re-target the algorithm for a different chip topology and native gate set, while obtaining similar quality results. We believe that empirical tools like ours can facilitate algorithmic exploration, gate set discovery for quantum processor designers, as well as providing useful optimization blocks within the quantum compilation tool-chain.

arXiv:1912.02727•Dec 5, 2019•15 citations
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>1d>1d>1, the discovered pattern yields a topology-legal implementation using at most 6d−46d-46d−4 CNOT gates, compared to the 6d−36d-36d−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.
We present an algorithm for compiling arbitrary unitaries into a sequence of gates native to a quantum processor. As CNOT gates are error-prone for the foreseeable Noisy-Intermediate-Scale Quantum devices era, our A* inspired algorithm minimizes their count while accounting for connectivity. We discuss the formulation of synthesis as a search problem as well as an algorithm to find solutions. For a workload of circuits with complexity appropriate for the NISQ era, we produce solutions well within the best upper bounds published in literature and match or exceed hand tuned implementations, as well as other existing synthesis alternatives. In particular, when comparing against state-of-the-art available synthesis packages we show 2.4× average (up to 5.3×) reduction in CNOT count. We also show how to re-target the algorithm for a different chip topology and native gate set while obtaining similar quality results. We believe that tools like ours can facilitate algorithmic exploration and guide gate set discovery for quantum processor designers, as well as being useful for optimization in the quantum compilation tool-chain.
Quantum circuit optimization is a central task in quantum computing, as current NISQ 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 two-qubit gate in the universal Clifford+T set. Minimizing CNOT gates is therefore particularly important, as these gates exhibit higher error rates and they typically introduce additional routing overhead due to hardware constraints. The problem of CNOT gate 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 qubit pairs. We introduce AlphaCNOT, an RL framework based on Monte Carlo Tree Search that effectively addresses the CNOT minimization problem by modeling it as a planning problem. In contrast to other RL-based solutions, 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 24.62% in CNOT count compared with the PMH baseline on linear reversible synthesis, and a consistent gate count reduction on different topologies with up to 8 qubits, also 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, thus fostering the transition toward the "quantum utility" era.
In the Noisy Intermediate-Scale Quantum (NISQ) era, efficient quantum circuit synthesis is essential for optimizing limited qubit resources and mitigating noise effects. Quantum Linear Reversible Circuits (QLRCs) are a fundamental class of circuits with applications in quantum compilation or quantum error correction. They are composed exclusively of CX and SWAP gates, which are among the noisiest operations on current quantum hardware. Therefore, their efficient synthesis is pivotal for executing QLRCs on NISQ processors, which have restricted connectivity between qubits. In this direction, we introduce a Reinforcement Learning (RL)-based synthesis approach using Proximal Policy Optimization (PPO) to synthesize QLRCs on generic topologies of up to five qubits. This work extends previous work that did not handle different topologies of quantum processors. Our method dynamically adapts to hardware constraints, learning optimal or near-optimal gate decompositions. We compare our approach against Qiskit’s synthesis methods for QLRCs, demonstrating that our RL-based synthesizer consistently achieves lower CX gate depth. These results highlight the potential of RL-driven quantum circuit synthesis as a powerful alternative to traditional heuristic-based techniques, paving the way for more efficient AI-based quantum compilation strategies in the NISQ era.
Quantum computing is expected to become a foundational technology for solving problems that exceed the capabilities of classical systems. As quantum algorithms and hardware technologies continue to advance, the need for scalable architectures becomes increasingly clear. Distributed quantum computing offers a promising path forward by interconnecting multiple smaller processors into a larger, more powerful system. However, distributed quantum computing introduces significant circuit depth overhead, as logical operations are typically decomposed into sequential physical procedures that require entanglement generation. These sequential operations limit the reliability of quantum algorithms in the NISQ era due to noise. In this work, we present a compiler that integrates logical-to-physical decomposition with depth-aware rescheduling to reduce the execution cost of distributed quantum circuits. The compiler identifies sequences of logical CNOT gates that share a control or target qubit, reschedules them into parallel instruction groups, and applies decompositions that allow multiple gates to be executed simultaneously using distributed shared entanglement resources. An algorithm is proposed that ensures parallelism is created when possible while keeping logical equivalence and that circuit depth is never increased. Benchmark results demonstrate that the compiler consistently reduces circuit depth for circuits containing inherently sequential CNOT structures, while leaving already-parallel circuits unchanged. These results highlight the value of combining scheduling and hardware-aware decomposition, and establish the compiler as a practical tool for improving the fidelity of distributed quantum computations.
Minimizing the number of CNOT gates required to synthesize a Clifford operator is a central problem in quantum circuit optimization. We extend the link--middle--cut (LMC) framework for linear reversible circuits to Clifford operators represented by binary symplectic tableaux. By introducing block-support connectivity graphs and determinantal invariants, we obtain efficiently computable lower bounds on ancilla-free CNOT complexity. We prove that these bounds are tight for qubit permutations: a permutation of nnn qubits with kkk cycles requires exactly 3(n−k)3(n-k)3(n−k) CNOT gates, even when arbitrary one-qubit Clifford gates are available. We also derive efficiently computable bounds for synthesis up to a permutation of the output qubits, corresponding to free qubit relabeling. Finally, we further demonstrate the utility of the bound by using it as an admissible heuristic for A∗A^*A∗-based Clifford synthesis and show that, on benchmark instances, the resulting search can prove optimality beyond what was possible with earlier SAT-based methods, and that it may be used in combination with earlier A∗A^*A∗ heuristics to improve the CNOT counts obtained through heuristic search.
We present an algorithm for compiling arbitrary unitaries into a sequence of gates native to a quantum processor. As accurate CNOT gates are hard for the foreseeable Noisy- Intermediate-Scale Quantum devices era, our A* inspired algorithm attempts to minimize their count, while accounting for connectivity. We discuss the search strategy together with metrics to expand the solution frontier. For a workload of circuits with complexity appropriate for the NISQ era, we produce solutions well within the best upper bounds published in literature and match or exceed hand tuned implementations, as well as other existing synthesis alternatives. In particular, when comparing against state-of-the-art available synthesis packages we show 2.4x average (up to 5.3x) reduction in CNOT count. We also show how to re-target the algorithm for a different chip topology and native gate set, while obtaining similar quality results. We believe that empirical tools like ours can facilitate algorithmic exploration, gate set discovery for quantum processor designers, as well as providing useful optimization blocks within the quantum compilation tool-chain.