CNOT Minimal Circuit Synthesis: A Reinforcement Learning Approach

• URL: http://arxiv.org/abs/2510.23304v1
• Date: Mon, 27 Oct 2025 13:13:39 GMT
• Title: CNOT Minimal Circuit Synthesis: A Reinforcement Learning Approach
• Authors: Riccardo Romanello, Daniele Lizzio Bosco, Jacopo Cossio, Dusan Sutulovic, Giuseppe Serra, Carla Piazza, Paolo Burelli,
• Abstract summary: We introduce a novel reinforcement learning approach to CNOT minimisation.<n>We trained an agent with m = 8, and evaluated it on matrices of size n that range from 3 to 15.<n>Results we obtained show that our method overperforms the state-of-the-art algorithm as the value of n increases.
• Score: 2.8635186297113493
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: CNOT gates are fundamental to quantum computing, as they facilitate entanglement, a crucial resource for quantum algorithms. Certain classes of quantum circuits are constructed exclusively from CNOT gates. Given their widespread use, it is imperative to minimise the number of CNOT gates employed. This problem, known as CNOT minimisation, remains an open challenge, with its computational complexity yet to be fully characterised. In this work, we introduce a novel reinforcement learning approach to address this task. Instead of training multiple reinforcement learning agents for different circuit sizes, we use a single agent up to a fixed size $m$. Matrices of sizes different from m are preprocessed using either embedding or Gaussian striping. To assess the efficacy of our approach, we trained an agent with m = 8, and evaluated it on matrices of size n that range from 3 to 15. The results we obtained show that our method overperforms the state-of-the-art algorithm as the value of n increases.

Related papers

• Decomposition of multi-qutrit gates generated by Weyl-Heisenberg strings [0.0]
  We introduce an algorithm that decomposes the exponential of an arbitrary tensor product of Weyl-Heisenberg operators into single- and two-qutrit gates.<n>We extend this approach to unitaries generated by Gell-Mann string (i.e., a tensor product of Gell-Mann matrices)<n>In particular, we generalize the Steiner-Gauss method, originally developed to reduce CNOT counts in qubit circuit, to optimize gate routing in qutrit-based systems.
  arXiv  Detail & Related papers  (2025-07-13T20:33:48Z)
• Efficient Algorithms for Quantum Hashing [0.0]
  We present a circuit that implements the phase form of quantum hashing using $2n-1$ CNOT gates.<n>We also propose an algorithm that provides a trade-off between the number of CNOT gates and the precision of rotation angles.
  arXiv  Detail & Related papers  (2025-07-09T16:32:15Z)
• Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
  CNOT circuits are a common building block of general quantum circuits. This article presents state-of-the-art algorithms for optimizing the number of CNOT gates. A simulated evaluation shows that the suggested is almost always beneficial and reduces the number of CNOT gates by up to 10%.
  arXiv  Detail & Related papers  (2024-08-07T19:51:22Z)
• Quantum Circuit Optimization with AlphaTensor [47.9303833600197]
  We develop AlphaTensor-Quantum, a method to minimize the number of T gates that are needed to implement a given circuit. Unlike existing methods for T-count optimization, AlphaTensor-Quantum can incorporate domain-specific knowledge about quantum computation and leverage gadgets. Remarkably, it discovers an efficient algorithm akin to Karatsuba's method for multiplication in finite fields.
  arXiv  Detail & Related papers  (2024-02-22T09:20:54Z)
• Quantum State Preparation Using an Exact CNOT Synthesis Formulation [8.078625517374967]
  Minimizing the use of CNOT gates in quantum state preparation is a crucial step in quantum compilation. We propose an effective state preparation algorithm using an exact CNOT synthesis formulation.
  arXiv  Detail & Related papers  (2024-01-02T03:37:00Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem. The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment. We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
  arXiv  Detail & Related papers  (2022-04-18T21:45:13Z)
• CNOT-count optimized quantum circuit of the Shor's algorithm [8.88308897530269]
  We present improved quantum circuit for modular exponentiation of a constant, which is the most expensive operation in Shor's algorithm for integer factorization. According to the number of CNOT gates, we analyze the running time and feasibility of Shor's algorithm on a ion trap quantum computer.
  arXiv  Detail & Related papers  (2021-12-21T16:56:22Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task. Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate. The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
  arXiv  Detail & Related papers  (2021-06-06T13:15:25Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  Variational quantum algorithms are believed to be promising for solving computationally hard problems. In this paper, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
  arXiv  Detail & Related papers  (2020-05-11T17:20:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.