We report optimal and asymptotically optimal reversible circuits composed of NOT, CNOT, and Toffoli (NCT) gates, keeping the count by the subsets of the gate types used. This study fine tunes the circuit complexity figures for the realization of reversible functions via reversible NCT circuits. An important consequence is a result on the limitation of the use of the T-count quantum circuit metric popular in applications.
We report optimal and asymptotically optimal reversible circuits composed of NOT, CNOT, and Toffoli (NCT) gates, keeping the count by the subsets of the gate types used. This study fine tunes the circuit complexity figures for the realization of reversible functions via reversible NCT circuits. An important consequence is a result on the limitation of the use of the T-count quantum circuit metric popular in applications.
We consider the problem of synthesizing optimized circuits for reversible functions using NOT, CNOT and Toffoli gates (NCT), which has important applications in circuit design and quantum cryptography. By defining the state space and state transitions from NCT gates, we transform the synthesis problem into a reachability problem of finding the shortest path connecting the identity function and the targeted function that is to be synthesized. Using Bounded Model Checking (BMC), we propose an algorithm for synthesizing the optimized circuit for reversible functions. For the synthesis of linear reversible functions, we design another method by directly parametrizing the linear invertible matrix. Our methods can produce optimal synthesis of reversible circuits when the number of bits is small, and also can be used as a subroutine of heuristic methods for large bits. Experimental results show the effectiveness of our methods.
The synthesis and optimization of quantum circuits are essential for the construction of quantum computers. This paper proposes two methods to reduce the quantum cost of 3-bit reversible circuits. The first method utilizes basic building blocks of gate pairs using different Toffoli decompositions. These gate pairs are used to reconstruct the quantum circuits where further optimization rules will be applied to synthesize the optimized circuit. The second method suggests using a new universal library, which provides better quantum cost when compared with previous work in both cost015 and cost115 metrics; this proposed new universal library “Negative NCT” uses gates that operate on the target qubit only when the control qubit’s state is zero. A combination of the proposed basic building blocks of pairs of gates and the proposed Negative NCT library is used in this work for synthesis and optimization, where the Negative NCT library showed better quantum cost after optimization compared with the NCT library despite having the same circuit size. The reversible circuits over three bits form a permutation group of size 40,320 (23!), which is a subset of the symmetric group, where the NCT library is considered as the generators of the permutation group.
This paper presents basic methods of reversible circuit description. To design reversible circuit a set of gates has to be chosen. Most popular libraries are composed of three types of gates so called CNT gates (Control, NOT and Toffoli). The gate indexing method presented in this paper is based on the CNT gates set. It introduces a uniform indexing of the gates used during synthesis process of reversible circuits. The paper is organized as follows. Section 1 recalls basic concepts of reversible logic. In Section 2 and 3 a graphical representation of the reversible gates and circuits is described. Section 4 describes proposed uniform NCT gates indexing. The presented gate indexing method provides gate numbering scheme independent of lines number of the designed circuit. The solution for a circuit consisting of smaller number of lines is a subset of solution for a larger circuit.
Reversible circuit synthesis is critical for quantum computing, but existing methods suffer from high gate counts that increase error susceptibility. This paper introduces a permutation group-driven greedy algorithm that reduces primitive quantum gates systematically in reversible circuits built from NOT, Feyn-man, and Toffoli (NCT) gates. By exploiting the algebraic structure of reversible functions, the proposed method applies iterative gate cancellation and substitution rules to minimize circuit depth. Experiments on NCT-based reversible circuits using IBM's Qiskit demonstrate substantial reductions in primitive quantum gates.
The synthesis of efficient reversible logic circuits is critical for fault-tolerant quantum computing. While standard libraries often treat the Toffoli gate as an atomic unit, its realization in the NCV library requires decomposition into 5 elementary gates. In this work, we propose a novel, systematic four-phase optimization methodology. First, we generate an optimal circuit in the strict NCT library (NOT, CNOT, Toffoli) using automated synthesis. Second, we replace each Toffoli gate with a specific NCV decomposition, permuting the control lines such that the final internal CNOT gate matches the subsequent linear gate in the circuit, allowing us to apply a cancellation rule (X ·X = I). Finally, post-synthesis local searches are applied using Mixed- Integer Non-Linear Programming (MINLP) techniques to further reduce the total gate count. Applying this method to the MIG, TSG, and MKG gates, we achieve Quantum Costs of 7, 14, and 12 respectively, matching or beating the best-known literature benchmarks.
The synthesis of efficient reversible logic circuits is critical for fault-tolerant quantum computing (FTQC). The primary motivation of this work is to overcome the inherent disadvantages of existing synthesis techniques: approximate heuristic methods often miss optimal solutions, while pure exact computational methods suffer from combinatorial explosion on deep circuits. While the strict NCT library (NOT, CNOT, Toffoli) is often preferred due to the high cost of distilling non-Clifford states required for arbitrary gates, standard physical implementations frequently utilize the broader NCV library (NOT, CNOT, V, V-dagger), requiring the decomposition of Toffoli gates into five elementary operations. To bridge this gap, this paper presents a unified, highly scalable methodology for the optimal design of reversible circuits across both libraries. First, a Mixed-Integer Non-Linear Programming (MINLP) formulation, linearized for the high-performance IBM ILOG CPLEX solver, is introduced to automate the exact generation of globally optimal strict NCT topologies. Second, a systematic four-phase optimization framework is proposed to reduce NCV costs. By replacing Toffoli gates with specific NCV decompositions, permuting control lines to match subsequent linear gates, and applying exact local searches via an extended MINLP solver on bounded sliding windows, significant gate cancellations are achieved. Applying this methodology to prominent primitives (MIG, SAYEM, URG, TSG, and MKG), we match global NCT optimality constraints and achieve highly optimized NCV Quantum Costs of 7, 14, and 12 for the MIG, TSG, and MKG gates, respectively, establishing best-known upper bounds that significantly outperform heuristic literature benchmarks.