CNOT Minimal Circuit Synthesis - A Reinforcement Learning Approach

CNOT gates are fundamental to quantum computting, as they facilitate entanglement, a crucial resource for quantum algorithms. Certain classes of quantum circuits, such as stabilizer circuits, rely heavily on CNOT gates and exhibit a structured normal form consisting of 11 independent computational blocks, many of which are composed entirely of CNOT operations. More generally, circuits constructed exclusively from CNOT gates are referred to as linear reversible circuits. Given their widespread use, it is imperative to minimise the number of CNOT gates employed. This problem, known as CNOT minimization, remains an open challenge, with its computational complexity yet to be fully characterized. Linear reversible circuits can be naturally represented as invertible binary matrices, establishing a direct correspondence between circuit optimization and matrix transformations. In this work, we introduce a novel reinforcement learning-based approach to CNOT minimization. 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, to increase their size, or Gaussian striping, to reduce it. To assess the efficacy of our approach we trained an agent with m = 8. We evaluated our technique on matrices of size n that ranges from 3 to 15. The results we obtained show that our method overperforms the state of the art Patel-Markov-Hayes algorithm as the value of n increases.