The reversible circuit synthesis problem can be reduced to permutation group.This allows Schreier-Sims Algorithm for the strong generating set-finding problem to be used to synthesize reversible circuits using the NCT library.Applying novel optimization rules to minimize the number of gates gives better quantum cost than that shown in the literature.Applications on how to integrate any three irreversible Boolean functions on a single 3-bit reversible circuit will be shown.
The reversible circuit synthesis problem can be reduced to permutation group.This allows Schreier-Sims Algorithm for the strong generating set-finding problem to be used to synthesize reversible circuits using the NCT library.Applying novel optimization rules to minimize the number of gates gives better quantum cost than that shown in the literature.Applications on how to integrate any three irreversible Boolean functions on a single 3-bit reversible circuit will be shown.
The reversible circuit synthesis problem can be reduced to permutation group. This allows Schreier-Sims Algorithm for the strong generating set-finding problem to be used to find tight bounds on the synthesis of 3-bit reversible circuits using the NFT library. The tight bounds include the maximum and minimum length of 3-bit reversible circuits, the maximum and minimum cost of 3-bit reversible circuits. The analysis shows better results than that found in the literature for the lower bound of the cost. The analysis also shows that there are 1960 universal reversible sub-libraries from the main NFT library.
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.
The synthesis of reversible logic circuits is a fundamental step in the design of fault-tolerant quantum arithmetic. Existing literature frequently minimizes Quantum Cost (QC) by utilizing the NCV library, which permits controlled-V and Vdagger gates. However, in the context of Fault-Tolerant Quantum Computing (FTQC), the strict NCT library (NOT, CNOT, Toffoli) is often preferred due to the high cost of distilling non-Clifford states required for arbitrary V-gates. Moreover, in the classical design of reversible circuits, only the NCT library can be used as V-gates are not available. In this paper, a new design method for reversible circuits is proposed, based on Mixed-Integer Non-Linear Programming (MINLP) within the Strict NCT Library. By formulating the problem as an MINLP model in GAMS, we successfully automated the optimization of five prominent reversible primitives (TSG, MKG, MIG, SAYEM, and URG) within the strict NCT library. Comparative analysis with the NCV costs found in the literature shows that the costs within the NCT library are comparable or better.
The synthesis of reversible logic circuits is a fundamental step in the design of fault-tolerant quantum arithmetic. Existing literature frequently minimizes Quantum Cost (QC) by utilizing the NCV library, which permits controlled-V and Vdagger gates. However, in the context of Fault-Tolerant Quantum Computing (FTQC), the strict NCT library (NOT, CNOT, Toffoli) is often preferred due to the high cost of distilling non-Clifford states required for arbitrary V-gates. Moreover, in the classical design of reversible circuits, only the NCT library can be used as V-gates are not available. In this paper, a new design method for reversible circuits is proposed, based on Mixed-Integer Non-Linear Programming (MINLP) within the Strict NCT Library. By formulating the problem as an MINLP model in GAMS, we successfully automated the optimization of five prominent reversible primitives (TSG, MKG, MIG, SAYEM, and URG) within the strict NCT library. Comparative analysis with the NCV costs found in the literature shows that the costs within the NCT library are comparable or better.
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.
Reversible logic has applications in various research areas, including signal processing, cryptography and quantum computation. In this article, direct NCT-based synthesis of a given k -cycle in a cycle-based synthesis scenario is examined. To this end, a set of seven building blocks is proposed that reveals the potential of direct synthesis of a given permutation to reduce both quantum cost and average runtime. To synthesize a given large cycle, we propose a decomposition algorithm to extract the suggested building blocks from the input specification. Then, a synthesis method is introduced that uses the building blocks and the decomposition algorithm. Finally, a hybrid synthesis framework is suggested that uses the proposed cycle-based synthesis method in conjunction with one of the recent NCT-based synthesis approaches which is based on Reed-Muller (RM) spectra. The time complexity and the effectiveness of the proposed synthesis approach are analyzed in detail. Our analyses show that the proposed hybrid framework leads to a better quantum cost in the worst-case scenario compared to the previously presented methods. The proposed framework always converges and typically synthesizes a given specification very fast compared to the available synthesis algorithms. Besides, the quantum costs of benchmark functions are improved about 20% on average (55% in the best case).